实现一个哈希表,首先我们要知道哈希表可以干什么,包含什么方法,实现哪些功能。
哈希表又叫散列表,是根据关键码值(Key, value)而直接进行访问的数据结构。oracle文档里面提到,用哈希表进行检索和存储,key首先要完成hashcode方法,以确定这个key属于哪个区间,也就是说具有相同hashcode的被放在同一块区间里,hashcode往往是取模得出的结果。
确定了位置,我们还要解决冲突问题,如果表中已经存在当前要存的key,我们应该先删除以前的那个key,先后把新的key加入到表中,这里我们要做两步,判断是否存在相同的key,如果存在就删除以前的key,注意的是这里说的key实际上是<key, value>对。
实现代码如下
import java.util.LinkedList;
public class HashDemo<K, V> {
private final int MAX_SIZE = 50;
LinkedList<Element<K,V>>[] items;
public HashDemo() {
items = new LinkedList[MAX_SIZE];
}
/* 官方实现hashcode代码
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
*/
public int hashCodeOfKey(K Key) {
return Key.toString().length() % items.length;
}
public void put(K key, V value) {
int h = hashCodeOfKey(key);
if(items[h] == null)
items[h] = new LinkedList<Element<K,V>>();
//检查当前的key是否已经存在
LinkedList<Element<K, V>> coll = items[h];
for(Element<K,V> e : coll) {
//如果存在就删除以前的元素
if(e.equivalent(key)) {
coll.remove(e);
break;
}
}
//把新的元素加到表中
Element<K, V> element = new Element<K, V>(key, value);
coll.add(element);
}
public V get(K key) {
int h = hashCodeOfKey(key);
if(items[h] == null) {
return null;
}
LinkedList<Element<K, V>> coll = items[h];
for(Element<K,V> e : coll) {
if(e.equivalent(key))
return e.getValue();
}
return null;
}
}
//Element类帮助我们处理表中的元素
class Element<K, V> {
private K key;
private V value;
public Element( K key, V value) {
this.key = key;
this.value = value;
}
public boolean equivalent(K k) {
return key.equals(k);
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}
参考资料:Cracking the Coding Interview,Gayle Laakmann McDowell
分享到:
相关推荐
问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立不同的哈希表; (3)采用链地址法...
C语言设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 1) 记录由外部输入。 2) 将生成...
数据结构的课程设计 哈希表实现电话号码查询系统
设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2)生成的哈希...
(1)每个人的信息至少包括姓名,...(2)假设人名为汉语拼音全拼形式,待插入哈希表的长度为你所在班级的人数。哈希函数用除留余数法构造,采用链地址法或二次探测再散列法解决冲突。 (3)完成菜单设计。操作有必要的提示。
数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(高分项目).zip代码完整,报告全面,下载即用。 数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(高分项目).zip代码完整,...
每组测试数据有两行,第一行有两个数n,m(0,m),第二行包含n个处于区间[−500000,500000]的整数,每个数后有一个空格。
问题描述: 设计哈希表实现电话号码查询系统。 基本要求: 1、设每个记录有下列数据项:电话号码、用户名、地址; 2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表; 3、采用再哈希法解决冲突; 4、...
数据结构 (课程设计)哈希表实现数据结构 (课程设计)哈希表实现
C语言基于哈希表实现通讯录--附源码
哈希表实现电话号码查询,解决冲突的函数,C语言代码
设计哈希表实现电话号码查询系统 数据结构课程设计
本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入、以及查找等功能。 (1)按提示输入相应的联系人的相关...
2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;3、采用再哈希法解决冲突; 4、查找并显示给定电话号码的记录; 5、查找并显示给定用户名的记录。6、在哈希函数确定的前提下,尝试各种不同类型...
哈希表查找,使用哈希表实现学生学籍管理======================
2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表; 3、采用再哈希法解决冲突; 4、查找并显示给定电话号码的记录; 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下,尝试各种不同类型...
哈希表实现电话号码查询系统方案.doc
数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(95分以上).zip本系统为电话号码查找系统,本系统最频繁的操作为查询功能,查询速度的快慢对此系统有至关重要的影响,因此应该选择合适的数据结构...