`
lydawen
  • 浏览: 472149 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

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

    博客分类:
  • java
 
阅读更多

原文: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重名的情况外,实际项目中还有什么典型应用吗?

相关推荐

    中软面试题,中软面试题,中软面试题

    中软面试题解读 中软面试题涵盖了多个IT领域的知识点,包括Java编程、XML解析、JNDI、设计模式、面向对象编程、集合框架、排序算法和数据库查询等。下面将逐一解读这些知识点。 抽象类和接口 抽象类和接口是Java...

    2021最新Java面试题合集.zip

    Java作为一门广泛使用的编程语言,其面试题涵盖了众多领域,包括基础、并发编程、网络、虚拟机、大数据处理以及各种框架。以下是对这些面试题集合的详细解析: 1. **BIO, NIO, AIO, Netty面试题 35道**: - **BIO*...

    黑马面试题总结

    ### 黑马面试题总结 #### 一、进程与线程状态 **知识点:** - **进程与线程的区别:** - **进程**:是系统进行资源分配和调度的基本单位,每个进程都有独立的代码和数据空间(程序上下文)。 - **线程**:是...

    Hibernate常见面试题

    这些知识点涵盖了常见的面试问题,可以帮助准备面试或深入理解Hibernate技术的人士更好地掌握该领域的内容。 ### Hibernate的检索方式 1. **导航对象图检索**:通过已加载的对象来访问与其关联的对象,这种检索...

    .net面试题(共156题)

    【.NET面试题详解】 1. .NET的内置对象: .NET框架提供了六个主要的内置对象,它们对于ASP.NET开发至关重要: - Response:该对象用于服务器向客户端浏览器发送信息,包括HTML、文本、文件等。 - Request:通过此...

    java面试题大全-葵花宝典-出现率比较高的面试题

    在Java面试中,经常会遇到关于Hibernate、对象持久化、ORM映射和检索策略的问题。以下是对这些知识点的详细解释: 1. **Hibernate的检索方式**: - **导航对象图检索**:通过对象之间的关联关系直接获取相关数据。...

    中科软面试题(java)

    中科软面试题(java) 本文总结了中科软面试题中的多个java技术相关知识点,涵盖了面向对象编程、Tomcat配置、Http请求、SQL语句、String和StringBuffer的差异、集合类、异常处理、包、接口、类等多个方面。 1. 面向...

    面试题集默写

    根据提供的文件信息,以下是关于Java面试题集默写的知识点总结: 标题为“面试题集默写”,描述为“这是我默写的java面试知识,小知识在于积累,尽量默写还是好些”,标签为“java知识”。文件中显示的内容是对...

    java后端面试题答案.docx

    Java 后端面试题答案 List 和 Set 是 Java 集合框架中的两个重要接口,都是继承自 Collection 接口。List 特点是元素有放入顺序,元素可重复,而 Set 特点是元素无放入顺序,元素不可重复。Set 的元素虽然无放入...

    hibernate面试题.doc

    - **建立索引**:为经常用于查询的字段创建索引,以加快数据检索速度。 - **减少表关联**:尽量避免复杂的多表连接查询,减少数据跨表的交互。 - **优化SQL**:编写高效的SQL语句,避免全表扫描,确保SQL能快速...

    PHP2021中高级面试题完整版

    PHP面试题大全 本资源提供了 PHP 面试题的完整...这些知识点涵盖了 PHP 面试题的基础知识点,包括简历准备、投递公司顺序建议、Redis 的基础知识点、Redis 的使用场景、Redis 的优势、Redis 相比 Memcached 的优势等。

    .Net面试题,本人在上海面试过的公司90%以上都是这里面出的,还有些是一模一样的。希望能给正在面试的朋友一些帮助。

    .Net 面试题知识点总结 本资源摘要信息旨在总结.NET 面试题中的一些重要知识点,涵盖 Web 服务器控件、Windows 控件、SqlDataSource 组件、GridView 控件、DataList 控件、DetailsView 控件、SiteMapPath 控件、...

    最新各大公司企业真实面试题-润信科技公司面试题.txt

    它内部使用哈希表结构存储键值对,通过哈希函数计算键的哈希码来定位数据的位置,从而实现快速查找。 #### 4. LinkedList 与 ArrayList 的区别 - **知识点**:`LinkedList` 与 `ArrayList` 的性能差异及应用场景。 ...

    Hibernate面试题及答案大集合

    ### Hibernate面试题及答案大集合解析 #### 1. 关系数据模型与对象模型之间的匹配关系 - **选项分析**: - A) 表对应类:正确。在ORM(对象关系映射)中,数据库中的每一张表通常对应着Java中的一个类。 - B) ...

    c# Java SQLserver面试题

    SQL Server面试题通常涵盖以下内容: 1. **SQL基本操作**:SELECT、INSERT、UPDATE、DELETE语句,子查询,联接操作(INNER JOIN、LEFT JOIN、RIGHT JOIN)。 2. **索引**:理解B树、聚集和非聚集索引,优化查询性能...

    阿里巴巴校园招聘面试试题合集总结

    - **HashMap**允许任何类型的对象作为键或值,只要键实现了`equals()`和`hashCode()`方法,确保能够正确地存储和检索数据。 **4.2 常见键值类型** - 常见的键类型包括`String`、`Integer`等不可变类型。 - 值类型...

    Java 后端面试题附答案

    ### Java后端面试题知识点解析 #### 1. ArrayList初始化及扩容机制 - **知识点**: - `ArrayList`的内部实现与扩容机制。 - **解释**: - `ArrayList`是一个动态数组,初始容量可以通过构造函数指定。当构造一个`...

    高级软件工程师面试题

    根据给定的“高级软件工程师面试题”文档的内容,我们可以提炼出以下重要的IT知识点: ### 类与对象 1. **类**:类是定义了一组相同类型的对象的模板,其中包括对象的状态(属性)和行为(方法)。类是面向对象...

    2024年java面试题-java集合相关面试题

    根据给定文件的信息,我们可以总结出以下关于Java集合的相关知识点: ### 一、集合容器概述 #### 1.... 集合(Collection)是指在Java中用来存储、...希望这些知识点能帮助你在面试中更好地应对关于Java集合的问题。

    C#.Net的常见面试试题及答案

    ADO.NET提供了多种数据库相关的对象,用于处理数据库连接、执行命令、检索数据等: - `DataTable`:表示内存中的表格数据。 - `DataRow`:表示`DataTable`中的一行数据。 - `DataColumn`:表示`DataTable`中的一列...

Global site tag (gtag.js) - Google Analytics