数据结构之哈希表

作者: 端碗吹水 | 来源:发表于2021-01-20 23:30 被阅读0次

哈希表基础

哈希表的英文叫“Hash Table”，我们平时也叫它“散列表”或者“Hash 表”，是一种常用的数据结构。Java中的HashMap、HashTable就是基于哈希表实现的。

为了学习哈希表，我们先从LeetCode上一个的问题开始：

https://leetcode-cn.com/problems/first-unique-character-in-a-string/

这是LeetCode上的第387号问题：字符串中的第一个唯一字符。需求是：给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。案例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

这道题相对来说比较简单，解题思路也比较多。这里给出的一种思路就是声明一个长度为26的整型数组，该数组的索引 0 ~ 1 就对应着字母 a ~ z。首先，遍历目标字符串，通过计算 char - 'a' 得到字符所对应的数组索引，并将该索引的元素进行+1，这样就实现了对出现的字符进行计数。最后，再遍历一次目标字符串，同样计算 char - 'a' 得到对应的数组索引，并判断该索引位置的数值是否为1，为1就代表已经找到第一个不重复的字符所在的索引了。

具体的实现代码如下：

public int firstUniqChar(String s) {
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) {
        freq[s.charAt(i) - 'a']++;
    }

    for (int i = 0; i < s.length(); i++) {
        if (freq[s.charAt(i) - 'a'] == 1) {
            return i;
        }
    }

    return -1;
}

实际上这就是一种典型的哈希表思想，因为其中的 int[26] freq 就是一个哈希表。通过这个数组，我们建立了每个字符和一个数字之间的映射关系。

而 s.charAt(i) - 'a' 则是一个哈希函数，所谓哈希函数就是可以基于某种规则对数据进行计算得到数据所映射的位置。在我们这个例子中，“数据”指的是字符串中的字符，“位置”则指的是数组中的索引。

通过这个简单的计算我们就能得到字符所对应的数组索引，进而得到字符所出现的次数，看得出来这个操作的时间复杂度是 $O(1)$ 。因此，访问哈希表的时间复杂度也就是 $O(1)$ 。

哈希表用的是数组支持按照下标随机访问数据的特性，实现高效的数据操作。所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有哈希表。

稍微总结一下哈希表就是：一种基于数组实现的线性结构，通过哈希函数来实现寻址，能够建立一种“数据”与“位置”的映射关系。利用的是数组支持按照下标随机访问元素的特性，通常情况下查询操作具有 $O(1)$ 的时间复杂度。

哈希函数的设计

从上一小节的例子我们可以看到，哈希函数在哈希表中起着非常关键的作用。在该例子中，哈希函数就是一个简单的运算，比较简单，也比较容易想到。

但是如果要设计一个“工业级”的哈希函数还是比较难的，对于一个通用的数据结构，我们需要考虑不同的数据类型：字符串、浮点数、日期等以及不同的数据格式：身份证号、单词、车牌号等，对于这种不同的情况如何得到能用于哈希计算的依据。所以对于一些特殊领域，有特殊领域的哈希函数设计方式，甚至还有专门的论文。

除此之外，我们还要设计哈希函数的计算规则，如何使数据能在数组中均匀的分布。然后还得思考如何解决哈希冲突，因为要想找到一个不同的 key 对应的哈希值都不一样的哈希函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种哈希冲突。而且，因为数组的存储空间有限，也会加大哈希冲突的概率。

这里总结下几点哈希函数设计的基本要求：

哈希函数计算得到的哈希值是一个非负整数
高效性：计算高效简便
均匀性：哈希值均匀分布
一致性：
- 如果 $key1 = key2$ ，那 $hash(key1) == hash(key2)$
- 如果 $key1 ≠ key2$ ，那 $hash(key1) ≠ hash(key2)$

