算法-基础篇-②数据结构-C(哈希表)

holic-x...大约 21 分钟

算法-基础篇-②数据结构-C(哈希表)

学习核心

哈希表概念核心
哈希冲突问题和解决方案
- 哈希冲突如何产生？
- 解决方案：链式寻址、开放寻址
哈希算法

学习资料

哈希表

哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。向哈希表中输入一个键 key ，可以在 O(1) 时间内获取对应的值 value

除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下所示

添加元素：仅需将元素添加至数组（链表）的尾部即可，使用 O(1) 时间
查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用 O(n) 时间
删除元素：需要先查询到元素，再从数组（链表）中删除，使用 O(n) 时间

元素操作效率对比	数组	链表	哈希表
查找元素	O(n)	O(n)	O(1)
添加元素	O(1)	O(1)	O(1)
删除元素	O(n)	O(n)	O(1)

观察发现，在哈希表中进行增删查改的时间复杂度都是 O(1) ，非常高效

1.哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等操作

/* 初始化哈希表 */
Map<Integer, String> map = new HashMap<>();

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");

/* 查询操作 */
// 向哈希表中输入键 key ，得到值 value
String name = map.get(15937);

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583);

哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值

/* 遍历哈希表 */
// 遍历键值对 key->value
for (Map.Entry <Integer, String> kv: map.entrySet()) {
    System.out.println(kv.getKey() + " -> " + kv.getValue());
}
// 单独遍历键 key
for (int key: map.keySet()) {
    System.out.println(key);
}
// 单独遍历值 value
for (String val: map.values()) {
    System.out.println(val);
}

2.哈希表简单实现

先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，将数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 定位对应的桶呢？这是通过哈希函数（hash function）实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ，可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步

通过某种哈希算法 hash() 计算得到哈希值
将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index

index = hash(key) % capacity

随后，就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100 。图示以 key 学号和 value 姓名为例，展示了哈希函数的工作原理

以下代码实现了一个简单哈希表。其中，将 key 和 value 封装成一个类 Pair ，以表示键值对

/* 键值对 */
class Pair {
    public int key;
    public String val;

    public Pair(int key, String val) {
        this.key = key;
        this.val = val;
    }
}

/* 基于数组实现的哈希表 */
class ArrayHashMap {
    private List<Pair> buckets;

    public ArrayHashMap() {
        // 初始化数组，包含 100 个桶
        buckets = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            buckets.add(null);
        }
    }

    /* 哈希函数 */
    private int hashFunc(int key) {
        int index = key % 100;
        return index;
    }

    /* 查询操作 */
    public String get(int key) {
        int index = hashFunc(key);
        Pair pair = buckets.get(index);
        if (pair == null)
            return null;
        return pair.val;
    }

    /* 添加操作 */
    public void put(int key, String val) {
        Pair pair = new Pair(key, val);
        int index = hashFunc(key);
        buckets.set(index, pair);
    }

    /* 删除操作 */
    public void remove(int key) {
        int index = hashFunc(key);
        // 置为 null ，代表删除
        buckets.set(index, null);
    }

    /* 获取所有键值对 */
    public List<Pair> pairSet() {
        List<Pair> pairSet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                pairSet.add(pair);
        }
        return pairSet;
    }

    /* 获取所有键 */
    public List<Integer> keySet() {
        List<Integer> keySet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                keySet.add(pair.key);
        }
        return keySet;
    }

    /* 获取所有值 */
    public List<String> valueSet() {
        List<String> valueSet = new ArrayList<>();
        for (Pair pair : buckets) {
            if (pair != null)
                valueSet.add(pair.val);
        }
        return valueSet;
    }

    /* 打印哈希表 */
    public void print() {
        for (Pair kv : pairSet()) {
            System.out.println(kv.key + " -> " + kv.val);
        }
    }
}

3.哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况

对于上述示例中的哈希函数，当查询学号为 12836 和 20336 的两个学生时，会发现两个数据通过哈希函数的输出结果相同（12836%100、20336%100都为36），会导致两个学号指向了同一个姓名，这种多个输入对应同一输出的情况成为哈希冲突。

且结合上述分析可知，哈希表的容量n越大，多个key被分配到同一个桶中的概率就越低，冲突就越少，因此可以通过扩容哈希表来减少哈希冲突

哈希表是如何扩容的？

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

