HashMap与HashTable与并发容器
HashMap与HashTable
先上图看看它们的结构jdk7：
从图中可以看出HashMap和HashTable的组成结构基本一致，但是有些许不同。
- 相同点
capacity：数组的长度
loadFactor：负载因子（链表长度占数组长度的比例，默认0.75）
threshold：扩容阈值（当链表长度到达阈值时就会自动扩容，等于capacity*loadFactor）
都是采用了数组加链表的方式进行存储，数组采用一次哈希查找，链表采用顺序查找。
每个最小存储单位都是一个Entry对象，包含Hash值，Key，Value，Next（用于指向下一个节点）。 - 不同点
Hash运算：HashMap采用位运算（与&，或|，非~，异或^），HashTable采用除法运算。
锁：HashMap没有加锁，在并发时线程不安全。HashTable加了synchronized锁。
长度设置：HashMap如果给它设置大小，会默认扩容成2的n次幂大小，不设置默认为16，扩容时直接放大为原来的2倍。HashTable如果给它设置大小，会使用你给定的大小，不设置默认为11，扩容时直接放大为原来的2n+1。
jdk8中HashMap的结构有一点变化，二次查找不一定总是从链表中查找了，如图：
转化为红黑树后，查找的效率由原来链表顺序查找的O(n)变成O(log2n)。
HashMap关于扩容：jdk7中是先判断是否需要扩容，再选择是否填值。jdk8中是先填入值，再判断是否需要扩容。那么问题就来了，阈值为8，有7个值，jdk7不需要扩容，插入值之后刚好饱和，jdk8中插入值之后，达到饱和进行扩容，如果之后没有新值需要插入，就会造成内存的浪费。
位运算的效率是要大大高于除法运算的，追求效率当然首选HashMap，追求安全咱也不选HashTable，因为concurrentHashMap安全且效率比HashTable高。
并发容器ConcurrentHashMap与ConcurrentLinkedQueue
ConcurrentHashMap
ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
个人认为HashEntry与Entry应该区别不大，所以基本可以认为ConcurrentHashMap就是在HashMap的基础上分段，而Segment是一种可重入锁（ReentrantLock），从而实现分段加锁又具备较高的效率。
ConcurrentHashMap初始化方法是通过initialCapacity、loadFactor和concurrencyLevel等几个参数来初始化segment数组、段偏移量segmentShift、段掩码segmentMask和每个segment里的HashEntry数组来实现的。
initialCapacity：初始容量（默认16）。
loadFactor：负载因子（默认0.75）。
concurrencyLevel：并发级别（默认16）。
segmentShift：段偏移量，用于定位参与散列运算的位数，等于ssize从1向左移位的次数，在默认情况下concurrencyLevel等于16，1需要向左移位移动4次，所以segmentShift等于4。
segmentMask：散列运算的掩码，等于ssize减1。
ssize：segment数组的长度，必须为2的n次幂，一般取大于或等于concurrencyLevel的最小的2的N次方值。通过按位与的散列算法来定位segments数组的索引。
threshold：segment的容量，即能容纳多少个HashEntry，threshold＝（int）cap*loadFactor。
cap：segment里HashEntry数组的长度，即实际有多少个HashEntry，cap=（int）initialCapacity/ssize。如果cap大于1，就会取大于等于cap的2的N次方值，所以cap不是1，就是2的N次方。
既然ConcurrentHashMap使用分段锁Segment来保护不同段的数据，那么在插入和获取元素的时候，必须先通过散列算法定位到Segment。所以在查询时，会有2次散列运算的过程，第一次散列定位到segment，第二次散列在segment中定位到元素HashEntry，之后可能会有链表或红黑树的查找，第二次就类似在HashMap中查找元素。
是否需要扩容是通过判断Segment里的HashEntry数组是否超过容量（threshold），如果超过阈值，则对数组进行扩容。在扩容的时候，首先会创建一个容量是原来容量两倍的数组，然后将原数组里的元素进行再散列后插入到新的数组里。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而只对某个segment进行扩容。
统计ConcurrentHashMap的大小，最安全的做法是在统计size的时候把所有Segment的put、remove和clean方法全部锁住，但是这种做法显然非常低效。因为在累加count操作过程中，之前累加过的count发生变化的几率非常小，所以ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小，如果统计的过程中，容器的count发生了变化，则再采用加锁的方式来统计所有Segment的大小。
ConcurrentLinkedQueue
ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部；当我们获取一个元素时，它会返回队列头部的元素。它采用了“wait-free”算法（即CAS算法）来实现，该算法在Michael&Scott算法上进行了一些修改。
ConcurrentLinkedQueue由head节点和tail节点组成，每个节点（Node）由节点元素（item）和指向下一个节点（next）的引用组成，节点与节点之间就是通过这个next关联起来，从而组成一张链表结构的队列。默认情况下head节点存储的元素为空，tail节点等于head节点。head节点始终是头节点，但tail节点却不一定始终是尾节点。
入队列
入队主要做两件事情：第一是将入队节点设置成当前队列尾节点的下一个节点；第二是更新tail节点，如果tail节点的next节点不为空，则将入队节点设置成tail节点，如果tail节点的next节点为空，则将入队节点设置成tail的next节点，所以tail节点不总是尾节点。这么做的好处是减少CAS更新tail节点的次数，提高入队的效率，当tail节点和尾节点的距离大于等于常量HOPS的值（默认等于1）时才更新tail节点。
入队方法永远返回true，所以不要通过返回值判断入队是否成功。
出队列
并不是每次出队时都更新head节点，当head节点里有元素时，直接弹出head节点里的元素，而不会更新head节点。只有当head节点里没有元素时，出队操作才会更新head节点。这种做法也是通过HOPS变量来减少使用CAS更新head节点的消耗，从而提高出队效率。
参考大佬：HashMap 和 HashTable 到底哪不同，Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析
参考书籍：java并发编程的艺术