Hashtatble、HashMap、ConcurrentHashMap区别

Hashtable命名没有遵循驼峰命名，HashMap命名遵循了驼峰命名。

Hashtable继承的是Dictionary类，HashMap继承的是AbstractMap类。

Hashtable在多线程的情况下是线程安全的，因为Hashtable在数据操作的方法上都加上了synchronized关键字。

 //Hashtable的put方法
public synchronized V put(K key, V value) 

HashMap没有实现线程安全，在多线程的状态下可能会造成环形链表和轮训。

Hashtable的默认初始化容量为11，默认加载因子是0.75f，扩容是基础容量翻一倍+1。

 public Hashtable() {
        this(11, 0.75f);
    }

HashMap的默认初始化容量为16，默认加载因子是0.75f，扩容是基础容量翻一倍。

Hashtable是安全失败机制（fail-safe），HashMap是快速失败机制（fail-fast）。

快速失败机制

在map使用迭代器进行遍历时，对元素进行删除，添加的操作时，会抛出java.util.ConcurrentModificationException异常。

java.util包下的集合类都是快速失败的。

 HashMap map = new HashMap();
        map.put(1,1);
        map.put(2,2);
        map.put(3,3);
        map.put(4,4);
        map.put(5,5);
        map.put(6,6);

        Set set = map.keySet();

        Iterator it = set.iterator();

         while(it.hasNext()){
            Integer key = it.next();
            map.put(key+10,22);
        }

//Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1442)
	at java.util.HashMap$KeyIterator.next(HashMap.java:1466)
	at RBTree.Test.main(Test.java:29)

安全失败机制

java.util.concurrent包下的集合类都是安全失败的

线程A正在遍历Hashtable，线程B此时进行修改，删除，添加的操作，线程A是拿不到最新的数据的，因为采用安全失败机制的容器先复制原有集合内容，在拷贝的集合上进行遍历。

1.7数组+链表

1.8数组+链表+红黑树。考虑到在数据量大的情况下导致某一桶的链表过长，使查询速度变慢的情况，加入的红黑树。当桶的长度大于64且链表长度大于8的时候，就会将链表转化为红黑树，如果链表长度小于等于6，红黑树又会退化为链表。

1.7头插法，可能会形成环，造成死循环。

1.8尾插法

1.7会颠倒链表的顺序；1.7则是在元素插入前。

1.8会保持原链表的顺序，而且1.8是在元素插入后检测是否需要扩容。

实现线程安全的原理

JDK1.7 segment+ReentrantLock+HashEntry

通过将一个整体的桶分成一个个segment,桶和entry里的key，value都实现了volatile关键字，volatile关键字可以保证数据的有序性和可见性，也就是一个线程对数据进行了修改，其他线程也能立刻看到最新的数据。所以ConcurrentHashMap在多线程情况下get()方法不需要添加synchronized关键字也能保证线程安全，并且效率高。

在进行put（）时，当前线程占据当前segment的锁，其余的线程会进行自旋，当自旋达到一定次数才会依旧没有获得锁，就会获得阻塞锁。

JDK1.8 CAS+synchronized+node

 在JDK1.8中，弃用了segment，将hashEntry换成了node，好处是降低了锁的粒度，减少了并发冲突。原来需要锁整块segment，现在只需要锁头部node。在put（）时，判断节点为null就利用CAS插入，失败就自旋保证成功。在桶长度>64且链表长度大于8时同样会转化为红黑树。