Java总结之映射家族--Map概览

所谓映射便是一一对应,map英语中是[地图]的意思,这也很好的反应了映射的概念。 即:地图上的某一点都会对应现实的某一点,说是映射可谓恰到好处。Map可以说是键值对的容器,key和value一一对应,也像是根据索引查找单词。 索引当然是不能重复的。如果你发现一个字典的索引有两个[apple],你肯定会认为这个字典有问题。或者一个地图上查询两个[合肥],恐怕你也不会相信这张地图是好的。所以Map可作为Set的超集,Java中的Set集合的底层便是根据Map实现的。

Map家族一览

Map接口.png

一、永恒闪耀的明星:HashMap

作为一个多考点的类,说起HashMap总是有种神圣不可侵犯的感觉。 相关话题: 哈希碰撞相关问题:什么是哈希碰撞,如何降低哈希碰撞几率,哈希碰撞后的解决方案 HashMap底层实现问题:链表数组+红黑树数组,为什么要使用这样的数据结构 由此可以引出链表与数组的比较:效率问题,空间问题,链表的实现 由此也引出红黑树的相关问题:什么是红黑树,红黑树的特点,红黑树的翻转,红黑树与AVL树的比较

HashMap.png

来看一下HashMap的数据结构

这里是Map总结篇,所以只是简单的看一下,在HashMap精析中会详细解释 1---打开源码,可以看出内部有一个Node类,而且是单链表 2---打开源码,可以看出内部有一个TreeNode类,而且是红黑树 3---可以看到内部维护一个链表的数组,当哈希冲突时将数据插入链表尾 4---所以HashMap集数组+单链表+红黑树于一身,对数据结构而言,确实很经典。

链表节点类:可见是一个单链表
 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
红黑树节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;  // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;    // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
}
//可以看到内部维护一个数组链表
transient Node<K,V>[] table;
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                   //tab:记录当前链表的数组
                   //n:当前链表的数组的长度
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//hash:传入键的hash值
            //可以看到添加元素并且没有哈希碰撞时,将元素放入数组的下一位
            tab[i] = newNode(hash, key, value, null);
        else {//否则,即哈希冲突了
            Node<K,V> e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)//如果是树,按树的插入
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//否则,按链表的插入,
            //关于bin:就像数组里放了一个个垃圾桶(链表),来一个哈希冲突的就往里扔一个,
            //所以binCount就是链表的容量
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                    //链表添加节点
                        p.next = newNode(hash, key, value, null);
                        //数量达到树化阀值
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//树化链表
                        break;
                    }
                    //省略...
    }
总结一下
1.HashMap会创建一个1 << 4(即16)的Node<K,V>(链表)数组,
2.当hash冲突时,该元素会插入到与其冲突的链表尾
3.当链表长度为8并且数组长度大于40时,链表转为红黑树  
4.当树元素小于等于6时会解除树化,分割成链表
为什么链表要化为红黑树
单链表查询、修改、移除、尾部添加元素的时间复杂度为O(n)
红黑树查询、修改、移除、添加元素的时间复杂度为O(logn)
在数据量比较大师O(logn)的效率要比O(n)快很多(可根据数学上两种曲线比较)
红黑树这么好,为什么不直接用红黑树?
1.考虑到哈希冲突的数据不会是巨量的
2.在数据量比较少(树化阀值为8)的时候O(n)和O(logn)并无不同
3.红黑树在插入和移除时会进行额外的旋转操作,而且维护的成员变量较多逻辑较复杂,所以低数据量时反而不如单链表

二、链式哈希映射:LinkedHashMap--我有序,我骄傲

LinkedHashMap<K,V>extends HashMap<K,V>,so LinkedHashMap拥有HashMap功力 可见Entry是继承自HashMap.Node(单链表)的, Entry<K,V> before, after,说明Entry是一个双链表 由此解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题,详细原理会另开一篇

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

LinkedHashMap.png


三、树形映射:TreeMap--我是红黑树

1----基于红黑树,由于红黑树是一种特殊的二分搜索树,所以可保证键的有序性,也可自定义排序规则 2----containsKey、get、put 和 remove 操作时间复杂度结尾O(logn)

