排版练习

本文《》由  发表自博客园博客，任何未经作者本人允许的人为或爬虫转载均为耍流氓。

原地址：http://www.cnblogs.com/gaochundong/p/hashtable_and_perfect_hashing.html

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

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

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

• 哈希表（Hashtable）
  • • 线性探查（Linear Probing）
    • 二次探查（Quadratic Probing）
    • 二度哈希（Rehashing）/双重哈希（Double Hashing）