深入理解HashMap

? 哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，本文会对java集合框架中HashMap的实现原理进行讲解，并对JDK1.8的HashMap源码进行分析。

面试官的灵魂拷问??

谈一下HashMap的特性？

HashMap中hash函数是怎么实现的？

为什么HashMap数组的长度必须是2的N次幂？

HashMap的扩容机制是什么？

为什么红黑树和链表的转换阈值是6和8不是7呢？

为什么jdk1.8中新增的是红黑树而不是AVL？

什么是HashMap?

???HashMap是基于哈希表的Map接口的非同步实现，是一种用于key-value的映射关系的集合，并且key和value都允许为null，且不保证顺序性。在1.7的时候底层采用数组+链表实现，1.8底层采用数组+链表+红黑树实现（以下基于1.8）。

数据结构

?

基本常量

//默认初始化大小?1<<4=16

static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<<?4;?//?aka?16

//最大容量

static?final?int?MAXIMUM_CAPACITY?=?1?<<?30;

//加载因子0.75

static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;

//当链表长度大于等于该值时转换为红黑树

static?final?int?TREEIFY_THRESHOLD?=?8;

//当红黑树的大小小于等于该值时转换回链表

static?final?int?UNTREEIFY_THRESHOLD?=?6;

//转换为红黑树时当前整个数组的大小必须大于等于这个值

//才进行转换，可以去看看转换代码treeifyBin

static?final?int?MIN_TREEIFY_CAPACITY?=?64;

构造函数

?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()?{

?????//?all?other?fields?defaulted?0.75f

????????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?

????}

上面三个构造函数中第二个函数调用调用的是第一个构造函数，第三个是默认的无参数构造。下面主要讲第一个。

在构造函数HashMap(int initialCapacity, float loadFactor)中,前面对两个参数进行了范围验证，然后设置加载因子，并且结算下一次扩容的阈值，这里看一下源码

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;

????}

以上tableSizeFor()这个函数的意思就是返回一个>=给定数的2^N。

>>>表示不带符号向右移动二进制数。

|=表示按二进制位或操作，并赋值等价于a=a|b。

以下

/**

?*

?*?以正数8为例

?*?源码：

?*?00000000?00000000?00000000?00001000

?*?>>>1

?*?00000000?00000000?00000000?00000100

?*?|=1

?*?00000000?00000000?00000000?00001100

?*?>>>2

?*?00000000?00000000?00000000?00000011

?*?|=2

?*?00000000?00000000?00000000?00001111

?*?>>>4

?*?00000000?00000000?00000000?00000000???到这里可以看出来，后面的计算是无效的

?*?|=4

?*?00000000?00000000?00000000?00001111

?*?-------------------------------------------------

?*?以正数7为例

?*?源码：

?*?00000000?00000000?00000000?00000111

?*?>>>1

?*?00000000?00000000?00000000?00000011

?*?|=1

?*?00000000?00000000?00000000?00000111

?*?>>>2

?*?00000000?00000000?00000000?00000001

?*?|=2

?*?00000000?00000000?00000000?00000111

?*/

?

上面整个计算过程的意思就是从高位到低位第一个1后面的数字全部置1。

为什么要把第一个1后面的数字全部置1？因为2在计算机中具有特殊的地位。如果一个数等于2^N，这个数的二进制表示肯定只有一个1(不包括符号位)。

代码一开始为什么要减1？可以看到上面正数8进行5次移位或等的结果是15,与预期初始化长度为8大了一个级别。这里减掉一个1,在进行移位运算的时候将自己本身也包含进去。

前面移位运算的结果总是2^N-1,所以在函数返回的时候+1，刚好等于2^N

hash函数

??static?final?int?hash(Object?key)?{

????????int?h;

????????return?(key?==?null)???0?:

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

????}

首先进行了>>>16位，也就是将高16位移动到低16位， 然后^按位异或(同为0，不同为1)，其运算结果高地位都参与进去了，增加了随机因子。

插入原理

因为put函数调用的直接就是putVal()方法，所以这里直接看putVal(),代码挺长;

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;

????????//判断数组是否存在和数组长度

????????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)

????????????//创建新的数组

????????????n?=?(tab?=?resize()).length;

?????????//判断该地址是否存在元素节点,并将p指向地址

????????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)

????????????tab[i]?=?newNode(hash,?key,?value,?null);//创建新的节点

????????else?{

????????????//该下标已存在节点

????????????Node<K,V>?e;?K?k;//声明临时节点

????????????if?(p.hash?==?hash?&&

????????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))

????????????????//如果元素的hash相同且equals相等，那么判定为同一个元素

