整合营销服务商

电脑端+手机端+微信端=数据同步管理

免费咨询热线:

「vue基础」Vue相关构建工具和基础插件简介

「vue基础」Vue相关构建工具和基础插件简介

系列上一篇文章「vue基础」新手快速入门篇(一),我们通过引入JS的文件,快速的了解了Vue的基础语法和简单用法,本篇文章笔者将带着大家继续学习,如何使用工程化工具构建Vue项目。

像其他框架一样,Vue 的生态也有很多一系列的工具,通过工具,可以快速帮我们构建项目、发布项目、部署打包等,方便我们调试,避免不必要的Bug等。本篇文章我将重点介绍下构建工具和调试用的浏览器插件,这两款工具都有相关的官方工具,因此推荐大家进行使用。

为什么使用构建工具

虽然我们可以通过引入 CDN JS 的方式快速构建项目,这种方式只适合你刚接触 Vue ,方便你快速上手学习Vue而已。但是我们还是需要一款现代化、模块化、高效的工具在实际的项目的开发中帮助提高开发效率。

拥有良好的构建工具为我们的开发工作带来了便捷,不仅如此,它确保了过程的可靠性、避免了重复性、减少人为犯错的机会。接下来让我们一起简单的了解下构建工具的核心特点。

使用 JavaScript 新特性

使用新的语法和功能(ES6+),让我们的代码更加简洁,可读性会更好,即使现代浏览器都支持ES2015,但是你的项目很有可能需要兼容低版本的浏览器,比如政府医院的项目,还有相当多的机器使用 windows XP。

通过添加 Babel 到我们的构建工具中,就能很轻松的将 ES6+ 这些语法编译成旧浏览器支持 JavaScript 语法。不仅如此,大家应该都比较清楚,ECMAScript 几乎每年都会发布新版本,估计现在都到10了,通过构建工具的引用,我们可以与时俱进的使用更多的新语法特性。

保证代码质量

ESLint 是一个可配置的 JavaScript 语法规则和代码风格的检查工具。ESLint 能够辅助你轻松写出高质量的 JavaScript 代码。甚至还有ESLint的官方Vue插件eslint-plugin-vue,它将帮助你生成符合最佳实践的高质量代码。

组件单文件化

引入构建工具的好处就是,你可以在应用程序里使用单文件组件(Vue’s single-file components,简称SFC)。SFC 的好处就是将代码、样式、模板组合在一起进行集中编写。将逻辑和UI放在一起的好处,由于所有相关内容都集中放在一起,便于维护,由于每个组件又是独立的,因此重用性更好。如下段代码所示:

工具中的 vue-loader webpack 插件,将标签内的HTML代码编译成JavaScript代码,和组件内的JavaScript代码一起打包到应用程序中。

压缩版本的JS,体积更小

经过构建工具压缩后,编译后的JS文件体积更小,这就意味着用户打开网站的速度会更快,用户的体验就会更好。

Vue CLI

Vue CLI 致力于将 Vue 生态中的工具基础标准化。它确保了各种构建工具能够基于智能的默认配置即可平稳衔接,这样你可以专注在撰写应用上,而不必花好几天去纠结配置的问题。与此同时,它也为每个工具提供了调整配置的灵活性,无需 eject。

安装 CLI

安装 CLI 工具十分简单,但是安装的前提,你需要安装 Node 环境。接下来,我们通过以下命令全局安装 CLI:

npm install -g @vue/cli

创建一个新项目

启动控制终端,然后输入以下命令进行创建:

vue create my-new-project

此命会在当前目录下,创建一个以项目名称命名的文件夹,然后通过交互输入的形式,进行配置项目选选项。如下图所示,我们选择默认方式:

完成创建后,项目文件的目录结构如下图所示:

切换到 package.json 你会看到项目的基础配置,如下图所示:

这里有几个命令需要解释下:

  • npm run serve: 这将启动本地开发服务器进行编译项目,该过程将会监听项目中文件夹所有文件,任何改动都会导致导致重新编译。
  • npm run build:主要用于项目打包发布,此命令将编译你的项目,创建优化的生产版本。
  • npm run lint:检查代码质量是否符合设定的规则。

接下来我们运行下 npm run serve 命令,效果如下图所示:

Webpack配置

Vue CLI构建工具是基于webpack之上的,但是抽象了所有配置,以方便我们进行开发和使用。你可以通过运行命令随时查看webpack的配置。命令如下所示:

vue inspect

如果使用手工方式创建项目

上述流程是通过默认集成的方式进行创建项目,你也可以选择手工的方式的方式进行创建,如下图所示:

接下来我们来了解下这些插件:

  • Babel: 项目预设默认选择这个方式,这个工具的主要作用就是方便你使用最新的JS语法编写项目,由它进行编译转换成低版本兼容的JS代码。
  • TypeScript: 如果你使用 TypeScript 编写项目,你一定要选择这个,这样你的代码才能被编译器识别转换。
  • 渐进式Web应用程序(PWA)支持: 这个主要是为了方便你创建PWA应用,该插件默认提供 PWA 所需要的比如脱机、自定义相关的配置模板。
  • Router: 我们大部分项目都有多个页面,这时候,我们就需要用上这个路由插件。
  • Vuex: 类似 React 中的 Redux,官方提供的一个插件,方便我们集中管理复杂的 state 数据
  • CSS Pre-processors: 如果你使用 SCSS/Sass, LESS 编写CSS,建议你选择这个插件。
  • Linter / Formatter: 通过此选项,你可以自行安装ESLint或者使用Airbnb配置,Standard配置或Prettier代码格这些选项。
  • 单元测试: 选择单元测试将为你提供安装Mocha、Chai或Jest作为测试工具的选项。
  • 端到端测试: 与单元测试类似,将会为你提供Cypress、Nightwatch 的安装选项。

如果你在创建项目时,错过了这些选项,你完全不用担心,你可以通过手工命令的形式自行安装,比如我们要安装 typescript 插件,命令如下:

vue add @vue/cli-plugin-typescript
# or
vue add @vue/typescript

浏览器开发工具

Vue的浏览器工具集成在谷歌开发者工具上,方便你查看正在运行中Vue应用程序,你可以点击https://github.com/vuejs/vue-devtools#installation 这个官方地址去下载安装vue-devtools,安装成功后,运行你的Vue站点,打开浏览器开发者工具,你就会看到一个Vue的选项卡,点击进行切换,你就会看到如下图所示的内容:

Components Tab

组件选项卡,将对于页面组件的结构进行了树形化,更加直观的展示了当前组件包含了哪些组件,组件里包含了哪些内容,比如props,data 等。

Vuex Tab

