专栏首页关忆北.HashMap不完全解读

HashMap不完全解读

HashMap的必知点

  1. HashMap是无序且不安全的数据结构。
  2. 存储结构是数组 + 链表 + 红黑树 (阈值为8 如果链表长度>=8则会把链表变成红黑树 ),数组中存储元素Entry,存储元素的位置被称为桶,每个bucket有且仅有一个元素并指定索引,以实现快速访问。
  3. HashMap 是以key–value对的形式存储的,key值是唯一的(可以为null),一个key只能对应着一个value,但是value是可以重复的。
  4. HashMap 如果再次添加相同的key值,它会覆盖key值所对应的内容,这也是与HashSet不同的一点,Set通过add添加相同的对象,不会再添加到Set中去。
  5. HashMap 提供了get方法,通过key值取对应的value值,但是HashSet只能通过迭代器Iterator来遍历数据,找对象。

HashMap的新特性

  1. jdk8中添加了红黑树,当链表长度大于等于8的时候链表会变成红黑树
  2. 链表新节点插入链表的顺序不同(jdk7是插入头结点,jdk8因为要把链表变为红 黑树所以采用插入尾节点)
  3. resize的逻辑修改(jdk7会出现死循环,jdk8不会)

HashMap为什么引入红黑树

为了解决jdk1.8以前hash冲突所导致的链化严重的问题,因为链表结构的查询效率是非常低的(O(n)),树结构的查询效率会高一些。

重写hashCode()和equals()方法

HashMap可以提供快速访问能力,即通过key可以查询到相应的value,通过哈希函数可以决定键值对的位置,在理想状况下(不出现hash冲突),查询的时间复杂度为O(1),当出现hash冲突时,使用开散列表解决冲突,对应一个特定hash值的位置存储的是一个链表头,指向hash到同一个位置的多个键值对组成的链表。

HashMap的数据存储

HashMap的数据是存在Node[] table数组(哈希桶)中的,它是一个Entry数组,Entry是HashMap的一个静态内部类。Entry封装了hash(定位数组索引位置)、key、value,next是指向链表的下一个Node节点。

Map及Map.Entry

Map.Entry是Map的一个内部接口。

Map.Entry的常用方法:

  • keySet()方法返回值是Map中key值的集合
  • entrySet()的返回值也是返回一个Set集合,此集合的类型为Map.Entry。

HashMap的put方法

HashMap put方法存储流程

引用美团技术团队的图片:

①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容; ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③; ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals; ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤; ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可; ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

HashMap解决hash冲突(碰撞)

不同的对象具有不同的hash值,当两个不同的对象计算出的hash值相同时便产生了hash冲突,HashMap使用数组+链表(链地址法)解决hash冲突。

map.put("key1","value1");
map.put("key 2","value 2");
	...
map.put("hashCode n","value n");

调用map的put方法进行数据存储时,首先根据key计算其hashCode,然后进行取模运算和高位运算来确定value的存储位置,在后期的调用put方法时不同的key计算得到的位置可能是一样的,这时会产生hash碰撞。

HashMap扩容

HashMap的容量与扩容机制

在HashMap其中一个构造函数中,可以指定HashMap的初始容量和负载因子,这两个变量关系到HashMap的扩容。

  • 负载因子是一个和扩容机制有关的值,阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) ,负载因子是0.75这是时间和空间的权衡。负载因子越大,Hash冲突的可能性就更大,负载因子越小,相同的数据,HashMap扩容的次数就越多,需要的空间就越大。
  • 阈值则指定了HashMap的最大容量(容纳key-value的极限值)。

扩容条件

比如说当前的默认容器容量是16,负载因子是0.75,16*0.75=12,也就是说,容器中超过12个元素的时候就会进行扩容操作。HashMap以2的整数次幂扩容。

明确参数

  1. bin:bucket,数组中存储Entry位置
  2. MAXIMUM_CAPACITY:最大容量(2的30次幂,1073741824)
  3. DEFAULT_LOAD_FACTOR:负载因子(默认0.75)
  4. TREEIFY_THRESHOLD: 链表转红黑树阈值
  5. DEFAULT_INITIAL_CAPACITY:默认初始容量(2的4次幂16)

1.This map usually acts as a binned (bucketed) hash table 2.static final int MAXIMUM_CAPACITY = 1 << 30; 3.static final float DEFAULT_LOAD_FACTOR = 0.75f; 4.static final int UNTREEIFY_THRESHOLD = 6; 5.static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

