[数据结构与算法]HashMap原理

java1.8中 HashMap是数组+链表+红黑树的结构

创建对象时，将加载因子初始化为0.75
当添加key-value时，通过key的哈希值得到在table的索引。然后判断该索引是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key是否相等。如果相等，则直接替换value，如果不相等，则需要判断是树结构还是链表结果。如果添加时发现容量不够，则需要扩容。
第一次添加，则需要扩容table容量为16，临界值为12（16*0.75）。
以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来临界值的2倍，依次类推。
java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认为8），并且table大小>=MIN_TREEIFY_CAPACITY（默认64），链表就会变化为红黑树。