目录

1哈希表的概念:

1.1哈希表的插入图示:

1.2哈希表的查询图示:

2.哈希冲突

2.1哈希冲突的概念:

2.2避免冲突

2.2.1哈希函数设计

2.2.2负载因子的调节

3.解决冲突

3.1闭散列:

3.2开散列/(哈希桶)

4.哈希表的实现

1哈希表的概念:

1.1哈希表的插入图示:

1.2哈希表的查询图示:

上图解释了如何以哈希的方式存储数据了;那么数据该如何读取呢?请看下图!

2.哈希冲突

2.1哈希冲突的概念:

对于 两个数据元素 的关键字 K1 和 K2（互不相等），但有：哈希函数：Hash(k1) == Hash(K2) ,即：不同的关键字通过相同的哈希函数计算出了相同的哈希地址，这种现象成为哈希冲突或 哈希碰撞。把具有不同关键码，但却具有相同的哈希地址的数据元素称为 “同义词”。

2.2避免冲突

哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这也就导致了一个问题,那就是冲突是必然会发生;虽然冲突是必然发生的;但是我们能做到的是尽量降低冲突的概率.

如何有效避免哈希冲突呢?从以下两个方面入手:哈希函数的设计,负载因子的调节!

2.2.1哈希函数设计

哈希函数设计不合理是引起哈希冲突的一个重要原因;那么常见的哈希函数主要是以下两种!

1.直接定制法:

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况

2.除留余数法:

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

2.2.2负载因子的调节

负载因子的定义: a = 填入表中的元素个数 / 哈希表的长度

通俗的理解就是:当哈希表长度一定时;随着插入表中元素的增加;负载因子(a)就会增大;而负载因子越大,冲突产生的概率就越大;所以我们可以通过降低负载因子来降低冲突率.

负载因子与冲突率的关系如下:

那么怎么调节负载因子呢?

由定义公式可知:a = 填入表中的元素个数 / 哈希表的长度;

我们可以通过增大分母来使负载因子a降低;也就是将哈希表的长度增长,通俗的讲:将数组扩容;

3.解决冲突

解决哈希冲突两种常见的方法是：闭散列和开散列

3.1闭散列:

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？ 有两种方式:线性探测 和 二次探测1.线性探测:从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。(通俗的理解就是:该位置发生冲突之后,直接在该位置后找下一个空位插入即可)

虽然是线性探测解决了寻找空位的问题,但是又引来了另一个问题:那就是会使产生冲突的数据堆积在一块,这与其找下一个空位置有关系，因为找空位置的方式就是挨 着往后逐个去找，因此二次探测为了避免该问题.

2.二次探测:找下一个空位置的方法为:H(i) = (H0 + i^2 ) % m, 或者：H(i)= (H0 - i^2) % m。其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。(通俗的理解就是:虽然也是找空位插入,但是在找空位的时候,跟上一个找的位置隔的更远了,也就使的冲突的数据分的更加开了)

闭散列的缺陷:闭散列虽然在一定程度上解决了哈希冲突;但是他存在着缺陷:例如不能随意物理删除元素;采用闭散 列处理哈希冲突时,不能随意物理删除哈希表中的已有元素,若直接删除元素会影响到其他元素的寻 找,这就导致了没有用的数据仍然存,使得空间利用率比较低! 那怎么办呢?就由开散列来解决!

3.2开散列/(哈希桶)

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关 键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各 链表的头结点存储在哈希表中. 文字比较抽象,直接上图:开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了!

4.哈希表的实现

public class HashBucket {static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;this.next = null;}}private Node[] array;public int usedsize;public HashBucket() {this.array = new Node[10];this.usedsize = 0;}public void put(int key, int val) {//1.确定下标==哈希函数int index = key % this.array.length;//2.遍历这个下标的链表Node cur = array[index];//头插法while (cur != null) {//如果key已经存在 更新valif (cur.key == key) {cur.val = val;return;}cur = cur.next;}//3.cur == null 当前数组下标下的链表 没有key 则将其以头插法进行插入Node node = new Node(key, val);node.next = array[index];array[index] = node;this.usedsize++;//4.判断是否需要扩容if (loadFactor() >= 0.75) {//扩容resize();}}public double loadFactor() {return this.usedsize * 1.0 / this.array.length;}public void resize() {//自己创建新的数组 该数组是原本数组长度的两倍Node[] newArray = new Node[2 * this.array.length];//需要把原本数组里所存储的数据全部重新进行哈希 因为数组的长度变了 哈希函数里的数值就变了 所以需要重新哈希//遍历原本的哈希桶//最外层循环 控制数组的下标for (int i = 0; i < array.length; i++) {Node cur = array[i];Node curNext = null;while (cur != null) {//记录cur.nextcurNext = cur.next;//重新确立新的下标 然后进行头插法int index = cur.key % newArray.length;cur.next = newArray[index];newArray[index] = cur;cur = curNext;}}this.array = newArray;}public int get(int key) {//以什么样的方式存储的 就以什么样的方式取出int index = key % this.array.length;Node cur = array[index];while (cur != null) {if (cur.key == key) {return cur.val;}cur = cur.next;}return -1;}}