数据结构：哈希表（二）

目录

一、哈希表

1、概念

二、哈希冲突

1、概念

2、冲突避免

（1）哈希函数设计

（2）负载因子调节

3、冲突解决

（1）闭散列

1、线性探测

2、二次探测

（2）开散列

4、哈希桶实现

（1）put(int key,int value)

（2）get(int key)

5、和java类集的关系

---

一、哈希表

1、概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。

顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。

---

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结 构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

---

而当我们向上述的结构中进行：

1、插入元素操作：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

2、搜索元素操作：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

能够实现这样的操方式即为我们的哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

---

例如：数据集合{1，7，6，4，5，9}； 哈希函数设置为：hash(key)=key%capacity; capacity为存储元素底层空间总的大小。

二、哈希冲突

1、概念

对于两个数据元素的关键字Ki 和Kj (i!=j)，有 Ki !=Kj (i!=j) ，但有：Hash(Ki)==Hash(Kj (i!=j))， 即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

2、冲突避免

首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量 的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

（1）哈希函数设计

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

1、哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须 在0到m-1之间

2、哈希函数计算出来的地址能均匀分布在整个空间中

3、哈希函数应该比较简单

常用哈希函数：

1、直接定制法

取关键字的某个线性函数为散列地址：Hash（Key）=A*Key+B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

2、除留余数法

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

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

（2）负载因子调节

负载因子 = 填入表中元素的个数 / 散列表的长度

负载因子与“填入表中的元素个数”成正比，所以负载因子越大，表明填入表中的元素越多，产生冲突的可能性就越大，反之，负载因子越小，标明填入表中的元素越少，产生冲突的可能性就越小。

正因是这样的性质，所以我们可以去增大我们散列表的长度，让我们的负载因子变小，而负载因子变小了，代表我们能填入的元素个数就增加了

3、冲突解决

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

（1）闭散列

闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下⼀个”空位置中去。

那我们如何寻找下⼀个空位置呢？这就引出了两个新的方法

1、线性探测

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

通过哈希函数获取待插入元素在哈希表中的位置 ， 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测 找到下一个空位置，插入新元素

 

而线性探测是有缺陷的，他会导致产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式 就是挨着往后逐个去找，而我们的接下来的二次探测就解决了这种缺陷。

2、二次探测

找下一个空位置的方法为：Hi = (H0+i^2)%m 或Hi=（H0-i^2)%m 其中 i= 1，2，3……，H0是通过对元素的关键码 key 进行哈希函数计算得到的位置，m是散列表的大小。

 

（2）开散列

开散列法又链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一字集合，每一个字集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。因此这种方法也被称为哈希桶。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。 

4、哈希桶实现

我们的哈希表是一个key-value模型，还是一个节点数组，并且他是带有负载因子的

public class HashBucket {public static class Node{public int key;public int val;Node next;public Node(int key,int val){this.key = key;this.val = val;}}public Node[] arr;public int usesize;public static final double LOAD_FACTOR = 0.75;
}

---

 

（1）put(int key,int value)

1、使用哈希函数计算出key的哈希地址

---

2、检查我们得到的哈希地址，去数组中查找key这个值是否存在，存在更新对应的value值

---

 

3、如果不存在我们就利用头插法在这个哈希地址处将这个结点插入，同时让我们的有效长度usesize++

---

4、之后我们要判断是否超过了我们的负载因子，如果超过了我们就要进行扩容

---

5、扩容后我们会发现，我们有的元素可以放到新的位置处，所以我们需要进行重新哈希，在重新哈希的过程中再次利用头插法进行插入元素，但是如果在同一位置处有多个元素，我们将第一个元素放入新的位置(cur.next),我们原本的cur下一个元素就会无法找到因此，我们需要将原本cur.next记录下来。

---

 

