哈希表

HashTable.cpp

概念

哈希函数：H(key): K -> D , key ∈ K

构造方法

• 直接定址法
• 除留余数法
• 数字分析法
• 折叠法
• 平方取中法

冲突处理方法

• 链地址法：key 相同的用单链表链接
• 开放定址法
  • 线性探测法：key 相同 -> 放到 key 的下一个位置，Hi = (H(key) + i) % m
  • 二次探测法：key 相同 -> 放到 Di = 1^2, -1^2, ..., ±（k)^2,(k<=m/2）
  • 随机探测法：H = (H(key) + 伪随机数) % m

线性探测的哈希表数据结构

线性探测的哈希表数据结构和图片

typedef char KeyType;
typedef struct {
    KeyType key;
}RcdType;
typedef struct {
    RcdType *rcd;
    int size;
    int count;
    bool *tag;
}HashTable;