负载因子（load factor）是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 0.75 时，系统会将哈希表扩容至原先的 2 倍

哈希冲突

结合上述分析，哈希冲突产生的原因是因为哈希函数的输入空间远大于输出空间，因此不可避免会出现“多个输入对应相同输出”的情况，进而导致哈希冲突。哈希冲突会导致查询结果错误，进而严重影响哈希表的可用性。

为了解决哈希冲突问题，最简单的方式就是进行哈希表扩容，直到冲突消失为止。这种方式简单粗暴，但效率非常低（因为哈希表扩容需要进行大量数据搬运和哈希值计算）。因此为了提升效率，可以考虑采用以下策略：

改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作（包括“链式地址”和“开放寻址”），但无法减少哈希冲突的发生
仅在必要时，即当哈希冲突比较严重时，才执行扩容操作

1.链式地址

在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中

基于链式地址实现的哈希表的操作方法发生了以下变化

查询元素：输入 key ，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比 key 以查找目标键值对
添加元素：首先通过哈希函数访问链表头节点，然后将节点（键值对）添加到链表中
删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除

链式地址存在以下局限性

占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间
查询效率降低：因为需要线性遍历链表来查找对应元素

需注意，当链表很长时，查询效率O(n)很差，此时可以将链表转化为“AVL树”或“红黑树”，进而优化链表的检索效率（将查询操作的时间复杂度优化至O(log n)）

2.开放寻址

开放寻址（open addressing）不引入额外的数据结构，而是通过"多次探测"来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。

线性探测

线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 1 ），直至找到空桶，将元素插入其中
查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None

下图展示了开放寻址（线性探测）哈希表的键值对分布。根据此哈希函数，最后两位相同的 key 都会被映射到相同的桶。而通过线性探测，它们被依次存储在该桶以及之下的桶中。

线性探测容易产生“聚集现象”。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶 None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在，如下图所示分析。

为了解决该问题，可以采用懒删除（lazy deletion）机制：它不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。在该机制下，None 和 TOMBSTONE 都代表空桶，都可以放置键值对。但不同的是，线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。

然而，懒删除可能会加速哈希表的性能退化。这是因为每次删除操作都会产生一个删除标记，随着 TOMBSTONE 的增加，搜索时间也会增加，因为线性探测可能需要跳过多个 TOMBSTONE 才能找到目标元素。

为此，考虑在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置。这样做的好处是当每次查询或添加元素时，元素会被移动至距离理想位置（探测起始点）更近的桶，从而优化查询效率。

平方探测

平方探测与线性探测类似，都是开放寻址的常见策略之一。当发生冲突时，平方探测不是简单地跳过一个固定的步数，而是跳过“探测次数的平方”的步数，即 1,4,9,… 步。

平方探测主要具有以下优势

平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应
平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀

然而，平方探测并不是完美的

仍然存在聚集现象，即某些位置比其他位置更容易被占用
由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它

多次哈希

顾名思义，多次哈希方法使用多个哈希函数 f1(x)、f2(x)、f3(x)、… 进行探测。

插入元素：若哈希函数 f1(x) 出现冲突，则尝试 f2(x) ，以此类推，直到找到空位后插入元素
查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回 None

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量

开放寻址（线性探测、平方探测和多次哈希）哈希表都存在“不能直接删除元素”的问题

3.编程语言的选择

各种编程语言采取了不同的哈希表实现策略：

Python 采用开放寻址
- 字典 dict 使用伪随机数进行探测
Java 采用链式地址
- 自 JDK 1.8 以来，当 HashMap 内数组长度达到 64 且链表长度达到 8 时，链表会转换为红黑树以提升查找性能
Go 采用链式地址
- Go 规定每个桶最多存储 8 个键值对，超出容量则连接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作，以确保性能

哈希算法

基于上述理论分析，无论是开放寻址还是链式地址，它们只能保证哈希表可以在发生冲突时正常工作，而无法减少哈希冲突的发生。

如果哈希冲突过于频繁，哈希表的性能则会急剧劣化。如下图所示，对于链式地址哈希表，理想情况下键值对均匀分布在各个桶中，达到最佳查询效率；最差情况下所有键值对都存储到同一个桶中，时间复杂度退化至 O(n)

