HashMap的遍历方式及底层原理

简介: HashMap的遍历方式及底层原理

概述

Map

    Map是Java中的一个接口,它继承自Collection接口,定义了键值对的存储和检索方法。Map中的键和值可以是任意类型的对象。常见的Map实现类有HashMap、TreeMap和LinkedHashMap等。

Map的全谱系图

HashMap

    HashMap是基于哈希表实现的,它提供了快速的插入和查找操作。它的存储方式是无序的,不保证键值对的顺序。

今天主要介绍HashMap

key和value

    HashMap中的key和value是键值对的组成部分。key是用于标识和查找值的对象,它必须是唯一的,且不可重复。value是与key关联的对象,它可以重复。在HashMap中,通过key来计算出存储位置并存储value,当需要获取value时,通过key来查找对应的value。HashMap中的key和value可以是任意对象,但通常会使用String、Integer等常用的类作为key和value。

HashMap的四种遍历方式

keySet

//定义一个往map里添加元素的方法
  public static Map inputMap(){
        Map<String, Integer> userMap = new HashMap<String, Integer> ();
        userMap.put("zhang1",1);
        userMap.put("zhang2",2);
        userMap.put("zhang3",3);
        userMap.put("zhang4",4);
        userMap.put("zhang5",5);
        return userMap;
    /*利用keyset进行遍历*/
    public static void showMap1(Map<String,Integer> userMap){
        for (String key:userMap.keySet()) {
            System.out.println(key+"***"+userMap.get(key));
        }
    }

values

 /*利用values进行遍历*/
    public static void showMap2(Map<String,Integer> userMap){
        for (Integer v:userMap.values()) {
          System.out.println(v);
        }
    }

entrySet

    /*利用entrySet进行遍历*/
    public static void showMap3(Map<String,Integer> userMap){
        for (Map.Entry<String,Integer> entry:userMap.entrySet()) {
            System.out.println(entry.getKey()+"==="+entry.getValue());
        }
    }

Iterator

/*利用Iterator进行遍历*/
    public static void showMap4(Map<String,Integer> userMap){
        Iterator<Map.Entry<String,Integer>> it=userMap.entrySet().iterator();
        while (it.hasNext()){
            Map.Entry<String,Integer> entry=it.next();
            System.out.println(entry.getKey()+"***"+entry.getValue());
        }
    }

性能分析

稍微修改一下inputMap代码

  public static Map inputMap(){
        Map<String, Integer> userMap = new HashMap<String, Integer> ();
        //定义一个数组,后面用来组合key用
        String str[]=new String[]{"a","b","c","d","e"};
        String key;
        Integer value;
        for (int i = 0; i < 100000; i++) {
        //定义一个随机数
            int m=(int) Math.random()*5;
            key=String.valueOf(str[m])+i*100;
            value=i;
            userMap.put(key,value);
        }
        return userMap;
    }

注意:给四种遍历方式分别加上开始时间和结束时间,同时把输出语句去掉,在条件一致的前提下测试性能

   /*利用values进行遍历*/
    public static void showMap2(Map<String,Integer> userMap){
        Long start=System.currentTimeMillis();
        for (Integer v:userMap.values()) {
        }
        Long end=System.currentTimeMillis();
        System.out.println("values="+(end-start));
    }

输出结果如图所示:

    Iterator和values速度最快,keyset速度最慢,当然每次运行时间会有些变化,但是keyset还是最慢,其他三个效率差不多。

应用场景

1.EntrySet遍历方式适用于需要在遍历过程中对键值对进行操作或者获取键值对的键和值的场景。

2.KeySet遍历方式适用于只需要获取键的场景。

3.Values遍历方式适用于只需要获取值的场景。

4.当需要在遍历过程中对HashMap进行修改操作时,可以使用迭代器遍历方式。迭代器提供了安全的遍历方式,可以在遍历过程中对HashMap进行增删操作,

而不会抛出ConcurrentModificationException异常。

当需要按照特定的顺序遍历HashMap时,可以使用迭代器遍历方式。迭代器可以通过调用HashMap的sort()方法进行排序,然后按照排序后的顺序遍历HashMap。

注意:如果使用JDK 8及以上的版本,并且希望代码简洁,还可以使用Lambda表达式遍历方式。此处不作为叙述内容。

二维表

遍历方式 获取键值对的键和值 获取键 获取值 是否支持修改操作 是否支持按照特定顺序遍历
EntrySet方式
KeySet方式
Values方式
迭代器方式

底层原理

我们通过测试发现

  • Hashmap是无序的(遍历输出顺序和put进去的顺序无关)
  • 但是也不是随机输出

那么put之后HashMap是如何决定键值映射所处的位置呢?

key是数值型

    public static void main(String[] args) {
        Map<Integer,String> map=new HashMap();
        map.put(120,"a");//120%16=8
        map.put(37,"a");//37%16=8
        map.put(61,"a");//61%16=8
        map.put(40,"a");//40%16=8
        map.put(92,"a");//92%16=8
        map.put(78,"a");//78%16=8
        System.out.println(map);
    }

   如代码注释所示,HashMap底层是通过位运算的方式将key转化为哈希码对16求余数(此处直接求余数)决定存储位置,其中120和40对16取余数(map在初始化的时候默认长度是16)结果都是8,产生了碰撞也就是坐标相同,此时会产生一个链表的形式。8这个坐标指向120,120键值映射的Entry里的next指向了40。

附一张HashMap的Entry结构


输出结果和上图分析一致

key是字符类型

 如果key是字符类型,定位的过程与其他类型的key是相同的。HashMap内部使用哈希算法来确定key在数组中的索引位置。具体的定位过程如下:


   首先,HashMap会调用key的hashCode()方法来获取key的哈希码。hashCode()方法是Object类的方法,所有的对象都可以调用该方法来获取它们的哈希码。


   然后,HashMap会使用哈希码进行计算,通过哈希算法将key映射到数组中的一个索引位置。HashMap使用的哈希算法是将哈希码与数组的长度进行按位与操作,得到的结果就是key在数组中的索引位置。


   如果发生哈希冲突(即不同的key计算出的索引位置相同),HashMap会使用链表或红黑树来解决冲突。具体来说,如果链表长度小于8,HashMap会将新的键值对添加到链表的末尾;如果链表长度大于等于8,HashMap会将链表转换为红黑树,以提高查找效率。


d81cc3c0ccc34aab86ef261577965d3b.png

 这里提一下红黑树(Red-Black Tree),它是一种自平衡的二叉搜索树,它在数据结构中被广泛应用。红黑树的特点是具有较好的平衡性和高效的查找、插入和删除操作。在Java中,红黑树主要用于解决HashMap中的哈希冲突。

TreeMap也使用了红黑树来实现有序映射。TreeMap是基于红黑树实现的,它根据键的自然顺序或自定义比较器的顺序对键进行排序。

总的来说红黑树是一种用于解决哈希冲突和实现有序映射的数据结构。在HashMap中,红黑树用于解决哈希冲突;而在TreeMap中,红黑树用于实现有序映射。

总结:

  HashMap的遍历方式主要有keySet、Values、ntrySet和Iterator。其中EntrySet适用于需要在遍历过程中对键值对进行操作或者获取键值对的键和值的场景。KeySet适用于只需要获取键的场景。 Values适用于只需要获取值的场景。 当需要在遍历过程中对HashMap进行修改操作时,可以使用迭代器方式。底层原理是通过遍历数组的每个元素,然后遍历链表或红黑树的每个节点来实现遍历。

相关文章
|
7月前
|
存储 缓存 安全
面试题-HashMap底层原理与HashTable的区别
字节跳动面试题-HashMap底层原理与HashTable的区别
65 0
|
7月前
|
存储 算法 Java
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)
在阅读了上篇文章《【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)》之后,相信您对HashMap的基本原理和基础结构已经有了初步的认识。接下来,我们将进一步深入探索HashMap的源码,揭示其深层次的技术细节。通过这次解析,您将更深入地理解HashMap的工作原理,掌握其核心实现。
63 0
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)
|
安全 Java API
java中HashMap的七种遍历方式
java.util.ConcurrentModificationException , 这种办法是非安全的 , 我们可以使用Iterator.remove() ,或者是Lambda 中的 removeIf() , 或者是Stream 中的 filter() 过滤或者删除相关数据
117 1
|
存储 算法 安全
HashMap底层实现原理
HashMap底层实现原理
167 0
|
2月前
|
机器学习/深度学习 算法
让星星⭐月亮告诉你,HashMap之tableSizeFor(int cap)方法原理详解(分2的n次幂和非2的n次幂两种情况讨论)
`HashMap` 的 `tableSizeFor(int cap)` 方法用于计算一个大于或等于给定容量 `cap` 的最小的 2 的幂次方值。该方法通过一系列的无符号右移和按位或运算,逐步将二进制数的高位全部置为 1,最后加 1 得到所需的 2 的幂次方值。具体步骤包括: 1. 将 `cap` 减 1,确保已经是 2 的幂次方的值直接返回。 2. 通过多次无符号右移和按位或运算,将最高位 1 后面的所有位都置为 1。 3. 最终加 1,确保返回值为 2 的幂次方。 该方法保证了 `HashMap` 的数组容量始终是 2 的幂次方,从而优化了哈希表的性能。
34 1
|
3月前
|
设计模式 安全 Java
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
假如有T1、T2两个线程同时对某链表扩容,他们都标记头结点和第二个结点,此时T2阻塞,T1执行完扩容后链表结点顺序反过来,此时T2恢复运行再进行翻转就会产生环形链表,即B.next=A;采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率。JDK8中,HashMap采用尾插法,扩容时链表节点位置不会翻转,解决了扩容死循环问题,但是性能差了一点,因为要遍历链表再查到尾部。例如15(即2^4-1)的二进制为1111,31的二进制为11111,63的二进制为111111,127的二进制为1111111。
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
|
7月前
|
Java
HashMap原理解析
HashMap原理解析
166 47
|
7月前
|
Java API
面试官上来就让手撕HashMap的7种遍历方式,当场愣住,最后只写出了3种
面试官上来就让手撕HashMap的7种遍历方式,当场愣住,最后只写出了3种
44 1