对于 “如果 $key1 ≠ key2$ ，那 $hash(key1) ≠ hash(key2)$ ” 只是逻辑上的体现，因为我们之前也说了，在真实情况下几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，所以针对散列冲突问题，我们需要通过其他途径来解决。

取模在哈希函数中的应用

这里介绍一种简单的哈希函数设计思路，那就是取模。对一个合适的数进行取模能得到一个小范围的整数，即便得到负整数也能通过简单的偏移规则转换成正整数。但你可能会有疑问了，数据类型有各种各样，都能进行取模吗？应该对什么样的数进行取模？

对于第一个问题，其实对于各种各样的数据类型，我们都可以将其转换为相应的整数。对于第二个问题，一般需要视情况而定。小整数对什么数取模差别不大，甚至都不需要取模，直接每个数字对应一个索引。如同上一小节中的例子，每个单词对应一个数组索引就可以了。

而对于大整型，例如身份证号、手机号等，这种无法直接对应索引的就需要进行取模了，一个简单的解决办法就是模一个素数。至于为什么是素数，这是一个数学上的问题，超出了本文的讨论范围，有兴趣的可以自行了解一下。下面这个网站列出了不同规模的整数用于取模的最佳素数：

https://planetmath.org/goodhashtableprimes

同样的，浮点型也可以转换成整型进行取模，因为在计算机中都是32位或者64位的二进制表示，只不过计算机解析成了浮点数，所以转成整型处理即可。

字符串类型则相对来说稍微复杂点，但同样也是转成整型，只是套路不太一样。对于数字内容的字符串，例如 166 ，我们可以将其每个字符想象成十进制的表示法，通过如下方式转换成整数：

166 = 1 * 10^2 + 6 * 10^1 + 6 * 10^0

这个计算很简单，因为 char 类型是可运算的，将每一个字符乘以进制数的 n 次方再加起来就可以了，这里的 n 取值是该字符后面的字符数量。例如，1 这个字符它后面还有两个字符，那么这个 n 就是 2 ，然后因为是 10 进制表示，所以其进制数是 10，也就得出了 1 * 10^2，其他字符以此类推，最后再进行相加就能将该字符串转换成整数了。

同理，字符串内容为单词的计算方式也是一样，只不过进制数需要改变一下，我们可以将字母看成是26进制的。如下示例：

code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0

这个进制数根据字符串内容不同是不固定的，例如要包含大写字母，可能进制数就需要设置为52，要包含标点符号、特殊符号等还需要将这个值设置得再大一些。总结成公式大概就是这样：

code = c * B^3 + o * B^2 + d * B^1 + e * B^0

因此，哈希函数的表示如下：

hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M

这个计算方式还有优化的空间，只需要简单的变换一下就能节省一些计算。如下所示：

hash(code) = ((((c * B) + o) * B + d) * B + e) % M

但是这样的计算对于整型来说还会有溢出的问题，所以我们需要将取模计算放进去，最终得出的哈希函数如下：

hash(code) = ((((c % M) * B + o) % M * B + d) % M * B + e) % M

转换成代码的表达如下：

int hash = 0;
for(int i = 0; i < s.length(); i++) {
    hash = (hash * B + s.charAt(i)) % M
}

解决了字符串的取模问题，复合类型也就简单了，因为和字符串类似。我们可以通过类似于 toString 的方式将复合类型转换为字符串，然后再根据上述规则转换成整型后取模。例如，日期类型：

Date: year, month, day, hour
hash(date) = ((((date.year % M) * B + date.month) % M * B + date.day) % M * B + date.hour) % M

Java中的 hashCode 方法

我们知道在Java中，可以通过重写 hashCode 方法来提供一个对象的哈希值。并且基础数据类型的包装类如Integer、Double、String等都已经重写了 hashCode 方法，对于这些类型直接调用即可。

对于我们自己定义的类型来说，就需要自行重写 hashCode 方法了。而通常一个对象里的字段都由基础类型或其包装类组成，因此也可以利用这些类型已有的 hashCode 方法。如下示例：

