看完帖子后,我对java感到困惑 哈希表内部使用单独的链接或链表或打开关闭地址来处理哈希表冲突。
有人可以告诉我哈希表在内部使用哪种技术吗?
如果你看一下源代码(有一些在线资源,或者在JDK的lib
目录中有一个src.jar
或src.zip
- 我认为JDK 11+它只在OpenJDK中,而不是Oracle的(,你可以看到Hashtable
是作为存储桶数组实现的,每个存储桶都是一个单链表。
数据存储在此处:
/**
* The hash table data.
*/
private transient Entry<?,?>[] table;
那么如果我们看get
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
我们可以看到,键的hashCode
用于选择存储桶,然后在该存储桶内线性搜索条目。
请注意,Hashtable
在很大程度上是一个遗留类,从 Java 1.2 开始被HashMap
取代。OpenJDK的HashMap
开始时基本上是按照Hashtable
的方式工作的,但是如果桶变得太大,它会切换到使用包含类似TreeMap
结构的桶(当桶装满时,它们查找内容的速度更快(。