Hashtable

简介

1. HashTable继承Dictionary类，实现Map接口。

   其中Dictionary类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类。
   在任何一个 Dictionary 对象中，每个键至多与一个值相关联。Map是**“key-value键值对”**接口。

2. 每个键和每个值都是一个对象。

3. HashTable采用"拉链法"实现哈希表，它定义了几个重要的参数：table、count、threshold、loadFactor、modCount。

• table：为一个Entry[]数组类型，Entry代表了“拉链”的节点，每一个Entry代表了一个键值对，哈希表的"key-value键值对"都是存储在Entry数组中的。
• count：HashTable的大小，注意这个大小并不是HashTable的容器大小，而是他所包含Entry键值对的数量。
• threshold：Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值=“容量*加载因子”。
• loadFactor：加载因子。
• modCount：用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了）。

4. 默认开始的时候，容量为11，加载因为为0.75 。

5. 每次扩容2倍+1

6. 线程安全

7. 键和值都不能为 null

8. 添加已有key元素则覆盖，新key则放在链表最前面，并且不会树化

构造方法

Hashtable() 构造一个新的，空的散列表，默认初始容量（11）和负载因子（0.75）。
Hashtable(int initialCapacity) 构造一个新的，空的哈希表，具有指定的初始容量和默认负载因子（0.75）。
Hashtable(int initialCapacity, float loadFactor) 构造一个新的，空的哈希表，具有指定的初始容量和指定的负载因子。
Hashtable(Map<? extends K,? extends V> t) 构造一个与给定Map相同的映射的新哈希表。

方法

void	clear() 清除此散列表，使其不包含键。
Object	clone() 创建这个散列表的浅拷贝。
V	compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 尝试计算指定键的映射及其当前映射的值（如果没有当前映射， null ）。
V	computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 如果指定的键尚未与某个值相关联（或映射到 null ），则尝试使用给定的映射函数计算其值，并将其输入到此映射中，除非 null 。
V	computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 如果指定的密钥的值存在且非空，则尝试计算给定密钥及其当前映射值的新映射。
boolean	contains(Object value) 测试一些键映射到这个哈希表中的指定值。
boolean	containsKey(Object key) 测试指定的对象是否在此哈希表中的键。
boolean	containsValue(Object value) 如果此哈希表将一个或多个键映射到此值，则返回true。
Enumeration<V>	elements() 返回此散列表中值的枚举。
Set<Map.Entry<K,V>>	entrySet() 返回此Map中包含的映射的Set视图。
boolean	equals(Object o) 根据Map界面中的定义，将指定的对象与此Map进行比较以相等。
void	forEach(BiConsumer<? super K,? super V> action) 对此映射中的每个条目执行给定的操作，直到所有条目都被处理或操作引发异常。
V	get(Object key) 返回到指定键所映射的值，或 null如果此映射包含该键的映射。
V	getOrDefault(Object key, V defaultValue) 返回到指定键所映射的值，或 defaultValue如果此映射包含该键的映射。
int	hashCode() 按照Map界面中的定义返回此Map的哈希码值。
boolean	isEmpty() 测试这个哈希表是否将值映射到值。
Enumeration<K>	keys() 返回此散列表中键的枚举。
Set<K>	keySet() 返回此Map中包含的键的Set视图。
V	merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) 如果指定的键尚未与值相关联或与null相关联，则将其与给定的非空值相关联。
V	put(K key, V value) 将指定的 key映射到此 key value中指定的value。
void	putAll(Map<? extends K,? extends V> t) 将所有从指定Map的映射复制到此散列表。
V	putIfAbsent(K key, V value) 如果指定的键尚未与值相关联（或映射到 null ）将其与给定值相关联并返回 null ，否则返回当前值。
protected void	rehash() 增加这个散列表的内部重组能力，从而更有效地适应和访问其条目。
V	remove(Object key) 从此散列表中删除键（及其对应的值）。
boolean	remove(Object key, Object value) 仅当指定的密钥当前映射到指定的值时删除该条目。
V	replace(K key, V value) 只有当目标映射到某个值时，才能替换指定键的条目。
boolean	replace(K key, V oldValue, V newValue) 仅当当前映射到指定的值时，才能替换指定键的条目。
void	replaceAll(BiFunction<? super K,? super V,? extends V> function) 将每个条目的值替换为对该条目调用给定函数的结果，直到所有条目都被处理或该函数抛出异常。
int	size() 返回此哈希表中的键数。
String	toString() 以一组条目的形式返回此 Hashtable对象的字符串表示形式，其括在大括号中，并以ASCII字符“ , ”（逗号和空格）分隔。
Collection<V>	values() 返回此Map中包含的值的Collection视图。

源码分析

public Hashtable(Map<? extends K, ? extends V> t) {this(Math.max(2*t.size(), 11), 0.75f);putAll(t);
}

定位index的方法:

int index = (hash & 0x7FFFFFFF) % tab.length;

put()方法:

public synchronized V put(K key, V value) {if (value == null) {throw new NullPointerException();}// Makes sure the key is not already in the hashtable.Entry<?,?> tab[] = table;int hash = key.hashCode();// 因为hash可能为负数，所以就先和0x7FFFFFFF相与// 在HashMap中，是用 (table.length - 1) & hash 计算要放置的位置int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)tab[index];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;
}

• ① 由于直接使用key.hashcode()，而没有向hashmap一样先判断key是否为null，所以key为null时，调用key.hashcode()会出错，所以hashtable中key也不能为null；
• ②hashtable中对hash值进行寻址的方法为hash%数组长度(与hashmap的index = hash & (tab.length – 1)不同，所以不要求数组长度必须为2的n次方)；
• ③遍历table[index]所连接的链表，查找是否已经存在key与需要插入的key值相同的节点，如果存在则直接更新value，并返回旧的value；
• ④如果table[index]所连接的链表上不存在相同的key，则通过addEntry()方法将新节点加到链表的开头

addEntry()方法:

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 exceededrehash();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);count++;
}

• 如果加入新节点后，hashtable中元素的个数超过了阈值threshold，则利用rehash()对数组进行扩容。
• e=table[index]，并将新节点加在了e节点的前面，最后table[index]=e。相当于把把新节点放在table[index]位置，即整个链表的首部。

rehash()方法:

protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// overflow-conscious codeint newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;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()方法中我们可以看到容量扩大两倍+1，同时需要将原来HashTable中的元素一一复制到新的HashTable中，这个过程是比较消耗时间的，同时还需要重新计算hashSeed的，毕竟容量已经变了。

关于阀值: 比如初始值11、加载因子默认0.75，那么这个时候阀值threshold=8 (11 * 0.7 5)，当容器中的元素达到8时，HashTable进行一次扩容操作，容量 = 8 * 2 + 1 = 17，而阀值threshold = 17*0.75 = 13，当容器元素再一次达到阀值时，HashTable还会进行扩容操作，依次类推。

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;
}

遍历table[index]链表，找到key值相同的节点的value返回，注意同样在该过程中使用到了key的equal方法，所以key被应用与hashtable时不仅要实现hashcode方法还有实现equal方法。

als(key)) {
return (V)e.value;
}
}
return null;
}

遍历table[index]链表，找到key值相同的节点的value返回，注意同样在该过程中使用到了key的equal方法，所以key被应用与hashtable时不仅要实现hashcode方法还有实现equal方法。> 附源码注释文章: https://www.cnblogs.com/wupeixuan/p/8620197.html