hashmap底层实现原理

1. 在内存中，数组是一块连续的区域。 拿上面的看电影来说，这几个人在电影院必须坐在一起。

2. 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。 比如看电影时，为了保证10个人能坐在一起，必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是，如果来的人不够10个，那么剩下的位置就浪费了。如果临时有多来了个人，那么10个就不够用了，这时可能需要将第11个位置上的人挪走，或者是他们11个人重新去找一个11连坐的位置，效率都很低。如果没有找到符合要求的作为，那么就没法坐了。

3. 插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。 比如原来去了5个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第五个都要往后移动一个位子，将第三个位置留给新来的人。 当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。

4. 随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。并且不利于扩展，数组定义的空间不够时要重新定义数组。

数组是一段连续的内存地址，需要先开辟内存空间，然后才能放值，不利于扩展，造成删除和插入效率很低。

1. 在内存中可以存在任何地方，不要求连续。 在电影院几个人可以随便坐。
   每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。 第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……
2. 增加数据和删除数据很容易。 再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
3. 查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。 要找到第三个人，必须从第一个人开始问起。
   不指定大小，扩展方便。链表大小不用定义，数据随意增删。

hashMap的数据结构是数组加链表,hashMap在初始化是数据结构是数组，默认长度16，同时会有负载因子是0.75，负载因子的作用是当数组的容量达到0.75时，就需要扩容，每次扩容是原来的2倍，就是在原来数组的元素的基础上进行链式扩容。
我们要操作hashMap是用到的是Entry对象，它有四个属性分别是key,value,hash值，next。key和value是进行put操作时赋值，hash值是根据key算出来的，hash值就是数据存储的位置，因此map中不允许出现相同的key值。
hashMap是不支持并发操作的，原因是在多线程情况下，上一个线程还没有结束，下一个线程就开始执行，他们用的是同一个hash值，就会造成数据丢失.

　　然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
底层代码：
put 方法：
传进来的参数是key , value。作用：key不存在就新增，存在就修改。
当插入第一个元素的时候，需要先初始化数组大小,默认初始化为16，并设置负载因子。 如果 key 为 null，最终会将这个 entry 放到 table[0] 中，获取对应key的hash 值,接着找到对应的数组下标，从而找到数组中的链表，循环遍历链表，看一下是否已经有相同的Key,如果有将原值进行覆盖，并返回原值。不存在重复的 key，将此 entry 添加到链表中，首先判断当前的map集合的长度(size)是否大于等于（map的容量乘以负载因子），条件成立就将现有容量扩大两倍，同时将key和value放到entry对象中，并map的size++;