W6

  1. 数据结构相关笔记①
  2. 数据结构相关笔记②
  3. 数据结构相关笔记③
  4. 数据结构相关笔记④
  5. 数据结构相关笔记⑤
  6. 数据结构相关笔记⑥
  7. 数据结构相关笔记⑦

映射 (Map)

Map（映射）是一种数据结构，它将键（key）和值（value）成对存储。每个键最多储存一个元素，可以通过键快速找到对应的值。

常见实现方式

  1. 链表（Linked List-Based Map）：每个节点存储一个键值对。可以处理任何类型的键。

    • 适用场景：小型数据集，且不需要频繁查找时使用。

  2. 数组（Array-Based Map）：键（key）直接作为数组的索引。这种实现方式需要键的范围是已知且受限的。

    • 适用场景：键的范围较小且密集，空间不成为问题时使用。

  3. 哈希表（HashTable）：使用哈希函数将键映射到存储位置，适合快速查找和插入。需要处理哈希冲突。

    • 适用场景：大多数实际应用场景，如字典（Dictionary）、集合（Set）等。

  4. 树（如红黑树）：使用平衡二叉搜索树存储键值对，保持顺序，适合需要有序数据的场合。

    • 适用场景：需要有序性且支持范围查询的场景，如数据库中的索引。

哈希表 (HashTable)

哈希表是一种数据结构，它通过哈希函数将键映射到存储位置。哈希表的查找和插入操作的时间复杂度为 O(1)。

哈希函数 (Hash Function)

哈希函数的两个组成部分：

  1. 哈希码（HashCode）函数：将输入的键（可以是整数、浮点数、字符串或任意对象）转换成一个整数。

    • 例如，如果输入是一个字符串 ‘word’，哈希码函数可能会将它转换成一个相应的整数，如 12345。

  2. 压缩函数（Compression Function）：将上一步得到的整数进一步压缩到一个固定的范围 [0，N-1]，其中 N 是哈希表的大小（数组的长度）。

    • 例如，如果 N=100，那么压缩函数会将输入整数压缩到 0 到 99 之间的一个值。

哈希函数实现方法

  • 模除法（Modular Division）：尤其适用于正整数键。通过对一个素数取模来计算哈希值：h(k) = k mod N。如果键的分布是随机且均匀的，且哈希表大小 N 适当选择为一个素数，那么哈希冲突的概率会很小。

哈希冲突 (Hash Collision)

分离链接法 (Separate Chaining)

当多个键被映射到同一个槽位时，它们会被依次存储在该槽位的链表中。

  • 装载因子：α = n/m，反映哈希表"满"的程度。保持装载因子 α 小于某个常数（例如 0.75）。在哈希表过满时，应该进行扩容（Rehashing），以降低装载因子，减少链表的长度。

  • 复杂度：

    1. get()：查找时间为 O(1)（计算哈希值）+ 遍历链表 O(α) -> O(1 + α)。
    2. put()：通常在链表的头部进行（或尾部，取决于实现）O(1)。最坏情况 O(n)，如果键已经存在，我们需要替换与之关联的值。
    3. remove()：查找 O(1 + α) + 删除 O(1) -> O(1 + α)。

线性探测法 (Linear Probing)

使用开放定址法，发生碰撞时，按线性顺序找到下一个空位来存放这个键。

  • 优点：无需附加空间（指针、链表、溢出区）。

  • 缺点：耗费时间大于 O(1)，主簇问题（Primary Clustering）。

  • 复杂度：

    1. get()：
      • α < 1 时：O(1)，当哈希表中的空槽位多时（即装载因子小），大部分插入操作都能在第一次探测或很少几次探测内找到一个空槽位。
      • α ≈ 1 时：O(n)，当装载因子接近 1 时（几乎所有槽位都被占用），插入和查找操作可能需要遍历整个哈希表来找到一个空槽位。
    2. put()：同 get()。
    3. remove()：同 get()。

布谷鸟散列 (Cuckoo Hashing)

Cuckoo Hashing 的名字来源于布谷鸟的筑巢行为：当布谷鸟把卵产在其他鸟的巢中时，原来的鸟卵会被挤出去。

  • 驱逐机制（Eviction）：当一个元素要插入哈希表时冲突，新的元素会挤掉旧的元素，旧的元素将被重新插入到另一个表 T2。如果 T2 的槽位也被占用，重复这个过程，可能会产生一连串的"踢出和重新插入"操作。

  • 查找和删除：

    1. get()：O(1)，只需要检查两个可能的位置。
    2. put()：最坏情况时间复杂度为 O(n)，但平均情况下是 O(1)。
    3. remove()：O(1)，只需要检查两个可能的位置。