目录

前言

一、散列表查找定义

1、散列表查找步骤       

        🎯整个散列过程分为两步：

2、Hash冲突

 二、散列函数的构造

1、直接定址法

2、数字分析法

 3、平方取中法

4、折叠法

 5、除留余数法

此方法为最常用的构造散列函数的方法：

6、随机数法 

7、总结散列函数 

三、处理散列冲突（哈希冲突解决） 

1、开放定址法

1）线性探测法

2）二次探测法

2、再散列函数法

3、链地址法 （Java的HashMap）

4、公共溢出区法

四、散列表的查找

1、算法实现（Java的HashTable为例）

1）定义散列表结构

2）初始化容器

3）定义散列函数（为存储数据）

4）查找记录

2、性能分析

---

前言

        数据结构和算法中，查找某个关键字key，有不同办法：

• 顺序表中，必须从头开始，挨个比较a[i]与key是或不是相等，相等返回i。
• 有序表中（例如：树结构），可以利用a[i]大于或小于key，折半查找，相等返回i。

        最终目的是找到a[i]的下标位置i，再通过顺序存储的存储位置计算方法：

                LOC(ai) = LOC(a1)+(i-1)*c

通过第一个元素内存位置，加上i-1个单元位置，得到最后的内存位置。

        为了查找到结果，比较了很多不必要的，是否可以通过关键字key直接得到要查找内容的内存地址呢？

---

一、散列表查找定义

        散列技术是在【记录的存储位置】和【它的关键字】之间建立一个【确定的对应关系函数f】，使得每个关键字key对应一个存储位置f(key)。

        查找时：根据【确定的对应关系函数f】找到给定值key的映射f(key)。

• 哈希函数/散列函数：一个【确定的对应关系函数f】就叫散列函数。
• 哈希表/散列表：采用此技术将【记录的存储位置】连一块的存储空间称为散列表/哈希表。
• 散列地址：【它的关键字】对应的存储位置，称为散列地址。

---

1、散列表查找步骤       

        🎯整个散列过程分为两步：

             第一步：存储：通过散列函数计算散列地址，按此散列地址储存记录。

             第二步：访问：按同样的散列函数计算散列地址，按此散列地址访问记录。

        由此可见：散列技术既是一种存储方法，又是一种查找方法。

适用场景：找到给定值相等的记录。

---

2、Hash冲突

         两个关键字 key1 不等于 key2，但是 f(key1) = f(key2)， 这种现象称为冲突。

---

 二、散列函数的构造

        散列技术听起来很简单，但是散列/哈希函数是个怎样的函数，就是个关键问题。怎样的函数，可以分散地均匀，怎样的函数计算起来简单、性能优？

1、直接定址法

地址	出生年月	人数
0000	1980	1000万人
0001	1981	1200万人
0002	1982	900万人
...	...	...
0041	2021	...
...	...	...

直接定址法：取关键字某个线性函数值为散列地址。

优点：简单，均匀，不会产生冲突。

缺点：事先知道关键字的分布。

使用场景：很不常用。

2、数字分析法

数字分析法：抽取数字位移或相加反转等办法，来计散列存储位置。

使用场景：

• 适用于关键字数字位数多
• 事先知道关键字的若干位分布比较均匀

 3、平方取中法

平方取中法：将关键字做平方运算，再取中间几位，用作散列地址。

使用场景：

• 关键字数字且位数不多
• 事先不知道关键字的分布

4、折叠法

折叠法 ：将关键字从左到右分割成位数相等的几部分，将这几部分叠加求和，并按散列表表长取后几位作为散列值。

使用场景：

• 不需要知道关键字的分布
• 关键字位数较多

 5、除留余数法

此方法为最常用的构造散列函数的方法：

        对于散列表长度为m的散列函数公式：f(key)=key mod p (p<m)

mod：是取模（求余数）的意思。不仅可以直接取模，也可以折叠或平方后取模。

