跳转至

Hash

概要

  • 散列函数
  • 单独链表法
  • 开放地址
  • 开放地址
    • 线性探测
    • 二次探测
    • 双重散列
  • 再散列
插值排序（interpolation sort）
  • 时间复杂度 \(O(1)\)
  • 基于公式的搜索（search by formula）

General Idea

符号表（Symbol Table）

  • Objects：一组 名称（name） + 属性（attribute） 对的集合（集合中的每个名称唯一）
  • Operations：
    • SymTab Create(TableSize)：创建一个空符号表
    • Boolean IsIn(SymTab, Name)：判断符号表中是否存在名称/查找
    • SymTab Insert(SymTab, Name, Attributes)：将名称和属性插入符号表
    • SymTab Modify(SymTab, Name, Attributes)：修改符号表中名称的属性
    • Attributes Find(SymTab, Name)：返回名称的属性
    • SymTab Delete(SymTab, Name)：从符号表中删除名称

散列表（Hash Table）

常见问题

  • 哈希冲突（Hash Collision）：不同的名称可能会被映射到同一个位置
  • 溢出（Overflow）：当表满时，无法插入新元素
  • 负载因子（Load Factor）：表中元素数量与表大小的比率，过高会导致性能下降

时间复杂度：

\[ T_{seacrh} = T_{insert} = T_{delete} = O(1) \]
  • 平均情况：\(O(1)\)
  • 最坏情况：\(O(n)\)（当所有元素都映射到同一个位置时）

Hash Function

散列函数f的性质：

  • f(x)必须容易计算，且最小化冲突的可能
  • f(x)
散列函数构造

  1. 数字关键词

    • 直接定址法：当关键字是整数且范围较小时，直接使用关键字作为索引
    • 除留余数法：使用关键字除以表大小，取余
    • 乘法散列法：将关键字乘以一个常数，取小数部分，再乘以表大小，取整
    • 平方取中法：将关键字平方，取中间的几位作为索引
    • 折叠法：将关键字分成几部分，分别求和后取模

  2. 字符串关键词

Separate Chaining

单独链表法（Separate Chaining）：每个位置存储一个链表，所有映射到同一位置的元素都存储在该链表中。

又称开散列法（Open Hashing）：使用链表来处理哈希冲突。

code

初始化
struct ListNode;
typedef struct ListNode *Position;
创建空表
从散列表中找键
将键插入散列表内

Open Addressing

开放地址 (open addressing)

又称闭散列法（Closed Hashing）：所有元素都存储在散列表内，冲突时寻找下一个空位置。

Linear Probing

线性探测 (linear probing)

Quadratic Probing

二次探测 (quadratic probing)

Double Hashing

双散列 (double hashing)

Rehashing

再散列 (rehashing)

HW14 -- Hash