论坛首页 招聘求职论坛

老话题,面试被鄙视,求解!

浏览 12203 次
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-07-15   最后修改:2011-07-15
某面试官谈到List和Map的时候要出一问题,有大数据量的User对象(name,sex,age)属性。

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

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

求解!
   发表时间:2011-07-15  
链表 linklist
0 请登录后投票
   发表时间:2011-07-16  
在多核的前提下,多线程,分段找,呵呵

因为只能用LIST的前提,遍历一次就好了。
0 请登录后投票
   发表时间: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的想法,也就是面试时应急的最直观的想法,可能有说不周全的地方,有些地方会有更优化的设计,抛砖引玉而已,这个就楼主自己考虑下吧。
0 请登录后投票
   发表时间: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的方法 还是有些模糊的……
0 请登录后投票
   发表时间:2011-07-16   最后修改:2011-07-16
我也是首先想到hash。但是hash有两个问题。
第一,数组要足够长,举个例子来说。是100个的数据,你的List也要整个integer的长度。
第二,Hash值重复怎么处理?

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

觉得没什么好书的吧。算法,如果j2ee的话,并不是那么重要。
0 请登录后投票
   发表时间: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对象。
0 请登录后投票
   发表时间:2011-07-16  
可以用MAP吗,LIST里加你那些字段,然后用LIST实例做KEY,value用相应的user对象
0 请登录后投票
   发表时间: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实现中的数组扩容问题,这个不难实现,你只要让他的下标计算值命中到长度允许范围内,长度就不是问题了。
0 请登录后投票
   发表时间:2011-07-17  
¥3000 java企业网站改版和优化
http://un.zhubajie.com/r/?u=5161194&l=http://task.zhubajie.com/894990/ 
有人可以做么
0 请登录后投票
论坛首页 招聘求职版

跳转论坛:
Global site tag (gtag.js) - Google Analytics