学习扔物线进阶视频课程笔记。HashMap、LeakCanary、BlockCanary源码分析。
HashMap
存储结构：数组+链表+红黑树
原理：存数据时，根据key计算出hash值，然后根据hash值和数组大小，确定索引index，判断数组在index这个索引上有没有数据。如果没有，直接创建链表添加当前数据，并把链表放在数组的index位置；如果有链表数据，判断在链表中有没有相同的key，如果有覆盖value值，如果没有将新数据添加到链表尾部，并判断是否需要将链表树化，如果需要，将链表结构变成红黑树结构；如果有红黑树数据，判断树中有没有相同的key，如果有覆盖value值，如果没有将新数据添加到树中，并对红黑树做自平衡处理。添加数据后，判断当前数据量是否大于阈值，这个阈值是使用容量*装载因子得到的，如果大于了阈值，会对数组做扩容，创建一个新的数组，大小为原来的两倍，然后将原数组数据复制到新数组。
查数据时，根据key计算出hash，然后根据hash和数组大小确定索引，然后在索引处的链表或者红黑树中查数据。
创建HashMap时，传入容量大小和装载因子，如果不写，默认使用16和0.75，此时并不会创建出数组，而是在第一次调用put方法时才创建，并且会保证容量大小为2的整数次方，为什么要将数组长度限制为2的整数次，主要有以下几个原因：1根据hash和数组大小确定索引时，len-1的二进制所有位都为1，可以使用hash&(len - 1)，二进制&计算效率比hash%len要高；2发生扩容的时候，也可以使用二进制计算快速确定新的索引位置，如果hash的二进制左边一位是0，那索引不变，如果是1，那索引为原索引+原数组长度。