【java数据结构】哈希表
【java数据结构】哈希表
- 一、概念
- 二、哈希函数
- 三、冲突
- 3.1 概念
- 3.2 冲突避免
- 3.2.1 冲突避免-设计哈希函数
- 3.2.1 冲突避免-负载因子调节
- 3.2 解决冲突
- 3.2.1 解决冲突-闭散列
- 3.2.2 解决冲突-开散列/哈希桶
- 哈希桶代码实现
博客最后附有整篇博客的全部代码!!!
一、概念
哈希表(Hash Table)是一种基于哈希函数实现的数据结构,用于存储键值对(Key-Value Pair)。它通过哈希函数将键(Key)映射到一个特定的存储位置,从而实现快速的数据查找、插入和删除操作。
HashMap的操作时间复杂度O(1),相比于TreeMap(操作时间复杂度O(logN))我们会更加偏向使用HashMap。
二、哈希函数
哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
例如:这里有一组数据集合{1,7,6,4,5,9}
但是如果再向集合中存储元素44,那么此时应该怎么存储?
三、冲突
3.1 概念
对于两个数据元素的关键字 和 (i != j),有 != ,但有:Hash( ) == Hash( ),即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。根据上述,我们发现再向集合中存储元素大小为44时,此时数组小标为4 的位置已经有元素,我们将这个就叫做冲突。
3.2 冲突避免
首先,我们明确,哈希存储的底层数组大小往往小于实际存储数据的大小,这就导致一个问题,冲突的发生是必然的,但我们能做的应该是尽量的避免冲突。
3.2.1 冲突避免-设计哈希函数
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:
- 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见哈希函数
- 直接定制法–(常用)
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况 - 除留余数法–(常用)
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址 - 平方取中法–(了解)
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况 - 折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况 - 随机数法–(了解)
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数
函数。通常应用于关键字长度不等时采用此法 - 数学分析法–(了解)
设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。
注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突
3.2.1 冲突避免-负载因子调节
概念:负载因子(Load Factor)是哈希表(如HashMap、Hashtable等)的一个重要参数,用于控制哈希表的扩容时机,从而在性能和内存使用之间取得平衡。
定义:负载因子是哈希表中元素数量与哈希表容量(桶的数量)之间的比例关系,计算公式为:
负载因子=当前元素个数 / 哈希表容量
负载因子和冲突率的关系粗略演示:
这里发现负载因子越大冲突率就越大,所以这里我们需要降低负载因子的大小,从而使冲突率降低。
负载因子是由当前元素个数和哈希表容量控制的,但我们不能控制当前元素个数,所以我们一般控制哈希表容量。在java系统库中,我们规定负载因子大小为0.75,当负载因子超过0.75,我们就会扩大哈希表容量。
3.2 解决冲突
解决哈希冲突的两种方法:开散列和闭散列
3.2.1 解决冲突-闭散列
闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。
- 线性探测
线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
伪删除法:
- 标记状态:
- EMPTY:表示该位置为空,可以插入新元素。
- EXIST:表示该位置有元素。
- DELETE:表示该位置的元素已被逻辑删除。
- 插入操作:
- 计算哈希值,找到初始位置。
- 如果该位置为空(EMPTY)或已被删除(DELETE),则可以插入新元素。
- 如果该位置已被占用(EXIST),则通过线性探测找到下一个空位置
- 查找操作:
- 计算哈希值,从初始位置开始查找。
- 如果遇到标记为EXIST的元素,比较键值是否匹配。
- 如果遇到标记为DELETE的位置,继续向后查找,直到遇到EMPTY为止。
- 删除操作:
- 计算哈希值,找到目标元素。
- 将目标元素的状态标记为DELETE,而不是直接物理删除。
- 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: H= (H0 +i^2 )% m, 或者:H= ( H0-i^2 )% m。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。
闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。
3.2.2 解决冲突-开散列/哈希桶
开散列法:又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
哈希桶代码实现
- 基本类型的哈希桶
static class Node{
int key;
int value;
Node next;
public Node(int key, int value){
this.key = key;
this.value = value;
}
}
public Node[] array=new Node[10];
public int useSized;
private static final double LOAD_FACTOR=0.75;
public void put(int key, int value){
//1.先获取插入元素的下标
int index=key% array.length;
Node cur=array[index];
//2.判断集合中是否已经包含key
while(cur!=null){
if(cur.key==key){
cur.value=value;
}
cur=cur.next;
}
//3.插入key
Node newNode=new Node(key,value);
newNode.next=array[index];
array[index]=newNode;
useSized++;
//4.判断是否需要扩容
if(Do_LOAD_FACTOR()>=LOAD_FACTOR){
resize();
}
}
private void resize() {
//5.因为数组容量扩大,所以需要重新遍历一遍原来的数组
Node[] newArray=new Node[array.length*2];
for(int i=0;i<array.length;i++){
Node cur=array[i];
while(cur!=null){
Node curN=cur.next;
int index=cur.key% newArray.length;
cur.next=newArray[index];
newArray[index]=cur;
cur=curN;
}
}
array=newArray;
}
private double Do_LOAD_FACTOR(){
return useSized*1.0 /array.length;
}
public int getValue(int key){
int index=key% array.length;
Node cur=array[index];
while(cur!=null){
if(cur.key==key){
return cur.value;
}
cur=cur.next;
}
return -1;
}
- 引用类型的哈希桶
class Person{
String name;
public Person(String name){
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person preson = (Person) o;
return Objects.equals(name, preson.name);
}
@Override
public int hashCode() {
return Objects.hashCode(name);
}
}
public class RTHashbucket<K,V> {
static class Node<K,V>{
K key;
V value;
Node<K,V> next;
public Node(K key, V value){
this.key = key;
this.value = value;
}
}
public Node<K,V>[] array=(Node<K, V>[])new Node[10];
public int useSized;
private static final double LOAD_FACTOR=0.75;
public void put(K key, V value){
int hash = key.hashCode();
int index = hash % array.length;
Node<K,V> cur=array[index];
while(cur!=null){
if(cur.key.equals(key)){
cur.value=value;
}
cur=cur.next;
}
Node<K,V> newNode=new Node<>(key, value);
newNode.next=array[index];
array[index]=newNode;
useSized++;
if(Do_LOAD_FACTOR()>=LOAD_FACTOR){
resize();
}
}
private void resize() {
Node<K,V>[] newArray=(Node<K, V>[]) new Node[2* array.length];
for(int i=0;i<array.length;i++){
Node<K,V> cur=array[i];
while(cur!=null){
Node<K,V> curN=cur.next;
int hash = cur.key.hashCode();
int index = hash % newArray.length;
cur.next=newArray[index];
newArray[index]=cur;
cur=curN;
}
}
array=newArray;
}
private double Do_LOAD_FACTOR() {
return useSized*1.0/array.length;
}
public V getValue(K key){
int hash = key.hashCode();
int index = hash % array.length;
Node<K,V> cur=array[index];
while(cur!=null){
if(cur.key==key){
return cur.value;
}
cur=cur.next;
}
return null;
}
}
在引用类型的哈希桶代码实现,有个非常重要的方法:hashCode()方法。
作用:
- hashCode()方法是将对象的内存地址或其他特征转换为一个整数值,从而让我们得到数组下标。
- 对象的比较:如果两个对象的哈希码不同,那么它们一定不相等;如果哈希码相同,还需要进一步调用 equals() 方法来确认对象是否相等。
注意:如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须覆写 hashCode 和 equals 方法,而且要做到 equals 相等的对象,hashCode 一定是一致的。
此篇博客的全部代码!!!