关于集合的一些总结

一、HashMap 底层实现原理

    从存储方式来讲：底层是Node数组，初始长度为16，每个元素是一个Node节点，实现了Map.Entry接口，属性有key、value、hash 以及指向下个节点的next，我们可以理解为链表的数组。
    当向集合中插入元素时，通过key的hash（）方法，计算出待插入元素在数组中下标
    如果当前下标没有元素，则直接new 一个Node节点，保存key/value/hash ，
    如果当前下标有元素，说明要插入的元素hash值和此下标对应的单链表所有元素值相同，即冲突，则沿着链表头结点，依次查找，如果遇到相同的key,则用新的value替换旧的value,
    如果没有相同key，则new一个Node节点，保存key/value/hash/next，插入到该下标的链表头部。
    插入元素之后，这里JDK1.8有个改进，插入元素后，程序会判断当前下标的单链表节点个数，如果节点个数大于8，HashMap会将链表转换成红黑树，提高查找效率，时间复杂度由O(1)变成O(n),当删除元素小于6时，自动转化为链表
    一旦插入新元素，HashMap会检查全部键值对的个数是否大于装载量阈值，这个阈值是计算出来的，是装载因子乘以数组容量，一旦元素个数大于阈值，HashMap会调用resize()方法，进行     扩容，HashMap直接扩容2倍，之所以扩容是2的倍数，我们知道HashMap可以根据key的hash值，通过取模，得到元素所在数组的下标，而HashMap从效率角度采用了位运算，即hash &(n-1)，而这个得出结果与 hash % length相同的条件是，length是2的倍数，所以HashMap扩容长度是2的倍数。

