在最近的一次采访中,我被问及HashMap如何在Java中工作,我能够很好地解释它,并解释在最坏的情况下,由于链接,HashMap可能会退化为一个列表.我被要求找出改善这种表现的方法,但在采访中我无法做到这一点.面试官让我抬头看"Trove".
我相信他指的是这个页面.我已经阅读了该页面上提供的描述,但仍然无法弄清楚它是如何克服java.util.HashMap的限制的.
即使是暗示也会受到赞赏.谢谢!!
关键词是开放式解决.所有条目都在一个大数组中,而不是散列到一个桶数组.添加元素时,如果元素的空间已在使用中,则只需向下移动数组即可找到可用空间.
只要数组保持足够大于条目数并且散列函数分布均匀,就可以保持平均查找时间较小.通过使用一个阵列,您可以获得更好的性能 - 它更加缓存友好.
但是,如果(例如)每个键散列到相同的值,它仍然具有最坏情况的线性行为,因此它不能避免该问题.
在Trove页面中,我认为有两个主要差异可以改善性能.
第一个是使用开放式寻址(http://en.wikipedia.org/wiki/Hash_table#Open_addressing).这并不能避免碰撞问题,但它确实意味着不需要为地图中的每个项目创建"Entry"对象.
第二个重要的区别是能够提供自己的哈希函数,它与密钥类提供的函数不同.因此,如果有意义的话,你可以提供更快的哈希函数.
Trove 的优点之一是它避免了对象创建，尤其是对于基元而言。对于嵌入式 java 设备中的大哈希表来说，由于内存消耗较少，这可能是有利的。
我看到的另一个优点是使用自定义哈希代码/函数，而不需要重写 hashcode()。对于特定的数据集，以及编写哈希函数的专家来说，这可能是一个优势。