常用的数据结构
队列(FIFO)
栈(LIFO)
链表
hash表
- hash冲突处理
- 开放式寻址
- 线性探测
- 表示依次检查索引为
hash(key) + 1、hash(key) + 2... 的位置。 i是冲突后的探查步数。- 公式：
hash(i) = (hash(key) + i) % TableSize
- 表示依次检查索引为
- 二次探查
- 规则：冲突后探查的步长是平方递增的，例如，检查位置为
hash(key) + 1²、hash(key) + 2²等。 - 公式：
hash(i) = (hash(key) + i²) % TableSize
- 规则：冲突后探查的步长是平方递增的，例如，检查位置为
- 双重hash
- 规则：采用第二个哈希函数来确定探查的步长。
- 公式：
hash(i) = (hash1(key) + i * hash2(key)) % TableSizehash1(key)是主哈希函数。hash2(key)是辅助哈希函数，通常选择hash2(key) = 1 + (key % (TableSize - 1))，确保探查步长不为零。
- 线性探测
- 使用链表
- 开放式寻址