锁定老帖子 主题:老话题,面试被鄙视,求解!
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-07-18
哦,姓名有重复的话,可以用lydawen的办法,在list中存个LinkedList比较合适
|
|
返回顶楼 | |
发表时间:2011-07-18
计算hashcode,对于每一个hash值用一个list来存储,
查找时,先计算hashcode,找到对应的list,对list进行遍历 貌似jdk就是这么多的 |
|
返回顶楼 | |
发表时间:2011-07-18
ListOrderedMap
|
|
返回顶楼 | |
发表时间:2011-07-18
这个就是个二维数组,可以解决~~定义User的hashcode方法
|
|
返回顶楼 | |
发表时间:2011-07-18
lydawen 写道
主类:
package com.kanmenzhu.test; import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; import java.util.List; /** * 测试主类 * * @param <V> */ public class FastList<V extends BaseUser> { //能保存的个数 private int LIST_SIZE=16; private List<LinkedList<V>> storeList; //当前保存个数 private int CUR_SIZE; //初始化list public FastList(int initSize){ this.LIST_SIZE=initSize; storeList=new ArrayList<LinkedList<V>>(LIST_SIZE); for(int i=0;i<LIST_SIZE;i++){ storeList.add(null); } } /** * 添加用户到list * @param bu * @return */ @SuppressWarnings("unchecked") public V addUser(V arg){ CUR_SIZE++; if(CUR_SIZE>LIST_SIZE){ throw new RuntimeException("容量超标,初始化容量设置太小!"); } int hashCode=(arg.getUserName()).hashCode(); int i=hashCode&(LIST_SIZE-1); Object o=storeList.get(i); BaseUser v; if(o!=null) { o=(LinkedList<V>)o; LinkedList<V> linkList=(LinkedList<V>)o; Iterator<V> iter=linkList.iterator(); for(v=iter.next();v!=null;v=iter.next()){ if(v.getUserName().equals(arg.getUserName())&&v.equals(arg)){ return arg; } if(!iter.hasNext()) break; } linkList.addLast(arg);//如果遍历下来,发现不存在姓名相同且用户也不相同的,则表示为同名或同索引用户,添加到链表未 return null; }else{//当前位置无数据 LinkedList<V> tempLinked=new LinkedList<V>(); tempLinked.add(arg); storeList.set(i, tempLinked); return null; } } /** * 根据姓名获取用户 * @param arg * @return */ @SuppressWarnings("unchecked") public List<V> getUser(String arg){ int hashCode=arg.hashCode(); int i=hashCode&(LIST_SIZE-1); List<V> retuList=new ArrayList<V>(); LinkedList<V> linkList=storeList.get(i); Iterator<V> iter=linkList.iterator(); BaseUser v; //遍历对应索引位置是否存在多个用户(用户姓名经过hash&list.size()之后可能存在同一位置多个不同名数据情况) for(v=iter.next();v!=null||iter.hasNext();v=iter.next()){ if(v.getUserName().equals(arg)){ retuList.add((V)v); } if(!iter.hasNext()) break; } if(retuList.size()==0) return null; return retuList; } public static void main(String[] args) { FastList<MyUser> fl=new FastList<MyUser>(16); MyUser mu1=new MyUser(); mu1.setAge(1); mu1.setUserName("张三"); MyUser mu2=new MyUser(); mu2.setAge(2); mu2.setUserName("张三"); MyUser mu3=new MyUser(); mu3.setAge(3); mu3.setUserName("李四"); fl.addUser(mu1); fl.addUser(mu2); fl.addUser(mu3); List<MyUser> ml=fl.getUser("张三"); for(MyUser mu:ml){ System.out.println(mu); } } } 辅助用户类:
package com.kanmenzhu.test;
/**
* 用户基类,以保证用户存在用户名方法
*
*/
public abstract class BaseUser {
protected abstract String getUserName();
}
用户类:
package com.kanmenzhu.test; /** * 测试用户类 * */ public class MyUser extends BaseUser { private String userName; private int age; @Override public String getUserName() { return userName; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public void setUserName(String userName) { this.userName = userName; } public String toString(){ return "userName:"+userName+" age:"+age; } } 代码上没太大难度,这里没考虑扩容的情况,hash与index的关系可以参数HashMap,重复度非常小。 为什么要用链表,可以在套个list。。。求解释 |
|
返回顶楼 | |
发表时间:2011-07-18
yanleihebei
个人认为本质上没太大区别。 考虑到一个节点可能存在多个同名用户,能性能可能会有点影响。ArrayList可能存在扩容导致的数组复制,而LinkedList因为链表数据结构且当前需求则不存在扩容导致数组复制。 |
|
返回顶楼 | |
发表时间:2011-07-19
受某楼上启发,关于构建list形式的map:
map有两种数据结构形式,即开放地址法和封闭地址法,区别在于对重复值的处理: HashMap是封闭地址法,此种方法优势大,使用多; list的map属开放地址法,重复时,可以将新值按一定规则放到其他位置上去,貌似没啥用处; |
|
返回顶楼 | |
发表时间:2011-08-03
HashMap 可以去除重复,先计算出要存入对象的HashCode 然后和HashMap中的对象进行比较,如果相同,调用equals 比较, 如果不同直接存入```
|
|
返回顶楼 | |