可见节点为红黑树
static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

TreeMap.png

四、哈希表:Hashtable--就让我成为历史,躲在JDK的漆黑角落。但面试官总爱挖坟...

Hashtable的老爹Dictionary这样介绍自己:"NOTE: This class is obsolete"

底层数组+链表实现,无论key还是value都不能为null,
线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低
初始size为11,扩容:newsize = olesize*2+1
计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length

Hashtable.png


五、并发哈希映射:ConcurrentHashMap--我为并发而生

不是一两句话能说清的 ConcurrentHashMap锁的粒度,为对每个数组元素(Node),Hashtable锁的粒度,为对整个数组

ConcurrentHashMap.png


最后总的比较一下

项目

线程安全?

实现

扩容方式

null键值

父类

HashMap

数组+单链表+红黑树

oldCap * 2

允许

AbstractMap

Hashtable

数组 + 链表

oldCap * 2 + 1

不允许

Dictionary

ConcurrentHashMap

数组+单链表+红黑树

oldCap * 2

允许

AbstractMap

LinkedHashMap

数组+单链表+红黑树+双链表

oldCap * 2

允许

HashMap

TreeMap

红黑树

----

允许

AbstractMap


后记:捷文规范

1.本文成长记录及勘误表

项目源码

日期

备注

V0.1--无

2018-10-1

Java总结之映射家族--Map概览

V0.2--无

-

-

2.更多关于我

笔名

QQ

微信

爱好

张风捷特烈

1981462002

zdl1994328

语言

我的github

我的简书

我的CSDN

个人网站

3.声明

1----本文由张风捷特烈原创,转载请注明 2----欢迎广大编程爱好者共同交流 3---个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正 4----看到这里,我在此感谢你的喜欢与支持

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发之途

Java集合框架源码解析之HashMap

17030
来自专栏JavaEdge

集合源码解析之HashMap(基于Java8)1 概述2 HashMap的数据结构三大集合与迭代子3 源码分析单线程rehash多线程并发下的rehashFast-fail

443110
来自专栏一枝花算不算浪漫

Java中常见数据结构Map之HashMap

38970
来自专栏海天一树

小朋友学C语言(4):单精度浮点数与双精度浮点数

上节课 简单介绍了浮点数。计算机程序中的浮点数分为单精度浮点数和双精度浮点数。 单精度和双精度精确的范围不一样。 计算机里的最基本的存储单位用位(bit)来表...

408120
来自专栏butterfly100

HashMap源码阅读

HashMap是Map家族中使用频度最高的一个,下文主要结合源码来讲解HashMap的工作原理。 1. 数据结构 HashMap的数据结构主要由数组+链表+红黑...

34590
来自专栏Android知识点总结

Java容器源码攻坚战--第三战:HashMap(一)

HashMap怪复杂的,如果一开始就上网上一大堆的HashMap的元素图,也没什么太大意思。 这里从一个小测试开始说起,一步步debug在HashMap里走一...

11950
来自专栏java初学

top K 问题

492160
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第11章 时间序列11.1 日期和时间数据类型及工具11.2 时间序列基础11.3 日期的范围、频率以及移动11.4 时区处理时区本地化和转换11.5 时期及其

时间序列(time series)数据是一种重要的结构化数据形式,应用于多个领域,包括金融学、经济学、生态学、神经科学、物理学等。在多个时间点观察或测量到的任何...

69560
来自专栏aCloudDeveloper

算法导论第十四章 数据结构的扩张

一、概要   我们在教科书上所学的所有数据结构都是最常规、最精简的数据结构,即便如此,基本上所有能遇上的问题都能用这些数据结构来解决。但是有一些特殊的问题,需要...

21470
来自专栏LanceToBigData

Java集合源码分析(四)HashMap

一、HashMap简介 1.1、HashMap概述   HashMap是基于哈希表的Map接口实现的,它存储的是内容是键值对<key,value>映射。此类不保...

31450

扫码关注云+社区

领取腾讯云代金券