蹊源的Java笔记—集合之Map接口

最新推荐文章于 2023-04-12 22:41:41 发布

蹊源的奇思妙想

最新推荐文章于 2023-04-12 22:41:41 发布

阅读量4.1k

点赞数 5

分类专栏： # java 文章标签：数据结构 hashmap 大厂数组蹊源

本文链接：https://blog.csdn.net/weixin_40990818/article/details/109372735

版权

java 专栏收录该内容

122 篇文章 7 订阅

订阅专栏

蹊源的Java笔记—集合之Map接口

前言

集合可以说Java最重要的数据结构了，在上期博客溪源我简单对Collection接口一些整理，这期博客会对另一个集合类接口—Map接口常见的知识点做了简单地整理。

集合之Collection接口可参考我的博客：蹊源的Java笔记—集合之Collection接口

JVM的原理可参考我的博客：蹊源的Java笔记—JVM

正文

集合类

集合类有两个接口组成：Collection和Map
在这里插入图片描述

Map接口

Map接口有三个实现类分别是：

HashMap:HashMap实现了Map接口，继承AbstractMap，它是基于哈希表（一种key-value的数据结构）的 Map接口的实现。
TreeMap:基于红黑树实现的，可使用Comparator对内部元素进行排序。
HashTable:HashMap用法类似，它通过synchronized来实现线程安全,它性能偏低，所以在jdk1.2被弃用,官方推荐使用ConcurrentHashMap作为其替代品。

HashMap

HashMap的数据结构

线性表：存储在连续的内存地址，查询快，插入和删除慢。
链式表：存储在间断的，大小不固定，插入和删除快，但是查询的速度慢。
HashMap:是由数组和链表组合构成的数据结构，是以上两种者折中的解决方案，插入或者删除只需要动一部分即可。

HashMap的底层数据结构

JDK1.7采用的是：数组+链表的方式
JDK1.8采用的是：数组+链表+红黑树的方式

在这里插入图片描述

HashMap单个结点的属性有：（在jdk1.7是Entry,在jdk1.8是Node）

hash:用于快速定位
key:标识符
Value:存储的数值
next:引用地址，便于插入、删除操作

由于JDK1.8引入了红黑树的概念，Node可以树化成TreeNode。

JDK1.8 HashMap 的主要参数

//默认初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//容量最大值
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子0.75 (当前已占当前最大容量的75%，会进行扩容操作)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树化的阈值，当桶中链表节点数大于8时，将链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//红黑树退化为链表的阈值，当桶中红黑树节点数小于6时，将红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
//最小的树化容量，进行树化的时候，还有一次判断，只有键值对数量大于64时才会发生转换，
//这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表而导致不必要的转化
static final int MIN_TREEIFY_CAPACITY = 64;

由于HashMap的特殊的数据结构，这里简单分析一下这些参数的意义：

1.默认初始容量

默认初始容量16，HashMap会使用Key的HashCode值去做位运算，从而得到index，这里index就是HashMap中数组的下标也就是二次散列处位置。
计算index的公式：index = HashCode（Key） & （Length- 1）

HashCode（Key)="key".hashCode() ，而Length即HashMap容量大小
这种计算index方式性能比较高，并且可以保证Hash能够尽可能的分布均匀。

2.默认的加载因子

默认的加载因子是0.75，在默认初始容量是16的情况下，会在12时自动扩容到原容量的两倍即扩容到32。
加载因子是0.75是基于提供空间利用率和减少查询成本的折中方案，当加载因子为1会增加其查询成本，当加载因子减到0.5时空间利用率比较低，会导致频繁触发扩容操作。

当触发HashMap扩容时，需要原HashMap中的数据必须重新计算其在新HashMap中的位置，并放进去。所以在日常的使用时，我们要尽可能考虑HashMap初始容量的大小，避免频繁触发扩容操作。

3.树化的阈值、红黑树退化为链表的阈值、最小的树化容量

链表发生树化的条件：当链表的长度大于等于8，并且当前HashMap的Node<K,V>大于64，红黑树就是增加检索的效率，当元素过少的情况下，完全没有必要进行树化浪费性能；
链表发生退化的条件：当链表从更高的数减少到小于等于7

这里要说明的是链表查询的时间复杂度是n,而红黑树查询的时间复杂度是logn。

