Java 之 HashMap 集合

Wesley13 等级 258 0 0

一、HashMap 概述

java.util.HashMap<k,v> 集合 implements Map<k,v> 接口

HashMap 集合的特点

1、HashMap 集合底层是哈希表:查询速度特别的快

JDK 1.8 之前:数组+单向链表

JDK 1.8 之后:数组+单向链表 | 红黑树(链表的长度超过8):提高查询的速度

2、HashMap 集合是一个无序的集合,存储元素和取出元素的顺序有可能不一致

二、HashMap 存储自定义类型键值

HashMap存储自定义类型键值

Map集合保证key是唯一的:作为key的元素,必须重写hashCode方法和equals方法,以保证key唯一

三、遍历集合

参考 Map 集合的遍历方式:Map 遍历

四、HashMap 源码分析

1、hashCode 值

hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法,它将任意大小的数据映射到一个固定大小的序列上,这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的,唯一性是指相同的“对象”产生的hash code永远是一样的。

Java 之 HashMap 集合

2、Entry 数组

HashMap和Hashtable是散列表,其中维护了一个长度为2的幂次方的Entry类型的数组table,数组的每一个元素被称为一个桶(bucket),你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象,放到了某个table[index]桶中。

使用数组的目的是查询和添加的效率高,可以根据索引直接定位到某个table[index]。

(1)数组元素类型: Map.Entry

Java 之 HashMap 集合

(2)初始容量:16

Java 之 HashMap 集合

(3)扩容为原来的2倍

Java 之 HashMap 集合

(4)那么 HashMap 是如何决定某个映射关系存在哪个桶的呢?

因为hash code是一个整数,而数组的长度也是一个整数,有两种思路:

①hash code值 % table.length会得到一个[0,table.length-1]范围的值,正好是下标范围,但是用%运算,不能保证均匀存放,可能会导致某些table[index]桶中的元素太多,而另一些太少,因此不合适。

②hash code值 & (table.length-1),因为table.length是2的幂次方,因此table.length-1是一个二进制低位全是1的数,所以&操作完,也会得到一个[0,table.length-1]范围的值。

Java 之 HashMap 集合

                              Java 之 HashMap 集合

3、HashMap 中的散列函数 hash()

    JDK1.7和JDK1.8关于hash()的实现代码不一样,但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果,尽量的均匀分布。

Java 之 HashMap 集合

  这里用 JDK1.8 的实例分析一下:

Java 之 HashMap 集合

  思考:那么,JDK1.8为什么要保留高16位呢?

因为一个HashMap的table数组一般不会特别大,至少在不断扩容之前,那么table.length-1的大部分高位都是0,直接用hashCode和table.length-1进行&运算的话,就会导致总是只有最低的几位是有效的,那么就算你的hashCode()实现的再好也难以避免发生碰撞,这时保留高16位的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征,显著减少了碰撞冲突的发生。

4、如何解决冲突?

虽然从设计hashCode()到上面HashMap的hash()函数,都尽量减少冲突,但是仍然存在两个不同的对象返回的hashCode值相同,或者hashCode值就算不同,通过hash()函数计算后,得到的index也会存在大量的相同,因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办?

JDK1.8之间使用:数组+链表的结构。

JDK1.8之后使用:数组+链表/红黑树的结构。

Java 之 HashMap 集合

                   Java 之 HashMap 集合

5、JDK1.7里HashMap 中几个常量与变量是什么?

(1)默认数组容量

Java 之 HashMap 集合

(2)默认加载因子

Java 之 HashMap 集合

思考: loadFactor 设置为 0.1 与 0.9 有什么区别?

当 loadFactor 为 0.1 时,扩容太频繁

当 loadFactor 为 0.9时,会导致 table[index] 下面的链表会很长,查询速度会降低。

(3)加载因子

Java 之 HashMap 集合

(4)阈值(临界值)

Java 之 HashMap 集合

6、JDK 1.6 中HashMap 的构造方法是怎么样的?

图1

Java 之 HashMap 集合

     图2

     Java 之 HashMap 集合

  可以看出 JDK1.6 中 table 数组初始化为了一个长度为 16 的空数组,默认加载因子为0.75,阈值为12。

6、JDK 1.7 中的 HashMap 的构造方法是怎么样的?

图1

Java 之 HashMap 集合

        图2

Java 之 HashMap 集合

               图3

Java 之 HashMap 集合

  可以从无参构造中看出,调用了有参的构造,但是有参的构造方法中并没有做什么,但是从上面的图三可以看出 table 数组初始化为了一个长度为0的长度为0的数组。

