HashMap与HashTable，ConcurrentHashMap的区别

主要从底层数据结构，线程安全，执行效率，是否允许Null值，初始容量及扩容，hash值计算来进行分析。

1.底层数据结构

    transient Node<K,V>[] table; //HashMap
    
    transient volatile Node<K,V>[] table;//ConcurrentHashMap
    
    private transient Entry<？,？>[] table;//HashTable

HashMap=数组+链表+红黑树

HashMap的底层数据结构是一个数组+链表+红黑树，数组的每个元素存储是一个链表的头结点，链表中存储了一组哈希值冲突的键值对，通过链地址法来解决哈希冲突的。为了避免链表长度过长，影响查找元素的效率，当链表的长度>8时，会将链表转换为红黑树，链表的长度<6时，将红黑树转换为链表(但是红黑树转换为链表的时机不是在删除链表时，而是在扩容时，发现红黑树分解后的两个链表<6，就按链表处理，否则就建立两个小的红黑树，设置到扩容后的位置)。之所以临界点为8是因为红黑树的查找时间复杂度为logN，链表的平均时间查找复杂度为N/2，当N为8时，logN为3，是小于N/2的，正好可以通过转换为红黑树减少查找的时间复杂度。

Hashtable=数组+链表

Hashtable底层数据结构跟HashMap一致，底层数据结构是一个数组+链表，也是通过链地址法来解决冲突，只是链表过长时，不会转换为红黑树来减少查找时的时间复杂度。Hashtable属于历史遗留类，实际开发中很少使用。

ConcurrentHashMap=数组+链表+红黑树

ConcurrentHashMap底层数据结构跟HashMap一致，底层数据结构是一个数组+链表+红黑树。只不过使用了volatile来进行修饰它的属性，来保证内存可见性(一个线程修改了这些属性后，会使得其他线程中对于该属性的缓存失效，以便下次读取时取最新的值)。

2.线程安全

HashMap 非线程安全

HashMap是非线程安全的。（例如多个线程插入多个键值对，如果两个键值对的key哈希冲突，可能会使得两个线程在操作同一个链表中的节点，导致一个键值对的value被覆盖）

HashTable 线程安全

HashTable是线程安全的，主要通过使用synchronized关键字修饰大部分方法，使得每次只能一个线程对HashTable进行同步修改，性能开销较大。

ConcurrentHashMap 线程安全

ConcurrentHashMap是线程安全的，主要是通过CAS操作+synchronized来保证线程安全的。

CAS操作

往ConcurrentHashMap中插入新的键值对时，如果对应的数组下标元素为null，那么通过CAS操作原子性地将节点设置到数组中。

//这是添加新的键值对的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
...其他代码
  if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) 				break; // 因为对应的数组下标元素为null，所以null作为预期值，new Node<K,V>(hash, key, value, null)作为即将更新的值，只有当内存中的值与即将预期值一致时，才会进行更新，保证原子性。
  }
...其他代码
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

synchronized锁

往ConcurrentHashMap中插入新的键值对时，如果对应的数组下标元素不为null，那么会对数组下标存储的元素(也就是链表的头节点)加synchronized锁， 然后进行插入操作，

Node<K,V> f = tabAt(tab, i = (n - 1) & hash));
synchronized (f) {//f就是数组下标存储的元素
    if (tabAt(tab, i) == f) {
        if (fh >= 0) {
            binCount = 1;
            for (Node<K,V> e = f;; ++binCount) {
                K ek;
                if (e.hash == hash &&
                    ((ek = e.key) == key ||
                     (ek != null && key.equals(ek)))) {
                    oldVal = e.val;
                    if (!onlyIfAbsent)
                        e.val = value;
                    break;
                }
                Node<K,V> pred = e;
                if ((e = e.next) == null) {
                    pred.next = new Node<K,V>(hash, key,
                                              value, null);
                    break;
                }
            }
        }
        else if (f instanceof TreeBin) {
            Node<K,V> p;
            binCount = 2;
            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                           value)) != null) {
                oldVal = p.val;
                if (!onlyIfAbsent)
                    p.val = value;
            }
        }
    }
}

3.执行效率

因为HashMap是非线程安全的，执行效率会高一些，其次是ConcurrentHashMap，因为HashTable在进行修改和访问时是对整个HashTable加synchronized锁，所以效率最低。

4.是否允许null值出现

HashMap的key和null都可以为null，如果key为null，那么计算的hash值会是0，最终计算得到的数组下标也会是0，所以key为null的键值对会存储在数组中的首元素的链表中。value为null的键值对也能正常插入，跟普通键值对插入过程一致。

static final int hash(Object key) {
	int h;
	return (key == null) ？ 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashTable的键和值都不能为null，如果将HashTable的一个键值对的key设置为null，因为null值没法调用hashCode()方法获取哈希值，所以会抛出空指针异常。同样value为null时，在put方法中会进行判断，然后抛出空指针异常。

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        Entry<？,？> tab[] = table;
        int hash = key.hashCode();
        ...其他代码
}

ConcurrentHashMap的键和值都不能为null,在putVal方法中会进行判断，为null会抛出空指针异常。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    ...其他代码
}

5.初始容量及扩容

不指定初始容量

如果不指定初始容量，HashMap和ConcurrentHashMap默认会是16，HashTable的容量默认会是11。

不指定初始容量

如果制定了初始容量，HashMap和ConcurrentHashMap的容量会是比初始容量稍微大一些的2的幂次方大小，HashTable会使用初始容量，

扩容

扩容时，HashMap和ConcurrentHashMap扩容时会是原来长度的两倍，HashTable则是2倍加上1.

6.hash值计算

HashTable会扩容为2n+1，HashTable之所以容量取11，及扩容时是是2n+1，是为了保证 HashTable的长度是一个素数，因为数组的下标是用key的hashCode与数组的长度取模进行计算得到的，而当数组的长度是素数时，可以保证计算得到的数组下标分布得更加均匀

public synchronized V put(K key, V value) {
         ...其他代码
        // Makes sure the key is not already in the hashtable.
        Entry<？,？> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        ...其他代码
}

HashMap和ConcurrentHashMap的hash值都是通过将key的hashCode()高16位与低16位进行异或运算(这样可以保留高位的特征，避免一些key的hashCode高位不同，低位相同，造成hash冲突)，得到hash值，然后将hash&(n-1)计算得到数组下标。（n为数组的长度，因为当n为2的整数次幂时，hash mod n的结果在数学上等于hash&(n-1)，而且计算机进行&运算更快，所以这也是HashMap的长度总是设置为2的整数次幂的原因）

//HashMap计算hash值的方法
static int hash(Object key) {
    int h;
    return (key == null) ？ 0 : (h = key.hashCode()) ^ (h >>> 16); 
}
//ConcurrentHashMap计算hash值的方法 
static  int spread(int h) {//h是对象的hashCode
    return (h ^ (h >>> 16)) & HASH_BITS;// HASH_BITS = 0x7fffffff;
}