现在的位置: 首页 > 综合 > 正文

Q13.2

2018年04月29日 ⁄ 综合 ⁄ 共 653字 ⁄ 字号 评论关闭

f转载自http://hawstein.com/posts/13.2.html

对比哈希表和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), 但由于输入数据的规模不大,因此这点时间差别可以忽略不计。

【上篇】
【下篇】

抱歉!评论已关闭.