一、HashTable

   1.1 简介

   1.2 类图

   1.3 源码分析

   1.3.1 属性与链表节点类

/**
 * 一个单向链表数组，哈希表的"key-value键值对"都是存储在Entry数组中的。
 */
private transient Entry[] table;

/**
 * 保存键值对数量
 */
private transient int count;

/**
 * Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"
 */
private int threshold;

/**
 *加载因子
 */
private float loadFactor;

/**
 * 用来实现fail-fast机制的
 */
private transient int modCount = 0;

//HashTable的节点，用来存储键值对。
//Entry是一个单向链表
private static class Entry implements Map.Entry {
//哈希值
    int hash;
    //存储的key和值value
    final K key;
    V value;
    // 指向的下一个Entry，即链表的下一个节点
    Entry next;

    protected Entry(int hash, K key, V value, Entry next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }
}

   1.3.2 put()操作

  put方法的工作原理是用key和hash计算出bucketIndex，在通过bucketIndex从数组中快速找到链表第一个节点位置，然后遍历这个链表直到找到相应的hash和key。如果位置上存在元素，则直接更新节点上的旧value值，并返回旧值。如果不存在，则将节点Entry存放到bucketIndex位置上。

//往HashTable中添加元素，多线程下put操作是安全的
public synchronized V put(K key, V value) {
    // HashTable不能插入null元素
    if (value == null) {
        throw new NullPointerException();
    }

    //计算出bucketindex，然后通过bucketindex来查找数组中的位置。如果位置上已经存在元素，则直接替换更新value
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }
    
    modCount++;
    //当容器中的元素数量超过阈值时，重新分配容器大小
    if (count >= threshold) {
        //
        rehash();

        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    //创建一个新节点
    Entry e = tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    return null;
}

   1.3.2 rehash()操作

//重新分配HashTable的空间大小，并将旧空间元素拷贝到新空间
protected void rehash() {
//定义一个oldMap节点存储旧空间，为下一步拷贝操作
    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;
    }
    Entry[] newMap = new Entry[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    boolean currentAltHashing = useAltHashing;
    useAltHashing = sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = currentAltHashing ^ useAltHashing;

    table = newMap;
    //将旧空间元素拷贝到新创建的空间
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry old = oldMap[i] ; old != null ; ) {
            Entry e = old;
            old = old.next;

            if (rehash) {
                e.hash = hash(e.key);
            }
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}

   1.3.3 get()操作

//从HashTable中查找key对应的值，再在线程下它也是安全的
public synchronized V get(Object key) {
    Entry tab[] = table;
    int hash = hash(key);
    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 e.value;
        }
    }
    return null;
}

   1.3.4 remove()操作

//移除指定位置元素，多线程下是安全的
public synchronized V remove(Object key) {
    Entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            //将prev的下一个节点指向被移除节点的下一个节点
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}