更加直观的展示了当前全局数据的存储状态,及相关 mutations 、getters 等内容。

Events Tab

你可以通过事件选项卡,定位事件来源于那个组件,点击对应的事件,你能看到和事件更多相关的信息。

安装 VSCode 插件

大部分前端开发者想必都喜欢用微软的 VSCode 开发工具,目前针对Vue来说,使用最广泛的要数 Vetur VSCode扩展插件,安装也十分简单:

  • 启动VSCode,并选择扩展选项卡菜单
  • 在搜索栏搜索“vetur”
  • 从结果中选择由Pine Wu 开发的 Vetur 插件,点击安装即可。如下图所示。

小节

今天的内容就和大家聊到这里,我们一起学习了为什么要使用构建工具,如何来安装构建工具以及相关的浏览器、编辑器插件,下一篇文章我将和大家聊聊如何编写自定义组件。

荐学习

  • 听说你很懂源码?Spring读懂了?还有这20道源码面试题接得住吗?
  • Aliyun四面真可怕,狂问基础+项目+源码+高阶,无爱了

一 HashMap 源码分析

1. 前置知识

1.1 什么是 Map

在实际需求中,我们常常会遇到这样的问题,在诸多的数据中,通过其编号来寻找某一些信息,从而进行查看或者修改,例如通过学号查询学生信息。今天我们所介绍的Map集合就可以很好帮助我们实现这种需求

1.1.1 概述

Map是一种存储元素对的集合(元素对分别称作 和 值 也称键值对)它将键映射到值的对象。一个映射不能包含重复的键,并且每个键最 多只能映射到一个值。

怎么理解呢?

键 (key):就是你存的值的编号 值 (value):就是你要存放的数据

你可以近似的将键理解为下标,值依据键而存储,每个键都有其对应值。这两者是1、1对应的

但在之前下标是整数,但是Map中键可以使任意类型的对象。

1.1.2 Map集合和Collection集合的区别

  • Map集合存储元素是成对出现的,Map集合的键是唯一的,值是可重复的
  • Collection集合存储元素是单独出现的,Collection的子类Set是唯一的,List是可重复的。
  • Map集合的数据结构值针对键有效,跟值无关,Collection集合的数据结构是针对元素有效

1.2 什么是散列表

散列表也叫hash表 ,是根据关键码值而进行直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射也叫散列函数,存放记录的数组叫散列表。

一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名到首字母的一个函数关系),在首字母为W的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母”是这个例子中散列函数的函数法则,存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。—— 维基百科

1.2.1 分析一下为什么要用散列表

哈希表其实就是数组的一种扩展,因为其本质上用的就是数组可以按照下标随机访问数据的特点,我们来一步一步看一下

首先创建一个数组,我们将数组的每一个存储空间看做一个一个箱子或者一个一个桶,存储一些 key-value 的数据如,【张三,20】【李四,30】【王五,40】【赵六,50】【孙七,60】,依次放置于数组中。

如果按照普通顺序表的查询方式,就需要从开始依次比对查询,但是数据量越多,顺序表查找耗费的时间就越长。在大量数据的情况下,很显然不上算。

还有很多种数据结构,它们并不关心元素的顺序,能够快速查找元素数据,其中一种就是:散列表

下面看看散列表如何做到这么高效处理的

1.2.2 散列表工作原理

这次依旧使用 5 个箱子(桶)空间的数组来存储数据,我们开始存第一个数据【张三,20】,散列表会使用哈希函数(Hash算法)计算出 “张三” 的键,也就是字符串 “张三” 的哈希值,例如返回一个 5372 ,将其做取余处理,除数为数组的长度,即:5372 mod 5=2,因此将其放在下标(index)为 2 的位置,例如 第二个数据的哈希值为 6386,继续操作 6386 mod 5=1,即将其放在下标(index)为 1 的位置,以此类推.....

但是有一种情况就会出现了,例如我们存储第三个数据【王五,40】的时候,经过哈希函数计算,得出的结果为 5277,5277 mod 5=2 ,但是 2 这个位置已经有【张三,20】这个数据存在了,这种存储位置重复了的情况便叫作冲突

1.2.3 如何解决 Hash 冲突

1.2.3.1 JDK 1.7

在 JDK 1.8 之前,HashMap 的底层是数组和链表。因此当出现哈希冲突后,使用拉链法解决冲突。

拉链法,就是将数组的每一个格子(箱子),都看作一个链表,例如下标为 1 的格子,就是一个链表,已经存储了 【张三,20】,若仍有数据哈希值 mod 后等于 1 ,则直接在 1 中的这个链表中追加上这些数据就可以了。

1.2.3.1 JDK 1.8

JDK 8 做了一些较大的调整,当数组中每个格子里的链表,长度大于阈值(默认为8)时,将链表转化为红黑树,就可以大大的减少搜索时间。

而且,如果散列表快满的情况下下,还会有机制进行再散列,下面会在源码中深入分析。

1.3 什么是红黑树

红黑树是一种复杂的树形结构,这里不做过于详细的解释,讲一下其基本的结构,有一个基本的概念。

红黑树就是为了防止二叉树一些极端的情况,例如变成一条线状,或者左右不均衡,从二叉查找树,2-3树 等演变出来的一种树形结构。最主要的目的就是为了保持平衡。保证树的左右分支叶子等基本平衡。

具体的数据结果演变是比较复杂的,这一篇还是主要讲解 HashMap ,有需要以后会专篇讲解一些常见的数据结构的 Java 版本

2. 源码分析

2.1 类成员

// 序列化自动生成的一个码,用来在正反序列化中验证版本一致性。
private static final long serialVersionUID=362498820763181265L;   

// 默认的初始容量 1 * 2^4=16
static final int DEFAULT_INITIAL_CAPACITY=1 << 4;

// 最大容量 1 * 2^30
static final int MAXIMUM_CAPACITY=1 << 30;

// 默认的加载因子 0.75
static final float DEFAULT_LOAD_FACTOR=0.75f;

// 桶的树化阈值,当桶(bucket)上的结点数大于这个值时会转成红黑树,
// 也就是上面提到的长度大于阈值(默认为8)时,将链表转化为红黑树
static final int TREEIFY_THRESHOLD=8;

// 桶的链表还原阈值,当桶(bucket)上的结点数小于这个值时树转链表
// 一个道理
static final int UNTREEIFY_THRESHOLD=6;

// 最小树形化容量阈值,当哈希表中的容量 > 该值时,才允许树形化链表 
// 否则,若桶内元素太多时,则直接扩容,而不是树形化
// 为了避免进行扩容和树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY=64;

// 存储元素的数组,总是2的幂次倍
transient Node<k,v>[] table; 

// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;

