HashMap 总结

介绍：

利用键值对方式储存数据的数据结构，查找时间复杂度可认为是O(1)

原理：

利用哈希函数，将要储存的值得关键信息提取出来（映射函数），再同值一起储存到数组中。

哈希碰撞问题：

在计算哈希值时，会遇到不同的值出现计算结果相同的情况，这种情况叫做哈希碰撞，一般会用链表+红黑树的方式解决，当查询到这类值得时候，就会转化为到链表查询，当链表太长时，还会转化为红黑树查找。

树化、链化关键值

• TREEIFY_THRESHOLD
• MIN_TREEIFY_CAPACITY
  HashMap中的table中链表长度大于8（TREEIFY_THRESHOLD）时会进行是否树化的判断，当table小于64（MIN_TREEIFY_CAPACITY）时先扩容

关键参数：

• initialCapacity 初始容量
  默认为16，当容量不够时会翻倍增加map容量。此时map会做resize操作，当键值对数量特别多的时候，默认值太小会影响性能。
• loadFactor 负载系数
  设定map在容量达到何种比例时需要扩容，比如设定0.5 那么在map容量为8时（默认总量为16）就需要翻倍扩容，对性能不利，默认为0.75是个对性能和空间利用折中的数，至于为什么是0.75可能需要了解泊松分布和指数分布的概念。

函数列表：

关键函数 介绍
get() 参数key，获取value
put() 存键值对
remove() 依据key 移除键值对
containsKey() 是否包含某key
containsValue() 是否包含某值
values() 所有值得集合
keySet() 所有key的集合