JAVA数据结构--哈希表的实现（分离链接法）
2024-09-27 06:08:37
哈希表（散列）的定义
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的特点是采用以常数平均时间执行插入、删除和查找。
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名
到首字母
的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则
，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
分离链接法定义
将散列到同一个值得所有元素保留到一个表中。
基本思想是采用N个链表组成链表数组，N为哈希表的长度。
哈希表构造实现
public SeparateChainingHashTable() {
this(DEFAULT_TABLE_SIZE);
}
public SeparateChainingHashTable(int size) {
theLists=new LinkedList[nextPrime(size)];
for(int i=0;i<theLists.length;i++) {
theLists[i]=new LinkedList<>();//初始化链表数组
}
}
基本操作实现
/*
* 哈希表插入元素
* */
public void insert(T x) {
List<T> whichList=theLists[myhash(x)];
/*
* 如果当前哈希地址的链表不含有元素，则链表中添加该元素
* */
if(!whichList.contains(x)) {
whichList.add(x);
if(++currentSize>theLists.length)//如果表长度不够，则扩容
rehash();
}
}
public void remove(T x) {
List<T> whichList=theLists[myhash(x)];
if(whichList.contains(x)) {
whichList.remove(x);
currentSize--;
}
}
public boolean contains(T x) {
List<T> whilchList=theLists[myhash(x)];
return whilchList.contains(x);
}
public void makeEmpty() {
for(int i=0;i<theLists.length;i++)
theLists[i].clear();
currentSize=0;
}
哈希表相关实现
private void rehash() {
List<T>[] oldLists=theLists;
theLists=new List[nextPrime(2*theLists.length)];
for(int j=0;j<theLists.length;j++)
theLists[j]=new LinkedList<>();
currentSize=0;
/*
* 更新哈希表
* */
for(List<T> list:oldLists)
for(T item:list)
insert(item);
}
/*
* myhash()方法获得哈希表的地址
* */
private int myhash(T x) {
int hashVal=x.hashCode();//hashCode()方法返回该对象的哈希码值
hashVal%=theLists.length;//对哈希表长度取余数
if(hashVal<0)
hashVal+=theLists.length;
return hashVal;
}
全部代码
import java.util.LinkedList;
import java.util.List; public class SeparateChainingHashTable<T>{
public SeparateChainingHashTable() {
this(DEFAULT_TABLE_SIZE);
}
public SeparateChainingHashTable(int size) {
theLists=new LinkedList[nextPrime(size)];
for(int i=0;i<theLists.length;i++) {
theLists[i]=new LinkedList<>();//初始化链表数组
}
} /*
* 哈希表插入元素
* */
public void insert(T x) {
List<T> whichList=theLists[myhash(x)];
/*
* 如果当前哈希地址的链表不含有元素，则链表中添加该元素
* */
if(!whichList.contains(x)) {
whichList.add(x);
if(++currentSize>theLists.length)//如果表长度不够，则扩容
rehash();
}
}
public void remove(T x) {
List<T> whichList=theLists[myhash(x)];
if(whichList.contains(x)) {
whichList.remove(x);
currentSize--;
}
}
public boolean contains(T x) {
List<T> whilchList=theLists[myhash(x)];
return whilchList.contains(x);
}
public void makeEmpty() {
for(int i=0;i<theLists.length;i++)
theLists[i].clear();
currentSize=0;
} private static final int DEFAULT_TABLE_SIZE=101; private List<T> [] theLists;
private int currentSize; /*
* 哈希表扩容，表长度为下一个素数
* */
private void rehash() {
List<T>[] oldLists=theLists;
theLists=new List[nextPrime(2*theLists.length)];
for(int j=0;j<theLists.length;j++)
theLists[j]=new LinkedList<>(); currentSize=0;
/*
* 更新哈希表
* */
for(List<T> list:oldLists)
for(T item:list)
insert(item);
}
/*
* myhash()方法获得哈希表的地址
* */
private int myhash(T x) {
int hashVal=x.hashCode();//hashCode()方法返回该对象的哈希码值
hashVal%=theLists.length;//对哈希表长度取余数
if(hashVal<0)
hashVal+=theLists.length;
return hashVal;
}
//下一个素数
private static int nextPrime(int n) {
if( n % 2 == 0 )
n++; for( ; !isPrime( n ); n += 2 )
; return n;
}
//判断是否是素数
private static boolean isPrime(int n) {
if( n == 2 || n == 3 )
return true; if( n == 1 || n % 2 == 0 )
return false; for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false; return true;
}
}
最新文章
- python类中super()和__init__()的区别
- form中的GET与POST
- history
- jenkins+gerrit
- jfinal配置rails的数据表
- MQ 2035(MQRC_NOT_AUTHORIZED)
- 【转】linux trap
- Understanding AMQP, the protocol used by RabbitMQ--reference
- php如何开启GD库
- drupal错误: Maximum execution time of 240 seconds exceeded
- 第二次项目冲刺（Beta阶段）第一天
- SQL Server 修改AlwaysOn共享网络位置
- vue组件之间的传值方式
- Xml文档规则
- 10个经典的Java面试题集合
- Git(介绍和安装)
- Java并发编程（三）Thread类的使用
- const读书笔记
- linux下Mysql多实例实现
- MYSQL社区版安装手册