Java 中级篇

HashMap 的底层数据结构是怎样的？

JDK1.8 之前

• JDK1.8之前HashMap底层是数组和链表结合在一起使用也就是链表散列。
• HashMap通过key的hashCode经过扰动函数处理过后得到hash值，然后通过(n - 1) & hash判断当前元素存放的位置(这里的n指的是数组的长度)，如果 当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
• 所谓扰动函数指的就是HashMap的hash方法。使用hash方法也就是扰动函数是为了防止一些实现比较差的hashCode()方法，换句话说使用扰动函数之后可以 减少碰撞。

JDK1.8 之后

当链表长度大于阈值(默认为8)时，会首先调用treeifyBin()方法。这个方法会根据HashMap数组来决定是否转换为红黑树。只有当数组长度大于或者等于64的 情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行resize()方法对数组扩容。