hashmap修改对应key的值_HashMap结构走析一遍

HashMap是我们日常编码中使用频率非常高的一个数据结构，也几乎是面试中必问的一个点，现在咱们对HashMap的结构来一次简单的走析。

public class HashMap   extends AbstractMap  implements Map, Cloneable, Serializable ｛｝

可以看到HashMap实现了Map接口。HashMap对Map接口的实现基于散列表(hash table)，所以在开始，咱们先看一下什么是散列表。

散列表

散列表是一种数据结构，我们可以把散列表看做一种特殊使用方式的数组，之所以特殊，是因为一般使用数组存放的元素E与数组的下标INDEX之间并没有特定的关系，而在散列表中元素E会与INDEX通过一个函数建立一种映射关系，当这个函数确定后，元素E在数组中的位置也随之确定。这个函数我们称它为哈希函数。哈希函数的实现不是固定的，可以根据实际情况进行设计编码。

哈希表的大小可以根据自己的需求进行设定，也就是修改这个特殊数组的长度，数据元素的存放只要根据哈希函数进行映射到相应的位置，用法比较容易，也比较灵活。但在使用的过程中，可能会产生“冲突”，举个列子，比如我们创建一个容积为10的数组Array[10],设定一个哈希函数F(x)=x%10,有9与19两个值，根据哈希函数映射，两个值都会映射到Array[9]的位置。要解决这“冲突”，最常见的方法是链地址法，创建一个元素为链表初始值为空的数组，当有“冲突”发生时，产生冲突的元素将成为对应数组元素地址中链表元素的下一个值，逻辑如下简图，HashMap采用的就是这种实现(在JDK1.8之后有升级实现，后面会有提及)。

左侧0-5是数组空间

通过上面打的描述我们来完善一下散列表的说明：散列表是一种以数组为基础，通过哈希函数进行存放位置寻找并通过合理方法进行冲突处理并确定最终处理位置后形成的一种数据结构形式。我们可以看到，碰撞“冲突”发生的越多，所产生的链表的长度会越长，随之会导致遍历的复杂度会有所上升。

接下来咱们走一遍HashMap的数据结构。

HashMap

兼容空值

先说明一下，HashMap支持key值或value值为null的映射，针对key值为null的情况，HashMap进行了特殊的操作。

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

可以看到，在当key为null的时候，将其hash值直接返回为0。通过此hash函数所获得的结果，HashMap会将其用于取模运算，从而确定元素在数组中所处的索引位置。

结构说明

HashMap这个数据结构中有如下成员变量

transient Node[] table;transient Set> entrySet;transient int size;transient int modCount;int threshold;final float loadFactor;

定义了这么一些常量：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final int MAXIMUM_CAPACITY = 1 << 30;static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;

来分别说明一下每个成员变量：

1、table

HashMap是数组+链表的实现，成员变量中的变量table就是基础数组，其中存放Node结构的元素，Node是HashMap的静态内部类，其基本结构如下

static class Node implements Map.Entry {    final int hash;    final K key;    V value;    Node next;    ...}

Node节点封装了原始的key值与value值以及下一个节点的引用next。通过next形成一条单向的链。table数组会在第一使用时初始化，在没有指定容量的情况下，会使用默认值DEFAULT_INITIAL_CAPACITY，也就是16，在使用过程中，数组的大小会根据需要进行扩容操作。这里特别说明一下，这个容量指的是基础数组的长度，也就是可以容纳链的数量，而不是HashMap所能承载key-value键值对的数量。这是一个小问题，但很多人都会搞错。

2、entrySet

简单说一下entrySet,这个变量是用来缓存entrySet()方法中涉及的返回值，entrySet()我们应该比较熟悉，作为map遍历的时候，我们多会用到它，entrySet()的实现如下：

public Set> entrySet() {    Set> es;    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;}

可以看到entrySet主要是用来放置中间结果，在代码中有关对entrySet的维护涉及一个比较有意思的迭代器的使用形式，说明篇幅会比较大，我后面会单起一篇文章来讲述HashMap对entrySet这个变量的维护。

3、size

size变量是用于记录map中包含的键值对的数量，hashmap会在添加或删除元素的时候对size进行维护。

