java集合-哈希表HashTable
一、简介
HashTable也是一种key-value结构，key-value不允许null，并且这个类的几乎全部的方法都加上了synchronized锁，来保证并发安全，由于加了锁所以性能方面会比较低。
二类图
public class Hashtable
extends Dictionary
implements Map, Cloneable, java.io.Serializable
也实现了Map接口，继承了java.util.Dictionary类，Dictionary类是一个抽象类，它定义了键映射到值的数据结构。
常用方法
添加单个元素 synchronized V put(K key, V value)
//添加单个元素
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {//value值非空判断
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
//拿到key的hash值
int hash = key.hashCode();
//数组长度取模运算得到下标index
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry entry = (Entry)tab[index];//通过index下标取得节点entry
for(; entry != null ; entry = entry.next) {//单链表entry开始遍历
//判断链表节点的hash跟key是否跟传入的key匹配
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;//找到对应链表节点，替换value值
entry.value = value;
return old;
}
}
//没有在链表中找到key存在的节点，单链表进行添加
addEntry(hash, key, value, index);
return null;
}
//链表添加元素
private void addEntry(int hash, K key, V value, int index) {
modCount++;//修改次数+1
Entry<?,?> tab[] = table;
if (count >= threshold) {//HashTable长度超过了 阈值，进行扩容
// 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 e = (Entry) tab[index];//根据下标取得链表节点
//链表头插
tab[index] = new Entry<>(hash, key, value, e);
count++;//长度+1
}
//扩容
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)//旧数组长度超过了最大值，直接return; 后面扩容代码不走了
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;//新数组长度 超过了最大值，赋值设置的数组最大值
}
//创建一个新的数组，长度是newCapacity
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;//修改次数+1
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//计算下一次扩容的阈值
table = newMap;//新数组赋值给 HashTable
//第一层for循环遍历 旧的数组
for (int i = oldCapacity ; i-- > 0 ;) {
//第二层for循环遍历，旧数组对应的单链表
for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
Entry e = old;//旧节点e
old = old.next;//链表下一个节点，用来判断是否终止第二层循环
//计算旧链表的hash 在新数组的位置
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
//旧节点 的next指向，新数组的下标的链表，头插
e.next = (Entry)newMap[index];
newMap[index] = e;//节点赋值给新数组
}
}
}
根据key获取元素 synchronized V get(Object key)
//获取元素的值
public synchronized V get(Object key) {
//HashTable的数组
Entry<?,?> tab[] = table;
//取得key的hash
int hash = key.hashCode();
//hash取模运算得到数组下标
int index = (hash & 0x7FFFFFFF) % tab.length;
//循环遍历链表节点的hash值和key是否等于 传的参数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;//没找到值，返回null
}
删除元素
//删除元素 synchronized V remove(Object key)
public synchronized V remove(Object key) {
//HashTable的数组
Entry<?,?> tab[] = table;
//取得key的hash
int hash = key.hashCode();
//hash取模运算得到数组下标
int index = (hash & 0x7FFFFFFF) % tab.length;
//根据下标取得链表
Entry e = (Entry)tab[index];
//这个for循环写的666，专门备注一下
/**
for语句格式（循环语句）
for(初始化语句;判断条件语句;控制条件语句){
循环体语句;
}
执行过程：
（1）执行初始化语句
（2）执行判断条件语句，看返回值
若是true，则继续执行；
若是false，则循环结束。
（3）执行循环体语句
（4）执行控制条件语句
（5）回到（2）继续执行语句
**/
/**
初始化语句： Entry prev = null
只是 定义参数 prev
判断条件语句：e != null
判断链表不为空
控制条件语句：prev = e, e = e.next
第一遍循环完给 初始化语句定义的参数prev 赋值
在把参数e 指向下一个链表节点
*/
for(Entry prev = null ; e != null ; prev = e, e = e.next) {
//判断这个链表节点的hash跟key是否跟传入的参数key 相等
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;//修改次数+1
//执行链表删除操作
if (prev != null) {
prev.next = e.next;//把记录了上一个节点prev 的next指向当前要删除的节点的下一个节点
} else { //等于 false 说明匹配到了第一个节点，直接把首节点的下一个节点赋值给数组即可
tab[index] = e.next;//
}
count--;//HashTable长度-1
//临时变量oldValue接收value并返回
V oldValue = e.value;
e.value = null;//等于null gc回收
return oldValue;
}
}
return null;//HashTable没有这个key返回null
}