public class Student {

    int grade;
    int cls;
    String firstName;
    String lastName;

    @Override
    public int hashCode() {
        // 哪些字段参与计算
        Object[] a = new Object[]{grade, cls, firstName, lastName};

        // 按照实际情况取合适的进制数，这里是仿照jdk源码取的31
        int B = 31;
        int result = 1;
        for (Object element : a) {
            result = result * B + (element == null ? 0 : element.hashCode());
        }

        return result;
    }
}

重写了 hashCode 方法后，我们还需要重写 equals 方法。因为不同的两个对象有可能哈希值是相等的，这也就是哈希冲突。此时我们就需要进一步通过 equals 方法来比较两个对象的内容是否相等，以此来区别它们是不是同一个对象。由此，我们可以得出一个结论：hashCode 相等不一定是同一个对象，hashCode 和 equals 都相等的情况下才能认为是同一个对象，而 equals 相等时 hashCode 必然相等。

重写 equals 方法也是有套路的，而且现在大部分IDE都支持自动生成，这里就不过多解释了。代码如下：

@Override
public boolean equals(Object o) {
    if (this == o) {
        return true;
    }
    if (o == null || getClass() != o.getClass()) {
        return false;
    }
    
    Student student = (Student) o;
    return grade == student.grade &&
            cls == student.cls &&
            Objects.equals(firstName, student.firstName) &&
            Objects.equals(lastName, student.lastName);
}

链地址法 Separate Chaining

现在我们已经了解清楚了哈希函数的设计，以及在Java中如何取得一个对象的哈希值、如何比较两个对象是否相等。接下来我们就可以进一步看看如何解决哈希冲突的问题了，我们常用的哈希冲突解决方法有两类，开放寻址法（open addressing）和链地址法（separate chaining）也叫链表法或拉链法。

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。但这种方法并不常用，因为相对复杂且局限性大，一般用于小数据量的情况，Java中的 ThreadLocalMap 用的是这种方法。

而链表法则是一种更加常用的哈希冲突解决办法，相比开放寻址法，它要简单很多。Java中的 HashMap、HashTable 就是用的这种方法。我们来看这个图，在哈希表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有哈希值相同的元素我们都放到相同槽位对应的链表中：

image.png

当插入的时候，我们只需要通过哈希函数计算出对应的哈希槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 $O(1)$ 。当查找、删除一个元素时，我们同样通过哈希函数计算出对应的槽，然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢？

实际上，这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 $O(k)$ 。对于分布比较均匀的哈希函数来说，理论上讲， $k=n/m$ ，其中 n 表示哈希表中数据的个数，m 表示哈希表中“槽”的个数。

当哈希冲突比较大，链表达到一定长度时，我们可以将其转换成一棵树，例如红黑树，避免查询效率退化到 $O(n)$ 。这也是Java8为什么会在 HashMap 中引入红黑树的原因。

实现属于我们自己的哈希表

有了前面的铺垫后，我们对哈希表的几个核心要点有了一定的了解，现在我们就来实现属于我们自己的哈希表。具体代码如下：

package hash;

import java.util.TreeMap;

/**
 * 哈希表
 * 
 * @author 01
 * @date 2021-01-20
 **/
public class HashTable<K, V> {

    /**
     * 借助TreeMap数组作为实际的存储容器
     * 目的是不需要自己去实现红黑树了，只需要关注哈希表实现本身
     */
    private TreeMap<K, V>[] table;

    /**
     * 哈希表的大小
     */
    private int capacity;

    /**
     * 元素的个数
     */
    private int size;

    public HashTable(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.table = new TreeMap[capacity];
        // 初始化数组
        for (int i = 0; i < capacity; i++) {
            this.table[i] = new TreeMap<>();
        }
    }

    public HashTable() {
        // 默认使用一个素数作为初始大小
        this(97);
    }