而键值对的分布则取决于哈希函数，参考前面的哈希函数示例：先计算哈希值，再对数组长度取模：index = hash(key) % capacity，当 capacity 固定时，哈希算法hash()则决定了键值对在哈希表中的分布情况。这意味着，为了降低哈希冲突的发生概率，应将注意力集中在哈希算法 hash() 的设计上。

1.哈希算法的目标

为了实现“既快又稳”的哈希表数据结构，哈希算法应具备以下特点

确定性：对于相同的输入，哈希算法应始终产生相同的输出。这样才能确保哈希表是可靠的
效率高：计算哈希值的过程应该足够快。计算开销越小，哈希表的实用性越高
均匀分布：哈希算法应使得键值对均匀分布在哈希表中。分布越均匀，哈希冲突的概率就越低

实际上，哈希算法除了可以用于实现哈希表，还广泛应用于其他领域中

密码存储：为了保护用户密码的安全，系统通常不会直接存储用户的明文密码，而是存储密码的哈希值。当用户输入密码时，系统会对输入的密码计算哈希值，然后与存储的哈希值进行比较。如果两者匹配，那么密码就被视为正确
数据完整性检查：数据发送方可以计算数据的哈希值并将其一同发送；接收方可以重新计算接收到的数据的哈希值，并与接收到的哈希值进行比较。如果两者匹配，那么数据就被视为完整

对于密码学的相关应用，为了防止从哈希值推导出原始密码等逆向工程，哈希算法需要具备更高等级的安全特性

单向性：无法通过哈希值反推出关于输入数据的任何信息
抗碰撞性：应当极难找到两个不同的输入，使得它们的哈希值相同
雪崩效应：输入的微小变化应当导致输出的显著且不可预测的变化

“均匀分布”与“抗碰撞性”是两个独立的概念，满足均匀分布不一定满足抗碰撞性。例如，在随机输入 key 下，哈希函数 key % 100 可以产生均匀分布的输出。然而该哈希算法过于简单，所有后两位相等的 key 的输出都相同，因此我们可以很容易地从哈希值反推出可用的 key ，从而破解密码。

2.哈希算法的设计

哈希算法的设计是一个需要考虑许多因素的复杂问题。然而对于某些要求不高的场景，也能设计一些简单的哈希算法

加法哈希：对输入的每个字符的 ASCII 码进行相加，将得到的总和作为哈希值
乘法哈希：利用乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII 码累积到哈希值中
异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中
旋转哈希：将每个字符的 ASCII 码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作

/* 加法哈希 */
int addHash(String key) {
    long hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash = (hash + (int) c) % MODULUS;
    }
    return (int) hash;
}

/* 乘法哈希 */
int mulHash(String key) {
    long hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash = (31 * hash + (int) c) % MODULUS;
    }
    return (int) hash;
}

/* 异或哈希 */
int xorHash(String key) {
    int hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash ^= (int) c;
    }
    return hash & MODULUS;
}

/* 旋转哈希 */
int rotHash(String key) {
    long hash = 0;
    final int MODULUS = 1000000007;
    for (char c : key.toCharArray()) {
        hash = ((hash << 4) ^ (hash >> 28) ^ (int) c) % MODULUS;
    }
    return (int) hash;
}

结合上述哈希算法实现分析，每种哈希算法的最后一步都是对大质数 1000000007 取模，以确保哈希值在合适的范围内。值得思考的是，为什么要强调对质数取模，或者说对合数取模的弊端是什么？这是一个有趣的问题。

先抛出结论：使用大质数作为模数，可以最大化地保证哈希值的均匀分布。因为质数不与其他数字存在公约数，可以减少因取模操作而产生的周期性模式，从而避免哈希冲突。

结合例子分析，假设选择合数9作为模数，它可以被3整除，那么所有可以被 3 整除的 key 都会被映射到 0、3、6 这三个哈希值。如果输入 key 恰好满足这种等差数列的数据分布，那么哈希值就会出现聚堆，从而加重哈希冲突。

modulus=9
key={0,3,6,9,12,15,18,21,24,27,30,33,36,39....}
hash={0,3,6,0,3,6,0,3,6,0,3,6,0,...}
# 如果key满足这种等差数列的数据分布，哈希值就会出现聚堆的情况，从而加重哈希冲突

如果将模数替换为质数13，由于 key 和 modulus 之间不存在公约数，因此输出的哈希值的均匀性会明显提升。

