前言
看起来集合跟并发安全似乎关系并不大，可能放在一起是因为课时原因吧。
集合规约
先看看大佬画的类图
- Collection是最顶层接口，并且继承于Iterable，这意味着所有的集合都可以遍历。
- Collection有三大子接口：Set、List、Queue。
- Map不是Collection。
数据结构
数据结构是指逻辑意义上的数据组织方式，及其相应的处理方式。
数据组织方式
-
线性结构
例如：数组、List、Set、Queue（即Collection） -
图结构
-
树结构
其实树结构是一种特殊的图机构。 -
Hash结构
例如：Map数据处理方式
以某种特定的算法实现对数据的增加、删除、修改、查找和遍历。
之所以我们很多的初级程序员感受不到对数据的操作处理方式的复杂性，是因为我们通常由数据库来管理我们的数据，即使到应用层，通常也是无脑ArrayList、HashMap。
算法的时间复杂度
对数据的操作是需要付出代价的。例如，关系型数据库经常使用索引数据结构：B+tree，可以实现对数据查找的算法复杂度达到O(logN)。而普通的线性结构要查找一个数据则需要O(N)。可能这样感受还是不直观，来，上图：
曲线越陡峭，需要操作就越多，对应的需要处理的时间也就更长。
绕不过去的HashMap
数据组织形式
HashMap采用数组+链表/红黑树的形式存储数据。
- 为什么数组取名为table？
因为数组的每个位置存放的是链表/红黑树，这才有了表的特征：横向、纵向。它还有了另外一个名字：Hash表。 - 存放一个元素，首先是根据key在数组中寻找一个位置，通常是取模。例如，数组长度为8，存放元素3，那么就存放到数组下标为3%8=3的位置。但是如果这个位置已经有其他元素了，怎么办呢？这个时候，链表的作用就显现出来了。在链表或者红黑树上增加当前元素就是了。而这种位置上已经有其他元素的情况，我们就成为Hash冲突。链表/红黑树上有多少个元素就意味着发生了多少次冲突。
- 取一个元素。这是存放元素的方向过程。在没有hash冲突的情况下，寻找一个元素，只需要取模找到对应位置就行。时间复杂度是O(1)。而当存在hash冲突的时候，链表存储冲突元素时，时间复杂度O(N)。如果是红黑树，时间复杂度就是O(logN)（N为冲突元素个数）。
- 当数组容量>=64且同一个槽冲突元素个数超过8个时，该槽位的冲突元素将从链表组织形式改为红黑树。
HashMap是什么时候分配空间的
除了public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }构造器外，不管是默认的无参构造器还是其他构造器，都没有分配table数组空间。那么，他是在什么时候分配空间的呢？在第一次put的时候，在判断table为空后，会调用resize方法申请空间。
第一个条件分支，对应的是传入了初始容量的构造参数：
而第二个条件分支，对应的是无参构造器
小结：
无参构造器不会计算数组容量，需要在resize中使用默认值。
传了初始容量的构造器，会先计算数组容量，并且用阈值threshold暂时存放。在resize时，将阈值作为容量来创建数组。
为什么要用阈值字段来存储？因为HashMap没有字段存储容量，只有存储阈值。实际上容量和阈值是可以通过负载因子来互相转换的。鉴于在判断扩容时，只需要跟阈值做比较，因此选择存储阈值，而计算容量是很划算的。
申请多大的空间
相信大家都了解到HashMap会把初始容量向上取整为第一个大于该容量的2^n。但他是如何做到的？
先看下java.lang.Integer#numberOfLeadingZeros这是个很神奇的方法。多亏了规范的方法命名，我得以了解到这个方法是计算数字的前面有多少个0。什么意思呢？就是在二进制表示中，这个数字的前面有多少位是为0的。例如：整数1，那么前面就有31个0.因为整数一共32位。现在你知道这个方法是干嘛的了，等会儿再回来看它是怎么做到的。
-1 在二进制中表示为32个1，对应的是-1的补码。
因此第一行语句就是把当前容量的有用的位数全部转换为1，例如：只要大于8【2的3次幂】但小于等于16【2的4次幂】的值，全部转换为15【1111】。以9为例，1001。-1无符号右移（32-4）=28位之后，就是15了。这样，只要再+1，就得到16，也就是2^n。
再来看看java.lang.Integer#numberOfLeadingZeros
怎么计算二进制表示中有多少个前导零呢？可以看到还是位移操作，虽然比较难理解，但是还是要理解啊。
经过一番向度娘的讨教，我找到了大佬的文章
核心思想是，把当前问题进行转换，转换为，寻找第一个不为0的位。然后再移位。而整数有32位，通过二分法来加速。如果你们有看大佬的文章，就会发现源码跟我上面贴的不太一样。n=-1，我贴出来的是n=31。我猜测，因为我用的JDK版本更高，因为效率更高。最后的移位只需要移动1次，而老版本移动的是31次。不得不说，Java这波操作已经超出了我的想象，连这点性能都要优化到极致！
晚安了各位。