7、JDK 1.7 中的 put 方法

源码分析:

Java 之 HashMap 集合

Java 之 HashMap 集合

执行步骤:

(1)先判断table是否为空数组,如果是,先初始化长度为16的Entry 类型的数组,并且把threshold计算为12;

这里如果你手动指定了数组的capacity,那么如果这个capacity不是2的n次方,会自动纠正为2的n次方;

(2)如果key是null,特殊对待,key为null的映射关系的hash值为0,index也为0;

(3)key 不是 null,那么先计算hash(key)获得 hash 值

(4)再通过处理过的hash值&(table.length-1)计算index,决定是在table[index],index在[0,table.length-1]范围内;

(5)判断table[index]桶下是否存在某个Entry的key与新的key的“相同”(hash值相同并且(满足key的地址相同或key的equals返回true)),如果是,用新的value替换原来的value;

(6)如果不存在,判断是否满足size达到阈值(threshold)并且table[index]不是null,如果是,先扩容;扩容会导致原来table中的所有元素都会重新计算位置,并调整存储位置;

(7)添加一个新的Entry对象至table[index](注意,这个index也是重新计算过的)中,并且把当前table[index]下的所有元素都连接到新的Entry的next下。

(8)size++,元素个数增加

  思考:

1、为什么要把数组的长度纠正为2的n次方?

① 后面算index = hash & table.length-1,这样才能保证[0,table.length-1]范围内

② 2的次方,根据它的散列算法,可以保证比较均匀的分散在它的数组的各个位置

2、扩容的条件是什么?

① size达到阈值threshold

② table[index]下面已经有映射关系,即不为空

8、JDK 1.8 中的 HashMap 的构造方法

Java 之 HashMap 集合

          Java 之 HashMap 集合

         Java 之 HashMap 集合

  可以看出,无参构造方法给加载因子赋值为0.75,其他的都为默认值。

9、JDK 1.8 中常量与变量

(1)_DEFAULT_INITIAL_CAPACITY_:默认的初始容量1<<4 (16)

(2)_MAXIMUM_CAPACITY_:最大容量  1 << 30

(3)static final float DEFAULT_LOAD_FACTOR = 0.75:默认加载因子 0.75

(4)static final int TREEIFY_THRESHOLD = 8; 默认树化阈值8,该阈值的作用是判断是否需要树化,树化的目的是为了提高查询效率;当某个链表的结点个数达到这个值时,可能会导致树化

(5)static final int MIN_TREEIFY_CAPACITY = 64;最小树化容量64,当某个链表的结点个数达到8时,还要检查table的长度是否达到64,如果没有达到,先扩容解决冲突问题

(6)static final int UNTREEIFY_THRESHOLD = 6;默认反树化阈值6,当删除了结点时,如果某棵红黑树的结点个数已经低于该值时,会把树重新变成链表,目的是减少复杂度

(7)Node<K,V>[] table:数组

(8)int size:记录有效映射关系的对数,也是Entry对象的个数

(9)int threshold:阈值,当size达到阈值时,考虑扩容

(10)double loadFactor:加载因子,影响扩容的频率

10、JDK 1.8 的 put 方法

源码分析:

Java 之 HashMap 集合

    (1)hash() 方法:使hashCode值更加散列

 1     static final int hash(Object key) {
 2         int h;
 3         //如果key是null,hash是0
 4         //如果key非null,用key的hashCode值 与 key的hashCode值高16进行异或
 5         //        即就是用key的hashCode值高16位与低16位进行了异或的干扰运算
 6         
 7         /*
 8         index = hash & table.length-1
 9         如果用key的原始的hashCode值  与 table.length-1 进行按位与,那么基本上高16没机会用上。
10         这样就会增加冲突的概率,为了降低冲突的概率,把高16位加入到hash信息中。
11         */
12         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
13     }

