HashMap基础知识

前言

文章分为五部分
HashMap的预备知识
HashMap的底层实现原理
HashMap的1.7和1.8
HashMap的put与get

提示：以下是本篇文章正文内容，下面案例可供参考

一、HashMap的预备知识

1.HashMap是Map的常用子类
java.util.HashMap<k,v> 集合 implements Map<k,v>接口

2.HashMap集合特点
HashMap集合底层是哈希表，查询速度特别快
jdk1.7：数组+单向链表
jdk1.8：数组+单向链表/红黑树（链表长度超过8，数组达到64）

3.HashMap集合是一个无序的集合，存储元素和取出元素的顺序有可能不一致

二、HashMap的底层实现原理

HashMap是Java中的最频繁的一种数据结构

在深入HashMap前先明白两种数据结构，数组和链表

数组

查询速度快，可以根据索引查询；但插入和删除比较困难

链表

查询速度慢，需要遍历整个链表，但插入和删除操作比较容易。

HashMap
底层是一个hash表（数组+链表），这种结构集合了数组和链表的好处 。在jdk1.7中，只是单纯的数组+链表的结构，但是如果散列表中的hash碰撞过多时，会造成效率的降低，所以在JKD1.8中对这种情况进行了控制，当一个hash值上的链表长度大于8时，该节点上的数据就不再以链表进行存储，而是转成了一个红黑树

HashMap 基于 Hash 算法实现的

1. 当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

三、HashMap的1.7和1.8

JDK1.7
JDK1.7采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8
相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）同时数组长度达到64，将链表转化为红黑树，以减少搜索时间。(红黑树节点为6时转回链表)

JDK1.8主要对HashMap进行了一系列优化

1. resize 扩容优化
2. 引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考
3. 解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。
   

四、HashMap的put与get

put方法
key的hashcode经过高低位异或后的值，然后(table.length - 1) & hash得到槽位下标

• 此时有四种情况

1. 当槽位（slot）为空，key和value包装为一个node对象，直接存储占用一个slot
2. 槽位不为空，判断key是否一样，一样则进行value替换；否则为hash冲突，存入链表中
3. 已经链化，和2过程相同，比较存入链表但是会判断是否达到了树化的扩容阈值标准
4. 红黑树的写入操作
   

get方法
拿到key算出对应索引
5. 根据得到的索引，映射到对应的哈希桶，判断该元素是不是头结点，如果是则直接拿到
6. 如果不是头一个节点，用do while循环遍历链表，链表都是next指向一次拿元素
7. 如果是红黑树，由于添加时保证树有序，则利用折半法遍历红黑树

如有不足，欢迎指出，共同进步！

• 文章版权归作者所有，欢迎转载