锁定老帖子 主题:老话题,面试被鄙视,求解!
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-07-15
最后修改:2011-07-15
现要求直允许使用List存放,如何实现按name快速检索到对应的User对象? 直接存储,然后算法查找啥的就免了…… 不解释,你懂的! 求解! 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2011-07-15
链表 linklist
|
|
返回顶楼 | |
发表时间:2011-07-16
在多核的前提下,多线程,分段找,呵呵
因为只能用LIST的前提,遍历一次就好了。 |
|
返回顶楼 | |
发表时间:2011-07-16
最后修改:2011-07-16
hamber 写道 某面试官谈到List和Map的时候要出一问题,有大数据量的User对象(name,sex,age)属性。
现要求直允许使用List存放,如何实现按name快速检索到对应的User对象? 直接存储,然后算法查找啥的就免了…… 不解释,你懂的! 求解! 我理解题目含义是要你用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的想法,也就是面试时应急的最直观的想法,可能有说不周全的地方,有些地方会有更优化的设计,抛砖引玉而已,这个就楼主自己考虑下吧。 |
|
返回顶楼 | |
发表时间:2011-07-16
最后修改:2011-07-16
xiao景天 写道 hamber 写道 某面试官谈到List和Map的时候要出一问题,有大数据量的User对象(name,sex,age)属性。
现要求直允许使用List存放,如何实现按name快速检索到对应的User对象? 直接存储,然后算法查找啥的就免了…… 不解释,你懂的! 求解! 我理解题目含义是要你用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的方法 还是有些模糊的…… |
|
返回顶楼 | |
发表时间:2011-07-16
最后修改:2011-07-16
我也是首先想到hash。但是hash有两个问题。
第一,数组要足够长,举个例子来说。是100个的数据,你的List也要整个integer的长度。 第二,Hash值重复怎么处理? 我想到个方法。就是用树的结构,根的下标为0,左节点为1,右节点为2。然后后面的节点依次类推。 具体代码要看书才能给出。 觉得没什么好书的吧。算法,如果j2ee的话,并不是那么重要。 |
|
返回顶楼 | |
发表时间:2011-07-16
最后修改:2011-07-16
nameList:
---------------- 0 : "name1" 1 : "name2" 2 : "name3" ... userList: --------------- 0 : User1 1 : User2 2 : User3 ... 改变nameList后要保持有序,改变nameList时要同时改变userList,因为要保持下标对应,最后折半查找name,找到name就可以用name的下标找到User对象。 |
|
返回顶楼 | |
发表时间:2011-07-16
可以用MAP吗,LIST里加你那些字段,然后用LIST实例做KEY,value用相应的user对象
|
|
返回顶楼 | |
发表时间:2011-07-17
hamber 写道 感谢你的回复,我主要当时没有想到hash值转为下标的方法,心里没底,虚了。 还有对你的第二点处理重复hash的方法 还是有些模糊的…… 有时间去研究一下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实现中的数组扩容问题,这个不难实现,你只要让他的下标计算值命中到长度允许范围内,长度就不是问题了。 |
|
返回顶楼 | |
发表时间:2011-07-17
¥3000 java企业网站改版和优化
http://un.zhubajie.com/r/?u=5161194&l=http://task.zhubajie.com/894990/ 有人可以做么 |
|
返回顶楼 | |