HashTable 的 Java 实现

[Powered]

http://www.cnblogs.com/goodwin/p/4102702.html

HashTable在java中

计算hash(key)得到index索引

那么是把value放在一个数组中,index作索引

还是把key-value对放在对应的bucket中?

[SoloCompany]

不管是什么实现 Bucket 当然需要存 key pair 了
否则，先不谈遍历，你 put 的时候怎么知道是否发生了 collision

[Powered]

@SoloCompany
所以是， bucket 中存 entry 对象， hash(key)得到的 index 是 bucket 的索引吗

[SoloCompany]

@Powered bucket 可以放一个链表，或者数组，因为你不能忽略 collision

[cloud107202]

一般 bucket 中是个 entry 链表， hash(key1)得到 bucket 的 index ，然后遍历链表，比对 key1 与链表每个 entry 对象的 key 。如果 hash 函数设计良好，元素均匀的分散在各个 bucket 中， entry 链表的遍历开销可认为是 O(1)