从源码分析java集合类原理（3）-HashMap原理分析（jdk1.7）

HashMap的原理在任何java面试中可以毫不夸张的说是被问到几率是最高的，很多拥有四五年工作经验的“老油条”可能也不能说明白其底层实现原理，今天我们就来把这个用的很多但是了解的很少的HashMap彻头彻尾的解析一遍。

在了解HashMap之前，首先我们要了解以下几个知识点

什么是Hash表？
什么是Hash算法？
什么是Hash冲突及Hash冲突的解决办法？
针对上面三个问题，是我们在了解HashMap原理之前必须了解的，它们是实现HashMap的基础。Hash表是一种数据结构，Hash表本质上还是一个数组，是一种特殊的线性表，它是通过Hash算法来决定数据在数组的存放位置的。举例说明Hash表的存取过程，Hash函数我们采用最简单的f(k)=k%4,数据集{5，6，7，8}


Hash表存取.png

上面是简单的Hash表的存取过程，上面其实存在着一个问题就是如果我现在需要再向Hash表中添加一个数据9，你会发现通过Hash函数计算应该存放到下标为1的位置，但是现在下标为1的位置已经存在数据了，此时引出一个Hash表中的另一个概念-Hash冲突，也就是两个不同元素映射到同一个位置上的情况，这种情况肯定是不允许存在的，下面再继续讨论下几种常用的解决Hash冲突的解决办法：

（1）、链地址法。链地址法的基本思路是将出现Hash冲突的数据放在一个链表中，这样数组的每一个数据元素都可能是一个链表，而链表是一个可动态增长的线性表，这样从某种程度上可以解决Hash冲突的问题。继续用上面讲到例子，继续添加数据9之后的结构就变成下面的结构。


链地址法.png

（2）、线性探测法。又称开放地址法，基本思路是在出现冲突的位置继续寻找下一个位置，如果下一个已经存在数据则继续寻找下一个位置，直到冲突解决。

（3）、再哈希法。再哈希法的基本思路就是同时定义多个Hash函数，如果出现冲突则换另一个Hash函数继续进行Hash运算，直到冲突解决。

介绍完Hash表和Hash函数及Hash冲突的相关特性之后，接下来正式进入文章的主题--HashMap的原理分析。这里注意jdk1.7和jdk1.8对HashMap的处理是有区别的，此篇文章我们先以jdk1.7 HashMap的原理进行分析。

在jdk1.7中HashMap采用数组加单链表的结构来存储数据，数据采用<key,value>的形式存储。HashMap的一个数据节点叫做Entry，其定义包括四个部分key,value,next,hash，其中key和value就是我们需要存储的数据，next是链表指向下一个节点的指针，hash是根据Hash函数对key进行hash运算得到的hash值，其源码定义如下：


Entry节点定义.png

另外在了解HashMap的原理之前我们首先需要了解几个概念：capacity容量是指HashMap中数组的大小（注意不是能够存储数据量大小，而是数组大小）；loadFactor加载因子，随着HashMap数据量的不断增加，Hash冲突的概率会越来越大，添加和查找数据的成本会越来越高，为了解决这个问题，我们需要对HashMap进行扩容，而扩容的时机就是这个加载因子决定的，当HashMap的大小达到capacity*loadFactor的时候，HashMap会进行扩容，HashMap的默认容量是16，默认加载因子为0.75，threshold 就是Capacity*loadFactor的值，也就是HashMap的扩容临界值大小。

HashMap共有四个构造函数HashMap(int initialCapacity, float loadFactor)，HashMap(int initialCapacity)，HashMap()，HashMap(Map<? extends K, ? extends V> m)。

（1）、HashMap()。该构造函数默认容量为16，默认加载因子为0.75。

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

（2）、HashMap(int initialCapacity)。该构造函数指定一个初始容量并使用默认加载因子0.75。

public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

（3）、HashMap(int initialCapacity, float loadFactor)。该构造函数我们可以指定HashMap的初始容量跟加载因子。

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;
 threshold = initialCapacity;
 init();
}

（4）、HashMap(Map<? extends K, ? extends V> m)。该构造函数根据我们指定的Map对象来构造一个HashMap对象。

public HashMap(Map<? extends K, ? extends V> m) {
 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
 inflateTable(threshold);

 putAllForCreate(m);
}

熟悉完HashMap中的一些简单概念及构造方法之后，我们继续通过源码来深入了解HashMap的数据存取操作的原理。

（1）、添加数据。向HashMap中添加数据是一个相对比较复杂的过程，如果是第一次添加数据，会调用inflateTable(int toSize)，此方法的主要作用就是创建一个大小为capacity的数组。如果key为null则调用putForNullKey(V value)方法添加数据，否则通过hash()函数计算key值对应的hash值,然后根据hash值确定数据在数组的位置下标i，最后遍历数组i下标的链表，如果存在key值相同的节点，则直接替换value并返回旧值；如果不存在key值相同的节点，则通过addEntry方法向链表中添加新数据节点（新数据节点添加到链表的首位置）。

public V put(K key, V value) {
//如果table是空，也就是第一次put数据的时候，通过inflateTable初始化
 if (table == EMPTY_TABLE) {
        inflateTable(threshold);
 }
 if (key == null)
//添加key为空的数据
 return putForNullKey(value);
//根据hash函数计算key的hash值并根据hash值确定在数组中的位置
    int hash = hash(key);
    int i = indexFor(hash, table.length);
//遍历i位置上链表的链表，如果存在key值相同的节点，则更新节点的value值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
            return oldValue;
 }
    }

 modCount++;
