摘要：简介声明文章均为本人技术笔记，转载请注明出处声明和一样也是散列表，存储元素也是键值对继承于类类声明了操作键值对的接口方法，实现接口定义键值对接口大部分类用修饰，证明是线程安全的基本数据结构键值对数组，每个本质上是一个单向链表的表头阈值装填因
Hashtable简介
声明
文章均为本人技术笔记，转载请注明出处https://segmentfault.com/u/yzwall
Hashtable声明
public class Hashtable extends Dictionary implements Map, Cloneable, java.io.Serializable
Hashtable和HashMap一样也是散列表，存储元素也是键值对；
Hashtable继承于Dictionary类（Dictionary类声明了操作键值对的接口方法），实现Map接口（定义键值对接口）；
Hashtable大部分类用synchronized修饰，证明Hashtable是线程安全的；
Hashtable基本数据结构
private transient Entry[] table：键值对/Entry数组，每个Entry本质上是一个单向链表的表头
private int threshold：rehash阈值
private float loadFactor：装填因子
private transient int modCount = 0： Hashtable结构化修改次数，用来实现fail-fast机制；
private transient volatile Set> entrySet：Hastable视图，键值对集合；
private transient volatile Set keySet：Hastable视图，key集，Hashtable中key不可重复；
private transient volatile Collection values：Hastable视图，value集合，可重复；
Hashtable中key和value是一对多关系；
键值对/Entry
private static class Entry implements Map.Entry {
final int hash;
final K key;
V value;
Entry next;
...
// 计算键值对的hashCode
public int hashCode() {
// "^" 按位异或, hash在调用构造器时传入
return hash ^ Objects.hashCode(value);
}
}
Hash函数
键值对
Hashtable方法分析
public synchronized boolean contains(Object value)
public boolean containsValue(Object value)内部调用contains(value);
判断是否含有该value的键值对，在Hashtable中hashCode相同的Entry用链表组织，hashCode不同的存储在Entry数组table中；
// in contains() method.
Entry tab[] = table;
// 查找：遍历所有Entry链表
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
public synchronized boolean containsKey(Object key)
散列分布策略
int index = (hash & 0x7FFFFFFF) % tab.length;
计算键值对的桶位（本质是键值对在tab数组中的索引），Hashtable本质上采用除数取余法进行散列分布，模运算效率较低
Hash函数
int hash = key.hashCode() Hashtable直接调用key的hashCode()计算hashCode；
containsKey方法体
Entry tab[] = table;
int hash = key.hashCode();
/**
* 计算index, % tab.length防止数组越界
* index表示key对应entry所在链表表头
*/
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;
public synchronized V get(Object key)：根据指定key查找对应value，查找原理与containsKey相同，查找成功返回value，否则返回null；
public synchronized V put(K key, V value)
设置键值对，key和value都不可为null，设置顺序:
如果Hashtable含有key，设置(key, oldValue) -> (key, newValue)；
如果Hashtable不含有key, 调用addEntry(...)添加新的键值对；
private void addEntry(int hash, K key, V value, int index)
当键值对个数超过阈值，先进行rehash然后添加entry，否则直接添加entry；
public synchronized V remove(Object key)
remove操作，计算key所在链表表头table[index]，然后进行单向链表的节点删除操作
public synchronized Object clone()
对Hashtable的浅拷贝操作，浅拷贝所有bucket（单向链表组织形式）的表头；
protected void rehash()
当Hashtable中键值对总数超过阈值（容量*装载因子）后，内部自动调用rehash()增加容量，重新计算每个键值对的hashCode;
int newCapacity = (oldCapacity << 1) + 1计算新容量 = 2 * 旧容量 + 1；并且根据新容量更新阈值；
...
for (int i = oldCapacity ; i-- > 0 ;) {
// 拷贝每个Entry链表
for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
// 重新计算每个Entry链表的表头索引（rehash）
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
// 开辟链表节点
e.next = (Entry)newMap[index];
// 拷贝
newMap[index] = e;
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/66972.html
