论坛首页 招聘求职论坛

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

浏览 12204 次
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-07-18  
哦,姓名有重复的话,可以用lydawen的办法,在list中存个LinkedList比较合适
0 请登录后投票
   发表时间:2011-07-18  
计算hashcode,对于每一个hash值用一个list来存储,

查找时,先计算hashcode,找到对应的list,对list进行遍历

貌似jdk就是这么多的
0 请登录后投票
   发表时间:2011-07-18  
ListOrderedMap
0 请登录后投票
   发表时间:2011-07-18  
这个就是个二维数组,可以解决~~定义User的hashcode方法
0 请登录后投票
   发表时间: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。。。求解释

0 请登录后投票
   发表时间:2011-07-18  

yanleihebei

 写道
为什么要用链表,可以在套个list。。。求解释

 个人认为本质上没太大区别。

考虑到一个节点可能存在多个同名用户,能性能可能会有点影响。ArrayList可能存在扩容导致的数组复制,而LinkedList因为链表数据结构且当前需求则不存在扩容导致数组复制。

0 请登录后投票
   发表时间:2011-07-19  
受某楼上启发,关于构建list形式的map:
map有两种数据结构形式,即开放地址法和封闭地址法,区别在于对重复值的处理:
HashMap是封闭地址法,此种方法优势大,使用多;
list的map属开放地址法,重复时,可以将新值按一定规则放到其他位置上去,貌似没啥用处;
0 请登录后投票
   发表时间:2011-08-03  
HashMap 可以去除重复,先计算出要存入对象的HashCode 然后和HashMap中的对象进行比较,如果相同,调用equals 比较, 如果不同直接存入```
0 请登录后投票
论坛首页 招聘求职版

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