一道关于使用List保存数据做快速检索面试题

原文：http://www.iteye.com/topic/1112278

 

 

 写道

有大数据量的User对象（name,sex,age）属性。

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

 

 

主类：

 

 

 

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，重复度非常小。

评论

3 楼 lydawen 2011-08-15  

hyj1254 写道

我曾被问过重写HashMap的问题，由于平常没接触过这方面的工作，所以即使知道HashMap的构造原理也不知道出于什么目的要重写。不知道除了lz所写的可以处理name重名的情况外，实际项目中还有什么典型应用吗?

重名问题考虑了，如果有重名的这个时候将返回一个重名List，HashMap原理也与这个类似，当两个Key最后算出来的索引一致且hashCode,equals都不相等，则添加到一个双向链表末端。我上边的实现是如果算出来的索引相等，则判断两个User是否equals，这里需要重载User的equals，如果equals不相等则添加到LinkedList末端。.

2 楼 lydawen 2011-07-18  

hyj1254 写道

我曾被问过重写HashMap的问题，由于平常没接触过这方面的工作，所以即使知道HashMap的构造原理也不知道出于什么目的要重写。不知道除了lz所写的可以处理name重名的情况外，实际项目中还有什么典型应用吗?

很少有涉及到复杂数据结构，一般面试的时候会有这些。

1 楼 hyj1254 2011-07-18  

我曾被问过重写HashMap的问题，由于平常没接触过这方面的工作，所以即使知道HashMap的构造原理也不知道出于什么目的要重写。不知道除了lz所写的可以处理name重名的情况外，实际项目中还有什么典型应用吗?