public void put(int key,int val){//计算哈希地址int index = key% arr.length;//判断是否出现相同的key值，出现就更新value值Node cur = arr[index];while(cur != null){if(cur.key == key){cur.val = val;return;}cur = cur.next;}//如果没有key值，使用头插法添加结点Node newNode = new Node(key,val);newNode.next = arr[index];arr[index] = newNode;usesize++;//增加有效长度//判断负载因子if(loadFactor() > LOAD_FACTOR){resize();//超过负载因子的值就进行扩容}}//计算负载因子private double loadFactor(){return usesize * 1.0 / arr.length;//由于是小数要乘以1.0}//扩容private void resize(){Node[] newarr = new Node[arr.length*2];//以2倍扩容//利用头插法重新哈希for(int i = 0; i < arr.length;i++){Node cur = arr[i];while(cur != null){int newindex = cur.key % newarr.length;Node curN = cur.next;cur.next = newarr[newindex];newarr[newindex] = cur;cur = curN;}}arr = newarr;//让arr指向新的数组}

---

 

（2）get(int key)

这个方法就很简单了，要我们根据key得到对应的value值，首先我们还是计算处哈希地址，根据得到的哈希地址，去查找，如果存在这个key值就返回他所对应的value值。

public int get(int key){int index = key % arr.length;Node cur = arr[index];while(cur != null){if(cur.key == key){return cur.val;}cur = cur.next;}return -1;}

---

 

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/ 删除/查找时间复杂度是O(1)。 

5、和java类集的关系

1、HashMap和HashSet即java中利用哈希表实现的Map和Set

2、java 中使用的是哈希桶方式解决冲突的

3、java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

     数组长度大于64， 并且链表长度大于8

4、java 中计算哈希值实际上是调用的类的hashCode方法，进行key的相等性比较是调用         key的 equals 方法。所以如果要用自定义类作为HashMap的key或者HashSet的值，必      须覆写 hashCode和equals方法，而且要做到equals相等的对象，hashCode一定是一        致的。

---

 

像是我们的第4个关系如果我们传入的key值是一个字符串，我们上述实现的哈希桶就就无法使用的，那么我们是否可以创建一个通用的哈希桶呢，这当然是可以的，我们之前学习过泛型，可以根据我们传入类型的不同进行改变

public class HashBucket1<K,V> {public static class Node<K,V>{public K key;public V val;Node<K,V> next;public Node(K key,V val){this.key = key;this.val = val;}}public Node<K,V>[] arr =(Node<K, V>[]) new Node[10];public int usesize;public static final double LOAD_FACTOR = 0.75;public void put(K key,V val){//计算哈希地址int hashcode = key.hashCode();int index = hashcode % arr.length;//判断是否出现相同的key值，出现就更新value值Node<K,V> cur = arr[index];while(cur != null){if(cur.key.equals(key)){cur.val = val;return;}cur = cur.next;}//如果没有key值，使用头插法添加结点Node<K,V> newNode = new Node(key,val);newNode.next = arr[index];arr[index] = newNode;usesize++;//增加有效长度//判断负载因子if(loadFactor() > LOAD_FACTOR){resize();//超过负载因子的值就进行扩容}}//计算负载因子private double loadFactor(){return usesize * 1.0 / arr.length;//由于是小数要乘以1.0}//扩容private void resize(){Node<K,V>[] newarr =(Node<K, V>[]) new Node[arr.length*2];//以2倍扩容//利用头插法重新哈希for(int i = 0; i < arr.length;i++){Node<K, V> cur = arr[i];while(cur != null){int hashcode = cur.key.hashCode();int newindex = hashcode % newarr.length;Node<K, V> curN = cur.next;cur.next = newarr[newindex];newarr[newindex] = cur;cur = curN;}}arr = newarr;//让arr指向新的数组}public V get(K key){int hashcode = key.hashCode();int index = hashcode % arr.length;Node<K,V> cur = arr[index];while(cur != null){if(cur.key.equals(key)){return cur.val;}cur = cur.next;}return null;}

但是在这里我们发现一件事，如果我们有两个引用他们的key值是相同的，这时我们put一个引用，但是我们用另一个引用去获得value值时我们却得不到

这时因为虽然两个引用的值时相同的但是他们的地址是不同的，然而我们要实现的哈希桶只有值是相同的就可以得到，所以我们要重写我们的hashCode()和equals()方法 

 重写之后我们就可以发现我们的person2也可以得到person1的value值了

 

---

好了，今天的分享就到这里了还请大家多多关注，我们下一篇见！