// 存放元素的个数(不是数组的长度)
transient int size;

// 扩容和修改的计数变量
transient int modCount;   

// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;

// 加载因子
final float loadFactor;

其中有几个需要强调的内容

threshold 临界值

  • 数组扩容的一个临界值,即当数组实际大小(容量 * 填充因子,即:threshold=capacity * loadFactor)超过临界值时,会进行扩容。

loadFactor加载因子

  • 加载因子就是表示哈希表中元素填满的程度,当表中元素过多,超过加载因子的值时,哈希表会自动扩容,一般是一倍,这种行为可以称作rehashing(再哈希)。
  • 加载因子的值设置越大,添加的元素就会越多,确实空间利用率的到了很大的提升,但是毫无疑问,就面临着哈希冲突的可能性增大,反之,空间利用率造成了浪费,但哈希冲突也减少了,所以我们希望在空间利用率与哈希冲突之间找到一种我们所能接受的平衡,经过一些试验,定在了0.75f。

2.2 两个节点

因为一定条件下会转换成红黑树这种数据结果,所以除了普通的 Node 节点,还有 树节点(TreeNode 节点)

2.2.1 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) {
        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; }

    // 重写了 hashCode, ^ 是位异或运算符
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue=value;
        value=newValue;
        return oldValue;
    }

    // 重写 equals() 方法
    public final boolean equals(Object o) {
        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.2.2 TreeNode 节点

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;
        }

2.3 构造方法

// 指定了具体容量大小和加载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity=MAXIMUM_CAPACITY;
    if (loadFactor <=0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor=loadFactor;
    this.threshold=tableSizeFor(initialCapacity);
}

// 指定了具体容量大小的构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 默认无参构造函数
public HashMap() {
    this.loadFactor=DEFAULT_LOAD_FACTOR; 
}

// 指定了 map 的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor=DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

tableSizeFor

/**
 * 返回一个大于输入参数,且最接近的,2的整数次幂的数
 * 只是一个初始化内容,创建哈希表时,会再重新赋值
 */
static final int tableSizeFor(int cap) {
    int n=cap - 1;
    n |=n >>> 1;
    n |=n >>> 2;
    n |=n >>> 4;
    n |=n >>> 8;
    n |=n >>> 16;
    return (n < 0) ? 1 : (n >=MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

putMapEntries

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 拿到给定 Map 的长度
    int s=m.size();
    if (s > 0) {
        // 判断当前实际存储数据的这个 table 是否已经初始化
        if (table==null) { // pre-size
            // 没初始化,就将 s 处理后设为m的实际元素个数
            float ft=((float)s / loadFactor) + 1.0F;
            // 防止小于最小容量(阈值)
            int t=((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 若大于临界值,则初始化阈值
            if (t > threshold)
                threshold=tableSizeFor(t);
        }
        // table 已初始化,并且给定 Map m 元素个数大于阈值,进行扩容处理
        else if (s > threshold)
            resize();
        // 将给定集合 m 中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key=e.getKey();
            V value=e.getValue();
            // putVal 方法会在介绍添加相关方法时介绍
            putVal(hash(key), key, value, false, evict);
        }
    }
}

2.4 添加方法

2.4.1 put()

对于 HashMap ,其提供给外界的公共添加方法只有 put(K key, V value) 一个,其他 put 方法都是供 put(K key, V value) 内部调用的

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

关于 putVal 的每个参数和细节下面接着说,看一下第一个参数 hash(key) 首先提一下,在 HashMap 中是如何计算 hash 值的,跳转到 3.1 可看,也可以看完最后去看也可以。

[3.1 hash() 中的扰动函数如何解决Hash冲突 ※](###3.1 hash() 中的扰动函数如何解决Hash冲突 ※)

2.4.2 putVal()

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未初始化(为null)或者长度为0,调用 resize 进行扩容
    if ((tab=table)==null || (n=tab.length)==0)
        n=(tab=resize()).length;
    // 若桶为空,即无发生碰撞
    // (n - 1) & hash 用来确定元素存放在哪个位置,即哪个桶中
    if ((p=tab[i=(n - 1) & hash])==null)
        // 新生成结点放入桶中(数组中)
        tab[i]=newNode(hash, key, value, null);
    // 若桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 若节点 key 存在,就和要插入的key比较
        if (p.hash==hash &&
            ((k=p.key)==key || (key !=null && key.equals(k))))
            // 如果key相同就直接覆盖 value
            e=p;
        // hash值不相等,即key不相等,转为红黑树结点
        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);
                    // 结点数量达到阈值,转化为红黑树
                    if (binCount >=TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 遍历的过程中,遇到相同 key 则覆盖 value
                if (e.hash==hash &&
                    ((k=e.key)==key || (key !=null && key.equals(k))))
                    // 相等,跳出循环
                    break;
                // 用于遍历桶中的链表,与前面的e=p.next组合,可以遍历链表
                p=e;
            }
        }
        // 在桶中找到key值、hash值与插入元素相等的结点
        if (e !=null) { 
            // 记录e的value
            V oldValue=e.value;
            // onlyIfAbsent 为 false 或者旧值为 null
            if (!onlyIfAbsent || oldValue==null)
                // 用新值替换旧值
                e.value=value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 超过最大容量,扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
} 

总结一下大致流程:

  • 先定位到具体的数组位置,例如叫做 A
  • 若 A 处没有元素就直接插入
  • 若 A 处 有元素就和待插入的 key 比较 key 相同就直接覆盖若 key 不相同,就判断 p 是否是一个树节点如果是就调用putTreeVal 方法将元素添加进入如果不是就遍历链表插入(尾插法)

2.5 获取方法

2.5.1 get()

同样 get 方法中也用到了 hash 方法计算 key 的哈希值,同样跳转到 3.1 可看,也可以看完最后去看也可以。

[3.1 hash() 中的扰动函数如何解决Hash冲突 ※](###3.1 hash() 中的扰动函数如何解决Hash冲突 ※)

public V get(Object key) {
    Node<K,V> e;
    return (e=getNode(hash(key), key))==null ? null : e.value;
}

2.5.2 getNode

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 保证计算出来的哈希值,确定是在哈希表上的
    if ((tab=table) !=null && (n=tab.length) > 0 &&
        (first=tab[(n - 1) & hash]) !=null) {
        // 要是直接在桶的首个位置上,直接就可以返回(这个桶中只有一个元素,或者在首个)
        if (first.hash==hash && // always check first node
            ((k=first.key)==key || (key !=null && key.equals(k))))
            return first;
        // 桶中不止一个节点
        if ((e=first.next) !=null) {
            // 在树中 get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash==hash &&
                    ((k=e.key)==key || (key !=null && key.equals(k))))
                    return e;
            } while ((e=e.next) !=null);
        }
    }
    return null;
}