(2)putVal() 方法

 1   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 2                    boolean evict) {
 3         Node<K,V>[] tab; //数组
 4         Node<K,V> p; //一个结点
 5         int n, i;//n是数组的长度   i是下标
 6         
 7         //tab和table等价
 8         //如果table是空的
 9         if ((tab = table) == null || (n = tab.length) == 0){
10             //n = (tab = resize()).length;
11             tab = resize();
12             n = tab.length;
13             /*
14             如果table是空的,resize()完成了
15             ①创建了一个长度为16的数组
16             ②threshold = 12
17             n= 16
18             */
19         }
20         //i = (n - 1) & hash ,下标 = 数组长度-1 & hash
21         //p = tab[i] 
22         //if(p==null) 条件满足的话说明 table[i]还没有元素
23         if ((p = tab[i = (n - 1) & hash]) == null){
24             //把新的映射关系直接放入table[i]
25             tab[i] = newNode(hash, key, value, null);
26             //newNode()方法就创建了一个Node类型的新结点,新结点的next是null
27         }else {
28             Node<K,V> e; 
29             K k;
30             //p是table[i]中第一个结点
31             //if(table[i]的第一个结点与新的映射关系的key重复)
32             if (p.hash == hash &&
33                 ((k = p.key) == key || (key != null && key.equals(k)))){
34                 e = p;//用e记录这个table[i]的第一个结点
35             }else if (p instanceof TreeNode){//如果table[i]第一个结点是一个树结点
36                 //单独处理树结点
37                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
38             }else {
39                 //table[i]的第一个结点不是树结点,也与新的映射关系的key不重复
40                 //binCount记录了table[i]下面的结点的个数
41                 for (int binCount = 0; ; ++binCount) {
42                     //如果p的下一个结点是空的,说明当前的p是最后一个结点
43                     if ((e = p.next) == null) {
44                         //把新的结点连接到table[i]的最后
45                         p.next = newNode(hash, key, value, null);
46                         
47                         //如果binCount>=8-1,达到7个时
48                         if (binCount >= TREEIFY_THRESHOLD - 1){ // -1 for 1st
49                             //要么扩容,要么树化
50                             treeifyBin(tab, hash);
51                         }
52                         break;
53                     }
54                     //如果key重复了,就跳出for循环
55                     if (e.hash == hash &&
56                         ((k = e.key) == key || (key != null && key.equals(k)))){
57                         break;
58                     }
59                     p = e;
60                 }
61             }
62             //如果这个e不是null,说明有key重复,就考虑替换原来的value
63             if (e != null) { // existing mapping for key
64                 V oldValue = e.value;
65                 if (!onlyIfAbsent || oldValue == null){
66                     e.value = value;
67                 }
68                 afterNodeAccess(e);
69                 return oldValue;
70             }
71         }
72         ++modCount;
73         
74         //元素个数增加
75         //size达到阈值
76         if (++size > threshold){
77             resize();//一旦扩容,重新调整所有映射关系的位置
78         }
79         afterNodeInsertion(evict);//什么也没干
80         return null;
81     }

(3)resize() 方法

 1 final Node<K,V>[] resize() {
 2         Node<K,V>[] oldTab = table;//oldTab原来的table
 3         //oldCap:原来数组的长度
 4         int oldCap = (oldTab == null) ? 0 : oldTab.length;
 5         
 6         //oldThr:原来的阈值
 7         int oldThr = threshold;//最开始threshold是0
 8         
 9         //newCap,新容量
10         //newThr:新阈值
11         int newCap, newThr = 0;
12         if (oldCap > 0) {//说明原来不是空数组
13             if (oldCap >= MAXIMUM_CAPACITY) {//是否达到数组最大限制
14                 threshold = Integer.MAX_VALUE;
15                 return oldTab;
16             }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
17                      oldCap >= DEFAULT_INITIAL_CAPACITY){
18                 //newCap = 旧的容量*2 ,新容量<最大数组容量限制
19                 //新容量:32,64,...
20                 //oldCap >= 初始容量16
21                 //新阈值重新算 = 24,48 ....
22                 newThr = oldThr << 1; // double threshold
23             }
24         }else if (oldThr > 0){ // initial capacity was placed in threshold
25             newCap = oldThr;
26         }else {               // zero initial threshold signifies using defaults
27             newCap = DEFAULT_INITIAL_CAPACITY;//新容量是默认初始化容量16
28             //新阈值= 默认的加载因子 * 默认的初始化容量 = 0.75*16 = 12
29             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
30         }
31         if (newThr == 0) {
32             float ft = (float)newCap * loadFactor;
33             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
34                       (int)ft : Integer.MAX_VALUE);
35         }
36         threshold = newThr;//阈值赋值为新阈值12,24.。。。
37         
38         //创建了一个新数组,长度为newCap,16,32,64.。。
39         @SuppressWarnings({"rawtypes","unchecked"})
40             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
41         table = newTab;
42         
43         
44         if (oldTab != null) {//原来不是空数组
45             //把原来的table中映射关系,倒腾到新的table中
46             for (int j = 0; j < oldCap; ++j) {
47                 Node<K,V> e;
48                 if ((e = oldTab[j]) != null) {//e是table下面的结点
49                     oldTab[j] = null;//把旧的table[j]位置清空
50                     if (e.next == null)//如果是最后一个结点
51                         newTab[e.hash & (newCap - 1)] = e;//重新计算e的在新table中的存储位置,然后放入
52                     else if (e instanceof TreeNode)//如果e是树结点
53                         //把原来的树拆解,放到新的table
54                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
55                     else { // preserve order
56                         Node<K,V> loHead = null, loTail = null;
57                         Node<K,V> hiHead = null, hiTail = null;
58                         Node<K,V> next;
59                         /*
60                         把原来table[i]下面的整个链表,重新挪到了新的table中
61                         */
62                         do {
63                             next = e.next;
64                             if ((e.hash & oldCap) == 0) {
65                                 if (loTail == null)
66                                     loHead = e;
67                                 else
68                                     loTail.next = e;
69                                 loTail = e;
70                             }
71                             else {
72                                 if (hiTail == null)
73                                     hiHead = e;
74                                 else
75                                     hiTail.next = e;
76                                 hiTail = e;
77                             }
78                         } while ((e = next) != null);
79                         if (loTail != null) {
80                             loTail.next = null;
81                             newTab[j] = loHead;
82                         }
83                         if (hiTail != null) {
84                             hiTail.next = null;
85                             newTab[j + oldCap] = hiHead;
86                         }
87                     }
88                 }
89             }
90         }
91         return newTab;
92     }

