[数据结构与算法]HashMap

HashMap

put流程

1. HashMap是懒惰创建数组的，首次使用才创建数组

2. 计算索引（桶下标）

3. 如果桶下标还没有人占用，创建Node占位返回

4. 如果桶下标已经有人占用

   如果是treeNode走红黑树的添加或更新逻辑

   如果是普通Node，走链表的添加或者跟新逻辑，如果链表长度超过树化阈值，一旦超过进行扩容

5. 返回前检查容量是否超过阈值，一旦超过进行扩容

1.7和1.8区别

1. 链表插入节点时，1.7是头插法，1.8是尾插法
2. 1.7大于等于阈值且没有空位时才扩容，而1.8是大于阈值就扩容
3. 1.8在扩容计算Node索引时，会优化

加载因子为何是0.75

1. 在空间占用和查询时间之间取得较好的平衡
2. 大于这个值，空间节省了，但链表就会比较长影响性能
3. 小于这个值，冲突减少了，但扩容就会更频繁，空间占用多

key能否为null，作为key的对象有什么要求

能，作为key必须重写hashCode和equals，并且key的内容不能修改