HashMap的原理

HashMap是基于哈希的一种数据结构，是通过键值（key-value）存储数据。

核心是将键的哈希值映射到数组的索引位置，通过数组+链表来处理哈希冲突。（Java8之后是通过数组+链表+红黑树）。

向HashMap添加一个元素时，首先通过键的hashCode()方法得到该元素的key的哈希值，通过计算得到table数组的索引，查看该索引处是否有元素，若没有则直接添加元素，若有元素，则通过equals()方法判断要添加的元素和该位置的元素的key的内容是否相同，如果相同则不添加，如果不同则将元素插入到链表尾部。

HashMap使用键的hashCode()方法计算哈希值，并通过indexFor方法（JSDK1.7之后的版本移出了这个方法，直接用[（n-1）&hash]）确定元素在数组中的存储位置。哈希值是经过一定扰动处理的，防止哈希值分布不均匀，从而减少冲突。

HashMap的默认初始容量是16，负载因子是0.75.当存储的元素数量超过16*0.75=12个时候，HashMap会触发扩容操作，容量*2并重新分配元素的位置，这种扩容比较耗时，频繁扩容会影响性能。当HashMap的数组大小大于等于64并且某一条链表的长度大于8时，链表就会树化，转化为红黑树。