4、modeCount

modCount在可能使HashMap的体积或者说size产生变化的方法中都进行了维护，这个值记录了HashMap被修改的次数，这个变量在单线程操作中有点多余，但在多线程操作时就可以起到校验的作用。当然现在，如果涉及多线程操作，一般不直接使用HashMap,而是使用Concurrent系列api,有关Concurrent系列的API使用，也会在之后的文章中讲述。

5、loadFactor

loadFactor 直译是装载因子，一般默认为DEFAULT_LOAD_FACTOR，也就是0.75，loadFactor是一个期望值，也就是HashMap中的size增长至大于capacity的75%时，就需要进行扩容，以保证HashMap的工作及使用效率，装载因子是一种空间与时间的折中值，因为装载因子越大，HashMap填满的元素越多，空间利用率高了，随之产生的“冲突”就越多，查找的时间成本就越高，装载因子越小，HashMap填满的元素就越少，空间利用率低，产生的“冲突”就越少，查找的时间成本也就降低了。

至于装载因子为什么默认是0.75，我这里只能给出一个“差不多”的说法，很多人说这个值是跟泊松分布有关，这是一个不准确的解释，有点因果颠倒的感觉，如果作为一个程序设计者，这个值完全可以通过多次调整，并测试得出，相信，这个值应该不是一个恒定的值，而是一条在一定值范围内的曲线，这里取值0.75更大的可能是开发者为了节省或者减少考虑的因素，在一定程度上为满足空间与时间而取的折中值(0.5不利于空间的利用，1会阻塞数据的写入)。

6、threshold

threshold这个值就是capacity与装载因子的乘积。算是一个中间结果，就不多解释了。

7、几个特别常量

这是在jdk1.8之后新增加了几个常量，TREEIFY_THRESHOLD 化树阈值，UNTREEIFY_THRESHOLD 还原阈值，MIN_TREEIFY_CAPACITY 最小化树阈值，这几个属性是对HashMap的数据结构的升级，主要用于控制HashMap中链表与红黑树的转换。当链表长度上升，通过与几个常量值的比较，就会触发链表与红黑树之间的转换，同时业扩展出一个新的数据结构，如下。也就是说1.8之后的HashMap是数组+链表+红黑树实现。

static final class TreeNode extends LinkedHashMap.Entry {    TreeNode parent;  // red-black tree links    TreeNode left;    TreeNode right;    TreeNode prev;    // needed to unlink next upon deletion    boolean red;  ...}

transient使用说明

很多人对HashMap中几个主要成员变量使用transient修饰感到困惑，其实这个是为了保证数据迁移时的准确性，现在JVM使用最广泛地就是Hotspot虚拟机，但并不是说只有这一种实现，不同的虚拟机实现的时候，对哈希值的实现是不同的，如果我们使用jvm默认的序列化，在不同实现的JVM上进行反序列化，是不能找到对应的值的。

HashMap扩容说明

当size的值大于threshold的值的时候，HashMap就会执行扩容操作，扩容操作时会重新计算数据的存放位置，是一种相对耗时的操作，所以我们在初始化HashMap时，应对容量作出预估，尽量减少在执行过程中的HashMap扩容现象。

if (++size > threshold)    resize();

HashMap的散列算法

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

还是开始的一段代码，HashMap通过hash方法对key值进行了特殊处理，通过无符号右移截取了key的哈希值的高位16位并与key值的哈希值进行了异或运算，作为了后续取模寻址计算的输入。这样做混合了原始哈希值的高低位，增大了低位的随机性。这个过程也就是做扰动计算。

i = (n - 1) & hash

这是HashMap中做目标寻址计算的索引函数，i就是数据的下标，n是数组的长度，hash是上面hash方法对key值进行哈希处理后的返回值。任意整数m对2^n取模等效于 m&(2^n-1),即上面的这段代码就是hash%( n -1)的变形。但因为将取模运算转换为了位运算，计算速度会有很大提升。

简单总结一下：HashMap是Map的具体实现，它实现了Map应有的所有可选操作，在实现上使用数组+链表+红黑树的形式，同时它兼容对null值的操作。

我们的目标：让生活更美好