HashMap实现原理基础篇

关于数据结构，我想大家在工作中常常会用到，HashMap的使用频率就更不用说了。不过许多工作了好几年，用过很多次HashMap的同学，仍然表示对HashMap的结构不太了解。本文想通过一种通俗易懂的方式，让大家了解HashMap的实现。

数据结构中常用数组和链表来实现对数据的存储，两者有各自的特点。

数组

数组存储区间是连续的，特点是：寻址容易，插入和删除困难。

链表

链表存储区间离散，特点是：寻址困难，插入和删除容易。

以上两种数据结构的区别，从事java和android研发的同学在面试过程中可能会遇到，很基础简单的问题，千万不要答错哦。

哈希表

哈希表采取了数组+链表的结构，综合了两者的特性，也就是说它寻址容易，插入删除也容易。哈希表既满足
了数据的查找方便，同时占用较小的内存空间，使用也很方便。

哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 链地址法，
链地址法可以解决一些可能出现的问题：

  1. 覆盖危机
  2. 发生碰撞

这些问题我们会在下文提到，在此，我们看看这个“链表的数组” 的结构：
内部结构.png

从上图我们可以发现哈希表是由数组+链表组成的：底层是一个数组，数组的每一项又是一个链表。（每新建HashMap的时候，就会初始化这样一个数组）

注意：数组中存储的，是链表地址的引用，链表中的存储的数据结构是Entry对象 。在链表这个维度， 有很多个Entry对象， 有Entry对象的集合。

在长度为16的数组中，每个元素存储的是一个链表的头结点的引用。这些元素按照既定的规则存储到数组中： 一般情况是通过hash(key)%length获得，也就是元素的key的哈希值对数组长度取余得到。
比如上述哈希表中，12%16=12，28%16=12，108%16=12，140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

在HashMap的内部实现了一个静态内部类Entry，其重要属性有key、 value 和 next。

从属性key、 value中可以看出Entry就是HashMap键值对实现的一个基础数据类型。

Entry的每一项有三个属性：key、 value、 next。 而Map的内容存在这个Entry集合里，这就是我们上文
说的：HashMap的底层是一个数组结构，数组的每一项又是一个链表.

下面我们来看看HashMap的实现：

既然是线性数组，为什么能散列存取？这里HashMap用了一个小算法，大致是这样实现：

// 存储时：
int hash = key.hashCode(); // hashCode理解为每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

// 取值时：
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

即根据对象的key获取HashCode值，用HashCode对length取余，得到存储位置index。 我想你或许已经发现了：既然是通过HashCode对length取余获取存储位置index，那么不同的HashCode对length取余的结果可能是相同的，也就是说，不同的对象可能存储在同样的index位置，这样就会有覆盖危机。

覆盖危机：

基于上文的算法： hash(key) % length，那么得出的index可能会相同，后来插入的数岂不是要覆盖
之前的？ 这可是很危险的，如何解决这个问题? 这里用到了链式数据结构的一个概念。还记得上文
提到的HashMap的内部Entry吗?除了key、value 外，还有个next属性，作用是用来指向下一个Entry。

举个栗子：

第一个键值对A 插入进来，通过计算其key的hashCode得到的index=0，记做：Entry[0] = A。一会后
又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做：B.next = A，
Entry[0] = B，如果又进来C，index也等于0，那么C.next = B，Entry[0] = C；这样我们发现index=0的
地方其实存取了A，B，C三个键值对，他们通过next这个属性链接在一起。由此可见，最后插入的元素
地址会存储在数组第一项里，而之前插入的元素，会用next与之相连. 这个方法称为链地址法。
以上是Jdk1.7的源码处理方式

插入对象的put方法：

public V put(K key， V value) {
        if (key == null)
            //null总是放在数组的第一个链表中
            return putForNullKey(value); 
        int hash = hash(key.HashCode());
        int i = indexFor(hash， table.length);
        //遍历链表
        for (Entry<K，V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果key在链表中已存在，则替换为新value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash， key， value， i);
        return null;
    }
 
/**  
 * HashMap 添加节点  
 *  
 * @param hash        当前key生成的hashcode  
 * @param key         要添加到 HashMap 的key  
 * @param value       要添加到 HashMap 的value  
 * @param 要添加的结点对应到数组的位置下标  
 */ 
