常用的数据结构

队列(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)) % TableSize
        • hash1(key) 是主哈希函数。
        • hash2(key) 是辅助哈希函数，通常选择 hash2(key) = 1 + (key % (TableSize - 1))，确保探查步长不为零。
  • 使用链表

</