在前几章的学习中，我们已经了解了数组和链表的基本特性，不管是数组还是链表，如果我们想要寻找一个特定的数值，时间复杂度都为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;
以上就是哈希表的定义啦，可见哈希表的插入删除很快，可是当数组快满，要进行数据迁移的话，性能下降得非常严重，所以设计数组长度时，必须知道将要储存多少数据，才能设计出一个合理有效的哈希表。
Leetcode题目 References This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.