HashMap中常见的几种操作

get操作：获取元素get(k)
1.判断表是否为空或者待查找的桶不为空，否则就会通过hash计算得到对应的二次散列处位置
2.首先检查待查找的桶的第一个元素是否是要找的元素，如果是直接返回
3.桶内红黑树，则调用getTreeNode()查找红黑树
4.桶内是链表，遍历链表寻找节点

put操作：新增put(k,v)
1.如果表为空或者表的长度为0，调用resize初始化表，为表分配空间，否则就通过hash计算得到对应的二次散列处位置
2.二次散列处的桶为空，直接插入元素
如果桶不为空则：

桶处的第一个节点与待插入节点的哈希相同且key“相等”，直接赋给变量e
桶中是红黑树，调用putTreeVal插入红黑树中
桶中是链表，遍历链表，如果其中存在相同的key，则赋给变量e；不存在则尾插法加入链表，并判断节点数是否大于8，如果大于8并且当前键值对数量大于64，则调用treeifyBin()转化为红黑树

3.完成上述操作后，检查当前HashMap的容量是否满足扩容条件，满足则扩容，不满足则结束。

在插入新节点时，JDK7采用的是头插法，JDK8采用的是尾插法。

采用头插法的原因是为了热点数据（新插入的数据）能够优先被查找，但是这种做法有可能在多线程的情况如果同时触发扩容的情况下，会重新计算HashMap各Node的位置就有可能会产生环形链表。
但是如果采用尾插法的方式，插入新的节点不会已有节点的前后关系，就不会造成环形链表的问题。

HashMap解决哈希冲突

我们通过key的HashCode进行hash运算得到index,即获得HashMap上的数组位置，却发现已经有元素已经存在了，这种情况则被称为Hash冲突或Hash碰撞。

解决Hash冲突有两种方法：

开放定址法：垂直维度，不会产生hash桶，只是一种数组结构，当发生冲突时，形成探索序列，沿此序列逐个单元地查找，直到找到给定的哈希地址，或者碰到一个开放的地址(即该地址单元为空)为止，查找时探查到开放的地址则表明表中无待查的哈希地址，即查找失败。简单来说，当发生hash冲突就是根据hash运算，获取槽点，来存取值。
链地址法: 水平纬度，Java HashMap就是这么做的，即将所有哈希地址相同的结点链接在同一个单链表或者红黑树中。

HashMap由于key可以是Object类型的（不支持基础数据类型），所以我们为了保证同一个key通过Hash运算能够得到相同的位置，需要同时重写：

先重写hashCode()：将对象的内部地址转换成一个整数返回,即hash值，决定对象在数组中存储的位置。
后重写equals()：只是比较2个对象之间的数据类型及类容是否相同，决定是覆盖还新增。

重写时注意：

hashCode hash值相同 ->equals 可以是true 也可以是false
hashCode hash值不同 ->equals一定false
equals true ->hashCode hash值一定相同
equals false ->hashCode hash值一定不相同

HashMap线程安全

HashMap并不是线程安全的，有两种常见情况下会引发线程不安全问题：

线程A/B同时对相同key进行put操作，A先进入但是在准备写入数据时阻塞，B顺利完数据写入，这个时候A继续操作，会把B数据覆盖，导致数据不一致。
如果采用头插法的方法，在进行扩容操作的时候可能产生环形链表的问题。

实现HashMap线程安全的方式

使用Collections.synchronizedMap(Map)创建线程安全的map集合：底层是通过普通Map对象 + 互斥锁synchronized (mutex) 的方式来实现的。
Hashtable：底层对所有数据操作都加上synchronized，效率低在JDK1.2官方推荐弃用。
ConcurrentHashMap：JDK1.7采用 Segment 分段锁，JDK1.8采用CAS + synchronized保证其并发安全性。

ConcurrentHashMap深层探究

JDK1.7 ConcurrentHashMap

在JDK1.7 ConcurrentHashMap的底层是通过数组+链表的方式来实现的，但是与普通的HashMap不同的是，ConcurrentHashMap的数组是Segment数组，它的数据结构如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    // hash桶
    transient volatile HashEntry<K,V>[] table;
    .....  
}

这样的数据结构意味着：

每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