void addEntry(int hash， K key， V value， int bucketIndex) {
    Entry<K，V> e = table[bucketIndex];
    //参数e， 是Entry.next
    table[bucketIndex] = new Entry<K，V>(hash， key， value， e); 
    // threshold=load factor*current capacity
    //如果size大于等于阈值 threshold，则扩充table大小。
    if ((size >= threshold) && (null != table[bucketIndex])) {    
        //扩容之后，数组长度变了 
        resize(2 * table.length);   
       //hash值是根据key与数组长度取模算的,长度变了,当然要重新计算hash值
        hash = (null != key) ? hash(key) : 0;    
        //数组长度变了，数组的下标与长度有关，需重算。    
        bucketIndex = indexFor(hash, table.length);
    }    
    createEntry(hash, key, value, bucketIndex);    
} 
/**  
 * 是否为链表
 * 1.   原来数组bucketIndex处为null，则直接插入 
 * 2.   原来数组bucketIndex有值，则根据Entry的构造函数，
         把新的结点存于数组中，原来数据用新结点的next指向
 */    
void createEntry(int hash, K key, V value, int bucketIndex) {    
    HashMap.Entry<K, V> e = table[bucketIndex];    
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);    
    size++;    
}

Entry[]的长度一定后，随着Map里面数据的越来越长，会不会影响性能？查看源码，HashMap在此做了优化，随着map的size越来越大（size++ >= threshold），就要resize，也就是重新调整Entry[]的大小 。 那么Entry[]会以一定的规则加长长度。这个resize的过程，简单的说就是把Entry扩充为2倍（resize(2 * table.length)），之后重新计算index，再把节点再放到新的Entry中。
想要了解这个resize的详细过程，思考如下几个问题：

这个优化是怎么做的?

获取对象的get方法

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.HashCode());
        //先定位到数组元素，再遍历该元素处的链表
        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.equals(k)))
                return e.value;
        }
        return null;
}

key为null的存取

  // null key总是存放在Entry[]数组的第一个元素。
   private V putForNullKey(V value) {
        for (Entry<K，V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0， null， value， 0);
        return null;
    }
 
    private V getForNullKey() {
        for (Entry<K，V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

确定数组index：HashCode % table.length取余

HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，即计算数组下标， 在设计hash函数
时，因为目前的table长度n为2的幂，所有计算下标的时候，是这样实现的：
   /**
     * Returns index for hash code h.
     */
    static int indexFor(int h， int length) {
        return h & (length-1);
    }
按位与运算，作用上相当于取模mod或者取余%。
设计者认为这种方式很容易发生碰撞，因此想到了一个顾全大局的方法(综合考虑了速度、作用、质量)，就
是把HashCode的高16bit和低16bit异或了一下。代码如下：
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 ： (h = key.HashCode()) ^ (h >>> 16);
}

由此很容易看出数组下标相同，并不表示HashCode相同。

那如果HashCode相同呢

碰撞的发生
当两个不同的键拥有相同的HashCode时，就称为”碰撞”.当我们将键值对传递给put方法时，他调用
键对象的HashCode(key)方法来计算HashCode，如果与现有的对象的HashCode相同，则碰撞发生，
那么如何存储这个put来的对象对象呢?
目前解决碰撞的方法有：
  • 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
  • 再哈希法
  • 链地址法(也称拉链法)
  • 建立一个公共溢出区
Java中使用链地址法：将所有关键字为同义词的节点链接在同一个单链表中

通俗的讲： 同样的HashCode对length取余得到同样的下标index，将对象Entry[index]
插入存储在下标为index的链表中，并用next指向，类似覆盖危机的解决方案。So 无论
多少个冲突，都只是在当前位置给单链表增加节点，是不是很简单？

流程如下：
int hash = key.HashCode(); 
int index = hash % Entry[].length;
Entry[index] = value; //之后执行插入
获取： 但是HashCode相同，如何取值呢？
首先：使用get方法，流程大致如下：
int hash = key.HashCode();
int index = hash % Entry[].length;
return Entry[index];
通过此方法可以获取一个下标为index的Entry对象（可能是单独的一个对象，也可能是一个链表；因为可能存
在HashCode相同的对象，存储在链表中），既然要与我们寻找的key值匹配，则需要用到key.equals()方法，
匹配找到链表中正确的节点，得到想要的值对象.

由此可见，就算两个对象的HashCode相同，但是他们可能并不相等

本篇是HashMap基础篇，旨在用通俗易懂的方式，介绍HashMap的数据结构与实现原理，下一篇是进阶篇，分析HashMapResize这个过程。最后用几个面试题，将这些知识点串联在一起。
参考文档：http://blog.csdn.net/caisini_vc/article/details/52452498

喜欢学习，乐于分享，不麻烦的话，给个❤鼓励下吧！

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