HashMap和ArrayList

自己学习笔记，仅供自己参考，如有不对欢迎指正

ArrayList

ArrayList的扩容机制
初始容量为10，当添加第11个元素的时候，会扩容1.5倍，当添加到16个元素的时候扩容为15*1.5=22，
当MAX_ARRAY_SIZE > Integer.MAX_VALUE - 8,则直接Integer.MAX_VALUE

HashMap

• 是有数组和链表两种数据结构组成，实现寻址容易，插入删除也容易。

• 默认长度是16，默认负载因子是0.75。

• 当链表长度超过阈值（8）时，将链表转换为红黑树。
  红黑树参考：https://zhuanlan.zhihu.com/p/79980618?utm_source=cn.wiz.note

• HashMap的存储结构。
  （1）将key的值进行hash之后进行存储，每一个hash值对应一个数据的下标，一个数组的下标有hash和数组长度计算得来
  （2）由于不同的key值可能具有相同的hash值，即一个数组的某个位置出现两个相同的元素，对于这种情况，hashmap采用链表的形式进行存储。

• HashMap的扩容 Resize
  触发条件：当数组的元素数量>数组大小（默认16）* loadFactor（负载因子默认0.75）
  扩容大小：扩容是2倍扩容的 （默认是16扩容后就是32）
  扩容后的变化：因为数组的长度变了，每个元素的下标也变了。重新加入链表或者红黑树。

• Entity：数组里每个元素存储的是一个链表的头结点。而组成链表的结点其实就是hashmap内部定义的一个类：Entity。Entity包含三个元素：key，value和指向下一个Entity的next。
  具体的插入逻辑：
  （1）先判断插入的位置是否已经有Entity,没有就创建一个Entity对象在该位置插入，插入结束。
  （2） 如果已经存在，通过equals方法将两个key进行比较，如果相同，则将value值替换，插入结束。
  （3）如果hash相同，但两个key不同，插入该Entity，把原来在位置上的Entity赋值给新的 Entity的next（比较难理解）
  现判断新的Entity插入（put）的位置永远是在链表的最前面

• HashMap的总体数据结构如下图（图片来自网络，仅学习使用，感谢作者）
  

  image.png

• 为什么HashMap中初始化大小是16，默认初始负载因子是0.75？
  （1）hahmap每次扩容都是以 2的整数次幂进行扩容。
  （2）过大浪费资源，过小需要频繁扩容浪费性能。
  （3）减少hash碰撞，提高map查询效率