哈希表的概念

在前几章的学习中,我们已经了解了数组和链表的基本特性,不管是数组还是链表,如果我们想要寻找一个特定的数值,时间复杂度都为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