分析 java.util.Hashtable 源码

概述

基于J11.这类已被淘汰。如果使用线程安全，则使用它ConcurrentHashMap，如果线程不安全，则使用HashMap。仅与HashMap进行比较

结构和依赖关系

HashTable 结构如下图所示

当遇到有同样 Hash 冲突问题(链接法，通过链表解决冲突问题)将通过链表来解决。

随着冲突的增加，链接法会导致查询时间越来越慢。当散列算法特别差时，会出现恶劣情况；元素总数n以及槽位数m中的k相等，如下图所示

在这种情况下，搜索的时间是 $O(1 a)$ 其中 $O(1)$ 为hash

从下图可以看出 Hashtable 与其他类的关系

classDiagram direction BT class Cloneable { <<Interface>> } class Dictionary~K, V~ class Hashtable~K, V~ class Map~K, V~ { <<Interface>> } class Serializable { <<Interface>> } Hashtable~K, V~ ..> Cloneable Hashtable~K, V~ --> Dictionary~K, V~ Hashtable~K, V~ ..> Map~K, V~ Hashtable~K, V~ ..> Serializable

实际上，Hashtable每个元素都是一个元素Map.Entry<k,v>，Entry是Map的集合形式 用来遍历Map。Hashtable实现了该接口，Hashtable它是一个集合，但存储是一个链表。

private static class Entry<K,V> implements Map.Entry<K,V> {  final int hash;  final K key;    V value;    Entry<K,V> next;    public K getKey(){...}  public V getValue(){...}  public V setValue(V value){...} }

Hashtable注意几个关键字段：

private int threshold; // 极限长度、容量*负载因子 private float loadFactor; // 负载因子 该值默认为0.75

如果把Hashtbale与桶相比，负载因子表明一桶水可以装半桶、满桶或四分之一桶。

负载因子越大，能装的水就越多。负载因子总是与临界值相匹配。临界值用于表示何时扩容，即如果水装不下，必须更换较大的瓶装水。Hashtable每次扩容都会扩大到原来的两倍大。

负载因子是时间和空间的平衡。当负载因子增加足够的空间时，不需要总是扩大容量，使用更多的空间；如果负载因子小，需要不断扩大容量，但空间使用较少。

通过一个put方法来了解

下图简述了put的流程

计算位置

Hashtable计算位置特别简单，即简单的除法

Entry<?,?> tab[] = table; int hash = key.hashCode();   int index = (hash & 0x7FFFFFFF) % tab.length;

插入元素

首先，Hashtable了解现在put操作是更新旧值还是插入新值。如果更新旧值，则返回旧值并更新它

以下是不断搜索链表的过程

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

如果是插入新值，则创建一个新值Entry并在容量不超过临界值的情况下插入：

Entry<K,V> e = (Entry<K,V>) tab[index];   tab[index] = new Entry<>(hash, key, value, e);   count  ;   modCount  ;

当然，如果容量超过临界值，则需要扩大容量

扩容

if (count >= threshold) {       // 扩容，并重新计算每个元素hash值     rehash();     // 扩容后插入新值     tab = table;       hash = key.hashCode();       index = (hash & 0x7FFFFFFF) % tab.length;   }

扩容的关键是rehash()该方法也很简单，只有以下步骤：

1. 计算新的临界值
2. 超过最大可接受容量的新临界值不再扩大
3. 创建一个新table(新桶)
4. 逐个计算hash并重新装填table

线程安全性

Hashtable线程安全，主要通过添加同步锁来解决，如put方法

public synchronized V put(K key, V value) {...}

但这种性能相对较低，不能保证组合方法的线程安全。

例如get和remove

public V getAndRemove(Object o){  V v = get(o);  remove(o);  return v; }

这不能保证线程的安全