读完这篇，希望你能真正理解什么是哈希表

阅读本文大概需要6分钟

我所写的这些数据结构，都是比较经典的，也是面试中经常会出现的，这篇文章我就不闲扯了，全是干货，如果你能读完，希望对你有所帮助~ 

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

arrayIndex=hugeNumber%arraySize

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

1.开放地址法

1.1 线性探测法

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

1. public class HashTable {

2.    private DataItem[] hashArray; //DateItem类是数据项，封装数据信息

3.    private int arraySize;

4.    private int itemNum; //数组中目前存储了多少项

5.    private DataItem nonItem; //用于删除项的

6.    public HashTable() {

7.        arraySize = 13;

8.        hashArray = new DataItem[arraySize];

9.        nonItem = new DataItem(-1); //deleted item key is -1

10.    }

11.    public boolean isFull() {

12.        return (itemNum == arraySize);

13.    }

14.    public boolean isEmpty() {

15.        return (itemNum == 0);

16.    }

17.    public void displayTable() {

18.        System.out.print("Table:");

19.        for(int j = 0; j < arraySize; j++) {

20.            if(hashArray[j] != null) {

21.                System.out.print(hashArray[j].getKey() + " ");

22.            }

23.            else {

24.                System.out.print("** ");

25.            }

26.        }

27.        System.out.println("");

28.    }

29.    public int hashFunction(int key) {

30.        return key % arraySize;     //hash function

31.    }

32.    public void insert(DataItem item) {

33.        if(isFull()) {          

34.            //扩展哈希表

35.            System.out.println("哈希表已满，重新哈希化..");

36.            extendHashTable();

37.        }

38.        int key = item.getKey();

39.        int hashVal = hashFunction(key);

40.        while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {

41.            ++hashVal;

42.            hashVal %= arraySize;

43.        }

44.        hashArray[hashVal] = item;

45.        itemNum++;

46.    }

47.    /*

48.     * 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上，因此不能直接拷贝，需要按顺序遍历老数组，并使用insert方法向新数组中插入每个数据项。这叫重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。

49.     */

50.    public void extendHashTable() { //扩展哈希表

51.        int num = arraySize;

52.        itemNum = 0; //重新记数，因为下面要把原来的数据转移到新的扩张的数组中

53.        arraySize *= 2; //数组大小翻倍

54.        DataItem[] oldHashArray = hashArray;

55.        hashArray = new DataItem[arraySize];

56.        for(int i = 0; i < num; i++) {

57.            insert(oldHashArray[i]);

58.        }

59.    }

60.    public DataItem delete(int key) {

61.        if(isEmpty()) {

62.            System.out.println("Hash table is empty!");

63.            return null;

64.        }

65.        int hashVal = hashFunction(key);

66.        while(hashArray[hashVal] != null) {

67.            if(hashArray[hashVal].getKey() == key) {

68.                DataItem temp = hashArray[hashVal];

69.                hashArray[hashVal] = nonItem; //nonItem表示空Item,其key为-1

70.                itemNum--;

71.                return temp;

72.            }

73.            ++hashVal;

74.            hashVal %= arraySize;

75.        }

76.        return null;

77.    }

78.    public DataItem find(int key) {

79.        int hashVal = hashFunction(key);

80.        while(hashArray[hashVal] != null) {

81.            if(hashArray[hashVal].getKey() == key) {

82.                return hashArray[hashVal];

83.            }

84.            ++hashVal;

85.            hashVal %= arraySize;

86.        }

87.        return null;

88.    }

89. }

90. class DataItem {

91.    private int iData;

92.    public DataItem (int data) {

93.        iData = data;

94.    }

95.    public int getKey() {

96.        return iData;

97.    }

98. }

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

为了解决这个问题，我们可以使用二次探测：二次探测是防止聚集产生的一种方式，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。线性探测中，如果哈希函数计算的原始下标是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（否则没有步长，每次探索都是原地踏步，算法将进入死循环）。

专家们已经发现下面形式的哈希函数工作的非常好：

stepSize=constant-key%constant

 其中 constant 是质数，且小于数组容量。

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