2.6 移除方法

2.6.1 remove()

同样 get 方法中也用到了 hash 方法计算 key 的哈希值,同样跳转到 3.1 可看,也可以看完最后去看也可以。

[3.1 hash() 中的扰动函数如何解决Hash冲突 ※](###3.1 hash() 中的扰动函数如何解决Hash冲突 ※)

public V remove(Object key) {
    Node<K,V> e;
    return (e=removeNode(hash(key), key, null, false, true))==null ?
        null : e.value;
}

2.6.2 removeNode()

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 桶不为空,映射的哈希值也存在
    if ((tab=table) !=null && (n=tab.length) > 0 &&
        (p=tab[index=(n - 1) & hash]) !=null) {
        Node<K,V> node=null, e; K k; V v;
        // 如果在桶的首位就找到对应元素,记录下来
        if (p.hash==hash &&
            ((k=p.key)==key || (key !=null && key.equals(k))))
            node=p;
        // 若不在首位,就去红黑树或者链表中查询了
        else if ((e=p.next) !=null) {
            if (p instanceof TreeNode)
                node=((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash==hash &&
                        ((k=e.key)==key ||
                         (key !=null && key.equals(k)))) {
                        node=e;
                        break;
                    }
                    p=e;
                } while ((e=e.next) !=null);
            }
        }
        // 找到了要删除的节点和值,就分三种情况去删除,链表,红黑树,桶的首位
        if (node !=null && (!matchValue || (v=node.value)==value ||
                             (value !=null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node==p)
                tab[index]=node.next;
            else
                p.next=node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

2.7 扩容方法

2.7.1 resize()

resize 在程序中是非常耗时的。要尽量避免用它。

  • 其过程中会重新分配 hash ,然后遍历hash表中所有的元素
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) {
        // 超过最大值,不再扩容,没办法了
        if (oldCap >=MAXIMUM_CAPACITY) {
            threshold=Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值,就扩充为原来的2倍
        else if ((newCap=oldCap << 1) < MAXIMUM_CAPACITY && oldCap >=DEFAULT_INITIAL_CAPACITY)
            newThr=oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 初始化时,threshold 暂时保存 initialCapacity 参数的值
        newCap=oldThr;
    else { 
        // signifies using defaults
        newCap=DEFAULT_INITIAL_CAPACITY;
        newThr=(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    if (newThr==0) {
        float ft=(float)newCap * loadFactor;
        newThr=(newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold=newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab=(Node<K,V>[])new Node[newCap];
    table=newTab;
    if (oldTab !=null) {
        // 将旧的键值对移动到新的哈希桶数组中
        for (int j=0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e=oldTab[j]) !=null) {
                oldTab[j]=null;
                // / 无链条,也就是没有下一个,只有自己
                if (e.next==null)
                    newTab[e.hash & (newCap - 1)]=e;
                else if (e instanceof TreeNode)
                    // 拆红黑树,先拆成两个子链表,再分别按需转成红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 拆链表,拆成两个子链表并保持原有顺序
                    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;
                        }
                        // 原索引 + oldCap
                        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;
                    }
                    // 原索引 +oldCap 放到新的哈希桶中
                    if (hiTail !=null) {
                        hiTail.next=null;
                        newTab[j + oldCap]=hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

3. 重点分析

3.1 hash() 中的扰动函数如何解决Hash冲突 ※

看HashMap的put方法源码:

  //HashMap 源码节选-JDK8
  public V put(K key, V value) {
      return putVal(hash(key), key, value, false, true);
  }

而我们的值在返回前需要经过HashMap中的hash方法

接着定位到hash方法的源码:

static final int hash(Object key) {
    int h;
    return (key==null) ? 0 : (h=key.hashCode()) ^ (h >>> 16);
}

hash方法的返回结果中是一句三目运算符,键 (key) 为null即返回 0,存在则返回后一句的内容

(h=key.hashCode()) ^ (h >>> 16)

JDK8中 HashMap——hash 方法中的这段代码叫做 “扰动函数

我们来分析一下:

hashCode 是 Object 类中的一个方法,在子类中一般都会重写,而根据我们之前自己给出的程序,暂以 Integer 类型为例,我们来看一下 Integer 中 hashCode 方法的源码:

  /**
   * Returns a hash code for this {@code Integer}.
   *
   * @return  a hash code value for this object, equal to the
   *          primitive {@code int} value represented by this
   *          {@code Integer} object.
   */
  @Override
  public int hashCode() {
      return Integer.hashCode(value);
  }

  /**
   * Returns a hash code for a {@code int} value; compatible with
   * {@code Integer.hashCode()}.
   *
   * @param value the value to hash
   * @since 1.8
   *
   * @return a hash code value for a {@code int} value.
   */
  public static int hashCode(int value) {
      return value;
  }

Integer 中 hashCode 方法的返回值就是这个数本身

注:整数的值因为与整数本身一样唯一,所以它是一个足够好的散列

所以,下面的 A、B 两个式子就是等价的

  //注:key为 hash(Object key)参数

  A:(h=key.hashCode()) ^ (h >>> 16)

  B:key ^ (key >>> 16)

分析到这一步,我们的式子只剩下位运算了,先不急着算什么,我们先理清思路

HashSet因为底层使用哈希表(链表结合数组)实现,存储时key通过一些运算后得出自己在数组中所处的位置。

我们在hashCoe方法中返回到了一个等同于本身值的散列值,但是考虑到int类型数据的范围:-2147483648~2147483647 ,很显然,这些散列值不能直接使用,因为内存是没有办法放得下,一个40亿长度的数组的。所以它使用了对数组长度进行取模运算,得余后再作为其数组下标,indexFor( ) ——JDK7中,就这样出现了,在JDK8中 indexFor()就消失了,而全部使用下面的语句代替,原理是一样的。

  //JDK8中
  (tab.length - 1) & hash;
  //JDK7中
  bucketIndex=indexFor(hash, table.length);

  static int indexFor(int h, int length) {
      return h & (length - 1);
  }

提一句,为什么取模运算时我们用 & 而不用 % 呢,因为位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快,这样就导致位运算 & 效率要比取模运算 % 高很多。

看到这里我们就知道了,存储时key需要通过hash方法indexFor( )运算,来确定自己的对应下标

(取模运算,应以JDK8为准,但为了称呼方便,还是按照JDK7的叫法来说,下面的例子均为此,特此提前声明)

但是先直接看与运算(&),好像又出现了一些问题,我们举个例子:

HashMap中初始长度为16,length - 1=15;其二进制表示为 00000000 00000000 00000000 00001111

而与运算计算方式为:遇0则0,我们随便举一个key值

          1111 1111 1010 0101 1111 0000 0011 1100
  &       0000 0000 0000 0000 0000 0000 0000 1111
  ----------------------------------------------------
          0000 0000 0000 0000 0000 0000 0000 1100

我们将这32位从中分开,左边16位称作高位,右边16位称作低位,可以看到经过&运算后 结果就是高位全部归0,剩下了低位的最后四位。但是问题就来了,我们按照当前初始长度为默认的16,HashCode值为下图两个,可以看到,在不经过扰动计算时,只进行与(&)运算后 Index值均为 12 这也就导致了哈希冲突

哈希冲突的简单理解:计划把一个对象插入到散列表(哈希表)中,但是发现这个位置已经被别的对象所占据了

例子中,两个不同的HashCode值却经过运算后,得到了相同的值,也就代表,他们都需要被放在下标为2的位置

一般来说,如果数据分布比较广泛,而且存储数据的数组长度比较大,那么哈希冲突就会比较少,否则很高。

但是,如果像上例中只取最后几位的时候,这可不是什么好事,即使我的数据分布很散乱,但是哈希冲突仍然会很严重。

别忘了,我们的扰动函数还在前面搁着呢,这个时候它就要发挥强大的作用了,还是使用上面两个发生了哈希冲突的数据,这一次我们加入扰动函数再进行与(&)运算

补充 :>>> 按位右移补零操作符,左操作数的值按右操作数指定的为主右移,移动得到的空位以零填充
^ 位异或运算,相同则 0,不同则 1

可以看到,本发生了哈希冲突的两组数据,经过扰动函数处理后,数值变得不再一样了,也就避免了冲突

其实在扰动函数中,将数据右位移16位,哈希码的高位和低位混合了起来,这也正解决了前面所讲 高位归0,计算只依赖低位最后几位的情况, 这使得高位的一些特征也对低位产生了影响,使得低位的随机性加强,能更好避免冲突

作者:BWH_Steven
原文链接:https://www.cnblogs.com/ideal-20/p/14424234.html

 本篇博客我们来介绍在 JDK1.8 中 HashMap 的源码实现,这也是最常用的一个集合。但是在介绍 HashMap 之前,我们先介绍什么是 Hash表。

1、哈希表

  Hash表也称为散列表,也有直接译作哈希表,Hash表是一种根据关键字值(key - value)而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中的一个位置来访问记录,以此来加快查找的速度。在链表、数组等数据结构中,查找某个关键字,通常要遍历整个数据结构,也就是O(N)的时间级,但是对于哈希表来说,只是O(1)的时间级。

  比如对于前面我们讲解的 ArrayList 集合和 LinkedList ,如果我们要查找这两个集合中的某个元素,通常是通过遍历整个集合,需要O(N)的时间级。

  如果是哈希表,它是通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表,只需要O(1)的时间级。

  ①、存放在哈希表中的数据是key-value 键值对,比如存放哈希表的数据为:

  {Key1-Value1,Key2-Value2,Key3-Value3,Key4-Value4,Key5-Value5,Key6-Value6}

  如果我们想查找是否存在键值对 Key3-Value3,首先通过 Key3 经过散列函数,得到值 k3,然后通过 k3 和散列表对应的值找到是 Value3。

  ②、当然也有可能存放哈希表的值只是 Value1,Value2,Value3这种类型:

  {Value1,Value2,Value3,Value4,Value5,Value6}

  这时候我们可以假设 Value1 是等于 Key1的,也就是{Value1-Value1,Value2-Value2,Value3-Value3,Value4-Value4,Value5-Value5,Value6-Value6}可以将 Value1经过散列函数转换成与散列表对应的值。

大家都用过汉语字典吧,汉语字典的优点是我们可以通过前面的拼音目录快速定位到所要查找的汉字。当给定我们某个汉字时,大脑会自动将汉字转换成拼音(如果我们认识,不认识可以通过偏旁部首),这个转换的过程我们可以看成是一个散列函数,之后在根据转换得到的拼音找到该字所在的页码,从而找到该汉字。

  汉语字典是哈希表的典型实现,但是我们仔细思考,会发现这样几个问题?

  ①、为什么要有散列函数?

  ②、多个 key 通过散列函数会得到相同的值,这时候怎么办?

  对于第一个问题,散列函数的存在能够帮助我们更快的确定key和value的映射关系,试想一下,如果没有汉字和拼音的转换规则(或者汉字和偏旁部首的),给你一个汉字,你该如何从字典中找到该汉字?我想除了遍历整部字典,你没有什么更好的办法。

  对于第二个问题,多个 key 通过散列函数得到相同的值,这其实也是哈希表最大的问题——冲突。比如同音字汉字,我们得到的拼音就会是相同的,那么我们该如何在字典中存放同音字汉字呢?有两种做法:

  第一种是开放地址法,当我们遇到冲突了,这时候通过另一种函数再计算一遍,得到相应的映射关系。比如对于汉语字典,一个字 “余”,拼音是“yu”,我们将其放在页码为567(假设在该位置),这时候又来了一个汉字“于”,拼音也是“yu”,那么这时候我们要是按照转换规则,也得将其放在页码为567的位置,但是我们发现这个页码已经被占用了,这时候怎么办?我们可以在通过另一种函数,得到的值加1。那么汉字"于"就会被放在576+1=577的位置。

  第二种是链地址法,我们可以将字典的每一页都看成是一个子数组或者子链表,当遇到冲突了,直接往当前页码的子数组或者子链表里面填充即可。那么我们进行同音字查找的时候,可能需要遍历其子数组或者子链表。如下图所示:

  对于开放地址法,可能会遇到二次冲突,三次冲突,所以需要良好的散列函数,分布的越均匀越好。对于链地址法,虽然不会造成二次冲突,但是如果一次冲突很多,那么会造成子数组或者子链表很长,那么我们查找所需遍历的时间也会很长。

2、什么是 HashMap?

  听名字就知道,HashMap 是一个利用哈希表原理来存储元素的集合。遇到冲突时,HashMap 是采用的链地址法来解决,在 JDK1.7 中,HashMap 是由 数组+链表构成的。但是在 JDK1.8 中,HashMap 是由 数组+链表+红黑树构成,新增了红黑树作为底层数据结构,结构变得复杂了,但是效率也变的更高效。下面我们来具体介绍在 JDK1.8 中 HashMap 是如何实现的。

3、HashMap定义

  HashMap 是一个散列表,它存储的内容是键值对(key-value)映射,而且 key 和 value 都可以为 null。

 public class HashMap<K,V> extends AbstractMap<K,V>
     implements Map<K,V>, Cloneable, Serializable {

  首先该类实现了一个 Map 接口,该接口定义了一组键值对映射通用的操作。储存一组成对的键-值对象,提供key(键)到value(值)的映射,Map中的key不要求有序,不允许重复。value同样不要求有序,但可以重复。但是我们发现该接口方法有很多,我们设计某个键值对的集合有时候并不像实现那么多方法,那该怎么办?

  JDK 还为我们提供了一个抽象类 AbstractMap ,该抽象类继承 Map 接口,所以如果我们不想实现所有的 Map 接口方法,就可以选择继承抽象类 AbstractMap 。

  但是我们发现 HashMap 类即继承了 AbstractMap 接口,也实现了 Map 接口,这样做难道不是多此一举?后面我们会讲的 LinkedHashSet 集合也有这样的写法。

  毕竟 JDK 经过这么多年的发展维护,博主起初也是认为这样是有具体的作用的,后来找了很多资料,发现这其实完全没有任何作用

据 java 集合框架的创始人Josh Bloch描述,这样的写法是一个失误。在java集合框架中,类似这样的写法很多,最开始写java集合框架的时候,他认为这样写,在某些地方可能是有价值的,直到他意识到错了。显然的,JDK的维护者,后来不认为这个小小的失误值得去修改,所以就这样存在下来了。  HashMap 集合还实现了 Cloneable 接口以及 Serializable 接口,分别用来进行对象克隆以及将对象进行序列化。

4、字段属性

//序列化和反序列化时,通过该字段进行版本一致性验证
    private static final long serialVersionUID=362498820763181265L;
    //默认 HashMap 集合初始容量为16(必须是 2 的倍数)
    static final int DEFAULT_INITIAL_CAPACITY=1 << 4; // aka 16
    //集合的最大容量,如果通过带参构造指定的最大容量超过此数,默认还是使用此数
    static final int MAXIMUM_CAPACITY=1 << 30;
    //默认的填充因子
    static final float DEFAULT_LOAD_FACTOR=0.75f;
    //当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
    static final int TREEIFY_THRESHOLD=8;
    //当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
    static final int UNTREEIFY_THRESHOLD=6;
    /**(JDK1.8新增)
     * 当集合中的容量大于这个值时,表中的桶才能进行树形化 ,否则桶内元素太多时会扩容,
     * 而不是树形化 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
     */
    static final int MIN_TREEIFY_CAPACITY=64;

  注意:后面三个字段是 JDK1.8 新增的,主要是用来进行红黑树和链表的互相转换。

/**
     * 初始化使用,长度总是 2的幂
     */
    transient Node<K,V>[] table;

    /**
     * 保存缓存的entrySet()
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 此映射中包含的键值映射的数量。(集合存储键值对的数量)
     */
    transient int size;

    /**
     * 跟前面ArrayList和LinkedList集合中的字段modCount一样,记录集合被修改的次数
     * 主要用于迭代器中的快速失败
     */
    transient int modCount;

    /**
     * 调整大小的下一个大小值(容量*加载因子)。capacity * load factor
     */
    int threshold;

    /**
     * 散列表的加载因子。
     */
    final float loadFactor;

  下面我们重点介绍上面几个字段:

  ①、Node[] table

  我们说 HashMap 是由数组+链表+红黑树组成,这里的数组就是 table 字段。后面对其进行初始化长度默认是 DEFAULTINITIALCAPACITY=16。而且 JDK 声明数组的长度总是 2的n次方(一定是合数),为什么这里要求是合数,一般我们知道哈希算法为了避免冲突都要求长度是质数,这里要求是合数,下面在介绍 HashMap 的hashCode() 方法(散列函数),我们再进行讲解。

  ②、size

  集合中存放key-value 的实时对数。

  ③、loadFactor

  装载因子,是用来衡量 HashMap 满的程度,计算HashMap的实时装载因子的方法为:size/capacity,而不是占用桶的数量去除以capacity。capacity 是桶的数量,也就是 table 的长度length。

  默认的负载因子0.75 是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子loadFactor 的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子 loadFactor 的值,这个值可以大于1。

  ④、threshold

  计算公式:capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容),扩容后的 HashMap 容量是之前容量的两倍

5、构造函数

  ①、默认无参构造函数

/**
     * 默认构造函数,初始化加载因子loadFactor=0.75
     */
    public HashMap() {
        this.loadFactor=DEFAULT_LOAD_FACTOR; 
    }

  无参构造器,初始化散列表的加载因子为0.75

  ②、指定初始容量的构造函数

/**
     * 
     * @param initialCapacity 指定初始化容量
     * @param loadFactor 加载因子 0.75
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //初始化容量不能小于 0 ,否则抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //如果初始化容量大于2的30次方,则初始化容量都为2的30次方
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity=MAXIMUM_CAPACITY;
        //如果加载因子小于0,或者加载因子是一个非数值,抛出异常
        if (loadFactor <=0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor=loadFactor;
        this.threshold=tableSizeFor(initialCapacity);
    }
    // 返回大于等于initialCapacity的最小的二次幂数值。
    // >>> 操作符表示无符号右移,高位取0。
    // | 按位或运算
    static final int tableSizeFor(int cap) {
        int n=cap - 1;
        n |=n >>> 1;
        n |=n >>> 2;
        n |=n >>> 4;
        n |=n >>> 8;
        n |=n >>> 16;
        return (n < 0) ? 1 : (n >=MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

6、确定哈希桶数组索引位置

  前面我们讲解哈希表的时候,我们知道是用散列函数来确定索引的位置。散列函数设计的越好,使得元素分布的越均匀。HashMap 是数组+链表+红黑树的组合,我们希望在有限个数组位置时,尽量每个位置的元素只有一个,那么当我们用散列函数求得索引位置的时候,我们能马上知道对应位置的元素是不是我们想要的,而不是要进行链表的遍历或者红黑树的遍历,这会大大优化我们的查询效率。我们看 HashMap 中的哈希算法:

static final int hash(Object key) {
        int h;
        return (key==null) ? 0 : (h=key.hashCode()) ^ (h >>> 16);
    }

    i=(table.length - 1) & hash;//这一步是在后面添加元素putVal()方法中进行位置的确定

  主要分为三步:

  ①、取 hashCode 值: key.hashCode()

  ②、高位参与运算:h>>>16

  ③、取模运算:(n-1) & hash

  这里获取 hashCode() 方法的值是变量,但是我们知道,对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(Object key) 所计算得到的 hash码 值总是相同的。

  为了让数组元素分布均匀,我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length),但是计算机都是二进制进行操作,取模运算相对开销还是很大的,那该如何优化呢?

  HashMap 使用的方法很巧妙,它通过 hash & (table.length -1)来得到该对象的保存位,前面说过 HashMap 底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当 length 总是2的n次方时,hash & (length-1)运算等价于对 length 取模,也就是 hash%length,但是&比%具有更高的效率。比如 n % 32=n & (32 -1)

  这也解释了为什么要保证数组的长度总是2的n次方。

  再就是在 JDK1.8 中还有个高位参与运算,hashCode() 得到的是一个32位 int 类型的值,通过hashCode()的高16位 异或 低16位实现的:(h=k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

  下面举例说明下,n为table的长度:

7、添加元素

//hash(key)就是上面讲的hash方法,对其进行了第一步和第二步处理
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
     * 
     * @param hash 索引的位置
     * @param key  键
     * @param value  值
     * @param onlyIfAbsent true 表示不要更改现有值
     * @param evict false表示table处于创建模式
     * @return
     */
    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为null或者长度为0,则进行初始化
         //resize()方法本来是用于扩容,由于初始化没有实际分配空间,这里用该方法进行空间分配,后面会详细讲解该方法
         if ((tab=table)==null || (n=tab.length)==0)
             n=(tab=resize()).length;
         //注意:这里用到了前面讲解获得key的hash码的第三步,取模运算,下面的if-else分别是 tab[i] 为null和不为null
         if ((p=tab[i=(n - 1) & hash])==null)
             tab[i]=newNode(hash, key, value, null);//tab[i] 为null,直接将新的key-value插入到计算的索引i位置
         else {//tab[i] 不为null,表示该位置已经有值了
             Node<K,V> e; K k;
             if (p.hash==hash &&
                 ((k=p.key)==key || (key !=null && key.equals(k))))
                 e=p;//节点key已经有值了,直接用新值覆盖
             //该链是红黑树
             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;
                     }
                     //key已经存在直接覆盖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;
    }

  ①、判断键值对数组 table 是否为空或为null,否则执行resize()进行扩容;

  ②、根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

  ③、判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

  ④、判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

  ⑤、遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

  ⑥、插入成功后,判断实际存在的键值对数量size是否超过了最大容量threshold,如果超过,进行扩容。

  ⑦、如果新插入的key不存在,则返回null,如果新插入的key存在,则返回原key对应的value值(注意新插入的value会覆盖原value值)

  注意1:看第 58,59 行代码:

if (++size > threshold)//超过最大容量,进行扩容
    resize();

  这里有个考点,我们知道 HashMap 是由数组+链表+红黑树(JDK1.8)组成,如果在添加元素时,发生冲突,会将冲突的数放在链表上,当链表长度超过8时,会自动转换成红黑树。

  那么有如下问题:数组上有5个元素,而某个链表上有3个元素,问此HashMap的 size 是多大?

  我们分析第58,59 行代码,很容易知道,只要是调用put() 方法添加元素,那么就会调用 ++size(这里有个例外是插入重复key的键值对,不会调用,但是重复key元素不会影响size),所以,上面的答案是 7。

  注意2:看第 53 、 60 行代码:

 afterNodeAccess(e);
 afterNodeInsertion(evict);

  这里调用的该方法,其实是调用了如下实现方法:

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

  这都是一个空的方法实现,我们在这里可以不用管,但是在后面介绍 LinkedHashMap 会用到,LinkedHashMap 是继承的 HashMap,并且重写了该方法,后面我们会详细介绍。

8、扩容机制

  扩容(resize),我们知道集合是由数组+链表+红黑树构成,向 HashMap 中插入元素时,如果HashMap 集合的元素已经大于了最大承载容量threshold(capacity * loadFactor),这里的threshold不是数组的最大长度。那么必须扩大数组的长度,Java中数组是无法自动扩容的,我们采用的方法是用一个更大的数组代替这个小的数组,就好比以前是用小桶装水,现在小桶装不下了,我们使用一个更大的桶。

  JDK1.8融入了红黑树的机制,比较复杂,这里我们先介绍 JDK1.7的扩容源码,便于理解,然后在介绍JDK1.8的源码。

//参数 newCapacity 为新数组的大小
    void resize(int newCapacity) {
        Entry[] oldTable=table;//引用扩容前的 Entry 数组
        int oldCapacity=oldTable.length;
        if (oldCapacity==MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了
            threshold=Integer.MAX_VALUE;///修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
            return;
        }

        Entry[] newTable=new Entry[newCapacity];//初始化一个新的Entry数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面
        table=newTable;
        threshold=(int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值
    }
    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;//访问下一个 Entry 链上的元素
            }
        }
    }

  通过方法我们可以看到,JDK1.7中首先是创建一个新的大容量数组,然后依次重新计算原集合所有元素的索引,然后重新赋值。如果数组某个位置发生了hash冲突,使用的是单链表的头插入方法,同一位置的新元素总是放在链表的头部,这样与原集合链表对比,扩容之后的可能就是倒序的链表了。

  下面我们在看看JDK1.8的。

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab=table;
        int oldCap=(oldTab==null) ? 0 : oldTab.length;//原数组如果为null,则长度赋值0
        int oldThr=threshold;
        int newCap, newThr=0;
        if (oldCap > 0) {//如果原数组长度大于0
            if (oldCap >=MAXIMUM_CAPACITY) {//数组大小如果已经大于等于最大值(2^30)
                threshold=Integer.MAX_VALUE;//修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
                return oldTab;
            }
            //原数组长度大于等于初始化长度16,并且原数组长度扩大1倍也小于2^30次方
            else if ((newCap=oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >=DEFAULT_INITIAL_CAPACITY)
                newThr=oldThr << 1; // 阀值扩大1倍
        }
        else if (oldThr > 0) //旧阀值大于0,则将新容量直接等于就阀值 
            newCap=oldThr;
        else {//阀值等于0,oldCap也等于0(集合未进行初始化)
            newCap=DEFAULT_INITIAL_CAPACITY;//数组长度初始化为16
            newThr=(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//阀值等于16*0.75=12
        }
        //计算新的阀值上限
        if (newThr==0) {
            float ft=(float)newCap * loadFactor;
            newThr=(newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold=newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab=(Node<K,V>[])new Node[newCap];
        table=newTab;
        if (oldTab !=null) {
            //把每个bucket都移动到新的buckets中
            for (int j=0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e=oldTab[j]) !=null) {
                    oldTab[j]=null;//元数据j位置置为null,便于垃圾回收
                    if (e.next==null)//数组没有下一个引用(不是链表)
                        newTab[e.hash & (newCap - 1)]=e;
                    else if (e instanceof TreeNode)//红黑树
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        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;
                            }
                            //原索引+oldCap
                            else {
                                if (hiTail==null)
                                    hiHead=e;
                                else
                                    hiTail.next=e;
                                hiTail=e;
                            }
                        } while ((e=next) !=null);
                        //原索引放到bucket里
                        if (loTail !=null) {
                            loTail.next=null;
                            newTab[j]=loHead;
                        }
                        //原索引+oldCap放到bucket里
                        if (hiTail !=null) {
                            hiTail.next=null;
                            newTab[j + oldCap]=hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

  该方法分为两部分,首先是计算新桶数组的容量 newCap 和新阈值 newThr,然后将原集合的元素重新映射到新集合中。

  相比于JDK1.7,1.8使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。

9、删除元素

  HashMap 删除元素首先是要找到 桶的位置,然后如果是链表,则进行链表遍历,找到需要删除的元素后,进行删除;如果是红黑树,也是进行树的遍历,找到元素删除后,进行平衡调节,注意,当红黑树的节点数小于 6 时,会转化成链表。

public V remove(Object key) {
        Node<K,V> e;
        return (e=removeNode(hash(key), key, null, false, true))==null ?
            null : e.value;
    }

    final Node<K,V> removeNode(int hash, Object key, Object value,
            boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //(n - 1) & hash找到桶的位置
        if ((tab=table) !=null && (n=tab.length) > 0 &&
        (p=tab[index=(n - 1) & hash]) !=null) {
        Node<K,V> node=null, e; K k; V v;
        //如果键的值与链表第一个节点相等,则将 node 指向该节点
        if (p.hash==hash &&
        ((k=p.key)==key || (key !=null && key.equals(k))))
        node=p;
        //如果桶节点存在下一个节点
        else if ((e=p.next) !=null) {
            //节点为红黑树
        if (p instanceof TreeNode)
         node=((TreeNode<K,V>)p).getTreeNode(hash, key);//找到需要删除的红黑树节点
        else {
         do {//遍历链表,找到待删除的节点
             if (e.hash==hash &&
                 ((k=e.key)==key ||
                  (key !=null && key.equals(k)))) {
                 node=e;
                 break;
             }
             p=e;
         } while ((e=e.next) !=null);
        }
        }
        //删除节点,并进行调节红黑树平衡
        if (node !=null && (!matchValue || (v=node.value)==value ||
                      (value !=null && value.equals(v)))) {
        if (node instanceof TreeNode)
         ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
        else if (node==p)
         tab[index]=node.next;
        else
         p.next=node.next;
        ++modCount;
        --size;
        afterNodeRemoval(node);
        return node;
        }
        }
        return null;
    }

  注意第 46 行代码

afterNodeRemoval(node);

  这也是为实现 LinkedHashMap 做准备的,在这里和上面一样,是一个空方法实现,可以不用管。而在 LinkedHashMap 中进行了重写,用来维护删除节点后,链表的前后关系。

10、查找元素

  ①、通过 key 查找 value

  首先通过 key 找到计算索引,找到桶位置,先检查第一个节点,如果是则返回,如果不是,则遍历其后面的链表或者红黑树。其余情况全部返回 null。

public V get(Object key) {
        Node<K,V> e;
        return (e=getNode(hash(key), key))==null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab=table) !=null && (n=tab.length) > 0 &&
            (first=tab[(n - 1) & hash]) !=null) {
            //根据key计算的索引检查第一个索引
            if (first.hash==hash && // always check first node
                ((k=first.key)==key || (key !=null && key.equals(k))))
                return first;
            //不是第一个节点
            if ((e=first.next) !=null) {
                if (first instanceof TreeNode)//遍历树查找元素
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    //遍历链表查找元素
                    if (e.hash==hash &&
                        ((k=e.key)==key || (key !=null && key.equals(k))))
                        return e;
                } while ((e=e.next) !=null);
            }
        }
        return null;
    }

  ②、判断是否存在给定的 key 或者 value

public boolean containsKey(Object key) {
        return getNode(hash(key), key) !=null;
    }
    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab=table) !=null && size > 0) {
            //遍历桶
            for (int i=0; i < tab.length; ++i) {
                //遍历桶中的每个节点元素
                for (Node<K,V> e=tab[i]; e !=null; e=e.next) {
                    if ((v=e.value)==value ||
                        (value !=null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

11、遍历元素

 首先构造一个 HashMap 集合:

 HashMap<String,Object> map=new HashMap<>();
 map.put("A","1");
 map.put("B","2");
 map.put("C","3");

  ①、分别获取 key 集合和 value 集合。

//1、分别获取key和value的集合
for(String key : map.keySet()){
    System.out.println(key);
}
for(Object value : map.values()){
    System.out.println(value);
}

  ②、获取 key 集合,然后遍历key集合,根据key分别得到相应value

 //2、获取key集合,然后遍历key,根据key得到 value
 Set<String> keySet=map.keySet();
 for(String str : keySet){
     System.out.println(str+"-"+map.get(str));
 }

  ③、得到 Entry 集合,然后遍历 Entry

 //3、得到 Entry 集合,然后遍历 Entry
 Set<Map.Entry<String,Object>> entrySet=map.entrySet();
 for(Map.Entry<String,Object> entry : entrySet){
     System.out.println(entry.getKey()+"-"+entry.getValue());
 }

  ④、迭代

//4、迭代
Iterator<Map.Entry<String,Object>> iterator=map.entrySet().iterator();
while(iterator.hasNext()){
    Map.Entry<String,Object> mapEntry=iterator.next();
    System.out.println(mapEntry.getKey()+"-"+mapEntry.getValue());
}

  基本上使用第三种方法是性能最好的,

  第一种遍历方法在我们只需要 key 集合或者只需要 value 集合时使用;

  第二种方法效率很低,不推荐使用;

  第四种方法效率也挺好,关键是在遍历的过程中我们可以对集合中的元素进行删除。

12、总结

  ①、基于JDK1.8的HashMap是由数组+链表+红黑树组成,当链表长度超过 8 时会自动转换成红黑树,当红黑树节点个数小于 6 时,又会转化成链表。相对于早期版本的 JDK HashMap 实现,新增了红黑树作为底层数据结构,在数据量较大且哈希碰撞较多时,能够极大的增加检索的效率。

  ②、允许 key 和 value 都为 null。key 重复会被覆盖,value 允许重复。

  ③、非线程安全

  ④、无序(遍历HashMap得到元素的顺序不是按照插入的顺序)

参考文档:https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#

http://www.importnew.com/20386.html

https://www.cnblogs.com/nullllun/p/8327664.html

本系列教程持续更新,可以微信搜索「 IT可乐 」第一时间阅读。回复《电子书》有我为大家特别筛选的书籍资料