(4)newNode() 方法

1  Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
2         //创建一个新结点
3        return new Node<>(hash, key, value, next);
4     }

(5)treeifyBin() 方法

 1 final void treeifyBin(Node<K,V>[] tab, int hash) {
 2         int n, index; 
 3         Node<K,V> e;
 4         //MIN_TREEIFY_CAPACITY:最小树化容量64
 5         //如果table是空的,或者  table的长度没有达到64
 6         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 7             resize();//先扩容
 8         else if ((e = tab[index = (n - 1) & hash]) != null) {
 9             //用e记录table[index]的结点的地址
10             TreeNode<K,V> hd = null, tl = null;
11             /*
12             do...while,把table[index]链表变为红黑树
13             */
14             do {
15                 TreeNode<K,V> p = replacementTreeNode(e, null);
16                 if (tl == null)
17                     hd = p;
18                 else {
19                     p.prev = tl;
20                     tl.next = p;
21                 }
22                 tl = p;
23             } while ((e = e.next) != null);
24             
25             if ((tab[index] = hd) != null)
26                 hd.treeify(tab);
27         }
28     }   

Java 之 HashMap 集合

     存储过程:

(1)先计算key的hash值,如果key是null,hash值就是0,如果为null,使用(h = key.hashCode()) ^ (h >>> 16)得到hash值;

(2)如果table是空的,先初始化table数组;

(3)通过hash值计算存储的索引位置index = hash & (table.length-1)

(4)如果table[index]==null,那么直接创建一个Node结点存储到table[index]中即可

(5)如果table[index]!=null,并且table[index]是一个TreeNode结点,说明table[index]下是一棵红黑树,如果该树的某个结点的key与新的key“相同”(hash值相同并且(满足key的地址相同或key的equals返回true)),那么用新的value替换原来的value,否则将(key,value)封装为一个TreeNode结点,连接到红黑树中。

(6)如果table[index]不是一个TreeNode结点,说明table[index]下是一个链表,如果该链表中的某个结点的key与新的key“相同”,那么用新的value替换原来的value,否则需要判断table[index]下结点个数,如果没有达到**TREEIFY_THRESHOLD****_(8)_**个,那么(key,value)将会封装为一个Node结点直接链接到链表尾部。

(7)如果table[index]下结点个数已经达到**TREEIFY_THRESHOLD(8)个,那么再判断table.length是否达到MIN_TREEIFY_CAPACITY(64)**,如果没达到,那么先扩容,扩容会导致所有元素重新计算index,并调整位置;

(8)如果table[index]下结点个数已经达到**TREEIFY_THRESHOLD(8)个并table.length也已经达到MIN_TREEIFY_CAPACITY(64)**,那么会将该链表转成一棵自平衡的红黑树,并将结点链接到红黑树中。

(9)如果新增结点而不是替换,那么size++,并且还要重新判断size是否达到threshold阈值,如果达到,还要扩容。

11、关于映射关系的 key 是否可以修改?

映射关系存储到HashMap中会存储key的hash值,这样就不用在每次查找时重新计算每一个Entry或Node(TreeNode)的hash值了,因此如果已经put到Map中的映射关系,再修改key的属性,而这个属性又参与hashcode值的计算,那么会导致匹配不上。

这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。

Java 之 HashMap 集合

收藏
评论区

相关推荐