    /**
     * 哈希函数，计算出key所对应的数组索引
     */
    private int hash(K key) {
        // 消除hashCode的符号，即转换成正整数，因为hashCode有可能是负数，然后对capacity取模
        return (key.hashCode() & Integer.MAX_VALUE) % capacity;
    }

    public int getSize() {
        return size;
    }

    /**
     * 添加元素
     */
    public void add(K key, V value) {
        TreeMap<K, V> node = table[hash(key)];
        if (node.containsKey(key)) {
            // key已存在，则更新
            node.put(key, value);
        }

        // 否则就是新增，维护下size
        node.put(key, value);
        size++;
    }

    /**
     * 删除元素
     */
    public V remove(K key) {
        TreeMap<K, V> node = table[hash(key)];
        V ret = null;
        if (node.containsKey(key)) {
            ret = node.remove(key);
            size--;
        }

        return ret;
    }

    /**
     * 更新元素
     */
    public void set(K key, V value) {
        TreeMap<K, V> node = table[hash(key)];
        if (!node.containsKey(key)) {
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        node.put(key, value);
    }

    /**
     * 判断key是否存在
     */
    public boolean containsKey(K key) {
        return table[hash(key)].containsKey(key);
    }

    /**
     * 根据key获取value
     */
    public V get(K key) {
        return table[hash(key)].get(key);
    }
}

哈希表的动态空间处理

上一小节中我们已经实现了一个基础的哈希表，为了简化实现使用了Java的 TreeMap 来作为装载数据的容器，省得自己去实现链表或红黑树了，让我们只需要关注哈希表的实现本身。但它依旧是个数组，我们也还得实现哈希函数计算出key所对应的数组索引，以及相应的增删查改方法。

正因为我们将 TreeMap 声明为一个数组，所以在初始化后，数组的长度就是固定的了。随着不断地添加数据，哈希表中的数据越来越密集，哈希冲突的概率就会越来越大，从而导致每个 TreeMap 里存储越来越多的数据，会使得哈希表的时间复杂度从 $O(1)$ 退化至 $O(logn)$ ，如果使用的是链表的话会退化至 $O(n)$ 。

为了解决这个问题，我们就要像实现动态数组那样，对哈希表实现动态扩容。扩容到合适的大小后可以减少哈希冲突的概率，将哈希表维持在一个较好的性能水平，这也是设计哈希表时非常关键的一个要素。

但是哈希表的动态扩容不像实现数组的动态扩容那么简单，数组动态扩容的条件只需要判断数组是否满了。而在哈希表中，初始化时就会填满数组，数组中存放的是一个个的 TreeMap ，这里的 TreeMap 可以想象为一颗树的根节点，我们添加的元素是挂到 TreeMap 里的。

所以我们的扩容条件就要变成：当数组中平均每个 TreeMap 承载的元素达到一定的程度时，就进行扩容。这个“程度”是一个具体的数值，通常称之为负载因子。即满足 元素个数 / 数组长度 >= 负载因子 时，我们就需要对哈希表进行扩容。同理，有扩容就有缩容，我们需要进行一个反向操作，当满足 元素个数 / 数组长度 < 负载因子 时，进行缩容。

基于这种方式，我们改造一下之前的哈希表，为其添加动态扩缩容功能。具体代码如下（仅贴出有改动的代码）：

public class HashTable<K, V> {

    ...

    /**
     * 负载因子
     */
    private static final double loadFactor = 0.75;

    /**
     * 初始容量
     */
    private static final int initCapacity = 16;

    ...

    public HashTable() {
        this(initCapacity);
    }

    ...

    /**
     * 添加元素
     */
    public void add(K key, V value) {
        TreeMap<K, V> node = table[hash(key)];
        if (node.containsKey(key)) {
            // key已存在，则更新
            node.put(key, value);
        }

        // 否则就是新增，维护下size
        node.put(key, value);
        size++;

        // 大于负载因子进行扩容
        if (size >= loadFactor * capacity) {
            // 每次扩容两倍
            resize(2 * capacity);
        }
    }