注：p最好小于或等于散列表的长度，最好是接近长度的最小质数或不包含小于20质因子的合数。

6、随机数法 

f(key) = random(key)： random为随机函数。

使用场景：

• 关键字长度不确定

7、总结散列函数 

综合以下因素，决策选择哪种散列函数：

1）计算散列地址所需的时间。

2）关键字的长度。

3）散列表的长度。

4）关键字的分布。

5）记录查找的频率。

---

三、处理散列冲突（哈希冲突解决） 

1、开放定址法

开放定址法：就是一旦发生冲突，就寻找（按一定的函数）下一个空的散列地址，只要散列表足够大。

开放定址法常见分类：

• 线性探测法
• 二次探测法
• 随机探测法

1）线性探测法

f(key) = ( f(key) + i ) MOD m (i = 1,2,3...,m-1)

例如：

关键字集合长度为12，m取12

key=48 --> f(48) = 0 冲突，就计算 ：( f(48) +1 ) mod 12 =1 ,还是冲突，就计算

( f(48) + 2 ) mod 12 =1 还是冲突继续...直到找到为止。

2）二次探测法

上述线性探测法i从1-6都试过了，没有空位置，这样看来效率很差，有没有效率好一点的办法？把 i 进行改进就可以做到查找的方式

i= 1的平方，-1的平方，2的平方，-2的平方，...，q的平方，-q的平方（q<=m/2）

• 增加平方的运算是为了不让关键字聚集在某一块区域

这样可以变成双向寻找可能空的位置。

3）随机探测法

 仍然是改进上述线性探测法i的取值方式：随机数（伪随机数）。

• 相同的随机种子，得到不会重复的数列
• 查找使用相同的随机种子，得到同样的数

2、再散列函数法

当冲突发生时使用另一种散列函数重新选址，冲突再换函数...总有一个会把冲突解决。 

3、链地址法 （Java的HashMap）

将所有的位置冲突的关键字放在链表中（如下图）。

此时不存在冲突换址，但也给查找时带来了 遍历链表的性能损耗。

4、公共溢出区法

将有冲突的收集统一管理到溢出表中，在朝查找时先找基本表，若不相等再再到溢出表顺序查找。（溢出很少时，性能较好）

---

四、散列表的查找

1、算法实现（Java的HashTable为例）

1）定义散列表结构

private static class Entry<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Entry<K,V> next;protected Entry(int hash, K key, V value, Entry<K,V> next) {this.hash = hash;this.key =  key;this.value = value;this.next = next;}//....public int hashCode() {return hash ^ Objects.hashCode(value);}}

2）初始化容器

public Hashtable(int initialCapacity, float loadFactor) {//初始容量if (initialCapacity==0)initialCapacity = 1;//加载因子this.loadFactor = loadFactor;//数据元素存储基本结构table = new Entry<?,?>[initialCapacity];//阈值threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

3）定义散列函数（为存储数据）

Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
Entry<K,V> entry = (Entry<K,V>)tab[index];

4）查找记录

    public synchronized V get(Object key) {Entry<?,?> tab[] = table;int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {if ((e.hash == hash) && e.key.equals(key)) {return (V)e.value;}}return null;}

存储数据和查询数据的方法很相似，用相同的散列函数。 

2、性能分析

如果没有冲突，散列表的查找复杂度为O(1)，效率非常高。

如果有冲突，查找的时间与以下相关：

• 散列函数是否均匀：散列函数的好坏直接影响了冲突的出现频繁与否。
• 处理冲突的方法：比如线性探测就没有二次探测好。
• 散列表的装填因子：
  • x = 记录个数 / 散列表的长度
  • x 标志着散列表的装满程度
  • 散列表的查找时间复杂度取决于装填因子，而不是记录的个数
  • 通常将散列表的空间设置的比查找的集合大，虽然浪费空间，但是查找效率提高。