在put操作的时候：首先会尝试自旋获取锁,如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
在get操作的时候：直接通过hash计算找到对应的Segment位置，在遍历链表获取对应的值，并且由于链表使用volatile，所以每次获取的值都是最新值。

JDK1.8 ConcurrentHashMap

在JDK1.8 ConcurrentHashMap 抛弃了原有的 Segment 分段锁（同时也意味着放弃了ReentrantLock），而采用了 CAS + synchronized来保证并发安全性。
相对于普通的HashMap对Node中的value和next使用volatile保证了多线程下的可见性。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

在进行put操作的时候：

根据key计算出hascode,并根据hashcode获取到对应的bucket的位置
判断是否需要进行初始化
如果bucket为空，使用CAS操作对尝试写入，失败则自旋保证成功。
判断当前是否正在扩容，如果正在扩容做一下扩容的辅助工作
如果bucket不为空，则发生hash冲突，使用synchronized对链表头部或者红黑树根节点加锁（锁分离思想），实现对整个桶进行加锁。
最后完成数据put操作

在进行get操作的时候：

由于value和next都使用了 volatile，所以保证了在获取元素时多线程下可以获取最新值。（没有涉及线程同步）

TreeMap

TreeMap底层原理是，并且它是有序的,它的有序性有两种方式：

采用自然排序的方式，即可以通过实现Comparable接口，重写compareTo方法
采用外置比较器的方式，在构造函数 TreeMap(Comparator<? super K> comparator) 中指定比较器

HashTable

HashTable数据结构和HashMap类似，它通过对所有的方法加上Synchronize从而实现线程安全。

HashTable和HashMap的区别：

Hashtable 是不允许键或值为 null 的，HashMap 的键和值则都可以为 null。
Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍（32），Hashtable 扩容规则为当前容量翻倍 +1（23）。
HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是fail-fast 的。

fail-fast

fail-fast（快速失败）：是Java集合中的一种机制，在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

fail-safe（安全失败）：java.util.concurrent包下的容器都是安全失败，在遍历时不是直接在集合内容上访问的,而是先copy原有集合内容,在拷贝的集合上进行遍历，因此采用安全失败的容器可以在多线程下并发使用，并发修改。

其他

1.有序的Map实现类

HashMap继承Map接口，本身是无序的，想要实现有序的集合的两个方法：

LinkedHashMap：采用双向循环链表（链表和红黑树都是双向的），有两种存取顺序的方式：元素插入的顺序和元素迭代的顺序；
TreeMap：TreeMap的顺序是取决于元素的自然排序或者指定的比较器。

LinkedHashMap的accessOrder存取顺序

当 accessOrder=false 时，记录元素插入的顺序（默认）
当 accessOrder=true时，记录元素迭代的顺序，近期访问少的元素的位置在近期访问多的元素的位置之前；若都没有被访问过则顺序是插入顺序；若访问次数相等，则最近访问的在后面；最近访问的元素就会在链表的末尾。（这顺序可以理解是LRU最近最少用的实现）

LinkedHashMap通过下面的回调函数来维护其顺序：

afterNodeRemoval(Node<K,V> p)：在元素插入的顺序模式时，删除节点后回调，链表去除被删除的节点
afterNodeInsertion(boolean evict)：在元素插入的顺序模式时，新增节点后回调，将新增的节点放在链表的最后
afterNodeAccess(Node<K,V> p)：在元素迭代的顺序模式时，访问节点后回调，将访问的节点放在链表的最后

因为是双向链表，所以链表末尾的next其实就是链表的队首，所以可以很简单地把链表按照存入顺序输出元素。

在这里插入图片描述

蹊源的奇思妙想

关注

5
点赞
踩
51

收藏

觉得还不错? 一键收藏
3
评论
蹊源的Java笔记—集合之Map接口

溪源的Java笔记—集合之Map接口前言集合可以说Java最重要的数据结构了，在上期博客溪源我简单对Collection接口一些整理，这期博客会对另一个集合类接口—Map接口常见的知识点做了简单地整理。集合之Collection接口可参考我的博客：溪源的Java笔记—集合之Collection接口正文集合类集合类有两个接口组成：Collection和MapMap接口Map接口有三个实现类分别是：HashMap:HashMap实现了Map接口，继承AbstractMap，它是基于哈希表（
复制链接

扫一扫