共计 4773 个字符,预计需要花费 12 分钟才能阅读完成。
本文基于 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
感激浏览
满腹经纶,如有你发现有谬误的中央,能够在后盾或者评论提出来,我会加以批改。
感谢您的浏览,欢送并感激关注!