resize源码:

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //如果当前长度大于最大容器长度(2的30次幂 1073741824则直接返回该对象,1073741824是极限长容量
            //static final int MAXIMUM_CAPACITY = 1 << 30;
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果当前长度小于最大容量且小于默认容量16,对原数据进行2倍扩容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //计算resize上限
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // 把每个bucket都移动到扩容后的buckets中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //省略移动bucket部分代码
                   		  ...
        }
        return newTab;
    }

参考文献:

美团技术网站:Java 8系列之重新认识HashMap

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.csdn.net/weixin_42313773复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • HashMap源码解读[面试专题](集合相关)

    加载因子越大,空间利用率就越高,index冲突的概率越大 加载因子越小(0.2),空间利用度不高,index冲突概率就比较小。 0.75科学计算:统计概率学...

    高大北
  • JDK 8 HashMap源码解读

    关于二叉树的知识点摘自:https://www.jianshu.com/p/bf73c8d50dc2

    用针戳左手中指指头
  • 大牛带你深入解读HashMap

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

    慕容千语
  • Java HashMap 核心源码解读

    本篇对HashMap实现的源码进行简单的分析。 所使用的HashMap源码的版本信息如下:

    哲洛不闹
  • Java之HashMap源码解读

    HashMap一直是数组加链表的数据结构,在数组的某个下标位置,有多次碰撞,则使用链表数据结果存储。在jdk1.8中,引入了红黑二叉查找树的数据结构。刚开始产生...

    程裕强
  • Java Review - HashMap & HashSet 源码解读

    小小工匠
  • JDK 7 HashMap原理解读

    数组是最基本的数据结构,ArrayList内部就是数组实现的,下标定位位置,然后在数组下标位置存放元素,每添加一个元素,下标就+1,map和list有一点相似,...

    用针戳左手中指指头
  • Java源码解读 --- HashMap&ConcurrentHashMap

    HashMap是一个常用的集合,日常使用可能我们并不关心它是如何实现的,不过它是面试中的常客。所以为了弄懂它,不妨看一看源码,同时也可以学习一下大牛的编程思想。

    贪挽懒月
  • 迟到一年HashMap解读

    HashMap和List这两个类是我们在Java语言编程时使用的频率非常高集合类。“知其然,更要知其所以然”。HashMap认识我已经好多年了,对我在工作中一直...

    静默加载
  • 面试必会:HashMap 实现原理解读

    HashMap是Java开发当中使用得非常多的一种数据结构,因为其可以快速的定位到需要查找到数据,其最快的速度可以达到O(1),最差的时候也可以达到O(n)。本...

    好好学java
  • HashMap框架源码深入解读,面试不用愁

    在Java Collections Framework的体系中中,主要有两个重要的接口,一个是List、Set和Queue所属的Collection,还有一个就...

    李红
  • HashMap1.8源码解读及相关面试题解读

    随着工作年限的增加,面试的时候对Map集合问的越来越细,本章针对jdk1.8的HashMap做详细解读,从源码层面去分析元素的添加、底层数组的扩容

    envoke
  • jdk8HashMap源码解读一【源码】

    我们使用 put(key, value) 存储对象到 HashMap 中,使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递...

    简单的程序员
  • 最通俗易懂的 HashMap 源码分析解读

    HashMap 作为最常用的集合类之一,有必要深入浅出的了解一下。这篇文章会深入到 HashMap 源码,刨析它的存储结构以及工作机制。

    未读代码
  • 我不喜欢读源码之HashMap源码解读

    很多人都不喜欢看看源代码,我也不喜欢看,我甚至不喜欢别人写的代码,事实说明,千万不要指望别人能写出多么优秀的代码,更不要指望自己能写出多么优秀的代码。看了Has...

    码农小麦
  • 一文解读JDK8中HashMap的源码

    HashMap是平时开发中非常常用的一个集合框架类,了解其内部构造及运行原理可以说是每一个Java程序员必不可少的,接下来就从源码一探究竟HashMap到底是什...

    beifengtz
  • JavaScript面向对象编程-第三版不完全系统解读

    关于JavaScript的百度说法,我们这里就不贴出来了,因为太多了,也找不到标准。烦请大家自行参考,方便自己理解。我们这里只给针对专业权威书籍《Object-...

    老九君
  • WebAssembly 不完全指北

    随着JavaScript的快速发展,目前它已然成为最流行的编程语言之一,这背后正是 Web 的发展所推动的。但是随着JavaScript被广泛的应用,它也暴露了...

    腾讯IVWEB团队

扫码关注腾讯云开发者

领取腾讯云代金券