图片 15

Java源码分析:HashMap 1.8 相对于1.7 到底更新了什么?

Posted by

图片 1

HashMap是Java使用频率很高的容器对象,内部使用了很多优化算法,源码非常值得学习.

  • HashMapJavaAndroid 开发中非常常见
  • HashMap 1.8 相对于 HashMap 1.7 更新多
  • 今天,我将通过源码分析HashMap 1.8 ,从而讲解HashMap 1.8 相对于
    HashMap 1.7 的更新内容,希望你们会喜欢。

关于HashMap

  • 非线程安全

HashTable对put和get使用了synchronized关键字,线程安全,但是已经被废弃,ConcurrentHashMap是推荐使用的线程安全,高并发Map实现

  • key-value存储
  • key和value都可以为null,多个为null的key会被后面的覆盖
  • key要求为不可变对象(引用类型必须重写hashCode和equals方法)

为了确保同一个对象的hash计算后的值唯一,不同的对象hash计算后的值一定不等.

  • HashMap内部存储结构为数组+链表+红黑树(JDK1.8开始)

图片 2

HashMap存储结构

  1. 本文基于版本 JDK 1.8,即 Java 8
  2. 关于版本 JDK 1.7,即
    Java 7,具体请看文章Java:手把手带你源码分析 HashMap 1.7

HashMap存储结构

在HashMap内部,有一个Node[] table
字段,Node类型就是数据保存在HashMap内部时的实际对象,Node实现Map.Entry接口,本质就是一个键值对,Node对象会持有下一个结点的引用,由此可知Node对象又维护了一个单向链表.

//HashMap中Node对象
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {...}
       ...
}

图片 3示意图

HashMap使用哈希表的意义

HashMap使用了哈希表来存储,当key值哈希冲突之后使用链表保存冲突的值,当数据哈希计算之后得到数组下标,把数据放在对应下标的链表上.

Map<String,Integer> map = new HashMap<>();
map.put("key",123);

使用hash算法是为了尽量减少hash冲突,如果默认的node数组很大,那么发生冲突的几率也会减小,但是会浪费很多的内存空间,为了平衡效率和空间,HashMap采用了负载因子(loadFactor)和扩容提高空间使用率,提高存取效率.075是对空间和时间效率的一个平衡选择,不建议自行修改,除非对内存和时间效率有取舍有要求时才会进行修改.

负载因子的作用是控制HashMap扩容的时机,默认为0.75,HashMap初始的table大小为16.
简单来说 : 当存储数量>table.length*0.75时,就会触发HashMap扩容

//HashMap成员变量
//默认负载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f; 
//默认桶的大小,1左移4位,就是16
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4

图片 4

HashMap的table变量

根据上面这段注释,可以知道HashMap内部的数组只有在第一次使用的时候才会被初始化,在必要的时候会进行扩容,而且数组的长度总是2的n次方数,使用2的n次方的原因是为了在模运算和扩容是进行优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,使用了高位运算.

HashMap使用了很多的算法和优化提高性能,但是当数据量很大时,哈希冲突无法避免,使用链表会导致数据的查找性能急剧下降,所以在JDK1.8加入了红黑树,当链表长度达到8时.链表会转为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能.

由于红黑树是另一个知识点,不会在HashMap的小结中出现.

  • 类定义

功能实现-方法

HashMap的内部实现了很多算法和功能,其中三个最具有代表性的方法是:根据key计算哈希桶数组索引下标,put方法,扩容.所以对这三个方法进行深入.

1.确定哈希桶数组索引位置

不管增删改查,第一步操作都是根据key的hash值获取key在哈希桶中的下标.由于HashMap的数据结构是数组+链表,由于数组的访问速度是最快的,所以应该尽量将存入的元素分布在不同的数组下标中,使得每个位置上的元素只有一个,当使用hash算法求得这个位置的时候,对应下标的元素就是所需元素,不需要遍历该位置上的链表,所以查询效率会很高.

数组在在内存中是连续的,所以查询效率是最高的,而链表是不连续的内存空间,每一次查询都需要遍历链表.

确定下标的步骤:

  • 步骤1
    • 取key的hashCode
    • key的hashCode无符号右移16位
    • 右移后的值与右移前的值做与运算.

