哈希表的概念
在前几章的学习中，我们已经了解了数组和链表的基本特性，不管是数组还是链表，如果我们想要寻找一个特定的数值，时间复杂度都为O(n)。那有什么办法用最快的速度来找到一个特定的元素呢，今天我们就来学习工业界中常用的数据结构“哈希表”，在哈希表中，不管是寻找、删除、增加一个新元素，时间复杂度都是O(1)。
哈希表以键值的方式来存储元素，也就是说每个数据都是以键值（key，value）的方式存储的，关键字（key）是不可重复的，而值是对应于键的。我们可以把哈希表简单理解为一本字典，每个键（key）是一个单词，而每个单词都有自己对应的解释，也就是值（value）。
哈希表的实现方式
那我们需要用什么数据结构实现哈希表呢？我们知道数组的特点是寻址容易，插入和删除数组困难。而链表的特点是寻址困难，插入和删除数据容易。那么我们能不能综合两者的特性，创建一种寻址容易，插入删除也容易的数据结构呢？是的，哈希表就使用这么一种聪明的实现方式：“拉链法”，可以简单理解为“一堆由链表组成的数组”，如图所示：
可以看到哈希表的左侧是数组，数组的每个成员包括一个指针，指向一个链表的头节点，当然链表可能为空，也可能链接多个节点。
我们存储键值对（key-value pair）的方式主要依靠键的特征，通过键的哈希值找到对应的数组下标，然后将其键值对添加到对应的链表中，寻找元素时，也是根据其键的哈希值，找到特定链表其对应的值。
那我们如何得到所谓的哈希值呢？我们先简单理解一下此过程：哈希表使用哈希函数（Hash Function）将键（key）转换成一个哈希值（整形数字），然后将该数组对数组长度取余，取余得到的数字就当做数组的下标，然后将其键值对添加到对应的链表中。寻找一个键所对应的值时，我们也是使用哈希函数将键转换为对应的数组下标，并在其链表中定位到该关键字所对应的数值。
哈希函数（Hash Function）
可见哈希表能快速添加和查找元素的核心原因就是哈希函数，哈希函数能快速将一个数值转换成哈希值（整数）。所以哈希表必须保持哈希值的计算一致，如果两个哈希值是不相同的，那么这两个哈希值的原始输入也是不相同的。
那如果两个不同的输入得到相同的哈希值呢？这也就是所谓的哈希值冲突，这也是为什么我们结合数组和链表来实现哈希表，如果一个关键字对应的数组下标已经有其他元素了，只需要在其对应的链表后创建一个新的节点即可。
简单来说，我们输入关键字x，使用哈希函数f(x)计算出哈希值y，然后使用哈希值y来找特定的数组下标，并在对应位置插入新数据。在之后的实现中，我们会使用Java来实现哈希表，而JVM自动生成哈希值，我们只需要再将其哈希值和我们的哈希表数组长度取模（mod）就能拿到其对应下标。
哈希表支持的操作
为了帮助大家更好地理解哈希表的原理，我们来详细描述一对键值被插入的过程，首先我们将键值对以链表节点的方式储存，其节点包含自己的键和值。如果我们要将一对键值存入哈希表，我们需要使用哈希函数计算键的哈希值，并与哈希表的长度取模，然后找到对应的数组下标，如果该位置没有其他键值节点，直接将其位置指向新节点即可。如果对应的位置有其他节点，直接将其新节点加到链表的最后面即可。
如果我们要查找一个键所对应的值，我们只需要计算该键对应的哈希值，找到数组下标所对应的头节点后，从头节点开始寻找我们所要的键值对。
以下哈希表支持的操作：
- get(K key)：通过特定的关键字拿到其所对应的值
- add(Key key, Value value)：将一对新的键值对加入哈希表
- remove(Key key)：通过关键字，删除哈希表中的键值对
- getSize()：当前键值对的数量
- isEmpty()：查看哈希表是否为空
Java实现
下面我们就来使用Java实现哈希表，在我们定义的键值对中，关键字为字符串类型，数值为整数类型，以下是哈希表和哈希表节点的定义：
import java.util.ArrayList;
public class HashMap {
static class HashNode<String, Integer> {
String key;
Integer value;
HashNode<String, Integer> next;
public HashNode(String key, Integer value) {
this.key = key;
this.value = value;
}
}
private ArrayList<HashNode<String, Integer>> bucketArray;
private int numBuckets;
private int size;
public HashMap() {
bucketArray = new ArrayList<>();
numBuckets = 10;
size = 0;
for(int i = 0; i < numBuckets; i++) {
bucketArray.add(null);
}
}
}HashNode就是键值对节点的定义，其中key就是关键字，而value是关键字对应的数值，还包含了next指向下一个节点。HashMap则是哈希表的定义，其中包含了数据类型为ArrayList的bucketArray，大家可以将其理解为哈希表图示左侧的Array，bucketArray中存储由HashNode组成的链表。HashMap还记录了numBuckets代表哈希表数组的长度（不是节点的数量），size代表当前bucket的数量。在哈希表初始化时，我们初始化bucketArray，然后给numBuckets设置一个初始值10，初始化size，并在每个bucketArray上加上一个空的头节点。
以下是getBucketIndex的定义：
private int getBucketIndex(String key) {
int hashCode = key.hashCode();
int index = hashCode % numBuckets;
return index;
}getBucketIndex的输入是一个关键字，输出是关键字对应的bucket位置。我们只需要通过Java内置的hashCode函数，将关键字转化成整数形式的hashCode，然后将hashCode和numBuckets取模，就能得到对应bucket的指数。以下是add的定义：
public void add(String key, Integer value) {
int bucketIndex = getBucketIndex(key);
HashNode<String, Integer> head = bucketArray.get(bucketIndex);
while (head != null) {
if (head.key.equals(key)) {
head.value = value;
return;
}
head = head.next;
}
size++;
head = bucketArray.get(bucketIndex);
HashNode<String, Integer> newNode = new HashNode<String, Integer>(key, value);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);
if ((1.0 * size) / numBuckets >= 0.7) {
ArrayList<HashNode<String, Integer>> temp = bucketArray;
bucketArray = new ArrayList<>();
numBuckets = 2 * numBuckets;
size = 0;
for (int i = 0; i < numBuckets; i++) {
bucketArray.add(null);
}
for (HashNode<String, Integer> headNode : temp) {
while(headNode != null) {
add(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}在add方法中，我们使用getBucketIndex拿到关键字对应的bucket指数，并从对应bucket的头节点开始，寻找是否有与其关键词对应的节点，如果找到其节点，更新节点的数据，然后返回。如果没有找到，我们创建一个新的键值对节点，然后将其next指针指向对应bukcet的头节点，再把新节点更新为对应bucket的头节点。如果当前键值对数量超过了bucket容量的70%，那么我们可以创建一个长度为当前数量两倍的bucketArray，并把当前的节点转移到新的bucketArray上。
get函数是通过关键字找到对应数组的函数：
public Integer get(String key) {
int bucketIndex = getBucketIndex(key);
HashNode<String, Integer> head = bucketArray.get(bucketIndex);
while (head != null) {
if (head.key.equals(key)) {
return head.value;
}
head = head.next;
}
return null;
}在此函数中，我们通过getBucketIndex拿到关键字对应的bucket指数，并拿到head头指针，然后顺着对应链表往下走，寻找是否有对应的关键字的节点，如果找到了，返回对应的数值，否则返回null。
public Integer remove(String key) {
int bucketIndex = getBucketIndex(key);
HashNode<String, Integer> head = bucketArray.get(bucketIndex);
HashNode<String, Integer> prev = null;
while (head != null) {
if (head.key.equals(key))
break;
prev = head;
head = head.next;
}
if (head == null) {
return null;
}
size--;
if (prev != null) {
prev.next = head.next;
} else {
bucketArray.set(bucketIndex, head.next);
}
return head.value;
}在remove函数中，我们通过getBucketIndex拿到对应的bucket指数，然后拿到头指针，通过迭代next指针，我们可以使用删除链表节点的方式来删除对应节点。最后是两个简单函数size和isEmpty的定义：
public int size() {
return size;
}
public boolean isEmpty() {
return size() == 0;
}以上就是哈希表的定义啦，可见哈希表的插入删除很快，可是当数组快满，要进行数据迁移的话，性能下降得非常严重，所以设计数组长度时，必须知道将要储存多少数据，才能设计出一个合理有效的哈希表。