HashMap1.7和1.8的实现原理

2020-03-11 本文已影响0人 Merbng

概述

HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null键和null值，因为key不允许重复，因此只能有一个键为null，另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不相同。HashMap是线程不安全的。
在此之前先介绍一下链表

什么是链表

链表是由一系列非连续的节点组成的存储结构，简单分下类的话，链表分为单向链表和双向链表，而单向/双向链表又可以分为循环链表和非循环链表

单向链表
单向链表就是通过每个节点的指针指向下一个节点从而链接起来的结构，最后一个节点的next指向null

单向链表
单向循环链表
单向循环链表和单向列表不同的是，最后一个节点的next不是指向null，而是指向head节点，形成一个环。

单向循环链表
双向链表
从名字就可以看出，双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的next指向null

双向链表
双向循环链表
双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成了一个环，而LinkedList就是基于双向链表设计的。

双向循环链表

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单项链表结构，它具有next指针，可以连接下一个Entry实体，依次来解决Hash冲突问题，因为HashMap是按照Key的hash值来计算Entry在HashMap中存储的位置的，如果hash值相同，而key内容不相等，那么就用链表来解决这种hash冲突。

总结

1、实现原理

HashMap是基于hashing的原理，我们使用put(key,value)存储对象到HashMap中，使用get(key)从HashMap中获取对象
当我们给put(key,value)方法传递键值时，它先调用key.hashCode()方法，返回的hashCode值，用于找到bucket的位置，来储存Entry对象
Map提供了一些常用方法，如keySet()、entrySet()等方法
keySet()方法返回值是Map中key值的集合；entrySet（）的返回值也是返回一个Set集合，此集合的类型为Map.Entry
如果有两个key的hashCode相同，你如何获取值对象？
当我们调用get(key)方法，HashMap会使用key的hashCode值，找到bucket位置，然后获取值对象
如果有两个值对象，储存在同一个bucket？
将会遍历链表直到找到值对象
这时会问因为你并没有值对象去比较，你是如何确定找到值对象的？
找到bucket位置之后，会调用keys.equals()方法，去找到链表中正确的节点，最终找到要找的值对象

完美的回答：

当获取对象时，通过key的equals（）方法找到正确的键值对key-value。然后返回值对象value
HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。
HashMap在每个链表节点中，储存键值对key-value对象
当两个不同的键对象key的hashcode相同时，会发生什么？
他们会储存在同一个bucket位置的链表中，并通过键对象key的equals（）方法来找到键值对key-value

2、底层的数据结构

HashMap的底层主要是基于数组和链表来实现的，他之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置
HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样
如果存储的对象多了，就有可能不同的对象所计算出了的hash值是相同的，这就出现了所谓的hash冲突
解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的

补充

值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap

Map map = Collections.synchronizedMap(new HashMap())

HashMap结合了ArrayList与LinkedList的两个实现的优点，虽然HashMap并不会像List的两种实现那样，在某项操作上性能较高，但是在基本操作（get和put）上具有稳定的性能

Q 1 .哈希表如何解决hash冲突

解决hash冲突

Q 2 .为什么HashMap具备以下特点：键值都允许为空、线程不安全、不保证有序、存储位置随时间变化

HashMap线程不安全的其中一个重要原因：多线程下容易出现resize()死循环，本质=并发执行put()操作导致触发扩容行为，从而导致环形链表，使得获取数据遍历链表时形成死循环，即Infinite Loop

image.png

在扩容resize()过程中，在将旧数组上的数据转移到新数组上时，转移数据操作=按旧链表的正序遍历链表，在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况
此时若（多线程）并发执行put()操作，一旦出现扩容的情况，则容易出现环形链表，从而在获取数据、遍历链表时形成死循环，即死锁状态
注：由于JDK1.8转移数据操作=按旧链表的正序遍历链表、在新链表的尾部依次插入，所以不会出现链表逆序、倒置的情况，故不容易出现环形链表的情况。
但JDK1.8还是线程不安全，因为无加同步锁保护。