数据结构是哈希表（hashTable）

Bertha 。 2022-06-15 01:15 197阅读 0赞

哈希表也称为散列表，是根据关键字值（key value）而直接进行访问的[数据结构][Link 1]。也就是说，它通过把关键字值映射到一个位置来访问记录，以加快查找的速度。这个映射函数称为哈希函数（也称为散列函数），映射过程称为哈希化，存放记录的数组叫做散列表。比如我们可以用下面的方法将关键字映射成数组的下标：arrayIndex = hugeNumber % arraySize。

哈希化之后难免会产生一个问题，那就是对不同的关键字，可能得到同一个散列地址，即同一个数组下标，这种现象称为冲突，那么我们该如何去处理冲突呢？一种方法是开放地址法，即通过系统的方法找到数组的另一个空位，把数据填入，而不再用哈希函数得到的数组下标，因为该位置已经有数据了；另一种方法是创建一个存放链表的数组，数组内不直接存储数据，这样当发生冲突时，新的数据项直接接到这个数组下标所指的链表中，这种方法叫做链地址法。下面针对这两种方法进行讨论。

# **1.开放地址法** #

## 线性探测法    ##

所谓线性探测，即线性地查找空白单元。如果21是要插入数据的位置，但是它已经被占用了，那么就是用22，然后23，以此类推。数组下标一直递增，直到找到空白位。下面是基于线性探测法的哈希表实现代码：

