careercup-C和C++ 13.2
浏览数：21 /
时间：2015年06月08日
13.2 浅析哈希表和STL map。对比哈希表和STL map。哈希表是怎么实现的？如果输入数据规模不大， 我们可以使用什么数据结构来代替哈希表。
解答
对比哈希表和STL map
在哈希表中，实值的存储位置由其键值对应的哈希函数值决定。因此， 存储在哈希表中的值是无序的。在哈希表中插入元素和查找元素的时间复杂度都是O(1)。 (假设冲突很少)。实现一个哈希表，冲突处理是必须要考虑的。
对于STL中的map，键/值对在其中是根据键进行排序的。它使用一根红黑树来保存数据， 因此插入和查找元素的时间复杂度都是O(logn)。而且不需要处理冲突问题。 STL中的map适合以下情况使用：
- 查找最小元素
- 查找最大元素
- 有序地输出元素
- 查找某个元素，或是当元素找不到时，查找比它大的最小元素
哈希表是怎么实现的
- 首先需要一个好的哈希函数来确保哈希值是均匀分布的。比如：对大质数取模
- 其次需要一个好的冲突解决方法：链表法(chaining，表中元素比较密集时用此法)， 探测法(probing，开放地址法，表中元素比较稀疏时用此法)。
- 动态地增加或减少哈希表的大小。比如，(表中元素数量)/(表大小)大于一个阈值时， 就增加哈希表的大小。我们新建一个大的哈希表，然后将旧表中的元素值， 通过新的哈希函数映射到新表。
如果输入数据规模不大，我们可以使用什么数据结构来代替哈希表。
你可以使用STL map来代替哈希表，尽管插入和查找元素的时间复杂度是O(logn)， 但由于输入数据的规模不大，因此这点时间差别可以忽略不计。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
