|
锁定老帖子 主题：老话题，面试被鄙视，求解！
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-07-17
最后修改：2011-07-17
主类：
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，重复度非常小。 |
| 返回顶楼 | |
|
发表时间：2011-07-17
如何被鄙视！？
|
| 返回顶楼 | |
|
发表时间：2011-07-17
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，重复度非常小。
正解+1，看来得多看看JDK里面HashMap的源代码了！ |
| 返回顶楼 | |
|
发表时间：2011-07-17
存list的list
偏移值是hash值对list长度取余 再加个系数 自动扩充 |
| 返回顶楼 | |
|
发表时间：2011-07-18
lydawen 写道
代码上没太大难度，这里没考虑扩容的情况，hash与index的关系可以参数HashMap，重复度非常小。 奇怪为什么不直接上Map呢? |
| 返回顶楼 | |
|
发表时间：2011-07-18
直接用Map,有什么好想的，
|
| 返回顶楼 | |
|
发表时间：2011-07-18
hyj1254 写道
lydawen 写道
代码上没太大难度，这里没考虑扩容的情况，hash与index的关系可以参数HashMap，重复度非常小。 奇怪为什么不直接上Map呢? 存在同名的用户怎么考虑？是上要求为使用List实现。 |
| 返回顶楼 | |
|
发表时间：2011-07-18
lydawen 写道
hyj1254 写道
lydawen 写道
代码上没太大难度，这里没考虑扩容的情况，hash与index的关系可以参数HashMap，重复度非常小。 奇怪为什么不直接上Map呢? 存在同名的用户怎么考虑？是上要求为使用List实现。
做业务系统的 你整这么个面试题 不是无聊么，明显有HashMap直接可用。。 JEE 业务才是王道吧。。。 |
| 返回顶楼 | |
|
发表时间：2011-07-18
dolwenjian 写道
最蛋疼这种，如果是做互联网还可以理解。。 做业务系统的 你整这么个面试题 不是无聊么，明显有HashMap直接可用。。 JEE 业务才是王道吧。。。
其实主要想考察对JDK底层实现的熟悉程度吧…… |
| 返回顶楼 | |
|
发表时间：2011-07-18
一个list存储user对象,一个map保存该user对象在list中的位置,可否?多耗费点空间而已.
|
| 返回顶楼 | |