modulus=13
key={0,3,6,9,12,15,18,21,24,27,30,33,36,39....}
hash={0,3,6,9,12,2,5,8,11,1,4,7,...}

如果能够保证 key 是随机均匀分布的，那么选择质数或者合数作为模数都可以，它们都能输出均匀分布的哈希值。而当 key 的分布存在某种周期性时，对合数取模更容易出现聚集现象。因此，通常选取质数作为模数，并且这个质数最好足够大，以尽可能消除周期性模式，提升哈希算法的稳健性。

3.常见哈希算法

不难发现，以上介绍的简单哈希算法都比较“脆弱”，远远没有达到哈希算法的设计目标。例如，由于加法和异或满足交换律，因此加法哈希和异或哈希无法区分内容相同但顺序不同的字符串，这可能会加剧哈希冲突，并引起一些安全问题。

在实际中，通常会用一些标准哈希算法，例如 MD5、SHA-1、SHA-2 和 SHA-3 等。它们可以将任意长度的输入数据映射到恒定长度的哈希值。近一个世纪以来，哈希算法处在不断升级与优化的过程中。一部分研究人员努力提升哈希算法的性能，另一部分研究人员和黑客则致力于寻找哈希算法的安全性问题。下表展示了在实际应用中常见的哈希算法

MD5 和 SHA-1 已多次被成功攻击，因此它们被各类安全应用弃用
SHA-2 系列中的 SHA-256 是最安全的哈希算法之一，仍未出现成功的攻击案例，因此常用在各类安全应用与协议中
SHA-3 相较 SHA-2 的实现开销更低、计算效率更高，但目前使用覆盖度不如 SHA-2 系列

	MD5	SHA-1	SHA-2	SHA-3
推出时间	1992	1995	2002	2008
输出长度	128 bit	160 bit	256/512 bit	224/256/384/512 bit
哈希冲突	较多	较多	很少	很少
安全等级	低，已被成功攻击	低，已被成功攻击	高	高
应用	已被弃用，仍用于数据完整性检查	已被弃用	加密货币交易验证、数字签名等	可用于替代 SHA-2

4.数据结构的哈希值

哈希表的 key 可以是整数、小数或字符串等数据类型。编程语言通常会为这些数据类型提供内置的哈希算法，用于计算哈希表中的桶索引。以 Python 为例，可以调用 hash() 函数来计算各种数据类型的哈希值

整数和布尔量的哈希值就是其本身
浮点数和字符串的哈希值计算较为复杂
元组的哈希值是对其中每一个元素进行哈希，然后将这些哈希值组合起来，得到单一的哈希值
对象的哈希值基于其内存地址生成。通过重写对象的哈希方法，可实现基于内容生成哈希值

int num = 3;
int hashNum = Integer.hashCode(num);
// 整数 3 的哈希值为 3

boolean bol = true;
int hashBol = Boolean.hashCode(bol);
// 布尔量 true 的哈希值为 1231

double dec = 3.14159;
int hashDec = Double.hashCode(dec);
// 小数 3.14159 的哈希值为 -1340954729

String str = "Hello 算法";
int hashStr = str.hashCode();
// 字符串“Hello 算法”的哈希值为 -727081396

Object[] arr = { 12836, "小哈" };
int hashTup = Arrays.hashCode(arr);
// 数组 [12836, 小哈] 的哈希值为 1151158

ListNode obj = new ListNode(0);
int hashObj = obj.hashCode();
// 节点对象 utils.ListNode@7dc5e7b4 的哈希值为 2110121908

在许多编程语言中，只有不可变对象才可作为哈希表的 key 。假如将列表（动态数组）作为 key ，当列表的内容发生变化时，它的哈希值也随之改变，就无法在哈希表中查询到原先的 value

虽然自定义对象（比如链表节点）的成员变量是可变的，但它是可哈希的。这是因为对象的哈希值通常是基于内存地址生成的，即使对象的内容发生了变化，但它的内存地址不变，哈希值仍然是不变的

有些情况下，在不同控制台中运行程序时，输出的哈希值是不同的。这是因为 Python 解释器在每次启动时，都会为字符串哈希函数加入一个随机的盐（salt）值。这种做法可以有效防止 HashDoS 攻击，提升哈希算法的安全性

昵称

邮箱

网址

按正序
按倒序
按热度

算法-基础篇-②数据结构-C(哈希表)

预览: