Map接口
Map是java集合中很重要的一个接口，我们在开发中经常用到，Map接口有一个特性
- 无序
- 不可重复
- key-value数据结构
常用的实现类有：Hashtable，HashMap，ConcurrentHashMap
这篇文章来聊聊Hashtable。
Hashtable
Hashtable是Map接口的一个实现类，但是我们使用的并不多，因为它使用synchronized关键字保证了线程安全，在并发场景下不会出现线程安全的问题，但是性能很低，所以并发场景下我们会使用ConcurrentHashMap来代替Hashtable。Hashtable底层使用Hash+链表 的数据结构来存储数据，我们一起来分析一下。
数据结构
Hashtable
这就是Hashtable的数据结构，这就是我们常说的Hash桶结构，Hashtable默认初始化11个数组长度的Hash桶（当然我们也可以通过构造函数指定），然后我们往容器中put数据的时候，根据key计算出来一个index值，这个值表示存放在Hash桶的哪个位置，如果当前位置为空，那么生成一个Entry对象，放入该位置，如果有值，则生成一个Entry对象，插入链表头结点的位置，接下来我们一步一步分析吧。
源码分析
重要属性
// 就是我们说的Hash桶
private transient Entry<?,?>[] table;
// 当前容器中的数据大小 也就是size
private transient int count;
// 负载因子，默认0.75
private float loadFactor;
// 扩容的阈值（capacity * loadFactory）
private int threshold;
Entry对象
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
public String toString() {
return key.toString()+"="+value.toString();
}
}
Entry是Hashtable的一个静态内部类，容器中每一个条数据对应一个Entry。
构造方法
// 无参构造方法，默认初始化Hash桶大小为11，负载因子为0.75
public Hashtable() {
this(11, 0.75f);
}
// 可设定容器大小，默认负载因子为0.75
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// 可在初始化容器的时候将数据写入容器中，如果数据大小小于11，这初始化容器大小为11，反之初始化大小为数据的2倍，负载因子还是0.75
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
// 后续解析
putAll(t);
}
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);
}
Hashtable提供了三个构造方法，默认的容器大小为11，负载因子为0.75；容器大小可以指定，也可在构造方法中传入要存储的数据，然后根据存储数据的大小初始化容器大小。
put(K key, V value)
容器为我们提供put方法将数据写入容器中，源码如下：
// 使用synchronized修饰，保证线程安全
public synchronized V put(K key, V value) {
// 不允许value为null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
// 计算key的hash值，这里的key也不能为空，否者抛出空指针异常
int hash = key.hashCode();
// 这里的0x7FFFFFFF是一个16进制表示的整型，是整型里最大值
// hash & 0x7FFFFFFF 位于运算主要是为了得到一个正整数
// 最终结果index就是hash槽的数组下标，也就是新增的数据存放的位置
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 取出hash槽中是否有数据，有则存在hash冲突，使用链表地址法解决
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 说明这个槽上有数据啦
for(; entry != null ; entry = entry.next) {
// 因为hash槽里存放的是一个链表，所以可以循环比较存放的key是否存在，存在者替换value值
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 走到这里，说明hash槽里没有数据或者存在存在数据但是没有相同的key
addEntry(hash, key, value, index);
return null;
}
/**
* 将数据写入容器中
* @param hash key的hash值
* @param key
* @param value key的hash值
* @param index hash槽的下标
*/
private void addEntry(int hash, K key, V value, int index) {
modCount++;
// 先获取hash数组
Entry<?,?> tab[] = table;
// 容器中的数据是否大于等于扩容的阈值
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
// 进行扩容
rehash();
tab = table;
// 扩容完成后重新计算hash值和index值
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
// 将数据写入hash数组的头
tab[index] = new Entry<>(hash, key, value, e);
// 容器数据量+1
count++;
}
/**
* 扩容
*/
protected void rehash() {
// 记录原始容器的容量
int oldCapacity = table.length;
// 记录原始容器
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 计算扩容后的容器大小，进行位运算（位运算cpu直接支持，运算快）
// 新容量=旧容量*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;
}
// 创建一个新的hash数组
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;
}
}
}
以上就完成数据的写入
image.png
流程如下：
- 根据计算key的hash值，然后 (hash & 0x7FFFFFFF) % tab.length计算hash数组的下表
1）0x7FFFFFFF是一个16进制表示整型最大的数，转成二进制为0111 1111 1111 1111 1111 1111 1111 1111，前右边第一位表示符号位，0表示整数，1表示负数，（&运算规则，0&0=0；0&1=0；1&0=0；1&1=1），所以hash & 0x7FFFFFFF主要是为了计算出一个正整数；为什么我们不通过Math.abs求绝对值来获取正整数呢？如果当hash被计算出来-2^31，正整数中没有32位去表示这个最小负数（因为java中int类型存储长度为32bit，符号位占用了1bit，所以可以用来表示int的数目的范围是31位），所以还是会返回一个负数，也就是绝对值返回一个负数。 - 当hash数组的位置中存在数据，查找这个hash数组位置上是否存在key一样的数据，如果有，则将value替换，到此结束。
- 如果hash数组对应位置上没有存在数据，或者存在位置，但是不存在相同的key，那么就会走addEntry方法
1） 首先判断是的需要扩容count >=threshold，如果成立，则开始扩容
扩容完成后重新计算hash值和index值
2） 在指定hash的index的位置插入新的entity到table[index]的位置，原来table[index]上的数据通过链表关联起来。
获取数据get(key)方法
/*
* get方法上也加了synchronized 关键字，所以获取数据的时候不能插入数据
*/
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
// 计算key的hash值
int hash = key.hashCode();
// 根据hash值计算index值
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
// 遍历链表，通过equals方法比较，得到结果
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
相比put方法，get方法简单很多，流程都是先得到table的index，然后通过equals方法比较key是否相同，然后得到结果。
其他的方法不做分析，都很简单，而且容易看懂，我们主要分析get和put方法就好了。
当我们看源码的时候，基本每个方法都会出现synchronized关键字，所以Hashtable能保证线程安全，但是带来的问题就是性能降低，所以高并发下我们一般不会使用。
源码中重复率比较高的代码
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
不管插入数据，获取数据还是删除数据，都是先要找到数据所在的位置才能进行操作，所以以上两行代码在Hashtable中随处可见。
总结
- Hashtable默认初始化容量大小为10，负载因子为0.75（容量可调整，负载因子不能调整）
- 方法使用synchronized修饰保证线程安全
- 当count>=threshold时需要扩容，扩容为原来的两倍+1
- 当发生hash冲突时，采用链表地址法来解决hash冲突的问题，采用头插法插入数据
下一篇我们分析HashMap，HashMap和Hashtable有很多相同的地方，但HashMap的性能更高一些，我们思考一个问题，当哈希冲严重时，会产生什么问题，假如插入的数据都落在table[0]的位置上，那么这个位置上的链表长度不断变大，会造成性能降低，所以我们需要一个很好的哈希算法让哈希冲突降低（这也就是在hasMap中为什么要求容量为2的次幂，以及默认负载因子为0.75的原因），数据结构上也需要做调整，比如HashMap中就引入和红黑树。
以上就是我对Hashtable的分析，如有错误，烦请支出更正，一起学习进步。
我是一个爱看源码的老谢，知道越多，不知道的越多。
