<--个人成长笔记系列-->知识点解析之HashMap(二)

JAVA知识点：

    （掌握）红黑树：是一个特殊的二叉树

    （掌握）HashMap源码分析：    

        （1）put方法的实现过程：①对Key值求Hash值，然后再计算下标②如果没有Hash碰撞，直接放入桶中③如果发生碰撞，以链表的方式拼接到后面④如果链表长度超过阀值（TREEIFY_THRESHOLD--8），就将链表转为红黑树⑤如果节点已经存在，就替换旧值⑥如果桶满了（容量*负载因子），就需要resize()；

        （2）HashMap中hash方式是怎么实现的：①高 16bit不变，低 16bit和 高 16bit 做了异或运算②(n-1) & hash -->下标

        （3）hash算法还有哪些实现方式：

        （4）HashMap是怎么解决冲突，讲一下扩容过程，假如一个值在原数组中，现在移动到新数组，位置变化了，那是怎么定位到这个值在新数组中的位置：①将新节点加到链表后②容量扩充为原来的2倍，然后对每个节点重新计算哈希值③这个值只可能有两个地方，一个是原下标位置，一个是在下标为<原下标+原容量>的位置

         （5）抛开HashMap，hash冲突有哪些解决办法：开放地址，链地址法   

        （6）针对Entry链太长，查找时间复杂度可能会达到O(n)，怎么优化：将链表转为红黑树，在JDK1.8中已经实现