static final int hash(Object key) {
        int h;

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  • 步骤2
    • 将调用hash(Object key)方法后获取的值和哈希桶长度-1做与运算

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
int n ;
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
...
}

这里就是hash算法确定下标的算法,本质上的流程为:取key的hashCode值、高位运算、取模运算。

由于HashMap使用了hashCode,所以只要确保key对象的不变性,那么调用hash(Object
key)就一定能获取相同的哈希值,其次因为要确保下标要在哈希桶内,所以比较容易想到的是对哈希值和桶长度进行取模,这样就能保证元素的分布相对均匀.但是模运算消耗较大,所以在HashMap中的做法是使用h&(table.length-1),根据之前的分析可以,哈希桶的长度是2的n次方,所以table.length-1之后,二进制后的数字全部都是1,所以无论h的值是什么,都相当于取模的结果,但是&比%效率更高.

&比%效率高的证明

例如table.length = 16, h =5;
1111&0101 = 0101 ,即等于5,哈希桶下标为5

图片 5

图1-1 h^(table.length-1)计算

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
2.HashMap的put方法

图片 6

图2-2 HashMap的put方法执行流程

  • ①判断HashMap的哈希桶是否为null,通过resize()方法进行扩容.
  • ②判断哈希桶下标是否存在元素,不存在则插入元素

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //①第一次初始化table长度,
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //②判断下标位置元素是否为空,如果为空插入一个新的值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            ...//这里涉及到hash冲突后的处理
      }
}
  • ③当前元素不为空,证明发生了hash冲突,所以判断两个新旧两个key的值是否相同或相等,如果相等,用新value覆盖旧value
  • ④如果新插入的结点是TreeNode,即判断table[i]是否为红黑树,如果是则在树中插入该值,否则继续执行后序代码
  • ⑤遍历table[i],判断链表中结点是否有后继结点,如果后继结点为空则插入到队尾,同时判断当前链表长度是否大于8,如果大于8,则将链表转为红黑树
  • ⑥在遍历链表的过程中,如果发现新值的key已存在链表中,则覆盖旧的value为新value
  • ⑦插入成功后,判断实际存在的键值对数量size是否大于负载容量thredshold,如果超过,就调用resize()进行扩容

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
...
 Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                //当前链表为红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //遍历链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //将新值插入到链表队尾,
                        p.next = newNode(hash, key, value, null);
                        //判断当前链表长度是否大于8,是就转为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    ⑥覆盖链表中的旧value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
         ++modCount;
        if (++size > threshold)
         //扩容
            resize();
        afterNodeInsertion(evict);
        return null;
}
  • 主要简介
3.扩容机制

扩容就是重新计算HashMap中哈希桶的大小,向HashMap中不断添加元素,而数组必须在初始化定义长度,当数组不足以存放更多的元素,就需要扩大数组的长度,方法是使用一个新的数组代替已有的数组.就像装水时小桶换大桶.

扩容步骤:

  • ①判断旧的数组是否大于0,如果大于0且小于HashMap最大允许容量,则新的数组长度为旧数组长度*2
  • ②将旧数组的负载容量(长度负载因子)2作为新数组的负载容量
  • ③创建一个新的Node数组,长度为旧数组长度*2

 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) {
        //如果旧的哈希桶长度大于最大可值,则将最大负载设为Integer的最大值,返回旧哈希桶
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
        //将旧桶的大小左移1位,相当于乘2,就是新桶的大小,同时新桶数量必须小于最大容量,并且旧桶长度大于默认容量
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
...

}
  • ④遍历旧数组,判断元素哈希值&旧数组长度是否为0,如果为0则将元素放在原下标,如果不为0则key的新下标的值等于原下标+旧数组长度.
    图中n为旧数组长度,key1为key在旧数组中的hash值,key2是key在新数组中hash计算后的值
