HashMap的的底层原理
文章目录
前言
HashMap是Java语言中用的最频繁的一种数据结构。同样也是面试的时候必问 的问题之一，在学习Java语言的过程中只有搞懂这一系列的数据结构的底层原理才能去灵活的运用，最终提高自己的工作效率。在讲解HashMap之前我们想要了解平时常用的数据结构，以及他们的优缺点，才能明白hashMap的用处，以及优缺点。
一、数组和链表的优缺点
数组：
因为有角标的存在所以查询速度快时间复杂度为O（1），可以根据索引查询；但插入和删除比较困难，每一次的插入与删除我们都要把被插入位置或添加位置之后的元素全部移动使时间复杂度为O（n），而且数组的存储位置是连续的，而且数组一旦被创建，不管里面的有效个数，长度是固定的，所有难免会有浪费空间的时候。
链表：
由于我们用头节点表示一个链表，也不存在角标，我们要从头节点一次向下下遍历，所以我们每一次的查询速度慢时间复杂度为O（n），需要遍历整个链表，但插入和删除操作比较容易，只需要O（1）的时间复杂度，而且链表的存储是散列的，所以存多少开多少空间，空间浪费较少。
二、什么是HashMap
hashmap是数组和链表组成的，数据结构中又叫“链表散列”。
简单来讲就是在hashMap中的一个逻辑图就是，在用一个数组来存储相应的链表的首地址（可以想象成在一个杆子上均匀的挂着很多个桶，然后桶里面放着东西），这里的桶的排列是连续的，而桶里的东西确实不连续的。
如图
三、HashMap的特点
- 快速存储 ：比如当我们对hashmap进行get和put的时候速度非常快
- 快速查找（时间复杂度o(1)）当我们通过key去get一个value的时候时间复杂度非常的低，效率非常高
- 可伸缩：1数组扩容，边长。2，单线列表如果长度超过8的话会变成红黑树
hashmap的Hash算法
在聊哈算法之前我们要知道在Java中所有对象都有hashcode（使用key的），如果使用object对象get hashcode的话会得到要给int类型的指，我们在hashmap中主要是用他的key去计算它的值的
四、JDK1.7与JDK1.8的HashMap区别
jdk1.8中添加了红黑树，当链表长度大于等于8的时候链表会变成红黑树
链表新节点插入链表的顺序不同（jdk1.7是插入头结点，jdk1.8因为要把链表变为红 黑树所以采用插入尾节点）
五、HashMap的容量与扩容机制
在HashMap中默认的加载因子是0.75
阈值(threshold) = 加载因子(loadFactor) x 容量(capacity)
根据HashMap的扩容机制，他会保证容量(capacity)的值永远都是2的幂 为了保证加载因子x容量的结果是一个整数，这个值是0.75(4/3)比较合理，因为这个数和任何2的次幂乘积结果都是整数。
理论上来说，加载因子越大越容易出现hash冲突，越小就会不可避免的会浪费空间 （容量一定加载因子越大，hashMap越瘦高，越小，越矮胖）
六、HashMap存储原理与存储流程
在存储时，获取到传过来的key，调用hash算法获取到hash值
获取到hash值之后调用indexFor方法，通过获取到的hash值以及数组的长度算
出数组的下标 (把哈希值和数组容量转换为二进，再在数组容量范围内与哈希值
进行一次与运算，同为1则1，不然则为0，得出数组的下标值，这样可以保证计算出的数组下标不会大于当前数组容量)
把传过来的key和value存到该数组下标当中。
如该数组下标下以及有值了，则使用链表，jdk7是把新增元素添加到头部节点 jdk8则添加到尾部节点。
七、hash冲突
在使用HashMap进行存储时，我们所计算的hashcode是通过函数实现的，计算出的hash值决定你存储在hashMap的什么位置，但是如果当前的位置已经有元素了就会产生hash冲突。
hash冲突的解决
在hashmap中用到链地址法，来解决hash冲突
就是将所有哈希地址相同的都链接在同一个链表中 ，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。