JDK集合源码之HashTable解析-阿里云开发者社区

对于HashMap源码剖析，可以参考：JDK集合源码之HashMap解析(上) 以及JDK集合源码之HashMap解析(下) ，HashMap底层红黑树实现(自己实现一个简单的红黑树)

1. 二者继的承体系有区别

HashTable

HashMap

从图中可以对比得出，二者都是源于Map口接口，都实现Cloneable和Serializable接口，二者都可以克隆和序列化。但HashMap的父类是AbstractMap，HashTable父类是Dictionary。

Dictionary 类是一个已经被废弃的类（见其源码中的注释）。父类被废弃，自然其子类Hashtable也用的比较少了。

2. HashTable比HashMap多提供了elments() 和contains() 两个方法

elments()方法继承自父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。

contains()方法判断该Hashtable中是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue()就只是调用了一下contains() 方法。

// 判断HashTable中是否存在value，存在返回true，否则返回false
public synchronized boolean contains(Object value) {
    if (value == null) {
        throw new NullPointerException();
    }
    Entry<?,?> tab[] = table;
    for (int i = tab.length ; i-- > 0 ;) {
        for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
            if (e.value.equals(value)) {
                return true;
            }
        }
    }
    return false;
}
public boolean containsValue(Object value) {
    return contains(value);
}

3. 二者对Null key 和Null value的支持不同

Hashtable中的Key 和 Value 均不可以为NULL，我们可以从其put()方法中得出：

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不可以为null，因为当key为null时候，null调用hashCode()会报空指针异常
    int hash = key.hashCode();
    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;
}

HashMap中，NULL可以作为键，且这样的键只能存在一个。可以有一个或多个键所对应的值为NULL。当get()方法返回NULL值时，可能是 HashMap中没有该键，也可能使该键所对应的值为NULL。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。

4. HashMap线程不安全，HashTable线程安全

Hashtable是线程安全的，它的每个方法中都加入了synchronize关键字。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步

HashMap是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题。使用HashMap时就必须要自己增加同步处。

虽然HashMap不是线程安全的，但是它的效率会比Hashtable要好很多。这样设计是合理的。在我们的日常使用当中，大部分时间是单线程操作的。HashMap把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

5. 二者初始容量大小和每次扩充容量大小的不同

Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。

HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。

创建时，如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说Hashtable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小。

之所以会有这样的不同，是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。HashMap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以HashMap为解决这问题，又对hash算法做了一些改动。这从而导致了Hashtable和HashMap的计算hash值的方法不同。

6. 二者计算hash值的方法不同

为了得到元素的位置，首先需要根据元素的KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。

Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数法来获得最终的位置。

Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。

HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。

HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高。

为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2的幂次方带来的效率提升给抵消掉。

HashTable源码

HashTable的属性

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

HashTable构造函数

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，获得大小为initialCapacity的table数组
    table = new Entry<?,?>[initialCapacity];
    // 计算阀值 ---> threshold的值=“容量*加载因子”
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}
// 空参构造方法，初始容量为11
public Hashtable() {
    this(11, 0.75f);
}
// 根据传入的Map集合直接初始化HashTable,容量为传入Map集合容量大小*2与11进行比较，取值较大者
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}
private int hash(Object k) {
     return hashSeed ^ k.hashCode();
}

HashTable几个常用成员方法

1. put方法