    /**
     * 删除元素
     */
    public V remove(K key) {
        TreeMap<K, V> node = table[hash(key)];
        V ret = null;
        if (node.containsKey(key)) {
            ret = node.remove(key);
            size--;

            // 小于负载因子进行缩容，并保证数组长度不小于initCapacity
            if (size < loadFactor * capacity && capacity / 2 >= initCapacity) {
                // 每次缩容两倍
                resize(capacity / 2);
            }
        }

        return ret;
    }

    /**
     * 动态扩缩容
     */
    private void resize(int newCapacity) {
        TreeMap<K, V>[] newTable = new TreeMap[newCapacity];
        for (int i = 0; i < newCapacity; i++) {
            newTable[i] = new TreeMap<>();
        }

        this.capacity = newCapacity;
        // 将原本数组中的数据迁移到新的数组中
        for (TreeMap<K, V> node : table) {
            // 为保证元素能够均匀分布在新的数组中，在迁移元素时，需要对元素重新进行哈希计算
            for (Map.Entry<K, V> entry : node.entrySet()) {
                newTable[hash(entry.getKey())]
                        .put(entry.getKey(), entry.getValue());
            }
        }
        this.table = newTable;
    }

    ...
}

哈希表更复杂的动态空间处理方法

在上一小节中，我们为哈希表添加了动态扩缩容的功能。你可能会有疑问，每次扩缩容都是原来的两倍，那么 capacity 不就无法保持是一个素数了吗？是的，如果只是简单的设置为两倍，就无法让 capacity 保持是一个素数，甚至不会是一个对取模友好的数。这会使得哈希函数的计算分布不均匀，增加哈希冲突的概率。

所以我们可以再对其做进一步的改造，在对象中声明一个素数表，当扩容到不同的规模时就从该素数表中取不同的素数作为新的数组长度。最终我们实现的哈希表代码如下：

package hash;

import java.util.Map;
import java.util.TreeMap;

/**
 * 哈希表
 *
 * @author 01
 * @date 2021-01-20
 **/
public class HashTable<K, V> {

    /**
     * 借助TreeMap数组作为实际的存储容器
     * 目的是不需要自己去实现红黑树了，只需要关注哈希表实现本身
     */
    private TreeMap<K, V>[] table;

    /**
     * 哈希表的大小
     */
    private int capacity;

    /**
     * 负载因子
     */
    private static final double loadFactor = 0.75;

    /**
     * 初始容量所对应的素数表索引
     */
    private int capacityIndex = 0;

    /**
     * 元素的个数
     */
    private int size;

    /**
     * 从 https://planetmath.org/goodhashtableprimes 网站
     * 中获取到的不同规模的整数用于取模的最佳素数，我们基于这里的素数
     * 作为扩缩容的大小，使得每次扩缩容可以将数组的长度保持始终是素数
     */
    private final int[] capacityArray = {
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
            6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
            402653189, 805306457, 1610612741
    };

    public HashTable() {
        this.capacity = capacityArray[capacityIndex];
        this.size = 0;
        this.table = new TreeMap[capacity];
        // 初始化数组
        for (int i = 0; i < capacity; i++) {
            this.table[i] = new TreeMap<>();
        }
    }

    /**
     * 哈希函数，计算出key所对应的数组索引
     */
    private int hash(K key) {
        // 消除hashCode的符号，即转换成正整数，因为hashCode有可能是负数，然后对 capacity 取模
        return (key.hashCode() & Integer.MAX_VALUE) % capacity;
    }

    public int getSize() {
        return size;
    }

