首页 > 代码库 > 排版练习

排版练习

我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个数组,为每个可能的关键字保留一个位置,就可以应用直接寻址技术。

哈希表(Hash Table)是普通数组概念的推广。当实际存储的的关键字数比可能的关键字总数较小时,这时采用哈希表就会比使用直接数组寻址更为有效。因为哈希表通常采用的数组尺寸与所要存储的关键字数是成比例的。

哈希表是一种动态集合数据结构,在一些合理的假设下,在哈希表中查找一个元素的期望时间是 O(1) 。

  • 哈希表(Hashtable)
    • 哈希冲突解决策略:开放寻址法(Open Addressing)
      • 线性探查(Linear Probing)
      • 二次探查(Quadratic Probing)
      • 二度哈希(Rehashing)/双重哈希(Double Hashing)
    • 哈希冲突解决策略:链接技术(chaining)
  • 哈希函数的设计
    • 除法哈希法(The Division Method)
    • 乘法哈希法(The Multiplication Method)
    • 全域哈希法(Universal Hashing)
  • 完美哈希(Perfect Hashing)

排版练习