哈希映射有哪些缺点？

Question

无论我使用什么语言,我总是希望使用等效的hashmap.但是,我正在接受一些练习面试的问题,并询问对此有何限制？

我能想到的唯一原因是有限的主内存,但那不仅限于哈希映射,还包括ArrayLists等.

Answer 1

1. 虽然哈希表具有恒定的时间插入,但哈希表有时需要增加其内部结构并重新填充其条目.这是一个与哈希表的当前大小成比例的操作.这样做的结果是插入时间并不总是一致的,即插入将是恒定的O(1),但是O(n)随着表的增长,偶尔会注意到线性延迟.(这种行为特征导致一些人建议在默认/天真的情况下支持使用哈希表的树.)
2. 您需要确保要添加的项目的哈希算法是合理的.这意味着对于任意一组元素,结果哈希码在哈希码类型的范围内传播得很好(在Java和C#中int).如果你有许多具有相同值的项目(任何人都为零？)那么你的哈希表将降级为精心设计的链表,性能将大幅下降.
3. 您需要确保项目的哈希代码不会随时间发生变化,并且实现了相等方法(Java equals()或.NET Equals())以比较用于哈希代码的相同字段集.(理想情况下,这意味着您添加到表中的对象是不可变的,但您也可以确保任何可变字段与哈希代码计算和equals方法无关:一个冒险的策略.通过更改哈希代码,表格将以后来检索它们时,无法找到您已添加的条目.
4. 哈希表通常不会保留排序 - 无论是自然顺序还是插入顺序.(那些通常使用并行结构来维护排序,或者在迭代时执行相对昂贵的排序.)

也可以看看:

• http://web.archive.org/web/20090430172748/http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/
• http://en.wikipedia.org/wiki/Hash_table#Drawbacks