二、ConcurrentHashMap数据结构，并发度高的原因
   底层是数组+链表，JDK1.7和JDK1.8有所差异。
   先说JDK1.7的，底层由segment数组和链表组成，segment是ConcurrentHashMap的内部类，继承了ReentrantLock类，主要有以下属性： transient volatile HashEntry<K,V>[] table、count(节点个数)、modCount、thresold(大小)、loadFator(负载因子），采用了分段锁技术，每当一个线程占用锁住一个segment,不会影响到其他的segment,就是说如果集合容量是16，则并发度为16。 

static final class Segment<K,V> extends ReentrantLock implements Serializable {

    private static final long serialVersionUID = 2249069246763182397L;

    // 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
    transient volatile HashEntry<K,V>[] table;

    transient int count;
        // 记得快速失败（fail—fast）么？
    transient int modCount;
        // 大小
    transient int threshold;
        // 负载因子
    final float loadFactor;

}

   Tips:
   1、volatile作用？
   只能保证单次读写的原子性，禁止指令重排序、保证了不同线程对变量进行操作的可见性，即一个线程修改了某个变量值，修改的值对其他线程是可见的
   2、transient作用？
   防止属性被序列化
   

   JDK1.7如何put?
   第一步会去尝试获取锁，如果获取失败，则有其他线程存在竞争，调用scanAndLockForPut()自旋获取锁，若尝试次数达到MAX,则改为阻塞锁获取。 先根据key的hash值定位到要put的segment,通过key的hashCode定位到segment的HashEntry,遍历HashEntry，如果找到相同的key,则用新的value替换旧的value，如果没有找到，则new 一个 HashEntry加入到segment，并在    加入前判断是否需要扩容，最后释放锁，所以put操作是线程安全的。

  JDK1.7如何get?
   现根据key的hash值定位到要get的segment，再通过一次hash定位到具体的HashEntry,遍历HashEntry,匹配key查找，由于value属性用volatile修饰，保证每次get的元素都是最新的，整个过程不需要加锁，但是因为JDK1.7基本是数组加链表的方式，put/get需要去遍历链表，导致效率很低，所以JDK1.8做了优化。JDK1.8抛弃了segment分段锁，而采用了CAS+synchronized来保证并发，底层是Node数组，属性有key、value、hash以及指向下个节点的next，区别是value和next用volatile修饰，保证了可见性，当链表长度8时，也会将链表转换成红黑树。

JDK1.8如何put，怎么保证线程安全性？

final V putVal(K key, V value, boolean onlyIfAbsent) {
// 根据key计算出hashCode
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
    // 判断是否需要进行初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
         // 根据key的hash定位到 Node节点，如果为空，表示当前节点可以插入元素，利用CAS尝试写入，失败则自旋保证成功
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
    // 如果当前位置的hashCode == MOVED,则当前位置需要扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
         // 如果都不满足，则利用synchronized锁写入数据
            V oldVal = null;
            synchronized (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;
                        }
                    }
                }
            }
            if (binCount != 0) {
          //如果数量大于TREEIFY_THRESHOLD则转换为红黑树
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

   
JDK1.8如何get？

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 根据计算出来的 hashcode 寻址
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果就在桶上那么直接返回值
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
      // 如果是红黑树那就按照树的方式获取值
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
       // 按链表方式遍历
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

Tips:
1、CAS:
全称是compare and set, 即比较替换，乐观锁技术，包含三个参数 CAS(V,E,N),V为需要更新的变量，E为期望的值，N为新值，只有当E和V相等的时候，才将V的值设为N，否则不做任何操作，
如果V值和E值不同，说明已有其他线程对值进行了更新，则当前线程什么都不做，直接返回V值
当多个线程尝试使用CAS同时更新一个变量时，只有其中一个线程能更新变量的值，而其他线程都失败，失败的线程不会被挂起，而是被告知此次竞争者失败，并且可以再次尝试
AtomicInteger

2、乐观锁和悲观锁
悲观锁：利用数据库锁机制对数据库进行加排他锁防止并发，修改数据前先加锁，其他对该数据的操作都会等待异常或抛出异常
乐观锁：不依赖数据库锁机制，假设数据一般情况下不会发生冲突，所以数据在提交更新时，才会检测，如果发现冲突，则返回更新失败。

三、HashMap 和 HashTable 区别？
继承关系不同：
HashTable 继承 Dictionnary类，hashMap 继承AbastractMap类实现了Map接口

允不允许NULL值:
HashTable键值对都不允许为Null,否则会抛出空指针异常，hashMap键为空，这样的键只有1个，允许一个或多个值为空，HashTable采用的是fail-safe机制，
默认初始容量和扩容机制不一样：
HashMap 初始容量为16，扩容为2的倍数，HashTable数组初始容量为11，扩容为2的倍数+1

哈希值使用方式不同：
HashTable直接使用对象的hashCode,hashMap重新计算hash

遍历内部方式不同
HashMap 使用iterator，支持fail-fast, 当其他线程改变了HashMap结构，如增加、删除，会抛出ConcurrentModifyException, HashTable还使用了Enumeration遍历，不支持fail-fast 机制，即快速失败机制。

Tips: 
什么是fail-fast机制？
当我们用迭代器遍历集合元素时，如果遍历过程中对集合对象结构进行了改变，如（增加、删除、修改操作），就会抛出ConcurrentModifyException异常，防止继续遍历，这就是快速失败机制。

fail-fast的原理是什么？
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量，
集合在遍历过程中，如果内容变化，就会改变modCount的值
每当迭代器使用hasNext() / next() 遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount的值，是的话返回继续变量，否则抛出异常，终止遍历。

什么是fail-safe机制？

同上，如果结构被改变，fail-safe机制不会抛出异常，因为集合改变时，fail-fafe机制会拷贝原集合一份数据，然后在复制的那份数据，同时也存在缺点，如复制需要额外空间和时间上开销，不能保证遍历是最新的内容

常见问题

• 谈谈你理解的 Hashtable，讲讲其中的 get put 过程。ConcurrentHashMap同问，1.8 做了什么优化？
• ConcurrentHashMap 是如何实现的？1.7、1.8 实现有何不同？为什么这么做？
• ConcurrentHashMap并发度为啥好这么多？
• CAS是啥？
• ABA是啥？场景有哪些，怎么解决？
• synchronized底层原理是啥？
• synchronized锁升级策略
• 快速失败（fail—fast）是啥，应用场景有哪些？安全失败（fail—safe）同问。