本文基于 JDK1.8 > 读完本文预计须要 15 分钟
摘要
想必 HashTable 大家都不会生疏（尽管当初不举荐用它了，举荐ConCurrentHashMap），但咱们说起 HashMap 很天然的就会想到 HashTable，也常常拿它两做比照。
大部分人想到的第一点就是：HashMap 线程不平安，HashTable 线程平安！看源码会发现HashTable 的所有办法都是 synchronized 润饰，看到这个咱们就晓得起因了。咱们先来看一遍 HashTable 的源码，它两的源码比照着看，成果更佳。咱们篇幅按一样的程序写便于比照观看。HashMap 源码浏览
首先咱们理解到 HashMap 继承自 AbstractMap 实现的是 Map 接口，而 HashTable 继承自 Dictionary 实现的是 Map 接口。可怜的是 Dictionary 曾经被弃用。
-
次要的不同点：
- 线程平安： HashMap 线程不平安 <–> HashTable 线程平安
- 实现形式： HashMap 用数组 + 链表 + 红黑树 <–> HashTable 用数组 + 链表
- 默认初始容量： HashMap 是 16 <–> HashTable 是 11
- key 是否可为 null: HashMap 能够容许存在一个为 null 的 key 和任意个为 null 的 value <–> HashTable 中的 key 和 value 都不容许为 null
要害变量：
// 外部寄存的键值对数组
private transient Entry<?,?>[] table;
// 寄存的键值对的数量
private transient int count;
// 扩容的阈值
private int threshold;
// 加载因子
private float loadFactor;四个构造方法：
// 构造方法 1
// 用指定的初始容量，加载因子搞一个空的 hash 表
public Hashtable(int initialCapacity, float loadFactor) {if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity:"+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load:"+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
// 构造方法 2
// 用指定的初始容量与默认的加载因子 0.75 搞一个空的 hash 表
public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);
}
// 构造方法 3
// 空参结构 默认应用这个 默认初始容量 11（HashMap 是 16），加载因子 0.75 调用构造方法 1 搞一个新的 hash 表
public Hashtable() {this(11, 0.75f);
}
// 构造方法 4
// 传入一个 map 搞一个与此 map 具用雷同映射的新 hash 表
public Hashtable(Map<? extends K, ? extends V> t) {this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
对四个构造方法简略总结一下, 与 HashMap 看起来十分相似啊，但有所区别：
- 构造函数并不像 HashMap 用的是一种懒加载的形式（用到的时候才去初始化），而是咔，一上来就给你先整一个新的空 Hash 表在那放着。
- 默认初始容量：HashMap 是 16，HashTable 是 11。
次要办法
hashtable->hashCode()
public synchronized boolean containsKey(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 true;}
}
return false;
}
咱们拎进去 containsKey()办法举例说明：
- HashTable 中没有像 HashMap 一样搞一个专门的 hash()办法，它间接调用了 Object 提供的本地办法 hashCode();
int hash = key.hashCode()，在 HashTable 中都是以这种形式获取 hashCode
hashtable->put()
以下是源代码（带正文）：
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
// 按位与左右保障失去整数 再取模防止超过长度
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 如果存在雷同的 key 则遍历链表把那个 key 对应的 value 换成新的 value
for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 调用新增办法
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
// 如果一旦大于等于阈值则扩容
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
// 间接放到这个哈希槽中，放到链表的第一个地位
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
// 把表中容量加 1
count++;
}
那么咱们来总结一下 put 办法：
- 对 value 判空，hashtable 不容许 key、value 为空
- 依据 key 的 hashCode 值找到对应的索引
- 如果存在雷同的 key 则遍历链表把那个 key 对应的 value 换成新的 value
- 判断表中键值对数量是否大于阈值
是，调用 rehash()办法扩容 - 间接把键值对插到哈希槽（链表第一位）
hashtable->get()
public synchronized V get(Object key) {Entry<?,?> tab[] = table;
int hash = key.hashCode();
// 寻址
int index = (hash & 0x7FFFFFFF) % tab.length;
// 遍历链表取出 key 对应的 value
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {if ((e.hash == hash) && e.key.equals(key)) {return (V)e.value;
}
}
return null;
}
那么咱们来总结一下 get()办法：
- 依据 key 的 hashCode 值找到对应索引，遍历链表取值
hashtable->rehash()
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 新的初始容量是旧表容量的 2 倍 +1
int newCapacity = (oldCapacity << 1) + 1;
// 达到最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
// 初始化一个新的哈希表
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
// 新的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// 数据迁徙到新表
for (int i = oldCapacity ; i-- > 0 ;) {for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
// 寻址
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
总结一下 rehash()办法：
- 求出新的容量（旧容量 2 倍 +1）
- 判断是否达到最大容量
- 依据新容量初始化一个新表
- 求出新的阈值
- 把旧表中的数据迁徙到新表
我想这会浏览完结之后应该对 HashTable 有了肯定的意识，心愿能在面试或者工作中帮到您！
参考文献
- JDK1.7&JDK1.8 源码。
- Java Code Geeks，HashMap performance improvements in Java 8，2014。
- 博客园，Java 汇合系列 10 之 HashMap 具体介绍 (源码解析) 和应用示例, 2013。
- 美团技术团队 Java 8 系列之重新认识 HashMap, 2016。
Hongchen 闲聊
放一张去年的照片【疏忽腿毛】，这是我去打羽毛球顺手拍的一张照片，过后是出门去球馆。我高中期间常打，然而上大学这个羽毛球就旷废了，来北京之后就没个静止喜好了。
恰好，我看合租的室友天天拎个拍搁客厅晃悠。于是，我让他拉上我，筹备从新给捡起来玩一玩，还是得把这身材锤炼好了，否则，怎么扛得住 996 呢【狗头】。
稍作思考，还是须要倒退一下本人的体育喜好，毕竟静止之后的快感还是有的。怕本人长时间躺着刷抖音之后的精力空洞【狗头】。
如果有喜爱打球的小伙伴能够一块打球，分割我！hahahahaha
年初了，感觉疫情常态化了，也去打了疫苗，心愿疫情早点过来！peaceeeee
感激浏览
满腹经纶，如有你发现有谬误的中央，能够在后盾或者评论提出来，我会加以批改。
感谢您的浏览，欢送并感激关注！