3 手写Java HashMap核心源码
手写Java HashMap核心源码 上一章手写LinkedList核心源码,本章我们来手写Java HashMap的核心源码。 我们来先了解一下HashMap的原理。HashMap 字面意思 hash map,map是映射的意思,HashMap就是用hash进行映射的意思。不明白?没关系。我们来具体讲解一下HashMap的原理。 HashMap
深入理解 hashcode 和 hash 用法
摘要 二进制计算的一些基础知识 为什么使用 hashcode String 类型的 hashcode 方法 为什么大部分 hashcode 方法使用 31 HashMap 的 hash 算法的实现原理(为什么右移 16 位,为什么要使用 ^ 位异或) HashMap 为什
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
10 HashSet HashMap源码 Properties
2 HashSet底层是使用HashMap实现的。当使用add方法将对象添加到Set当中时,实际上是将该对象作为**底层所维护的Map对象的key**,而value则都是同一个Object对象(该对象我们用不上); 3\. HashMap底层维护一个Node数组,我们向HashMap中所放置的对象实际上是存储在该数组当中; HashMap中的Pu
Java中HashMap的实现原理
**总结:HashMap的实现原理:** 1. **利用key的hashCode重新hash计算出当前对象的元素在数组中的下标** 2. **存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中** 3. **获取时,直接找到hash值对应
java HashMap hash方法分析
下面分别分析下,JDK1.7 与 JDK1.8 中 hash方法的运算过程,并且左后结合JDK1.8 中 hash方法来进行详细说明。 JDK1.7 中HashMap 中hash table 定位算法:  int hash = hash(key.hashCode());  int i = indexFor(hash, table.length);  
java语言基础6
hashmap的数据结构,HashMap的数据结构是数组+链表+红黑树(红黑树since JDK1.8)。我们常把数组中的每一个节点称为一个桶。当向桶中添加一个键值对时,首先计算键值对中key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这种现象称为碰撞,这时按照尾插法(jdk1.7及以前为头插法)的方式添
Collectors.groupingBy分组后的排序问题
默认groupingBy代码里会生成一个HashMap(hashMap是无序的,put的顺序与get的顺序不一致) * HashMap是无序的,HashMap在put的时候是根据key的hashcode进行hash然后放入对应的地方。所以在按照一定顺序put进HashMap中,然后遍历出HashMap的顺序跟put的顺序不同(除非在put的时候key已
GridView实现九宫格
GridView gv=(GridView)findViewById(R.id.g1);         ArrayList<HashMap<String,Object>>data=new ArrayList<HashMap<String, Object>>();         for(int i=0;i<images.length;i++)
HashMap 怎么 hash?又如何 map?
HashMap 是 Java 中 Map 的一个实现类,它是一个双列结构(数据+链表),这样的结构使得它的查询和插入效率都很高。HashMap 允许 null 键和值,它的键唯一,元素的存储无序,并且它是线程不安全的。 ![](https://oscimg.oschina.net/oscnet/24e81018b69298cf434a8eb39682070
HashMap中神奇的h & (length
众所周知,HashMap是基于Hash表的Map接口实现,HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。但是知道了Hash值之后,又是怎么确定出key在数组中的索引呢? 根据源码得知如下方法 static
HashMap多线程下死循环的坑记录
**PS:不得不说Java编程思想这本书是真心强大..** **学习内容:** **1.HashMap<K,V>在多线程的情况下出现的死循环现象** **当初学Java的时候只是知道HashMap<K,V>在并发的情况下使用的话,会出现线程安全问题,但是一直都没有进行深入的研究,也是最近实验室的徒弟在问起这个问题的原因之后,才开始进行了一个深入的研究
HashMap容量分析
了解过HashMap都应该知道,HashMap内部会创建一个Entry<K, V> table数组来存放元素,而且这个数组的长度永远都是2的指数次方。那么问题来了,为什么选择2的指数次方呢? 首先,思考一下计算出hash值后,应该存放在数组的哪个位置?显然用求余(模)最简单。然而模的效率并不高,看看JDK是怎么做的,indexFor方法: st
HashMap解惑
 HashMap中有一些我们容易忽视的点 1\. 关于key的hash和equals public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); }
Java学习总结
Java HashMap和HashTable jdk1.8中采用数组+链表+红黑树实现 首先会创建一个默认长度为16,默认加载因为0.75的table数组 根据hash值和数组的长度计算应存入的位置 判断当前位置是否为空,如果为空则直接存入 如果当前位置不为空,则调用equals方法比较属性值 如果一样则替换为新的,如果不一样则采用头插法插入 当节点数多于8