关于集合Map

一、Map中的put方法

1. map的数据结构

首先要知道map的一个数据结构，在jdk1.7以前，map的数据结构是 数组+链表 但在jdk1.8，map的数据结构就变成了 数组+链表+红黑树 ，本身是数组，但由于hash算法有hash冲突（hash算法会返回一个int型的数据，当返回的数据相同时，就叫hash冲突），所以加入了链表，但随着hash冲突的增加，链表越来越长，查找起来也不方便，所以加入了红黑树（又叫自平衡二叉树：在一条支路太长时，会自动的分出一个支路，以加快查找数据速度）。

2. put方法
当插入一个元素时，会判断键值对数组（存键值对的）是否存在，如果不存在则调用resize方法扩容。如果存在会利用存入的key来计算一个hash值找到对应的一个索引值 （i），
判断对应索引值的数组元素 table[i] 是否为空，为空就直接插入到数组然后判断数组大小是否超过最大容量，超过就扩容，没超过就结束。不为空的话就看键值对数组对应存储的key是否存在，存在就覆盖，不存在就判断是否在红黑树里，是就直接插入红黑树里，不是的话就在链表里，遍历链表，判断key是否存在，存在就覆盖，不存在就插入，还要判断插入后链表长度大于8且数组长度大于64，链表就转变成红黑树结构。
3. HashMap的长度为何总是2的幂次方

为了能让HashMap存取高效，尽量较少的发生碰撞，数量尽量分配均匀，每个链表和红黑树的长度尽量相同。就是数据应该放哪里的一个方法，可以用hash%length（数组长度）的方式来实现，但是取余操作是一个很费时间的操作，但是如果除数是2的幂次方的话，取余操作等价于 与其除数-1的与操作，就是 hash%length 等价于hash&length-1 与操作的效率比取余操作效率高出很多，那为什么不用与操作呢。