公众号merlinsea
- HashMap
- 底层是由数组+链表+红黑树（jdk8开始）实现，是线程不安全的，初始容量是16，默认装载因子是0.75,当hashMap实际存储的位置为16*0.75=12时，如果再来一个新的位置存储元素，那么就会发生扩容，扩容的目的在于减少hash碰撞,hashMap采用链表法解决hash碰撞问题。源码中是先插入再判断是否需要扩容！！
- 数组作用：数组中的每个位置相当于一个槽，可以根据key的hash值&arr.length-1得到这个key应该放在哪个槽中。数组中的每一个槽用于存放hash值相同的key值。
- 链表作用：用于解决hash冲突，所有映射到同一个槽的元素都产生了hash冲突，通过链地址法解决hash冲突问题。
- 红黑树作用：当链表的个数大于8的时候，会发生链转树，目的在于把原来在链表中O(n)的查询效率降低为O(logn)
- 为什么不使用二叉树？答：因为二叉树在某些情况下可能会退化为单链表，就不满足logn的查询效率！！
- Put(key,val)的过程：
- 判断table是否为空，为空则需要进行扩容
- 否则通过hash&(table.length-1)确定table中的槽位
- 如果槽位为空，直接插入。
- 否则判断是否是红黑树节点，是的话按红黑树的方式插入
- 否则则是链表，则需要一个个往下找，如果找到key相同的就替换（替换不会引发链表长度增加就不会发生链转树），否则采用尾插法（还需要判别是否会发生链转树）
