当前位置： 首页 > article >正文

对HashMap的理解

article 2024/11/16 3:23:11

马上要秋招了，HashMap作为重要的知识点，一直没时间整理，今天晚上室友太吵睡不着，整理一下HashMap的笔记

在我看来，从代码层次呢，分为带参数的和不带参数的；HashMap从版本方面，分为JDK1.7之前，和JDK1.8之后；底层主要使用的方法，就是hashcode和equals方法。JDK1.7之前，使用的是数组和链表的组合，JDK1.8之后，使用的是数组+链表+红黑树的组合。

HashMap的优点：结合了数组和链表两种组合，（JDK1.8后新增了红黑树）这种结构使得HashMap能够提供快速的查找、插入和删除操作

目录

一、先从代码构造方法入手

1.无参构造

 2.带参构造——第一个参数：底层数组的长度；第二个参数：加载因子

二、版本方面：分为JDK1.7之前的，和JDK1.8之后的；

1.以JDK1.7为例展开介绍

1.1 一般的差异和问题都是围绕 增加展开的;

1.1.1  增加时，键（key）不能相同，如果相同就会发生覆盖，成为“改”，返回值就是被覆盖的值（value）。

1.1.2  在底层代码中，每个key都有对应的哈希值（hashcode()），根据哈希值得到在数组的索引，根据索引找到位置

源码：通过二次散列和扰动函数，增加哈希值的随机性和分布的均匀性，减少哈希冲突的机会

具体过程：

1.1.3 数组的扩容：

条件：（同时满足）

过程：

特殊情况：

在扩容条件这一块，有两种极端情况：

扩容过程时候启用了多线程：

1.2  modCount：追踪结构性修改的次数

用途一：在循环的时候不可以使用集合的方法来进行元素的添加（put）或者删除（remove）

用途二：避免并发修改—— 当多个线程对集合进行操作时，一条线程去添加元素，另一条去删除元素，最终肯定会出现问题，modCount可以提前停止程序的运行，并抛出异常ConcurrentModificationException。

一、先从代码构造方法入手

1.无参构造

        HashMap<String,String> hm = new HashMap<>();

 2.带参构造——第一个参数：底层数组的长度；第二个参数：加载因子

        HashMap<String,String> hm = new HashMap<>(16,0.75F);

解释：这两个参数都是定义一个底层数组长度为16，加载因子为0.75的HashMap双列链表，这个链表的泛型为 String类型，也就是<key,value>的类型。注意：加载因子是扩容条件之一。

二、版本方面：分为JDK1.7之前的，和JDK1.8之后的；

1.以JDK1.7为例展开介绍

1.1 一般的差异和问题都是围绕 增加展开的;

hm.put("a","App");
hm.put("b","Box");
1.1.1  增加时，键（key）不能相同，如果相同就会发生覆盖，成为“改”，返回值就是被覆盖的值（value）。
hm.put("b","Boy"); //覆盖key="b"的值，并将原本的值返回，
1.1.2  在底层代码中，每个key都有对应的哈希值（hashcode()），根据哈希值得到在数组的索引，根据索引找到位置
源码：通过二次散列和扰动函数，增加哈希值的随机性和分布的均匀性，减少哈希冲突的机会
  • 计算哈希值——hash()方法
    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
	            //对字符串键使用备选哈希函数
                return sun.misc.Hashing.stringHash32((String) k);
            }
            //随机种子,用来降低冲突发生的几率
            h = hashSeed;
        }
        //二次散列：增加哈希值的随机性和分布的均匀性
        h ^= k.hashCode();

        //扰动函数
        //混合高低位，极大的避免了因为低位的相同而导致的哈希冲突。
        //由于最后要和数组长度 相与，数组的长度一般不会超过4位二进制
        //所以一般用的就是低四位二进制位，如果不进行下面操作，
        //一个hashCode()得出的是32位二进制位，就会有 2^18 种可能性会发生哈希冲突
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
  •  根据哈希值计算索引——indexFor()方法：
   static int indexFor(int h, int length) {
	    //把hash值和数组的长度进行“与”操作
        //保证计算出的索引在 数组索引范围内
        return h & (length-1);
    }
具体过程：
  • 如果这个位置（索引处）没人（元素），直接坐下（放进数组）。
  • 如果这个位置有人了，调用equals方法，对比一下key值，如果两个key相同，直接将值value覆盖；如果不同（也就是发生了哈希碰撞），霸占他的位置，让他坐下一排（头连接：新元素放在数组中，老元素作为链表元素连接到新元素后面）；
1.1.3 数组的扩容：
条件：（同时满足）
  • 当前数组中的元素数量 >= 数组的阈值（阈值 = 数组的长度 * 加载因子——> 16 * 0.75 = 12），也就是超过了12；
  • 当前要存的位置已经有元素了，且两者的键不同（哈希碰撞）。
