java基础——HashMap、HashTable、ConcurrentHashMap的区别

一、HashMap

基于哈希表实现的，每一个元素是一个key-value对，内部通过单链表解决冲突问题。容量不足时，会自动增长，并且HashMap的长度总是2的n次方。
是非线程安全的。
实现了Serializable接口，支持序列化。实现了Cloneable接口，能被克隆。

存数据的过程：

内部是一个存数据的Entry数组，HashMap采用链表解决冲突，每一个Entry本质是一个单向链表。数组中的元素是单链表的头结点。
当准备添加一个key-value时：

1. 首先通过hash(key)方法计算hash值；
2. 然后通过indexFox(hash,length)求给key-value对的位置（计算方法：先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入立案表头。）
   注意：
   1.key与value都允许null。key为null的键值对永远放在以table[0]为头结点的链表中。
   2.存储数据的数组默认是16.HashMap有自己的扩容机制：
   

变量size：记录HashMap的底层数组中一用槽的数量
变量threshold：是HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold=容量*加载因子）
变量DFEAULT_LOAD_FECTOR=0.75f：加载因子为0.75

扩容条件：

当size>threshold时，对HashMap扩容。

扩容：

是新建一个HashMap的底层数组，然后调用transfer方法，将HashMap的全部元素添加到新的HashMap中。

JDK1.7中：

new一个新的数组，然后对old元素rehash，复制加入

JDK1.8中：

改进了resize()方法：
1、首先判断是初始化还是扩容——扩容时，先看Capacity变量若未大于max，则令阈值左移1位（扩为2倍）
2、然后new一个table，将原数组放入，放入的原则是元素要么在原位置，要么是在原位置再移动2次幂的位置具体实现为——rehash元素，在高位多1bit，若为0，索引不变；若为1，地址变为原索引+oldCapaccity.

HashMap的构造方法：

注意：使用HashMap时，最好预估元素的个数，有助于提高HashMap的性能。
共有四个构造方法：设计两个重要参数：初始容量和加载因子，默认是16和0.75.（加载因子越大，对空间的利用更充分，但是查找效率会低，一般不要修改加载因子）
构造方法会将实际容量设为不小于指定的容量的2的次方的一个数，且最大值不能超过2的30次方。

二、Hashtable

1、同样基于哈希表实现，每个元素同样是一个key-value对。内部也是通过单链表解决冲突问题。容量不足时，会自动扩容
2、是JDK1.0引入的类，是线程安全的，用于多线程环境中
3、同样实现了Serializable接口，支持序列化，实现了Cloneable接口，能被克隆

HashMap与Hashtable的区别：

1、继承的父类不同
HashMap继承AbstractMap类，Hashtable继承自Dictionary类。都实现了Map接口
2、线程安全性不同
HashMap不是线程安全的——在多线程下使用时，需要增加同步处理。可以通过对自然封装该映射的对象进行同步操作来实现，如：
在创建时完成这一操作

Map m=Collections.synchronizedMap(new HashMap(...));

Hashtable中的方法是Synchronized的，所以是线程安全的。
3、是否提供contains方法
HashMap用containsValue和containsKey替换了contains方法。
HashTable三个contains方法都有，其中，contains与containsValue功能相同。
4、key和value是否允许null值
hashtable不允许key和value有null
hashmap允许key和value有null,只能一个键值是null，可以有多个value是null.
5、两个内部遍历方法不同
都使用了Iterator，hashtable还使用了Enumeration
6、hash值不同
hashtable直接使用对象的hashCode，求位置索引时用取模运算；
HashMap重新计算了hash值，求位置索引时用与运算，一般先用hash&0x7FFFFFFF后，再对length取模
7、内部实现使用的数组初始化和扩容方式不同
HashMap默认是16，要求扩容一定是2 的整数次幂，扩容时变为原来容量的2倍
hashtable默认是11，不要求一定是2的整数次幂，扩容时变为原来容量的2倍加1

HashMap为什么是线程不安全的？

底层是一个哈希表，当发生冲突时，HashMap采用链表的方式来解决的，在对应的数组位置存放链表的头结点。新加入的结点会从头结点加入。
在多线程访问时：

1）在put操作时，会调用addEntry方

