数据结构之哈希表

缺乏、安全感 2022-01-23 03:03 347阅读 0赞

哈希表的相关学习：

## 哈希表 ##

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

## 哈希函数 ##

![20190526104304.png][]

哈希表是时间与空间之间的平衡,因此哈希函数的设计很重要。所以哈希函数应该尽量减少Hash冲突。也就是说“键”通过哈希函数得到的“索引”分布越均匀越好。

### 整形 ###

对于小范围的整数比如`-100~100`,我们完全可以对整数直接使用把它映射到`0~200`之间,而对于身份证这种的大整数,通常我们采用的是取模,比如大整数的后四位相当于`mod 10000`,这里有一个小问题,如果我们选择的数字如果不好的话,就有可能可能导致数据映射分布不均匀,因此我们最好寻找一个素数.

![20190526105544.png][]

如果选择一个合适的素数呢,这里有一个选择:

![20190526105723.png][]

图片来源:[https://planetmath.org/goodhashtableprimes][https_planetmath.org_goodhashtableprimes]

### 浮点型 ###

在计算机中都是32位或者64位的二进制表表示,只不过计算j级解析成了浮点数

![20190526115339.png][]

### 字符串 ###

字符串我们需要把它也转成整型处理

![20190526115537.png][]

我们对上面的方法进行优化一下,这就涉及到数学方面的知识了

![20190526115755.png][]

对于字符串来说,计算出来的大整形如果特别大的话可能会出现内存溢出,因此我们可以对取模的过程分别挪到式子里面.

![20190526120023.png][]

对于整个字符串来说我们可以写程序也是十分容易地写出来他的处理函数

<table> 
 <tbody> 
 <tr> 
 <td><pre>1 2 3 </pre></td> 
 <td><pre>int hash = 0; for (int i = 0; i &lt; s.length; i++) {
 hash = (hash * B + s.charAt(i)) % M; </pre></td> 
 </tr> 
 </tbody> 
</table>

### 案例 ###

![20190526152303.png][]

我们可以看到在实际的运行过程中对于整数的负数来说,依旧存在整数类型int中,对于浮点数和字符串来说都有都i是按照上面的方法.来进行计算。对于hashCode值相同我们并没有办法取判断是否属于一个对象，因此在equals和hashCode相同鼓的时候我们才能够说这个两个对象是相同的。

## 哈希冲突处理 ##

### 链地址法 ###

哈希表本质就是一个数组，

![20190526153109.png][]

对于哈希表我们只需要让他求出K1然后在模于M，当然这个大M是一个素数。对于负数来说，可以直接用绝对值来解决负数的问题。

![20190526153139.png][]

当然我们有时候看别人的代码或者源码的时候会看到

![20190526153453.png][]

用16进制法表示的整型，先和一个16进制表示的`0x7fffffff`的结果我们在对M取模，这个表示的是用二进制表示的话是31个`1`,整型有32位，最高位是符号位，32位和31位相与，这样做是吧最高位的32位，模成了0，符号位的问题我们就解决了。因此如果我们记录的`k1`的值为`4`，那么我们就可可以把k1存储到地址4这个位置中去。

![20190526154202.png][]

如果k2的索引位置为1，那么假设k3的位置也为1，那么我们就产生了hash冲突，如何解决呢？

![20190526154417.png][]

这里我们可以采用链表的方式，对于整个哈希表我们开M个空间，由于会出现hash冲突，我们可以把它做成链表，这种方法也叫*separate chaining*，当然我们已可以存红黑树，或者TreeMap。

![20190526154901.png][]

本质上来说，HashMap就是一个TreeMap数组，HashSet就是一个TreeSet数组。对于Java8来说，Java8之前每一个位置对应的是一个链表，Java8开始之后，当哈希冲突达到了一定的程度，每一个位置从链表转化为红黑树，这个阈值为8；

### 代码实现 ###

<table> 
 <tbody> 
 <tr> 
 <td><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 </pre></td> 
 <td><pre>import java.util.LinkedList; import java.util.List; public class HashTable&lt;T&gt;{
 public HashTable() {
 this(DEFAULT_TABLE_SIZE); } public HashTable(int size) {
 theLists=new LinkedList[nextPrime(size)]; for(int i=0;i&lt;theLists.length;i++) {
 theLists[i]=new LinkedList&lt;&gt;();//初始化链表数组 } } /* * 哈希表插入元素 * */ public void insert(T x) {
 List&lt;T&gt; whichList=theLists[myhash(x)]; /* * 如果当前哈希地址的链表不含有元素，则链表中添加该元素 * */ if(!whichList.contains(x)) {
 whichList.add(x); if(++currentSize&gt;theLists.length)//如果表长度不够，则扩容 rehash(); } } public void remove(T x) {
 List&lt;T&gt; whichList=theLists[myhash(x)]; if(whichList.contains(x)) {
 whichList.remove(x); currentSize--; } } public boolean contains(T x) {
 List&lt;T&gt; whilchList=theLists[myhash(x)]; return whilchList.contains(x); } public void makeEmpty() {
 for(int i=0;i&lt;theLists.length;i++) theLists[i].clear(); currentSize=0; } private static final int DEFAULT_TABLE_SIZE=101; private List&lt;T&gt; [] theLists; private int currentSize; /* * 哈希表扩容，表长度为下一个素数 * */ private void rehash() {
 List&lt;T&gt;[] oldLists=theLists; theLists=new List[nextPrime(2*theLists.length)]; for(int j=0;j&lt;theLists.length;j++) theLists[j]=new LinkedList&lt;&gt;(); currentSize=0; /* * 更新哈希表 * */ for(List&lt;T&gt; list:oldLists) for(T item:list) insert(item); } /* * myhash()方法获得哈希表的地址 * */ private int myhash(T x) {
 int hashVal=x.hashCode();//hashCode()方法返回该对象的哈希码值 hashVal%=theLists.length;//对哈希表长度取余数 if(hashVal&lt;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 &lt;= n; i += 2 ) if( n % i == 0 ) return false; return true; } } </pre></td> 
 </tr> 
 </tbody> 
</table>

### 开放地址法 ###

这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述：  
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))  
其中： H ( key ) 为关键字 key 的直接哈希地址， m 为哈希表的长度， di 为每次再探测时的地址增量。  
采用这种方法时，首先计算出元素的直接哈希地址 H ( key ) ，如果该存储单元已被其他元素占用，则继续查看地址为 H ( key ) + d 2 的存储单元，如此重复直至找到某个存储单元为空时，将关键字为 key 的数据元素存放到该单元。  
增量 d 可以有不同的取法，并根据其取法有不同的称呼：  
（ 1 ） d i ＝ 1 ， 2 ， 3 ， …… 线性探测再散列；  
（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列；  
（ 3 ） d i ＝ 伪随机序列 伪随机再散列；

例1设有哈希函数 H ( key ) = key mod 7 ，哈希表的地址空间为 0 ～ 6 ，对关键字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ）按线性探测再散列和二次探测再散列的方法分别构造哈希表。  
解：  
（ 1 ）线性探测再散列：  
32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ；  
55 ％ 7 = 6 发生冲突，下一个存储地址（ 6 ＋ 1 ）％ 7 ＝ 0 ，仍然发生冲突，再下一个存储地址：（ 6 ＋ 2 ）％ 7 ＝ 1 未发生冲突，可以存入。  
22 ％ 7 ＝ 1 发生冲突，下一个存储地址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未发生冲突；  
38 ％ 7 ＝ 3 ；  
21 ％ 7 ＝ 0 发生冲突，按照上面方法继续探测直至空间 5 ，不发生冲突，所得到的哈希表对应存储位置：  
下标： 0 1 2 3 4 5 6

49 55 22 38 32 21 13

当然还有其他的方法比如`再哈希法`，Coalesced Hashing法（综合了Seperate Chainging 和 Open Addressiing）等。

### 代码实现 ###

<table> 
 <tbody> 
 <tr> 
 <td><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 </pre></td> 
 <td><pre>class DataItem { //数据 private int iData; // data item (key) public DataItem(int ii) { iData = ii; } public int getKey(){ return iData; } } class HashTable{
 //数组实现的哈希表，开放地址法之线性探测 private DataItem[] hashArray; //存放数据的数组 private int arraySize; private DataItem nonItem; //用作删除标志 public HashTable(int size) {
 //构造函数 arraySize = size; hashArray = new DataItem[arraySize]; nonItem = new DataItem(-1); // deleted item key is -1 } public void displayTable(){
 //显示哈希表 System.out.print("Table: "); for(int j=0; j&lt;arraySize; j++) { if(hashArray[j] != null) System.out.print(hashArray[j].getKey() + " "); else System.out.print("** "); } System.out.println(""); } //哈希函数 public int hashFunc(int key) { return key % arraySize; } //在哈希表中插入数据 public void insert(DataItem item){ int key = item.getKey(); // 获取数据的键值 int hashVal = hashFunc(key); // 计算其哈希值 while(hashArray[hashVal] != null &amp;&amp; hashArray[hashVal].getKey() != -1){ ++hashVal; // 插入位置被占，线性探测下一位置 hashVal %= arraySize; // 不让超过数组的大小 } hashArray[hashVal] = item; // 找到空位后插入 } //在哈希表中删除 public DataItem delete(int key) { int hashVal = hashFunc(key); // 计算其哈希值 while(hashArray[hashVal] != null){ if(hashArray[hashVal].getKey() == key){ DataItem temp = hashArray[hashVal]; // 记录已删除的数据 hashArray[hashVal] = nonItem; // 删除它 return temp; } ++hashVal; // 到下一单元找 hashVal %= arraySize; } return null; // 没有找到要删除的数据 } //在哈希表中查找 public DataItem find(int key) { int hashVal = hashFunc(key); //哈希这个键 while(hashArray[hashVal] != null) { // 直到空的单元 if(hashArray[hashVal].getKey() == key) return hashArray[hashVal]; // 找到 ++hashVal; // 去下一单元找 hashVal %= arraySize; // 不让超过数组的大小 } return null; // 没有找到 } } </pre></td> 
 </tr> 
 </tbody> 
</table>

## 参考资料 ##

[https://www.cnblogs.com/vincentme/p/7920237.html][https_www.cnblogs.com_vincentme_p_7920237.html]

[https://blog.csdn.net/w\_fenghui/article/details/2010387][https_blog.csdn.net_w_fenghui_article_details_2010387]

[https://128kj.iteye.com/blog/1744810][https_128kj.iteye.com_blog_1744810]

[20190526104304.png]: /images/20220123/de0b7b90e3ef4bf2a4734b96e80f59f6.png
[20190526105544.png]: /images/20220123/bfde80dda2104092afdd584f0a46760a.png
[20190526105723.png]: /images/20220123/299ffa24f9d9419aa7602da7496fa9bb.png
[https_planetmath.org_goodhashtableprimes]: https://planetmath.org/goodhashtableprimes
[20190526115339.png]: /images/20220123/8418724b318d4771a8377f31e8d4524a.png
[20190526115537.png]: /images/20220123/fdb9a4ce28534888bf1a47993c3763e8.png
[20190526115755.png]: /images/20220123/8c4c219bbb6043adabd242bebf3e892a.png
[20190526120023.png]: /images/20220123/9cc2205f0f3f4dafb20a91b071ba56bc.png
[20190526152303.png]: /images/20220123/922dcd7c74324d3fbc42522056f38183.png
[20190526153109.png]: /images/20220123/9183b299264e40c98fcd907289369b4d.png
[20190526153139.png]: /images/20220123/25dc943b420a437899b50a06b56a9d03.png
[20190526153453.png]: /images/20220123/702194b70ff74b57ac8cf5e233404036.png
[20190526154202.png]: /images/20220123/d3e1f43165d24af59d291f639432acad.png
[20190526154417.png]: /images/20220123/fc384d427ec341e0ac0f7652656660dd.png
[20190526154901.png]: /images/20220123/0cccab0bafeb4f91939e43fb1c91e506.png
[https_www.cnblogs.com_vincentme_p_7920237.html]: https://www.cnblogs.com/vincentme/p/7920237.html
[https_blog.csdn.net_w_fenghui_article_details_2010387]: https://blog.csdn.net/w_fenghui/article/details/2010387
[https_128kj.iteye.com_blog_1744810]: https://128kj.iteye.com/blog/1744810