菜鸟笔记
提升您的技术认知

菜鸟教程

rapidjson 构造数组将函数实现放在头文件中RapidJSON解析和生成Json绝对路径和相对路径gcc 优化选项 -O1 -O2 -O3 -Os 优先级Python求一个整数位数的方法python中判断数字位数的几种方法python计算分位数查看hive的版本如何查看hadoop的版本elasticsearch查看所有indexsublime 列模式 列编辑shell遍历目录下所有文件http-parser解析http报文详解supervisor守护工具配置lnmp为已有站点手动更新ssl证书记录java 最长回文、最长回文子串ssh免密码登录为Linux内核开启BBR加速frp服务开机自启x86架构下,页面大小为什么是4K?如何限制对象只能建立在堆上或者栈上进程间通信的方式SyntaxError: Non-ASCII character '\xe5'TCP 连接半关闭问题ucontext 协程库代码分析python中yield的用法详解为PHP7.0安装redis扩展ucontext 简单协程库ImportError: No module named cv2的完美解决方法HashMap扩容全过程关于HashMap常见面试考点(底层原理+扩容机制)DOS批处理中的字符串处理详解(字符串截取)Linux下如何查找.sh后缀的文件core文件出现“is not a core dump: File format not recognized”的原因和解决方法(看/proc/pid/limits)记一次docker问题定位(perf,iostat等性能分析)Protocol Buffers 2.5.0 安装python 使用thrift序列化与反序列化对象PHP的base64_decode乱码linux中后台运行 java -jarLinux常用命令--文件搜索Linux常用命令--文件基础操作与文件权限变更Linux常用命令--软件包管理之(RPM包管理)Linux常用命令--文件编辑与查看Linux常用命令--文件压缩与挂载Linux常用命令--系统管理Linux常用命令--系统管理之(用户管理、用户组管理)Linux常用命令--系统管理之(进程管理、定时任务、系统监控)Linux常用命令--软件包管理之(服务管理)Linux常用命令--软件包管理之(yum与源码包安装)Linux初窥:Linux下SSH免密码登录配置如何查看CentOS7的版本信息Linux环境变量文件介绍Linux下Tomcat的安装与配置CentOS解决-bash: vim: command not found10 个提高效率的 Linux 命令别名shell比较浮点数和整数crontab 30秒执行一次Python中字典合并的四种方法shell查看CPU 硬盘 内存使用率Python 四大主流 Web 编程框架python:web后台框架简单实现如何使用 BRPC Dummy Serverlist、vector使用erase()时需要注意的地方——迭代器失效容器删除元素后迭代器失效_STL源码剖析——vector容器STL的erase()陷阱-迭代器失效总结.bashrc中定义实用的别名和函数

HashMap扩容全过程

阅读 : 200

   1.如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方,一个是原下标的位置,另一种是在下标为<原下标+原容量>的位置

  2.重新调整HashMap大小存在什么问题吗?

  • 当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。(多线程的环境下不使用HashMap)
  • 为什么多线程会导致死循环,它是怎么发生的?

  HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。这时候,HashMap需要扩展它的长度,也就是    进行Resize。

  Resize是什么?首先我们先认识2个变量 

  1.Capacity

  HashMap的当前长度。HashMap的长度是2的幂。

  2.LoadFactor

  HashMap负载因子,默认值为0.75f。

  衡量HashMap是否进行Resize的条件如下:

  HashMap.Size >= Capacity * LoadFactor

   Resize步骤

  1.扩容:创建一个新的Entry空数组,长度是原数组的2倍。

  2.ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。为什么要重新Hash呢?因为长度扩大以后,Hash的规则也随之改变。

  hash公式:index = HashCode(Key) & (Length - 1)

  我们假设rehash之前的HashMap是这样的

  

 

  那么rehash之后可能是这样

  

 

  代码是这样的

  

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

/**

 * Transfers all entries from current table to newTable.

 */

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) {

                e.hash = null == e.key ? 0 : hash(e.key);

            }

            int i = indexFor(e.hash, newCapacity);

            e.next = newTable[i];

            newTable[i] = e;

            e = next;

        }

    }

}

  现在假设一个场景,有一个hashmap如下

  

当有A,B这两个线程要对该hash map进行put操作

此时由于空间的不足,该hashmap必将进行扩容

假如此时线程B遍历到Entry3对象,刚执行完红框里的这行代码,线程就被挂起。对于线程B来说:

e = Entry3

next = Entry2

这时候线程A畅通无阻地进行着Rehash,当ReHash完成后,结果如下(图中的e和next,代表线程B的两个引用):

直到这一步,看起来没什么毛病。接下来线程B恢复,继续执行属于它自己的ReHash。线程B刚才的状态是:

 

e = Entry3

next = Entry2

 

我们继续执代码,Entry3放入了线程B的数组下标为3的位置,并且e指向了Entry2。此时e和next的指向如下:

e = Entry2

next = Entry2

 

接下来用头插法把Entry2插入到了线程B的数组的头结点

e = Entry2

next = Entry3

e = Entry3

next = Entry3.next = null

 

newTable[i] = Entry2这里若果是正常情况是newTable[i] =null,但是由于Entry2的hash被定为带同一个数组地址

e = Entry3

Entry2.next = Entry3

Entry3.next = Entry2

链表出现了环形!导致了死循环(多线程下请使用CocurrentHashMap)