//如果链表中不存在key值相同的节点，则添加新节点
 addEntry(hash, key, value, i);
    return null;
}

inflateTable初始化方法首先通过roundUpToPowerOf2方法返回一个大于toSize的2的幂值作为创建数组的大小。

private void inflateTable(int toSize) {
 // 返回大于toSize的2幂值，也就是当前HashMap的容量
 int capacity = roundUpToPowerOf2(toSize);

 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//新建一个capacity大小的数组 
table = new Entry[capacity];
 initHashSeedAsNeeded(capacity);
}

addEntry方法首先判断HashMap数据量是否达到扩容临界值并且数据存放数组的位置已经存在数据，此时会调resize方法进行扩容，扩容大小为原容量的2倍（size>threshold不一定会触发扩容机制，扩容的条件是两个，一个是size>threshold；一个是数组对应位置非空即已经存在数据，只有满足两个条件的时候才会扩容）。

void addEntry(int hash, K key, V value, int bucketIndex) {
//添加数据之前首先判断是否需要扩容，如果当前数据量大于临界值threshold并且插入的位置已经有数据，则需要扩容，扩容之后的容量大小为之前的2倍
 if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
 hash = (null != key) ? hash(key) : 0;
 bucketIndex = indexFor(hash, table.length);
 }
   //将新数据添加到数组中
    createEntry(hash, key, value, bucketIndex);
}

resize方法是HashMap比较核心的一个方法，也是在很多面试中面试官会经常问到关于HashMap扩容原理问题的出处，扩容之前会判断当前容量是否已经达到最大值MAXIMUM_CAPACITY，如果达到容量最大值就不再继续扩容了。接下来用扩容后的容量新创建一个数组，再创建新数组之后，通过transfer方法将原数组中的所有数据key重新进行hash计算并放到新数组对应位置。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE;
        return;
 }
//新建一个扩容后容量的数组
 Entry[] newTable = new Entry[newCapacity];
//通过遍历原数组中的所有数据并重新计算hash值，然后将数据添加到新数组中
 transfer(newTable, initHashSeedAsNeeded(newCapacity));
//新数组赋值为原数组对象，至此数组扩容正式完成
 table = newTable;
//更新新的临界值
 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

createEntry方法主要是通过已确定的数组下标将新数据添加到链表当中去，并且是添加到链表表头的位置。

void createEntry(int hash, K key, V value, int bucketIndex) {
//新节点的next为原bucketIndex位置的数据，换句话说，也就是新节点添加到了bucketIndex链表的表头
    Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
}
数据插入.png

（2）、根据key值获取数据。获取数据的操作结合着添加数据操作来看就比较容易理解，首先判断key值是否为null，如果为null则在数组第一个位置table[0]（前面讲过key为null的数据放在了table[0]的位置）的位置，然后遍历table[0]位置的链表直到找到key值相等的节点。key值不为空的情况，首先根据key进行hash计算找到key值对应的数组下标，然后遍历链表找到key值相等的节点。

public V get(Object key) {
 if (key == null)
    //key为null时获取
 return getForNullKey();
    //key不为null时获取数据
 Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
 if (size == 0) {
 return null;
 }
//根据上面添加数据的逻辑，key为null的数据都放在数组的第一个位置，遍历数组第一个位置的链表，找到key值为空的数据返回
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null)
 return e.value;
 }
 return null;
}

final Entry<K,V> getEntry(Object key) {
 if (size == 0) {
 return null;
 }
//获取key值的hash值
 int hash = (key == null) ? 0 : hash(key);
//首先根据hash值获取数据的数组下标，然后遍历链表直到key值相等节点，返回节点value
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
 e != null;
 e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 }
 return null;
}

（3）、删除数据。删除数据查找目标数据的逻辑与（2）一致，不在赘述，当遍历找到目标数据节点之后需要删除节点，如果目标节点是首节点，这直接将目标节点的后继节点赋值给数组对应位置。如果目标节点不是首节点，则将目标节点的后继节点作为目标节点前驱节点的后继节点（可自行学习了解一下链表的删除）。

final Entry<K,V> removeEntryForKey(Object key) {
 if (size == 0) {
 return null;
 }
    //首先通过Hash函数找到对应key值对应的数组位置
 int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
 Entry<K,V> prev = table[i];
 Entry<K,V> e = prev;
//遍历数组位置链表，找到key值对应的数据节点，然后改变
    while (e != null) {
        Entry<K,V> next = e.next;
 Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
 modCount++;
 size--;
//如果是key值是首节点，直接将首节点的后继节点赋值给数组i位置
            if (prev == e)
 table[i] = next;
            else
//如果key不是首节点，则将目标节点的后继节点作为目标节点前驱节点的后继节点（链表的删除）
 prev.next = next;
 e.recordRemoval(this);
            return e;
 }
        prev = e;
 e = next;
 }

 return e;
}

总结：HashMap是通过数组加链表的形式进行数据存储的，当存储数据量达到Capacity*loadFactor并且数组对应位置已经存在数据时需要对其进行扩容，扩容的中心思想就是重新创建一个之前两倍的数组，并对原数组数据重新进行Hash计算并添加到新数组中。

才疏学浅，码字不易，有总结不到位的请各路大神多多指教，欢迎交流！

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,098评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,213评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,960评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,519评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,512评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,533评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,914评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,574评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,804评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,563评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,644评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,350评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,933评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,908评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,146评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,847评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,361评论 2赞 342