两个线程同时读同一个数组位置调用addEntry方法时，两个线程会同时得到现在的头结点。然后线程A写入新结点，线程B也写入新结点，那么会造成B操作覆盖A操作，A写入的新结点丢失

2）删除键值对

多个线程同时操作一个数组位置时，也都会先获取现在状态下的头结点，之后再把结果写回到数组位置，但是其他线程可能已经修改了这个位置，此时就会覆盖其他线程的修改

3）扩容时

当多个线程同时检测到一个HashMap需要扩容时，会同时resize，此时一个线程可能会覆盖其他线程resize的结果

三、ConcurrentHashMap

ConcurrentHashMap继承AbstractMap，实现ConcurrentMap、Serializable接口

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

3.1 JDK6/7中主要使用锁段（segment）来实现减小锁粒度，把hashmap分割成若干个锁段。

1）put时：
需要锁住Segment
2）get时：
不需要加锁，使用volatile来保证可见性

3.2 JDK7中，当长度过长碰撞会很繁琐，链表的增改删查会影响性能。

JDK8中完全重写了CurrentHashMap，主要变化有：
1、将Segment改为node，来减小锁粒度
2、设计了MOVED状态，当resize中，线程2put时，会帮助resize
3、使用了三个CAS操作来确保node的一些操作的原子性，代替锁
4、sizeCtl的不同值来代表不同含义，起到控制作用

底层仍然使用数组+链表+红黑树实现

3.3 sizeCtl属性：

取值不同，代表不同的含义：
1、负数：正在进行初始化或扩容
2、-1代表正在初始化
3、-N代表有N-1个线程正在进行扩容操作
4、正数或0代表hash表没有被初始化，这个数值表示初始化或下一次进行扩容的大小

3.4 Node类：

包装了key-value键值对，与HashMap不同的是对value和next属性设置了volatile同步锁（与JDK7的Segment相同），不允许调用setValue方法直接改变Node的value，增加find方法辅助map.get()方法。

static class Node<K,V> implements Map.Entry<K,V> 
...
Node<K,V> find(int h, Object k) {
            Node<K,V> e = this;
            if (k != null) {
                do {
                    K ek;
                    if (e.hash == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                } while ((e = e.next) != null);
            }
            return null;
        }

3.5 TreeNode类：

当链表长度过长时，会转换为TreeNode。与HashMap不同的是：不是直接转换为红黑树，而是包装为TreeNode放在TreeBin对象中，有TreeBin完成红黑树的包装。带有next指针。

3.6 TreeBin类：

包装的是TreeNode结点。代替TreeNode的根结点，在实际的ConcurrentHashMap的数组中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。并带有读写锁。

3.7 三个核心方法：

    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

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

    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

U.getObjectVolatile、U.compareAndSwapObject、U.putObjectVolatile是ConcurrentHashMap中定义的三个原子操作，用于针对指定位置的节点进行操作。其中，U.compareAndSwapXXX，这个方法是利用一个CAS算法实现无锁化的修改值的操作，可以大大降低锁代理的性能消耗。
CAS算法的基本思想是：
不断地比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作，因为此时当前线程中的值已经不是最新的值。（与乐观锁、SVN的思想比较类似）。

3.8 扩容方法：

transfer：与HashMap很像，支持并发扩容，但没有加锁！！！！整个扩容操作分为两部分：
第一部分：构建一个nextTable，容量是原来的两倍，是在单线程下完成的。
第二部分：将原来table中的元素复制到nextTable中，允许多线程操作。
整体流程如下：
首先定义不允许key或value为null的情况放入。
对于每一个放入的值，首先利用spread方法对key的hashCode进行一次hash计算，由此来确定这个值在table中的位置。
如果位置是空，直接放入，不需要加锁
如果位置存在结点，发生了hash冲突——先判断节点的类型——是链表节点，则得到的结点就是hash值相同的节点组成的链表的头结点。需要依次向后遍历确定新加入的值的位置。如果有key值相同的，就更新value；否则在链表尾部插入新结点。如果加入新结点后链表长度大于8，就把链表转换成红黑树。如果这个节点的类型已经是树节点的话，直接调用树节点的插入方式插入新的值。