![](https://upload-images.jianshu.io/upload_images/2786935-7cabf8860aa98d0e.png)

图3-1 原key在新的哈希桶下标位计算方法



由图中可以得知,只要判断原key在高位新增的是0或是1,就能得到新的下标.



![](https://upload-images.jianshu.io/upload_images/2786935-d90c7d344129e7e2.png)

图3-2 key在新数组中下标计算方法

源码实现

final Node<K,V>[] resize() {
...
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //计算原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //放在原下标
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //放在新的下标,下标位置=原下标+旧数组成长度
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
...
}

参考资料:
Java
8系列之重新认识HashMap

图片 7示意图

  • HashMap 的实现在 JDK 1.7JDK 1.8 差别较大
  • 今天,我将对照 JDK 1.7的源码,在此基础上讲解 JDK 1.8
    HashMap 的源码解析

请务必打开JDK 1.7对照看:Java:手把手带你源码分析 HashMap 1.7

2.1 主要介绍

图片 8示意图

关于 红黑树 的简介

图片 9示意图

更加具体的了解,请:点击阅读文章

2.2 存储流程

注:为了让大家有个感性的认识,只是简单的画出存储流程,更加详细 &
具体的存储流程会在下面源码分析中给出

图片 10示意图

2.3 数组元素 & 链表节点的 实现类

  • HashMap中的数组元素 & 链表节点 采用 Node类 实现

JDK 1.7 的对比(Entry类),仅仅只是换了名字

  • 该类的源码分析如下

具体分析请看注释

/** * Node = HashMap的内部类,实现了Map.Entry接口,本质是 = 一个映射 * 实现了getKey()、getValue()、equals和hashCode()等方法 **/ static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 哈希值,HashMap根据该值确定记录的位置 final K key; // key V value; // value Node<K,V> next;// 链表下一个节点 // 构造方法 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } // 返回 与 此项 对应的键 public final V getValue() { return value; } // 返回 与 此项 对应的值 public final String toString() { return key + "=" + value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } /** * hashCode() */ public final int hashCode() { return Objects.hashCode ^ Objects.hashCode; } /** * equals() * 作用:判断2个Entry是否相等,必须key和value都相等,才返回true */ public final boolean equals { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey && Objects.equals(value, e.getValue return true; } return false; } }

2.4 红黑树节点 实现类

  • HashMap中的红黑树节点 采用 TreeNode 类 实现

 /** * 红黑树节点 实现类:继承自LinkedHashMap.Entry<K,V>类 */ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { // 属性 = 父节点、左子树、右子树、删除辅助节点 + 颜色 TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; boolean red; // 构造函数 TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } // 返回当前节点的根节点 final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } 

3.1 主要使用API

JDK 1.7 基本相同

V get(Object key); // 获得指定键的值V put(K key, V value); // 添加键值对void putAll(Map<? extends K, ? extends V> m); // 将指定Map中的键值对 复制到 此Map中V remove(Object key); // 删除该键值对boolean containsKey(Object key); // 判断是否存在该键的键值对;是 则返回trueboolean containsValue(Object value); // 判断是否存在该值的键值对;是 则返回true Set<K> keySet(); // 单独抽取key序列,将所有key生成一个SetCollection<V> values(); // 单独value序列,将所有value生成一个Collectionvoid clear(); // 清除哈希表中的所有键值对int size(); // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对boolean isEmpty(); // 判断HashMap是否为空;size == 0时 表示为 空 

3.2 使用流程

JDK 1.7 基本相同

  • 在具体使用时,主要流程是:
  1. 声明1个 HashMap的对象
  2. HashMap 添加数据(成对 放入 键 – 值对)
  3. 获取 HashMap 的某个数据
  4. 获取 HashMap 的全部数据:遍历HashMap
  • 示例代码

import java.util.Collection;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Set;public class HashMapTest { public static void main(String[] args) { /** * 1. 声明1个 HashMap的对象 */ Map<String, Integer> map = new HashMap<String, Integer>(); /** * 2. 向HashMap添加数据(成对 放入 键 - 值对) */ map.put("Android", 1); map.put("Java", 2); map.put; map.put("数据挖掘", 4); map.put("产品经理", 5); /** * 3. 获取 HashMap 的某个数据 */ System.out.println("key = 产品经理时的值为:" + map.get; /** * 4. 获取 HashMap 的全部数据:遍历HashMap * 核心思想: * 步骤1:获得key-value对 或 key 或 value的Set集合 * 步骤2:遍历上述Set集合(使用for循环 、 迭代器均可) * 方法共有3种:分别针对 key-value对 或 key 或 value */ // 方法1:获得key-value的Set集合 再遍历 System.out.println; // 1. 获得key-value对的Set集合 Set<Map.Entry<String, Integer>> entrySet = map.entrySet(); // 2. 遍历Set集合,从而获取key-value // 2.1 通过for循环 for(Map.Entry<String, Integer> entry : entrySet){ System.out.print(entry.getKey; System.out.println(entry.getValue; } System.out.println("----------"); // 2.2 通过迭代器:先获得key-value对的Iterator,再循环遍历 Iterator iter1 = entrySet.iterator(); while (iter1.hasNext { // 遍历时,需先获取entry,再分别获取key、value Map.Entry entry = (Map.Entry) iter1.next(); System.out.print entry.getKey; System.out.println entry.getValue; } // 方法2:获得key的Set集合 再遍历 System.out.println; // 1. 获得key的Set集合 Set<String> keySet = map.keySet(); // 2. 遍历Set集合,从而获取key,再获取value // 2.1 通过for循环 for(String key : keySet){ System.out.print; System.out.println(map.get; } System.out.println("----------"); // 2.2 通过迭代器:先获得key的Iterator,再循环遍历 Iterator iter2 = keySet.iterator(); String key = null; while (iter2.hasNext { key = iter2.next(); System.out.print; System.out.println(map.get; } // 方法3:获得value的Set集合 再遍历 System.out.println; // 1. 获得value的Set集合 Collection valueSet = map.values(); // 2. 遍历Set集合,从而获取value // 2.1 获得values 的Iterator Iterator iter3 = valueSet.iterator(); // 2.2 通过遍历,直接获取value while (iter3.hasNext { System.out.println(iter3.next; } }}// 注:对于遍历方式,推荐使用针对 key-value对的方式:效率高// 原因: // 1. 对于 遍历keySet 、valueSet,实质上 = 遍历了2次:1 = 转为 iterator 迭代器遍历、2 = 从 HashMap 中取出 key 的 value 操作(通过 key 值 hashCode 和 equals 索引) // 2. 对于 遍历 entrySet ,实质 = 遍历了1次 = 获取存储实体Entry(存储了key 和 value )
  • 运行结果

方法1Java2iOS3数据挖掘4Android1产品经理5----------Java2iOS3数据挖掘4Android1产品经理5方法2Java2iOS3数据挖掘4Android1产品经理5----------Java2iOS3数据挖掘4Android1产品经理5方法323415

下面,我们按照上述的使用过程,对一个个步骤进行源码解析

  • 在进行真正的源码分析前,先讲解HashMap中的重要参数
  • HashMap中的主要参数 同 JDK 1.7 ,即:容量、加载因子、扩容阈值
  • 但由于数据结构中引入了 红黑树,故加入了
    与红黑树相关的参数。具体介绍如下:

 /** * 主要参数 同 JDK 1.7 * 即:容量、加载因子、扩容阈值 */ // 1. 容量: 必须是2的幂 & <最大容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16 static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 = 2的30次方(若传入的容量过大,将被最大值替换) // 2. 加载因子(Load factor):HashMap在其容量自动增加前可达到多满的一种尺度 final float loadFactor; // 实际加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子 = 0.75 // 3. 扩容阈值(threshold):当哈希表的大小 ≥ 扩容阈值时,就会扩容哈希表(即扩充HashMap的容量) // a. 扩容 = 对哈希表进行resize操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数 // b. 扩容阈值 = 容量 x 加载因子 int threshold; // 4. 其他 transient Node<K,V>[] table; // 存储数据的Node类型 数组,长度 = 2的幂;数组的每个元素 = 1个单链表 transient int size;// HashMap的大小,即 HashMap中存储的键值对的数量 /** * 与红黑树相关的参数 */ // 1. 桶的树化阈值:即 链表转成红黑树的阈值,在存储数据时,当链表长度 > 该值时,则将链表转换成红黑树 static final int TREEIFY_THRESHOLD = 8; // 2. 桶的链表还原阈值:即 红黑树转为链表的阈值,当在扩容时(此时HashMap的数据存储位置会重新计算),在重新计算存储位置后,当原有的红黑树内数量 < 6时,则将 红黑树转换成链表 static final int UNTREEIFY_THRESHOLD = 6; // 3. 最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表 (即 将链表 转换成红黑树) // 否则,若桶内元素太多时,则直接扩容,而不是树形化 // 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD static final int MIN_TREEIFY_CAPACITY = 64; 
  • 此处 再次详细说明 加载因子

JDK 1.7,但由于其重要性,故此处再次说明

图片 11示意图

  • 总结 数据结构 & 参数方面与 JDK 1.7的区别

图片 12示意图

  • 本次的源码分析主要是根据 使用步骤 进行相关函数的详细分析
  • 主要分析内容如下:

图片 13示意图

  • 下面,我将对每个步骤内容的主要方法进行详细分析

步骤1:声明1个 HashMap的对象

此处主要分析的构造函数 类似 JDK 1.7

/** * 函数使用原型 */ Map<String,Integer> map = new HashMap<String,Integer>(); /** * 源码分析:主要是HashMap的构造函数 = 4个 * 仅贴出关于HashMap构造函数的源码 */public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{ // 省略上节阐述的参数 /** * 构造函数1:默认构造函数 * 加载因子 & 容量 = 默认 = 0.75、16 */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } /** * 构造函数2:指定“容量大小”的构造函数 * 加载因子 = 默认 = 0.75 、容量 = 指定大小 */ public HashMap(int initialCapacity) { // 实际上是调用指定“容量大小”和“加载因子”的构造函数 // 只是在传入的加载因子参数 = 默认加载因子 this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 构造函数3:指定“容量大小”和“加载因子”的构造函数 * 加载因子 & 容量 = 自己指定 */ public HashMap(int initialCapacity, float loadFactor) { // 指定初始容量必须非负,否则报错 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // HashMap的最大容量只能是MAXIMUM_CAPACITY,哪怕传入的 > 最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 填充比必须为正 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 设置 加载因子 this.loadFactor = loadFactor; // 设置 扩容阈值 // 注:此处不是真正的阈值,仅仅只是将传入的容量大小转化为:>传入容量大小的最小的2的幂,该阈值后面会重新计算 // 下面会详细讲解 ->> 分析1 this.threshold = tableSizeFor(initialCapacity); } /** * 构造函数4:包含“子Map”的构造函数 * 即 构造出来的HashMap包含传入Map的映射关系 * 加载因子 & 容量 = 默认 */ public HashMap(Map<? extends K, ? extends V> m) { // 设置容量大小 & 加载因子 = 默认 this.loadFactor = DEFAULT_LOAD_FACTOR; // 将传入的子Map中的全部元素逐个添加到HashMap中 putMapEntries; }} /** * 分析1:tableSizeFor(initialCapacity) * 作用:将传入的容量大小转化为:>传入容量大小的最小的2的幂 * 与JDK 1.7对比:类似于JDK 1.7 中 inflateTable()里的 roundUpToPowerOf2 */ static final int tableSizeFor { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return  ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}
  • 注:(同JDK 1.7类似)
    1. 此处仅用于接收初始容量大小(capacity)、加载因子(Load factor),但仍无真正初始化哈希表,即初始化存储数组table
    2. 此处先给出结论:真正初始化哈希表(初始化存储数组table)是在第1次添加键值对时,即第1次调用put()时。下面会详细说明

至此,关于HashMap的构造函数讲解完毕。

步骤2:向HashMap添加数据(成对 放入 键 – 值对)

  • 在该步骤中,与JDK 1.7的差别较大:

图片 14示意图

下面会对上述区别进行详细讲解

  • 添加数据的流程如下

注:为了让大家有个感性的认识,只是简单的画出存储流程,更加详细 &
具体的存储流程会在下面源码分析中给出

图片 15示意图

  • 源码分析

 /** * 函数使用原型 */ map.put("Android", 1); map.put("Java", 2); map.put; map.put("数据挖掘", 4); map.put("产品经理", 5); /** * 源码分析:主要分析HashMap的put函数 */ public V put(K key, V value) { // 1. 对传入数组的键Key计算Hash值 ->>分析1 // 2. 再调用putVal()添加数据进去 ->>分析2 return putVal, key, value, false, true); }

下面,将详细讲解 上面的2个主要分析点

相关文章

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注