转载

Hashtable、HashMap、TreeMap

Hashtable、HashMap、TreeMap都是比较常见的一些Map实现，它们都是 key-value 键值对的形式存储和操作数据的容器类，同时他们的元素中不能有重复的key,一个key也只能映射一个value值。

下面我从不同的维度来分别说说这三个集合，文章中涉及到的源码版本是 JDK8

底层数据结构

Hashtable 和 HashMap 底层都是采用数组存储数据
TreeMap 底层是采用红黑树存储数据

元素特性

Hashtable

Hashtable 中存储的 key 和 value 都不能为 null ，这个从它的源码实现是可以看出来的

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    ...//省略部分
    return null;
}

这是 Hashtable 添加元素的源码实现，从开头的if判断就可以发现它的 value 值是不允许为 null 的，而它的 key 虽然没有显式判断，但是在执行 int hash = key.hashCode(); 这句代码时，如果 key 为 null 的话，代码执行到这里程序就崩了，所以从侧面也反应出 key 也不能为 null

HashMap

HashMap 中存储的 key 和 value 都允许为 null ，这个依然是从源码中看出来的。

//HashMap的put方法具体实现比较复杂代码比较多，这里我只贴出添加元素时涉及到key和value的相关代码
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
    return new TreeNode<>(hash, key, value, next);
}

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    ...
}

//TreeNode最终还是继承自Node，所以这里就不贴出TreeNode的构造函数了

从上面的几段代码中可以看到在将 key-value 添加到 HashMap 中时没有任何地方会使用它们，因此 key 和 value 都是可以为 null 的

但是一个 HashMap 中只能有一个 key 为 null ，但是可以有多个 value 为 null

TreeMap

TreeMap 中如果用户未实现 Comparator 接口，则 key 不能为 null ，如果实现了 Comparator 接口，那么 key 能否为 null 则需要根据 Comparator 接口的具体实现有关。 value 则是可以为 null 。至于原因，我们依然通过源码来寻求答案

public V put(K key, V value) {
    ...
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    } else {
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    ...
    return null;
}

通过上面的代码可以很明显的看到当成员变量 comparator 为空时( Comparator 接口未实现)，有明显的 key 的非空判断，而当实现了该接口后，这会通过 Comparator 接口的 compare 方法比较当前 key 与 TreeMap 中已存在的 key 是否相等，所以这个时候 key 能否为 nul 就跟 Comparator 接口的 compare 方法具体实现有关了。

注意这段代码

cmp = k.compareTo(t.key);
if (cmp < 0)
    t = t.left;
else if (cmp > 0)
    t = t.right;
else
    return t.setValue(value);

从上面的代码中我们还可以看出 TreeMap 的 key 是有序的，而且当前节点的 key 比其左子树节点的 key 要大，而比右子树节点的 key 要小。

有序性

Hashtable 和 HashMap 都是无序的
TreeMap 的 key 是有序的，有序的原因在前面分析其 put 源码的时候已经说过了。要注意的是这里是 key 是有序的，而不是其 value 是有序的，而且其默认是升序排序方式(深度优先搜索)，对于其排序方式，可以自定义实现 Comparator 接口来自定义排序规则

初始化和扩容方式

Hashtable

默认初始化容量为11个
容量阈值默认为当前容量的0.75倍，当集合数据大于等于阈值时就会进行扩容
不要求底层数组的容量一定为2的幂次方
扩容时会将容量变为原来的2倍加1
在初始化时就会创建底层数组

扩容时会创建一个扩容后的新数组，然后将原来数组的数据拷贝到新数组中

private void addEntry(int hash, K key, V value, int index) {
    ...
    if (count >= threshold) {//数据个数大于等于阈值时进行扩容
        rehash();
        ...
    }
    ...
}
//扩容函数
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    
    //此处将oldCapacity左移一位，即将其扩大一倍
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    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;
        }
    }
}

HashMap

默认初始化容量为16个
容量阈值默认为当前容量的0.75倍，当集合数据大于等于阈值时就会进行扩容
底层数据的容量要求一定是2的幂次方
扩容时会将容量变为原来的2倍
初始化时不会创建底层数组，而是在调用put方法添加数据时再创建底层数据

扩容时会创建一个扩容后的新数组，然后将原来数组的数据拷贝到新数组中

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//初始化创建底层数组
    ...
    if (++size > threshold)//元素个数大于等于阈值则进行扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}
//初始化或扩容函数
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {//MAXIMUM_CAPACITY=2^30
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)//此处的newCap = oldCap << 1则是进行数组扩容一倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);//重新计算新的阈值
    }
    threshold = newThr;
    ....
    return newTab;
}

TreeMap

TreeMap

线程安全性

`Hashtable`

其方法都采用了 synchronized 修饰，因此是线程安全的，不会出现两个线程同时对数据进行操作的情况，它保证了线程安全性。但也因为这样导致其在多线程环境下使用此集合效率低下，因为一个线程访问其同步方法时，其他访问 Hashtable 的线程都会处于阻塞状态，现在已不推荐使用此集合。

`HashMap`

HashMap 的方法没有采用 synchronized 修饰，所以是非线程安全的，在程序中任一时刻可能会存在多个线程同时修改其数据，从而导致数据不一致。

在多线程环境下，我们可以使用下面两种方式使用 HashMap

使用 Collections.synchronizedMap() 方法将 HashMap 转换为线程安全的 SynchronizedMap 包装类,其内部也是使用 synchronized 来达到同步效果，只不过此时锁住的是一个 Object 类型的成员变量,和锁住 HashMap 对象本身效果是一样，效率也比较低下，仅仅适合用在并发度不高的情景。
使用 ConcurrentHashMap 集合，相较于 Hashtable 锁住的是对象整体， ConcurrentHashMap 基于 lock 实现锁分段技术。首先将 Map 存放的数据分成一段一段的存储方式，然后给每一段数据分配一把锁，当一个线程占用锁访问其中一个段的数据时，其他段的数据也能被其他线程访问。 ConcurrentHashMap 不仅保证了多线程运行环境下的数据访问安全性，而且性能上有长足的提升

`TreeMap`

HashMap 的方法没有采用 synchronized 修饰，所以 TreeMap 也是非线程安全的。

在多线程环境下建议使用 ConcurrentSkipListMap 代替

HashMap的哈希冲突

HashMap 采用 链地址法 来解决哈希冲突，对哈希冲突或链地址法不了解的同学请参考我的另外一篇文章 Hash冲突解决方法

但是在 HashMap 中对链地址法采用了一点点变化，对于哈希冲突导致出现同义词元素显示采用单链表存放，当这个链表大小超过一个阈值(TREEIFY_THRESHOLD=8)且 HashMap 的大小大于等于另一个容量阈值(MIN_TREEIFY_CAPACITY = 64),就会把这个单链表该造为树形结构。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //此处判断链表的大小是否超过阈值
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                ...
            }
        }
        ...
    }
   ...
    return null;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //HashMap的元素大小大于等于MIN_TREEIFY_CAPACITY则将该单链表改造成红黑树
        //树改造逻辑
    }
}

为什么要改造呢，我的理解是这样的：