某面试官谈到List和Map的时候要出一问题，有大数据量的User对象（name,sex,age）属性。

现要求直允许使用List存放，如何实现按name快速检索到对应的User对象？

直接存储，然后算法查找啥的就免了…… 不解释，你懂的！

求解！

链表 linklist

在多核的前提下，多线程，分段找，呵呵

因为只能用LIST的前提，遍历一次就好了。

我理解题目含义是要你用List实现Map(name,User)。因为对大数据量的检索最先想到的肯定是hashmap速度最快了。

一般来说是hashmap，它是由name计算hashcode，然后根据一个算法算出[下标]，然后存储到table[下标]的对应位置，若不同name算出相同的hashcode，那么根据name+hashcode一起定位它的User，用List来实现的话，

1是arraylist有一个set(int,E)方法的，你可以根据name算出hashcode，再把hashcode按一定算法处理后当做list的下标来set，当然长度问题你自己得考虑下如何设计了，不能抛异常.

2是map中有Entry的处理，也就是对于相同的hashcode，会做成一个链表，这个就可以用linkedlist来代替了，相同hashcode的name，可以根据name+hashcode在链表上找到唯一的符合E(包含hash,name,User等值)，返回你的User就可以了。

这样你存储所有数据量后，可以直接设计一个get(name)方法，根据name和name.hashcode()计算后直接锁定到List的某一数组下标值，得到value，返回你的User。

ps：当然这个只是最common的想法，也就是面试时应急的最直观的想法，可能有说不周全的地方，有些地方会有更优化的设计，抛砖引玉而已，这个就楼主自己考虑下吧。

感谢你的回复，我主要当时没有想到hash值转为下标的方法，心里没底，虚了。
还有对你的第二点处理重复hash的方法 还是有些模糊的……

我也是首先想到hash。但是hash有两个问题。
第一，数组要足够长，举个例子来说。是100个的数据，你的List也要整个integer的长度。
第二，Hash值重复怎么处理？

我想到个方法。就是用树的结构，根的下标为0，左节点为1，右节点为2。然后后面的节点依次类推。
具体代码要看书才能给出。

觉得没什么好书的吧。算法，如果j2ee的话，并不是那么重要。

nameList:
----------------
0 : "name1"
1 : "name2"
2 : "name3"
...

userList:
---------------
0 : User1
1 : User2
2 : User3
...

改变nameList后要保持有序，改变nameList时要同时改变userList，因为要保持下标对应，最后折半查找name，找到name就可以用name的下标找到User对象。

可以用MAP吗，LIST里加你那些字段，然后用LIST实例做KEY，value用相应的user对象

有时间去研究一下hashmap底层的实现就清楚了，想进阿里，这一关是必须的，互联网基本都会接触到这个，而大数据量处理都是参考hashmap或者currenthashmap来设计的，可以参考林昊的那本书的例子参考下，hashmap是几个集合中大数据量处理效率最好的，当然在大并发量时候currenthashmap更优。重复hash指的是两个不同的name.hashcode()得到的值是相同的，如果没有Entry的辅助就会替换出错了，所以在Entry中是根据name值+hashcode值都相同的证明是同一个key，可以替换，而如果name值+hashcode值是不同的那么证明他们不是同一个name，那么就不是同一个key，那么在相同的hashcode值时候就设计了一个Entry类，其中有一个属性是类型为Entry的next，其实也就相当于在相同的hashcode值上有一个Entry链表，可以通过next进行迭代（其实是循环链表），所以就会在链表上寻找相同的name+hashcode值相同就是同一个key这样。

希望解释能让你清楚。另外至于长度问题，可以参考List和Map实现中的数组扩容问题，这个不难实现，你只要让他的下标计算值命中到长度允许范围内，长度就不是问题了。

￥3000 java企业网站改版和优化
http://un.zhubajie.com/r/?u=5161194&l=http://task.zhubajie.com/894990/ 
有人可以做么