**\[html\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  public class HashTable \{  
2.        
3.      private DataItem\[\] hashArray; // DateItem类是数据项，封装数据信息  
4.      private int arraySize=10;  
5.      private int itemNum; // 数组中目前存储了多少项  
6.      private DataItem nonItem; // 用于删除项的  
7.    
8.      public HashTable() \{  
9.          hashArray = new DataItem\[arraySize\];  
10.         nonItem = new DataItem(-1); // deleted item key is -1  
11.     \}  
12.   
13.     public boolean isFull() \{  
14.         return (itemNum == arraySize);  
15.     \}  
16.   
17.     public boolean isEmpty() \{  
18.         return (itemNum == 0);  
19.     \}  
20.   
21.     public void displayTable() \{  
22.         System.out.print("Table:");  
23.         for (int j = 0; j **<** **arraySize**; j++) \{  
24.             if (hashArray\[j\] != null) \{  
25.                 System.out.print(hashArray\[j\].getKey() + " ");  
26.             \} else \{  
27.                 System.out.print("\*\* ");  
28.             \}  
29.         \}  
30.         System.out.println("");  
31.     \}  
32.   
33.     public int hashFunction(int key) \{  
34.         return key % arraySize; // hash function  
35.     \}  
36.   
37.     public void insert(DataItem item) \{  
38.         if (isFull()) \{  
39.             // 扩展哈希表  
40.             System.out.println("哈希表已满，重新哈希化..");  
41.             extendHashTable();  
42.         \}  
43.         int key = item.getKey();  
44.         int hashVal = hashFunction(key);  
45.         while (hashArray\[hashVal\] != null && hashArray\[hashVal\].getKey() != -1) \{  
46.             ++hashVal;  
47.             hashVal %= arraySize;  
48.         \}  
49.         hashArray\[hashVal\] = item;  
50.         itemNum++;  
51.     \}  
52.   
53.     /\*  
54.      \* 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。  
55.      \* 但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上，因此不能直接拷贝，需要按顺序遍历老数组，  
56.      \* 并使用insert方法向新数组中插入每个数据项。这叫重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。  
57.      \*/  
58.     public void extendHashTable() \{ // 扩展哈希表  
59.         int num = arraySize;  
60.         itemNum = 0; // 重新记数，因为下面要把原来的数据转移到新的扩张的数组中  
61.         arraySize \*= 2; // 数组大小翻倍  
62.         DataItem\[\] oldHashArray = hashArray;  
63.         hashArray = new DataItem\[arraySize\];  
64.         for (int i = 0; i **<** **num**; i++) \{  
65.             insert(oldHashArray\[i\]);  
66.         \}  
67.     \}  
68.   
69.     public DataItem delete(int key) \{  
70.         if (isEmpty()) \{  
71.             System.out.println("Hash table is empty!");  
72.             return null;  
73.         \}  
74.         int hashVal = hashFunction(key);  
75.         while (hashArray\[hashVal\] != null) \{  
76.             if (hashArray\[hashVal\].getKey() == key) \{  
77.                 DataItem temp = hashArray\[hashVal\];  
78.                 hashArray\[hashVal\] = nonItem; // nonItem表示空Item,其key为-1  
79.                 itemNum--;  
80.                 return temp;  
81.             \}  
82.             ++hashVal;  
83.             hashVal %= arraySize;  
84.         \}  
85.         return null;  
86.     \}  
87.   
88.     public DataItem find(int key) \{  
89.         int hashVal = hashFunction(key);  
90.         while (hashArray\[hashVal\] != null) \{  
91.             if (hashArray\[hashVal\].getKey() == key) \{  
92.                 return hashArray\[hashVal\];  
93.             \}  
94.             ++hashVal;  
95.             hashVal %= arraySize;  
96.         \}  
97.         return null;  
98.     \}  
99. \}  
100.   
101. class DataItem \{  
102.     private int iData;  
103.   
104.     public DataItem(int data) \{  
105.         iData = data;  
106.     \}  
107.   
108.     public int getKey() \{  
109.         return iData;  
110.     \}  
111. \}

线性探测有个弊端，即数据可能会发生聚集。一旦聚集形成，它会变得越来越大，那些哈希化后落在聚集范围内的数据项，都要一步步的移动，并且插在聚集的最后，因此使聚集变得更大。聚集越大，它增长的也越快。这就导致了哈希表的某个部分包含大量的聚集，而另一部分很稀疏。

为了解决这个问题，我们可以使用二次探测：二次探测是防止聚集产生的一种方式，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。线性探测中，如果哈希函数计算的原始下标是x, 线性探测就是x+1, x+2, x+3, 以此类推；而在二次探测中，探测的过程是x+1, x+4, x+9, x+16，以此类推，到原始位置的距离是步数的平方。二次探测虽然消除了原始的聚集问题，但是产生了另一种更细的聚集问题，叫二次聚集：比如讲184，302，420和544依次插入表中，它们的映射都是7，那么302需要以1为步长探测，420需要以4为步长探测， 544需要以9为步长探测。只要有一项其关键字映射到7，就需要更长步长的探测，这个现象叫做二次聚集。二次聚集不是一个严重的问题，但是二次探测不会经常使用，因为还有好的解决方法，比如再哈希法。

## 再哈希法    ##

为了消除原始聚集和二次聚集，现在需要的一种方法是产生一种依赖关键字的探测序列，而不是每个关键字都一样。即：不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。再哈希法就是把关键字用不同的哈希函数再做一遍哈希化，用这个结果作为步长，对于指定的关键字，步长在整个探测中是不变的，不同关键字使用不同的步长、经验说明，第二个哈希函数必须具备如下特点：

1. 和第一个哈希函数不同；

2. 不能输出0（否则没有步长，每次探索都是原地踏步，[算法][Link 1]将进入死循环）。

专家们已经发现下面形式的哈希函数工作的非常好：stepSize = constant - key % constant; 其中constant是质数，且小于数组容量。

再哈希法要求表的容量是一个质数，假如表长度为15(0-14)，非质数，有一个特定关键字映射到0，步长为5，则探测序列是0,5,10,0,5,10,以此类推一直循环下去。[算法][Link 2]只尝试这三个单元，所以不可能找到某些空白单元，最终算法导致崩溃。如果数组容量为13, 质数，探测序列最终会访问所有单元。即0,5,10,2,7,12,4,9,1,6,11,3,一直下去，只要表中有一个空位，就可以探测到它。下面看看再哈希法的代码：

**\[html\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  public class HashTableDouble \{  
2.      private DataItem\[\] hashArray;  
3.      private int arraySize;  
4.      private int itemNum;  
5.      private DataItem nonItem;  
6.    
7.      public HashTableDouble() \{  
8.          arraySize = 13;  
9.          hashArray = new DataItem\[arraySize\];  
10.         nonItem = new DataItem(-1);  
11.     \}  
12.   
13.     public void displayTable() \{  
14.         System.out.print("Table:");  
15.         for (int i = 0; i **<** **arraySize**; i++) \{  
16.             if (hashArray\[i\] != null) \{  
17.                 System.out.print(hashArray\[i\].getKey() + " ");  
18.             \} else \{  
19.                 System.out.print("\*\* ");  
20.             \}  
21.         \}  
22.         System.out.println("");  
23.     \}  
24.   
25.     public int hashFunction1(int key) \{ // first hash function  
26.         return key % arraySize;  
27.     \}  
28.   
29.     public int hashFunction2(int key) \{ // second hash function  
30.         return 5 - key % 5;  
31.     \}  
32.   
33.     public boolean isFull() \{  
34.         return (itemNum == arraySize);  
35.     \}  
36.   
37.     public boolean isEmpty() \{  
38.         return (itemNum == 0);  
39.     \}  
40.   
41.     public void insert(DataItem item) \{  
42.         if (isFull()) \{  
43.             System.out.println("哈希表已满，重新哈希化..");  
44.             extendHashTable();  
45.         \}  
46.         int key = item.getKey();  
47.         int hashVal = hashFunction1(key);  
48.         int stepSize = hashFunction2(key); // 用hashFunction2计算探测步数  
49.         while (hashArray\[hashVal\] != null && hashArray\[hashVal\].getKey() != -1) \{  
50.             hashVal += stepSize;  
51.             hashVal %= arraySize; // 以指定的步数向后探测  
52.         \}  
53.         hashArray\[hashVal\] = item;  
54.         itemNum++;  
55.     \}  
56.   
57.     public void extendHashTable() \{  
58.         int num = arraySize;  
59.         itemNum = 0; // 重新记数，因为下面要把原来的数据转移到新的扩张的数组中  
60.         arraySize \*= 2; // 数组大小翻倍  
61.         DataItem\[\] oldHashArray = hashArray;  
62.         hashArray = new DataItem\[arraySize\];  
63.         for (int i = 0; i **<** **num**; i++) \{  
64.             insert(oldHashArray\[i\]);  
65.         \}  
66.     \}  
67.   
68.     public DataItem delete(int key) \{  
69.         if (isEmpty()) \{  
70.             System.out.println("Hash table is empty!");  
71.             return null;  
72.         \}  
73.         int hashVal = hashFunction1(key);  
74.         int stepSize = hashFunction2(key);  
75.         while (hashArray\[hashVal\] != null) \{  
76.             if (hashArray\[hashVal\].getKey() == key) \{  
77.                 DataItem temp = hashArray\[hashVal\];  
78.                 hashArray\[hashVal\] = nonItem;  
79.                 itemNum--;  
80.                 return temp;  
81.             \}  
82.             hashVal += stepSize;  
83.             hashVal %= arraySize;  
84.         \}  
85.         return null;  
86.     \}  
87.   
88.     public DataItem find(int key) \{  
89.         int hashVal = hashFunction1(key);  
90.         int stepSize = hashFunction2(key);  
91.         while (hashArray\[hashVal\] != null) \{  
92.             if (hashArray\[hashVal\].getKey() == key) \{  
93.                 return hashArray\[hashVal\];  
94.             \}  
95.             hashVal += stepSize;  
96.             hashVal %= arraySize;  
97.         \}  
98.         return null;  
99.     \}  
100. \}  
101.   
102. class DataItem \{  
103.     private int iData;  
104.   
105.     public DataItem(int data) \{  
106.         iData = data;  
107.     \}  
108.   
109.     public int getKey() \{  
110.         return iData;  
111.     \}  
112. \}

# **2.链地址法**    #

在开放地址法中，通过再哈希法寻找一个空位解决冲突问题，另一个方法是在哈希表每个单元中设置链表（即链地址法），某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加到链表中，不需要在原始的数组中寻找空位。下面看看链地址法的代码：

**\[html\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  public class HashTableDouble \{  
2.      private SortedList\[\] hashArray; // 数组中存放链表  
3.      private int arraySize;  
4.    
5.      public HashTableDouble(int size) \{  
6.          arraySize = size;  
7.          hashArray = new SortedList\[arraySize\];  
8.          // new出每个空链表初始化数组  
9.          for (int i = 0; i **<** **arraySize**; i++) \{  
10.             hashArray\[i\] = new SortedList();  
11.         \}  
12.     \}  
13.   
14.     public void displayTable() \{  
15.         for (int i = 0; i **<** **arraySize**; i++) \{  
16.             System.out.print(i + ": ");  
17.             hashArray\[i\].displayList();  
18.         \}  
19.     \}  
20.   
21.     public int hashFunction(int key) \{  
22.         return key % arraySize;  
23.     \}  
24.   
25.     public void insert(LinkNode node) \{  
26.         int key = node.getKey();  
27.         int hashVal = hashFunction(key);  
28.         hashArray\[hashVal\].insert(node); // 直接往链表中添加即可  
29.     \}  
30.   
31.     public LinkNode delete(int key) \{  
32.         int hashVal = hashFunction(key);  
33.         LinkNode temp = find(key);  
34.         hashArray\[hashVal\].delete(key);// 从链表中找到要删除的数据项，直接删除  
35.         return temp;  
36.     \}  
37.   
38.     public LinkNode find(int key) \{  
39.         int hashVal = hashFunction(key);  
40.         LinkNode node = hashArray\[hashVal\].find(key);  
41.         return node;  
42.     \}  
43. \}

这里用的链表是有序链表LinkNode

**\[html\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  public class SortedList \{  
2.      private LinkNode first;    
3.      public SortedList() \{    
4.          first = null;    
5.      \}    
6.      public boolean isEmpty() \{    
7.          return (first == null);    
8.      \}    
9.      public void insert(LinkNode node) \{    
10.         int key = node.getKey();    
11.         LinkNode previous = null;    
12.         LinkNode current = first;    
13.         while(current != null && current.getKey() **<** **key**) \{    
14.             previous = current;    
15.             current = current.next;    
16.         \}    
17.         if(previous == null) \{    
18.             first = node;    
19.         \}    
20.         else \{    
21.             node.next = current;    
22.             previous.next = node;    
23.         \}    
24.     \}    
25.     public void delete(int key) \{    
26.         LinkNode previous = null;    
27.         LinkNode current = first;    
28.         if(isEmpty()) \{    
29.             System.out.println("chain is empty!");    
30.             return;    
31.         \}    
32.         while(current != null && current.getKey() != key) \{    
33.             previous = current;    
34.             current = current.next;    
35.         \}    
36.         if(previous == null) \{    
37.             first = first.next;    
38.         \}    
39.         else \{    
40.             previous.next = current.next;    
41.         \}    
42.     \}    
43.     public LinkNode find(int key) \{    
44.         LinkNode current = first;    
45.         while(current != null && current.getKey() **<**= key) \{    
46.             if(current.getKey() == key) \{    
47.                 return current;    
48.             \}    
49.             current = current.next;    
50.         \}    
51.         return null;    
52.     \}    
53.     public void displayList() \{    
54.         System.out.print("List(First-**>**Last):");    
55.         LinkNode current = first;    
56.         while(current != null) \{    
57.             current.displayLink();    
58.             current = current.next;    
59.         \}    
60.         System.out.println("");    
61.     \}    
62. \}    
63. class LinkNode \{    
64.     private int iData;    
65.     public LinkNode next;    
66.     public LinkNode(int data) \{    
67.         iData = data;    
68.     \}    
69.     public int getKey() \{    
70.         return iData;    
71.     \}    
72.     public void displayLink() \{    
73.         System.out.print(iData + " ");    
74.     \}    
75. \}

在没有冲突的情况下，哈希表中执行插入和删除操作可以达到O(1)的时间级。

[Link 1]: http://lib.csdn.net/base/31
[view plain]: http://blog.csdn.net/xiangzhihong8/article/details/51598299#
[Link 2]: http://lib.csdn.net/base/datastructure