    /**
     * 添加元素
     */
    public void add(K key, V value) {
        TreeMap<K, V> node = table[hash(key)];
        if (node.containsKey(key)) {
            // key已存在，则更新
            node.put(key, value);
        }

        // 否则就是新增，维护下size
        node.put(key, value);
        size++;

        // 大于负载因子进行扩容，并确保不会发生数组越界
        if (size >= loadFactor * capacity &&
                capacityIndex + 1 < capacityArray.length) {
            // 每次扩容的大小是下一个素数
            capacityIndex++;
            resize(capacityArray[capacityIndex]);
        }
    }

    /**
     * 删除元素
     */
    public V remove(K key) {
        TreeMap<K, V> node = table[hash(key)];
        V ret = null;
        if (node.containsKey(key)) {
            ret = node.remove(key);
            size--;

            // 小于负载因子进行缩容，并确保不会发生数组越界
            if (size < loadFactor * capacity && capacityIndex - 1 >= 0) {
                // 每次缩容的大小是上一个素数
                capacityIndex--;
                resize(capacityArray[capacityIndex]);
            }
        }

        return ret;
    }

    /**
     * 动态扩缩容
     */
    private void resize(int newCapacity) {
        TreeMap<K, V>[] newTable = new TreeMap[newCapacity];
        for (int i = 0; i < newCapacity; i++) {
            newTable[i] = new TreeMap<>();
        }

        this.capacity = newCapacity;
        // 将原本数组中的数据迁移到新的数组中
        for (TreeMap<K, V> node : table) {
            // 为保证元素能够均匀分布在新的数组中，在迁移元素时，需要对元素重新进行哈希计算
            for (Map.Entry<K, V> entry : node.entrySet()) {
                newTable[hash(entry.getKey())]
                        .put(entry.getKey(), entry.getValue());
            }
        }
        this.table = newTable;
    }

    /**
     * 更新元素
     */
    public void set(K key, V value) {
        TreeMap<K, V> node = table[hash(key)];
        if (!node.containsKey(key)) {
            throw new IllegalArgumentException(key + " doesn't exist!");
        }

        node.put(key, value);
    }

    /**
     * 判断key是否存在
     */
    public boolean containsKey(K key) {
        return table[hash(key)].containsKey(key);
    }

    /**
     * 根据key获取value
     */
    public V get(K key) {
        return table[hash(key)].get(key);
    }
}

完成了动态扩缩容功能后，我们可以简单分析下添加操作的时间复杂度。插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 $O(1)$ 。最坏情况下，哈希表负载达到负载因子，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 $O(n)$ 。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 $O(1)$ 。

最后

在学习了哈希表后，我们认识到哈希表是一个非常高效的数据结构，设计良好的哈希表各个操作的时间复杂度能达到 $O(1)$ 级别。但在编程领域，总是在空间换时间、时间换空间以及各种 trade-off。所以，一个数据结构或算法在某些方面有良好的表现，通常也在其他方面做出一定的牺牲。哈希表就是一个典型的空间换时间，组合了不同的数据结构，并且牺牲了顺序性，换来了 $O(1)$ 的时间复杂度，这前提还得是设计良好。

不知道你有没有发现，在本文中我们实现的哈希表实际上有一个小 bug，为了简化流程只专注于哈希表本身的实现，我们是直接使用 TreeMap 来存储数据，而 TreeMap 底层是红黑树，要求 key 是具有可比较性的。但在我们的实现中没有对 key 要求实现 Comparable 接口，所以当存入的 key 是没有实现 Comparable 接口的对象时就会报错。

你可以尝试一下解决这个问题，例如选择将 TreeMap 替换成 LinkedList，或者传入一个 Comparator 给 TreeMap ，甚至可以实现自己的链表或红黑树来替换掉 TreeMap 。

数据结构之哈希表

哈希表基础

哈希函数的设计

取模在哈希函数中的应用

Java中的 hashCode 方法

链地址法 Separate Chaining

实现属于我们自己的哈希表

哈希表的动态空间处理

哈希表更复杂的动态空间处理方法

最后

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读