// 获取synchronized锁
public synchronized V put(K key, V value) {
    // 如果value是空抛出异常
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    // 计算key的哈希值和index
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 遍历对应index位置的链表
    for(; entry != null ; entry = entry.next) {
        // 如果key 已经存在，则更新数据
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // 增加新Entry元素
    addEntry(hash, key, value, index);
    return null;
}

步骤

1.获取synchronized锁。

2.put方法不允许null值，如果发现是null，则直接抛出异常。

3.计算key的哈希值和index

4.遍历对应位置的链表，如果发现已经存在相同的hash和key，则更新value，并返回旧值。

5.如果不存在相同的key的Entry节点，则调用addEntry方法增加节点。

2. 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 exceeded
        // 重新构建桶数组（相当于扩容方法），并对数组中所有键值对重哈希，耗时
        rehash();
        tab = table;
        // 根据key，获取hash值
        hash = key.hashCode();
        // 取摸运算（相当于HashMap定位桶的槽位）
        // int index = (hash & 0x7FFFFFFF) % tab.length; ？？？
        // （前31一个1代表数值，在计算机中整型最高位（32位）是符号位 0代表正数，1代表负数）
        // 0x7FFFFFFF: 16进制表示的整型,是整型里面的最大值
        // 0x7FFFFFFF: 0111 1111 1111 1111 1111 1111 1111 1111：除符号位外的所有1
        // (hash & 0x7FFFFFFF) 将产生正整数
        // (hash & 0x7FFFFFFF) % tab.length 将在标签长度的范围内
        // 所有hashtable采用奇数导致的hash冲突会比较少，采用偶数会导致的冲突会增多
        // h & (length-1); hashmap采用相与的方法，所有采用2的幂次方的长度会导致的冲突比较少
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // Creates the new entry.
    @SuppressWarnings("unchecked")
    // 获取index槽位的桶中的Entry链表,头节点是e
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // 生成一个新结点, 将新结点插到链表首部，其下一个结点是e
    tab[index] = new Entry<>(hash, key, value, e);
    // 有效元素数量++
    count++;
}

步骤

当前容量超过阈值,需要扩容
生成一个新结点, 将新结点插到链表首部

3. rehash方法(扩容方法)

相当于hashmap中的resize()方法

protected void rehash() {
    // 获取当前table数组的容量（数组长度）
    int oldCapacity = table.length;
    // oldMap: 当前table数组
    Entry<?,?>[] oldMap = table;
    // 扩容扩为原来的两倍+1  ---> 即：扩容为原来的 2n + 1 这样可以确保容量是奇数
    // 奇数有利于index = (hash & 0x7FFFFFFF) % tab.length 求桶位的时候减少hash冲突
    // 这种方式类似于HashMap： hash & (tab.length-1),确保容量为2的幂次方，可以减少hash冲突
    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;
    }
    // newMap：新table数组
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    // HashTable结构修改次数++
    modCount++;
    // 计算下一次rehash的阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    // 把旧哈希表的键值对重新哈希到新哈希表中去（双重循环，耗时！）
    // 这个方法类似于HashMap扩容后，将旧数组数据赋给新数组，
    // 在HashMap中会将其旧数组每个桶位进一步‘打散'，放置到新数组对应的桶位上（有一个重新计算桶位的过程）
    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;
        // 根据新table数组容量newCapacity重新计算桶位
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            // 链表放入该桶中
            newMap[index] = e;
        }
    }
}

步骤

数组长度增加一倍（如果超过上限，则设置成上限值）。
更新哈希表的扩容门限值。
遍历旧表中的节点，计算在新表中的index，插入到对应位置链表的头部。

4. get方法

public synchronized V get(Object key) {// 根据键取出对应索引  
      Entry tab[] = table;  
      int hash = hash(key);// 先根据key计算hash值  
      int index = (hash & 0x7FFFFFFF) % tab.length;// 再根据hash值找到索引  
      for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {// 遍历entry链  
          if ((e.hash == hash) && e.key.equals(key)) {// 若找到该键  
              return e.value;// 返回对应的值  
          }  
      }  
      return null;// 否则返回null  
  }

骤

先获取synchronized锁。
计算key的哈希值和index。
在对应位置的链表中寻找具有相同hash和key的节点，返回节点的value。
如果遍历结束都没有找到节点，则返回null。

5. remove方法

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    // 计算key的哈希值和index
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        // 遍历对应位置的链表，寻找待删除节点
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
        // 更新前驱节点的next，指向e的next
           if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            // 返回待删除节点的value值
            return oldValue;
        }
    }
    // 如果不存在，返回null
    return null;
}

步骤

先获取synchronized锁。
计算key的哈希值和index。
遍历对应位置的链表，寻找待删除节点，如果存在，用e表示待删除节点，pre表示前驱节点。如果不存在，返回null。
更新前驱节点的next，指向e的next。返回待删除节点的value值。

JDK集合源码之HashTable解析

1. 二者继的承体系有区别

3. 二者对Null key 和Null value的支持不同

HashTable源码

HashTable的属性

HashTable构造函数

HashTable几个常用成员方法

1. put方法

步骤

3. rehash方法(扩容方法)

步骤

4. get方法

骤

5. remove方法

步骤

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像