过程：
  • 以原数组长度的两倍（16 * 2 = 32） 去创建一个新数组；
  • 将老数组的元素从0索引开始，有链表先算链表，从链表头元素依次向下取，等链表结束后，再按照数组索引向下取元素，取出来的元素依次重新计算哈希值，再放入新数组中。
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next; // 保存下一个节点的引用，防止在移动节点过程中断链
            if (rehash) { //一般为false
                e.hash = null == e.key ? 0 : hash(e.key); // 重新计算hash值
            }
            int i = indexFor(e.hash, newCapacity); // 计算在新table中的位置
            e.next = newTable[i]; // 将e节点指向新table的头节点
            newTable[i] = e; // 将新table的头节点指向e
            e = next; // 移动到下一个节点
        }
    }
}
特殊情况：
在扩容条件这一块，有两种极端情况：
  • 第一种，可能存16个元素，正好16个元素哈希值都不同，且索引也不同，这样当存入第17个元素时，才会发生了哈希碰撞，触发扩容机制。
  • 第二种，最多存16+15 = 31个，正好前11个元素全部发生哈希碰撞，此时小于阈值不满足第一个条件，然后后面15个元素都没有发生哈希碰撞，不满足第二个条件，当存入下一个的时候，才会触发扩容机制
扩容过程时候启用了多线程：

问题：由于老数组扩容存入新数组时候，需要重新计算哈希值，然后放入老数组，但是有可能老数组中同一条链表上的元素，被倒序重新放入了新数组中（头连接，后来者居上）；当两条线程同时进行数组扩容时候，第一条线程扩容完后，第二条线程的next和e的指向的变反了，导致出现环路，报出异常。

参考文档：

详细https://www.cnblogs.com/seeall/p/18063073icon-default.png?t=O83Ahttps://www.cnblogs.com/seeall/p/18063073简单：HashMap多线程扩容导致死循环解析（JDK1.7）_hashmap1.7 扩容死循环问题-CSDN博客文章浏览阅读616次，点赞11次，收藏12次。由于头插法的原因，再次执行头插法的时候会将原来的链表顺序反过来，所以当第一个线程执行完扩容之后会将顺序从。最后由于e等于null，退出循环，当下次遍历到该元素时就会进入死循环。1->2->3 到 3->2->1。线程二第一次执行插入结束后。线程二准备第二次循环结束后。线程二第二次执行插入结束后。线程二准备第二次循环结束后。线程二第三次执行插入结束后。线程二准备第三次循环结束后。_hashmap1.7 扩容死循环问题https://blog.csdn.net/qq_51902025/article/details/135628412

解决方法：

  • 第一种：防止扩容——创建HashMap的同时设置合适的数组长度和加载因子。
  • 第二种：在开启多线程的同时加锁——synchronized

 

 

1.2  modCount：追踪结构性修改的次数

用途一：在循环的时候不可以使用集合的方法来进行元素的添加（put）或者删除（remove）
  • 原因：在JDK1.7中，HashMap在这个版本中通过modCount字段来追踪结构性修改的次数，调用迭代器方法时（增强for循环编译成class文件时也会转换成迭代器的方法，Lambda表达式底层也是迭代器或增强for循环），会将modCount 赋值给expectedModCount，每次调用迭代器中的next()方法，都会检查expectedModCount和modCount是否相等，如果不相等则抛出ConcurrentModificationException异常。
  • 解决方法：需要在遍历的同时对元素进行添加或者删除，需要调用迭代器（Iterator）中的方法。其内部会对expectedModCount重新赋值。
用途二：避免并发修改—— 当多个线程对集合进行操作时，一条线程去添加元素，另一条去删除元素，最终肯定会出现问题，modCount可以提前停止程序的运行，并抛出异常ConcurrentModificationException。

JDK1.8下一章再写吧，一点这个写了4个小时，中间电脑蓝屏了一次，打开后全没了，还以为白写了2多小时，没想到自动保存草稿了，嗯~很nice。


http://www.kler.cn/a/292504.html

相关文章：

  • 云计算研究实训室建设方案
  • javaWeb小白项目--学生宿舍管理系统
  • 两种鼠标hover切换对应图片方法对比
  • goframe开发一个企业网站 统一返回响应码 18
  • android studio 更改gradle版本方法（备忘）
  • 行业类别-金融科技-子类别区块链技术-细分类别智能合约-应用场景供应链金融课题
  • 使用本地预训练模型可视化卷积每一部分
  • 基于自适应多变量超扭转的 Lyapunov 重新设计 RLV 姿态控制
  • Facebook与区块链：构建更安全的社交网络生态
  • MFC dll无法显示tooltip问题
  • Java-数据结构-链表-习题（三）(๑´ㅂ`๑)
  • java开发简历详解
  • Dubbo缓存
  • HTML 基础知识详解与代码示例
  • C++笔记16•数据结构:关联式容器map和set•
  • Java健康养老智慧相伴养老护理小程序系统源码代办陪诊陪护更安心
  • 阿里云身份证二要素详细使用
  • 第T2周：彩色图片分类
  • 828华为云征文｜基于华为云Flexus云服务器X搭建jumpserver堡垒机软件
  • 电子病历、开药发药、住院检查、会员管理，SaaS模式B/S架构的云医院管理系统源码，云计算技术的医疗信息化解决方案
  • 经验笔记：Feeds流设计与实现
  • SpringMVC 第一次复学笔记
  • 解决 EasyExcel BigDecimal 加%的问题
  • 请解释Java Web中的Filter的作用和使用场景。什么是Java Web中的JSP？请解释其与Servlet的关系及各自优势。
  • OPC DA
  • 2024数学建模国赛高教社杯C题:农作物的种植策略 思路代码文章助攻手把手保姆级