HashTable 的 Java 实现

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

This topic created in 3472 days ago, the information mentioned may be changed or developed.

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

HashTable在java中

计算hash(key)得到index索引

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

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

4 replies • 2016-10-25 09:51:08 +08:00

SoloCompany

Oct 25, 2016

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

Powered

Oct 25, 2016 via Android

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

SoloCompany

Oct 25, 2016

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

cloud107202

Oct 25, 2016

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