这是我参与新手入门的第1篇文章

====================分割线=======================

Java中HashMap底层实现原理(JDK1.8)（上）

一、认识数组

什么是数组？

数组是指有序的元素序列。如果将有限个类型相同的变量的集合命名，那么这个名称就是数组名，而组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量

数组用人话说就是做好记号的一个存储空间

java常见的数组有 ArrayList、LinkList…

数组的特性是什么？

因为下标索引的存在，使得数组的查找的时候效率高，但是数组的扩容代价很大，使得它扩容缓慢

数组的扩容

数组的扩容是需要重新生成一个比原来长的数组，然后把旧的数组每个元素放入新的数组当中去从而完成扩容。

数组的删除也是如此，新建一个比原来短的数组然后把需要的装入旧数组，完成删除

二、认识链表

什么是链表？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

用人话就是 链表里面存放着数据 + 下一个链表的地址，也就是你手拉手另一个人记住他的样子是谁。

三、认识数组 + 链表

HashMap 是什么

众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。

1. 在jdk 1.6、jdk1.7中，HashMap采用位桶 + 链表实现，即使用链表处理冲突
2. 在jdk1.8中，HashMap采用位桶 + 链表 + 红黑树实现，当链表长度超过阈值8的时候，将链表转换为红黑树，这样大大减少了查找时间

HashMap的实现原理

首先有一个数组，它的每一个元素存储的都是一个链表

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。

当添加一个元素（key-value）时，首先计算key的hash值，然后把key插入到数组中，如果存在同一hash值，那么将存在这个桶下

约定前面的数组结构的每一个格格称为桶

基于hashcode相同，值不一定相同，两个对象equals相等，那么这两个对象的HashCode一定也相同，我们就可以先用hashcode比较得出数组的位置，然后用equals来比较是否相等，也就是用equals筛选

Eg： hash表中有1、2、3、4、5、6、7、8个位置，存第一个数，hashcode为1，该数就放在hash表中1的位置，存到100个数字，hash表中8个位置会有很多数字了，1中可能有20个数字，存101个数字时，他先查hashcode值对应的位置，假设为1，那么就有20个数字和他的hashcode相同，他只需要跟这20个数字相比较(equals)，如果每一个相同，那么就放在1这个位置，这样比较的次数就少了很多，实际上hash表中有很多位置，这里只是举例只有8个，所以比较的次数会让你觉得也挺多的，实际上，如果hash表很大，那么比较的次数就很少很少了。

Eg: 用个例子说明：上面说的hash表中的8个位置，就好比8个桶，每个桶里能装很多的对象，对象A通过hash函数算法得到将它放到1号桶中，当然肯定有别的对象也会放到1号桶中，如果对象B也通过算法分到了1号桶，那么它如何识别桶中其他对象是否和它一样呢，这时候就需要equals方法来进行筛选了。