文章首发csdn博客地址：https://blog.csdn.net/u013277209?viewmode=contents
一：整体实现
- HashTable和HashMap实现大致相同，都是基于哈希表来实现的，数组+链表的形式（和HashMap有稍微的区别，HashMap加入了红黑树），它存储的内容是键值对(key-value)映射。
- Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。Dictionary是一个过时的键值对映射的抽象类，jdk已经不建议使用，新的实现应该实现Map接口，而不是扩展这个类。
- HashTable方法加了synchronized关键字，所以是线程安全的。
二：重要字段
private transient Entry<?,?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount = 0;
table实现哈希表的数组结构，数组长度最小为1，默认为11，里面存储着Entry
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值，用于定位数组索引位置
final K key;//键
V value;//值
Entry<K,V> next;//链表下一个元素
}
Entry是HashTable的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。
count是HashTable中实际存在的键值对数量，而modCount字段主要用来记录HashTable内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
loadFactor为负载因子(默认值是0.75)，threshold是HashTable所能容纳的最大数据量的Entry(键值对)个数。threshold = length * loadFactor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
threshold就是在此loadFactor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新rehash(扩容)，扩容后的HashTable容量是之前容量的两倍+1。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
三：扩容机制
当前键值对的数量count >= threshold时会触发扩容。
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
//新容量=旧容量 * 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;
}
//新建一个size = newCapacity的数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
//重新计算阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
//将原来的元素拷贝到新的HashTable中，对数组链表数据进行重新 hash index 计算，
//rehash之后会使得最早插入的数据回到链表的第一位
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中,并且对每个元素根据hash值从新计算下标，这个过程是比较消耗时间的。
四：put方法
put方法的整个处理流程：计算key的hash值，根据hash值获得key在table数组中的索引位置，然后迭代该key处的Entry链表（我们暂且理解为链表），若该链表中存在一个这个的key对象，那么就直接替换其value值即可，否则在将改key-value节点插入该index索引位置处
public synchronized V put(K key, V value) {
// 值不能为空
if (value == null) {
throw new NullPointerException();
}
//计算key的hash值，确认在table[]中的索引位置
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
//迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
//如果不存在，则创建entry加入hash表中
addEntry(hash, key, value, index);
return null;
}
//在指定索引位置加入key-value键值对
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;
}
// 创建entry并加入到链表的头
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
五：get方法
get方法比较简单，处理过程就是计算key的hash值，判断在table数组中的索引位置，然后迭代链表，匹配直到找到相对应key的value,若没有找到返回null。
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;
}
六：HashTable和HashMap区别
- HashMap线程不安全，HashTable是线程安全的。HashMap内部实现没有任何线程同步相关的代码，所以相对而言性能要好一点。如果在多线程中使用HashMap需要自己管理线程同步。HashTable大部分对外接口都使用synchronized包裹，所以是线程安全的，但是性能会相对差一些。
- 二者的基类不一样。HashMap派生于AbstractMap，HashTable派生于Dictionary。它们都实现Map, Cloneable, Serializable这些接口。AbstractMap中提供的基础方法更多，并且实现了多个通用的方法，而在Dictionary中只有少量的接口，并且都是abstract类型。
- key和value的取值范围不同。HashMap的key和value都可以为null，但是HashTable key和value都不能为null。对于HashMap如果get返回null，并不能表明HashMap不存在这个key，如果需要判断HashMap中是否包含某个key，就需要使用containsKey这个方法来判断。
- 算法不一样。HashMap的initialCapacity为16，而HashTable的initialCapacity为11。HashMap中初始容量必须是2的幂,如果初始化传入的initialCapacity不是2的幂，将会自动调整为大于出入的initialCapacity最小的2的幂。HashMap使用自己的计算hash的方法(会依赖key的hashCode方法)，HashTable则使用key的hashCode方法得到。
网友评论