????????????????e?=?p;

????????????//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);

????????????????????????//?判断是否满足转换为红黑树

????????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?

????????????????????????????treeifyBin(tab,?hash);//转换为红黑树

????????????????????????break;

????????????????????}

????????????????????//判断链表内的元素和赋值的元素是否为同一个元素

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

????}

执行流程图

?

扩容机制

resize()源码

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

????????????}

????????????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

????????????newCap?=?oldThr;

????????else?{???????????????//?zero?initial?threshold?signifies?using?defaults

????????????newCap?=?DEFAULT_INITIAL_CAPACITY;

????????????//这里0.75*数组长度

????????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);

????????}

????????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?{?//?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;

????????????????????????????}

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

????????????????????????}

????????????????????}

????????????????}

????????????}

????????}

????????return?newTab;

????}

扩容机制

?

扩容时高低链问题

先看代码是如何通过hash定位数组下标的·

????????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)

????????????tab[i]?=?newNode(hash,?key,?value,?null);

首先知道数组的长度永远是2^N次方，转换为2进制，只有1个1，(2^N)-1,二进制从2^N这一位的后一位开始为后面全是1，采用这种方式分布也是可以让不同的hash值定位到相同的下标上面。（注:同一个链表里面的所有节点hash不一定相同，相同hash的肯定定位到同一个链表）

再看看如何区分高链和低链的

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

????}

上面代码就是hash & oldCap时=0时就是低链，!=就是高链，将高链偏移一个原始数组的位置即可。

(注：这里(2^N)-1和(2^N-1)在二进制的时候除了第一位一样，其余位全部不一样，所以偏移一个原始数组位置）

为什么转换阈值不是7？

直接看什么时候转换的

???//插入时

???if?(binCount?>=?TREEIFY_THRESHOLD?-?1)

????????treeifyBin(tab,?hash);

//转换或者移除时，很多地方大差不差

?if?(lc?<=?UNTREEIFY_THRESHOLD)

??????tab[index]?=?loHead.untreeify(map);

转换红黑树条件>=7，转换回来条件<=6，插入的时候是已经存在了7个，当前插入的算一个，相当于间隔了一个的。如果是7的话，那么链表和红黑树之间的切换范围值就太小了。如果我的链表长度不停地在7和8之间切换，那岂不是得来回变换形态？所以选择6是一种折中的考虑。

为什么jdk1.8选用红黑树？

AVL树性质

本身首先是一棵二叉搜索树。

带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）

红黑树性质

每个节点，不是红色就是黑色的；

根节点是黑色的；

如果一个节点是红色的，则它的两个子节点是黑色的(没有连续的红色结点，可以有连续的黑色节点,这里意味着最长路径最差情况是最短路径的1倍)

对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。(每条路径的黑色结点个数相等)

每个叶子节点都是黑色的（这里的叶子节点是指的NIL节点（空节点）） 优缺点：因为不要求严格平衡，在查询效率上比AVL少许，但是在插入效率上比AVL效率高，这里增删改差的效率比较平衡；

整体来说：AVL树侧重于搜索，红黑树因为不要求严格彭亨，在插入和搜索两个功能上性能比较均匀，所以选用红黑树。

其他常见问题

Q：什么是哈希碰撞？

A：HashMap中2个对象产生相同的hashcode时就是哈希碰撞

Q：HashMap是如何解决哈希碰撞？

A：产生哈希碰撞的对象，以链表的形式存储在数组的同一个位置上

Q：HashMap的数组中同一链表上对象的hashcode都一样的吗？

A：不是，而且大多数情况下都不一样

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

推荐阅读更多精彩内容

  • 概述 键值对操作在大的业务场景中经常用到，HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据...
    ZMRWEGo阅读 533评论 0赞 4
  • 简述 HashMap是一种比较常见的map子类，是由数组+链表组成(JDK8以后采用的是数组+链表+红黑树的形式)...
    CDF_cc7d阅读 935评论 0赞 7
  • HashMap解决了什么问题？ 任何数据结构的产生总对应要解决一个实际的问题，HashMap的产生要解决问题就是：...
    竖起大拇指阅读 164评论 0赞 0
  • 1,HashMap的概要 HashMap内部使用了哈希函数,是关联数组哈希表,是线程不安全的,它允许自己的key为...
    chengcongyue阅读 405评论 0赞 0
  • 1. 散列表（哈希表） 这部分内容是科普散列表的实现原理，不会涉及HashMap的细节。后续分析HashMap时会...
    彳亍口巴阅读 154评论 0赞 3