Cracking the coding interview--Q13.2

February 11, 2013
作者:Hawstein
出处:http://hawstein.com/posts/13.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Compare and contrast a hash table vs. an STL map. How is a hash table implemented?If the number of inputs is small, what data structure options can be used instead of a hash table?

译文:

对比哈希表和STL map。哈希表是怎么实现的?如果输入数据规模不大, 我们可以使用什么数据结构来代替哈希表。

解答

对比哈希表和STL map

在哈希表中,实值的存储位置由其键值对应的哈希函数值决定。因此, 存储在哈希表中的值是无序的。在哈希表中插入元素和查找元素的时间复杂度都是O(1)。 (假设冲突很少)。实现一个哈希表,冲突处理是必须要考虑的。

对于STL中的map,键/值对在其中是根据键进行排序的。它使用一根红黑树来保存数据, 因此插入和查找元素的时间复杂度都是O(logn)。而且不需要处理冲突问题。 STL中的map适合以下情况使用:

  1. 查找最小元素

  2. 查找最大元素

  3. 有序地输出元素

  4. 查找某个元素,或是当元素找不到时,查找比它大的最小元素

哈希表是怎么实现的

  1. 首先需要一个好的哈希函数来确保哈希值是均匀分布的。比如:对大质数取模

  2. 其次需要一个好的冲突解决方法:链表法(chaining,表中元素比较密集时用此法), 探测法(probing,开放地址法,表中元素比较稀疏时用此法)。

  3. 动态地增加或减少哈希表的大小。比如,(表中元素数量)/(表大小)大于一个阈值时, 就增加哈希表的大小。我们新建一个大的哈希表,然后将旧表中的元素值, 通过新的哈希函数映射到新表。

如果输入数据规模不大,我们可以使用什么数据结构来代替哈希表。

你可以使用STL map来代替哈希表,尽管插入和查找元素的时间复杂度是O(logn), 但由于输入数据的规模不大,因此这点时间差别可以忽略不计。

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview