如何保证容器是线程安全的?ConcurrentHashMap如何实现线程安全?

Java提供了不同层面的线程安全支持.在传统集合框架内部,除了Hashtable等同步容器,还提供了所谓的同步包装器, 我们可以调用collections工具类提供的包装方法,来获取一个同步的包装容器, 但是他们都是利用粗颗粒度的同步方式,在高并发的情况下,性能比较低下。

另外,更加普遍的选择是利用并发包提供的线程安全容器类,他提供了:

各种并发容器，比如 ConcurrentHashMap、CopyOnWriteArrayList;
各种线程安全队列,如ArrayBlockingQueue,SynchronousQueue;
各种有序容器的线程安全版本等。

Hashtable，HashMap，TreeMap有何不同？

Hashtable是早期Java类库提供的一个哈希表实现，本身是同步的，不支持null键和值，HashTable其方法函数都是同步的（采用synchronized修饰），不会出现两个线程同时对数据进行操作的情况，因此保证了线程安全性。也正因为如此，在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时，其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候，另外一个线程即使执行获取其他数据的操作也必须被阻塞，大大降低了程序的运行效率，在新版本中已被废弃，不推荐使用。

HashMap是应用更加广泛的哈希表实现，行为大致上与hashTable一致，主要区别在于hashMap不是同步的，支持null键和值等。通常情况下，HashMap进行put和get操作,可以达到常数时间的性能,所以他是绝大部分利用键值对存取场景的首先,比如,实现用户ID和用户信息对应的运行时的存储结构。

初始化时：HashTable在不指定容量的情况下的默认容量为11，且不要求底层数组的容量一定要为2的整数次幂；HashMap默认容量为16，且要求容量一定为2的整数次幂。
扩容时：Hashtable将容量变为原来的2倍加1；HashMap扩容将容量变为原来的2倍。

TreeMap则是基于红黑树的一种提供顺序访问的Map，和HashMap不同，他的get，put，remove之类的操作时间复杂度都为O(log(n))，具体顺序可以由指定的Comparator来决定,或者根据键的自然顺序来判断。

另外还有一些有序Map, 虽然LinkedHashMap和TreeMap都可以保证某种顺序,但是二者还是非常不同的。

LinkedHashMap通常提供的是遍历顺序符合插入顺序，他的实现是通过维护一个双向链表，通过特定的构造函数，我们可以创建反应访问顺序的实例，普通的操作比如put,get等,都算作”访问”。

在这种行为适用于一些特定的应用场景，例如，我们构建一个空间占用敏感的资源池，希望可以自动将最不常访问的对象释放掉，就可以用LinkedHashMap来实现。

HashMap的实现

HashMap扩展自AbstractMao，其性能表现非常依赖于哈希码的有效性。这里就会讲到hashCode和equals的一些基本约定:

equals相等,hashcode也一定要相等;
重写了hashcode也要重写equals;
hashCode需要保持一致性,状态改变返回的哈希值仍然需要一致;
equals的自反性，对称性，传递性，一致性,非空性等特性;


自反性: 对于任何非null的引用值x, x.equals(x)必须返回true;

对称性: 对于任何非null的引用值x和y,当且仅当y.equals(x)返回true时，x.equals(y)必须返回true;

传递性: 对于任何非null的引用值x,y和z，如果x.equals(y)返回true，并且y.equals(z)返回true，那么x.equals(z)返回true;

一致性: 对于任何非null的引用值x和y，只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致地返回true，或者一致地返回false;

非空性: 对于任何非null的引用值x和y，只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致地返回true，或者一致地返回false

HashMap的内部结构，可以看做是数组和链表组成的复合结构，数组被分为一个个桶(bucket)
,通过哈希值来决定键值对在这个数组的寻址;哈希值相同的键值对,则以链表形式存储,如果链表的大小超过了阈值(TREEIFY_THRESHOLD, 8),就会被改造为树形结构。

当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时，它们会储存在同一个bucket位置的链表中，可通过键对象的equals()方法用来找到键值对。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbent,
               boolean evit) {
    Node<K,V>[] tab; Node<K,V> p; int , i;
    if ((tab = table) == null || (n = tab.length) = 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == ull)
        tab[i] = newNode(hash, key, value, nll);
    else {
        // ...
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for first 
           treeifyBin(tab, hash);
        //  ... 
     }
}

从put源码中可以看到 ,如果表格为null,则通过resize来进行初始化,resize兼顾了两个职责,创建初始存储表格, 或者在容量不满足需求的时候进行扩容。因此HashMap按照lazy-load原则, 在首次使用时被初始化。

具体键值对在哈希表的位置取决于下面的位运算。

1	i = (n - 1) & hash

仔细观察哈希值的源头,我们就会发现,他并不是key本身的hashCode,而是来自于HashMap内部的另一个方法。为什么这里需要将高位数据移位到低位进行异或运算呢？这事因为有些数据计算出的哈希值差异主要在高位，而HashMap里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。

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

下面我们继续看看resize方法, 经常会有面试题来追问他的源码设计。

final Node<K,V>[] resize() {
    // ...
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACIY &&
                oldCap >= DEFAULT_INITIAL_CAPAITY)
        newThr = oldThr << 1; // double there
       // ... 
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {  
        // zero initial threshold signifies using defaultsfults
        newCap = DEFAULT_INITIAL_CAPAITY;
        newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY；
    }
    if (newThr ==0){
        float ft = (float)newCap * loadFator;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
    }
    threshold = neThr;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newap];
    table = n；
    // 移动到新的数组结构 e 数组结构 
   }

根据resize源码, 我们可以归纳为:

门限值等于(负载因子) x 容量,如果构建HashMap的时候没有指定,那就按照默认常量值。
门限通常是以倍数进行调整(newThr = oldThr << 1),前面提到,根据putVal中的逻辑,当元素个数超过门限大小时,则调整Map大小。
扩容后，需要将老的数组中的元素放入新的数组，这是主要的开销来源；

容量，负载因子和树化

为什么我们需要在乎容量和负载因子呢？

因为容量和负载洗漱决定了可用桶的数量，空桶太多会浪费空间，如果太慢则会严重影响操作性能，极端情况下，如果只有一个桶，那么他就退化成了链表，完全不能提供所谓的常数时间存的性能。

那么我们在时间中应该如何选择呢？

如果能够知道HashMap要存取的键值对数量，可以考虑预先设置合适的容量大小，具体数值我们可以根据扩容发生的条件来进行简单的预估，根据代码分析，需要

1	负载因子 * 容量 > 元素数量

所以,预先设置的容量需要满足,大于”预估元素数量 / 负载因子”, 同时时2的幂数,就可以得到。

而对于负载因子,我建议:

如果没有特别需求,不要进行轻易地更改,因为JDK自身默认的负载因子就是非常符合通用场景的需求的。
如果确实需要跳转，建议不要设置超过0.75的数值，因为会显著增加冲突，降低HashMap的性能；
如果使用太小的负载因子，按照上面的公式，预设容量值也进行调整，否则可能会导致更加频繁的扩容，增加无谓的消耗；

下面来讲一讲对于树化的改造。

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) {
        // 树化改造逻辑
    }
}

这是简化之后的treeifyBin示意,可以理解为,当bin的数量大于TREEIFY_THRESHOLD时:

如果容量小于MIN_TREEIFY_CAPACITY,只会进行简单扩容;
如果容量大于MIN_TREEIFY_CAPACITY,只会进行树化改造;

那么为什么HashMap要树化呢?

本质上是一个安全问题,其实也是一个性能问题。因为在元素放置过程中，如果一个对象哈希冲突，都被放置在同一个桶里，则会形成一个链表，我们都知道链表是线性的，会严重影响存取的性能。

而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端进行交互，导致CPU大量占用，就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似的攻击事件。

解决哈希冲突的办法

解决哈希冲突的常用方法有：

开放定址法

基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

再哈希法

这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

线性再散列

最常用的方法就是线性再散列。即插入元素时，没有发生冲突放在原有的规则下的空槽下，发生冲突时，简单遍历hash表，找到表中下一个空槽，进行元素插入。查找元素时，找到相应的位置的元素，如果不匹配则进行遍历hash表。主要的缺点在于不能从表中删除元素。

非线性再散列

就是冲突时，再hash，核心思想是，如果产生冲突，产生一个新的hash值进行寻址，如果还是冲突，则继续。主要的缺点在于不能从表中删除元素。

Hashtable，HashMap，TreeMap有何不同 ？