1. public class HashDouble {

2.    private DataItem[] hashArray;

3.    private int arraySize;

4.    private int itemNum;

5.    private DataItem nonItem;

6.    public HashDouble() {

7.        arraySize = 13;

8.        hashArray = new DataItem[arraySize];

9.        nonItem = new DataItem(-1);

10.    }

11.    public void displayTable() {

12.        System.out.print("Table:");

13.        for(int i = 0; i < arraySize; i++) {

14.            if(hashArray[i] != null) {

15.                System.out.print(hashArray[i].getKey() + " ");

16.            }

17.            else {

18.                System.out.print("** ");

19.            }

20.        }

21.        System.out.println("");

22.    }

23.    public int hashFunction1(int key) { //first hash function

24.        return key % arraySize;

25.    }

26.    public int hashFunction2(int key) { //second hash function

27.        return 5 - key % 5;

28.    }

29.    public boolean isFull() {

30.        return (itemNum == arraySize);

31.    }

32.    public boolean isEmpty() {

33.        return (itemNum == 0);

34.    }

35.    public void insert(DataItem item) {

36.        if(isFull()) {

37.            System.out.println("哈希表已满，重新哈希化..");

38.            extendHashTable();

39.        }

40.        int key = item.getKey();

41.        int hashVal = hashFunction1(key);

42.        int stepSize = hashFunction2(key); //用hashFunction2计算探测步数

43.        while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {

44.            hashVal += stepSize;

45.            hashVal %= arraySize; //以指定的步数向后探测

46.        }

47.        hashArray[hashVal] = item;

48.        itemNum++;

49.    }

50.    public void extendHashTable() {

51.        int num = arraySize;

52.        itemNum = 0; //重新记数，因为下面要把原来的数据转移到新的扩张的数组中

53.        arraySize *= 2; //数组大小翻倍

54.        DataItem[] oldHashArray = hashArray;

55.        hashArray = new DataItem[arraySize];

56.        for(int i = 0; i < num; i++) {

57.            insert(oldHashArray[i]);

58.        }

59.    }

60.    public DataItem delete(int key) {

61.        if(isEmpty()) {

62.            System.out.println("Hash table is empty!");

63.            return null;

64.        }

65.        int hashVal = hashFunction1(key);

66.        int stepSize = hashFunction2(key);

67.        while(hashArray[hashVal] != null) {

68.            if(hashArray[hashVal].getKey() == key) {

69.                DataItem temp = hashArray[hashVal];

70.                hashArray[hashVal] = nonItem;

71.                itemNum--;

72.                return temp;

73.            }

74. hashVal += stepSize;

75.            hashVal %= arraySize;

76.        }

77.        return null;

78.    }

79.    public DataItem find(int key) {

80.        int hashVal = hashFunction1(key);

81.        int stepSize = hashFunction2(key);

82.        while(hashArray[hashVal] != null) {

83.            if(hashArray[hashVal].getKey() == key) {

84.                return hashArray[hashVal];

85.            }

86.            hashVal += stepSize;

87.            hashVal %= arraySize;

88.        }

89.        return null;

90.    }

91. }

2. 链地址法

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

1. public class HashChain {

2.    private SortedList[] hashArray; //数组中存放链表

3.    private int arraySize;

4.    public HashChain(int size) {

5.        arraySize = size;

6.        hashArray = new SortedList[arraySize];

7.        //new出每个空链表初始化数组

8.        for(int i = 0; i < arraySize; i++) {

9.            hashArray[i] = new SortedList();

10.        }

11.    }

12.    public void displayTable() {

13.        for(int i = 0; i < arraySize; i++) {

14.            System.out.print(i + ": ");

15.            hashArray[i].displayList();

16.        }

17.    }

18.    public int hashFunction(int key) {

19.        return key % arraySize;

20.    }

21.    public void insert(LinkNode node) {

22.        int key = node.getKey();

23.        int hashVal = hashFunction(key);

24.        hashArray[hashVal].insert(node); //直接往链表中添加即可

25.    }

26.    public LinkNode delete(int key) {

27.        int hashVal = hashFunction(key);

28.        LinkNode temp = find(key);

29.        hashArray[hashVal].delete(key);//从链表中找到要删除的数据项，直接删除

30.        return temp;

31.    }

32.    public LinkNode find(int key) {

33.        int hashVal = hashFunction(key);

34.        LinkNode node = hashArray[hashVal].find(key);

35.        return node;

36.    }

37. }

下面是链表类的代码，用的是有序链表：

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)的时间级，这是相当快的，如果发生冲突了，存取时间就依赖后来的长度，查找或删除时也得挨个判断，但是最差也就O(N)级别。

哈希表就分享这么多，本文建议收藏，在等班车的时候、吃饭排队的时候可以拿出来看看。利用碎片化时间来学习！

END

人之所以能，是相信能！这世上没有天才，你若对得起时间，时间便对得起你。关注我们，每天进步一点点~

↓↓↓

更多相关阅读：