Java HashMap 核心源码解读

本篇对HashMap实现的源码进行简单的分析。 所使用的HashMap源码的版本信息如下:

/*
* @(#)HashMap.java 1.73 07/03/13
*
* Copyright 2006 Sun Microsystems, Inc.
 All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. 
Use is subject to license terms.
*/

一.概述

在Java中每一个对象都有一个哈希码,这个值可以通过hashCode()方法获得。

hashCode()的值和对象的equals方法息息相关,是两个对象的值是否相等的依据,所以当我们覆盖一个类的equals方法的时候也必须覆盖hashCode方法。

例如String的hashCode方法为:

public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;

for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}

可以看得出,一个字符串的哈希值为s[0]31n-1 + s[1]31n-2 + … + s[n-1],是一个整数。也就是说所有的字符串可以通过hashCode()将其映射到整数的区间中,由于在java中整数的个数是有限的(四个字节有正负,第一位为符号位-231 ~ 231 -1),当s[0]31n-1 + s[1]31n-2 + … + s[n-1]足够大的时候可能会溢出,导致其变成负值。从上面的情况我们可以看出两个不同的字符串可能会被映射到同一个整数,发生冲突。因此java的开发人员选择了31这个乘数因子,尽量使得各个字符串映射的结果在整个java的整数域内均匀分布。

谈完java对象的哈希码,我们来看看今天的主角HashMap,HashMap可以看作是Java实现的哈希表。HashMap中存放的是key-value对,对应的类型为java.util.HashMap.Entry,所以在HashMap中数据都存放在一个Entry引用类型的数组table中。这里key是一个对象,为了把对象映射到table中的一个位置,我们可以通过求余法来,所以我们可以使用 [key的hashCode % table的长度]来计算位置(当然在实际操作的时候由于需要考虑table上的key的均匀分布可能需要对key的hashCode做一些处理)。

二.源码解析

相关属性 首先肯定是需要一个数组table,作为数据结构的骨干。

transient Entry[] table;

这边定义了一个Entry数组的引用。 继续介绍几个概念把

capacity容量 是指数组table的长度 loadFactor 装载因子,是实际存放量/capacity容量 的一个比值,在代码中这个属性是描述了装载因子的最大值,默认大小为0.75 threshold(阈值)代表hashmap存放内容数量的一个临界点,当存放量大于这个值的时候,就需要将table进行夸张,也就是新建一个两倍大的数组,并将老的元素转移过去。threshold = (int)(capacity * loadFactor);

put方法详解

public V put(K key, V value) {
        if (key == 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;
            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中我们的key可以为null,所以第一步就处理了key为null的情况。 当key为非null的时候,你也许会认为:恩,直接和table长度相除取模吧,但是这里没有,而是又好像做了一次哈希,这是为什么呢?这个还得先看indexFor(hash, table.length)方法,这个方法是决定存放位置的

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

明眼的都可以发现,因为在HashMap中table的长度为2n (我们把运算都换成二进制进行考虑),所以h & (length-1)就等价于h%length,这也就是说,如果对原本的hashCode不做变换的话,其除去低length-1位后的部分不会对key在table中的位置产生任何影响,这样只要保持低length-1位不变,不管高位如何都会冲突,所以就想办法使得高位对其结果也产生影响,于是就对hashCode又做了一次哈希

static int hash(int h) {
// This function ensures that hashCodes 
//that differ only by
// constant multiples at each bit position
 //have a bounded
// number of collisions 
//(approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
    }

当找到key所对应的位置的时候,对对应位置的Entry的链表进行遍历,如果以及存在key的话,就更新对应的value,并返回老的value。如果是新的key的话,就将其增加进去。modCount是用来记录hashmap结构变化的次数的,这个在hashmap的fail-fast机制中需要使用(当某一个线程获取了map的游标之后,另一个线程对map做了结构修改的操作,那么原先准备遍历的线程会抛出异常)。addEntry的方法如下

void addEntry(int hash, K key, V value, 
int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>
(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

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

get方法其实就是将key以put时相同的方法算出在table的所在位置,然后对所在位置的链表进行遍历,找到hash值和key都相等的Entry并将value返回。

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2015-06-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏轻扬小栈

刚发现:虚函数可以突破子类中的private限制

12630
来自专栏Danny的专栏

设计模式奠基石——UML关系转化为代码

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

21530
来自专栏云霄雨霁

数据压缩----霍夫曼树和霍夫曼压缩

20800
来自专栏数据结构与算法

洛谷 P3386 【模板】二分图匹配 Dinic版

题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每...

34890
来自专栏Java 源码分析

HashMap 源码分析

HashMap 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所以在...

29970
来自专栏和蔼的张星的图像处理专栏

数据结构栈队列链表树二叉查找树

这学期刚回到所里的时候把c++数据结构看了一遍,基本的数据结构照着视频也敲了一遍,不过那个时候自己对c++的了解只限于一些基本的语法,c++primer也还没有...

18940
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十八】Map接口集合详解

四、Map接口 Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。同时它也没有继承Collecti...

38460
来自专栏Ryan Miao

Java8-理解Collector

31040
来自专栏Java爬坑系列

【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

26150
来自专栏互联网开发者交流社区

HashMap相关(二)

13250

扫码关注云+社区

领取腾讯云代金券