Java HashMap 核心源码解读

图片 4

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

前言

明天来介绍下HashMap,在此以前的List,讲了ArrayList、LinkedList,就前双方来说,反映的是二种考虑:

  • ArrayList以数组形式贯彻,顺序插入、查找快,插入、删除超级慢

  • LinkedList以链表格局完成,顺序插入、查找非常的慢,插入、删除方便

那正是说是不是有一种数据结构能够结合方面二种的优点呢?有,答案正是HashMap。它是根据哈希表的
Map 接口的达成,以key-value的花样存在。

HashMap会对null值key实行特殊管理,总是放到table[0]位置

组织图如下:

黑色线条:世袭

海水绿线条:接口完毕

图片 1

image.png

HashMap和ConcurrentHashMap的区分,HashMap的底层源码,

HashMap本质是数组加链表,根据key得到hash值,然后总计出数组下标,要是四个key对应到同一个下标,就用链表串起来,新插入的在头里。

ConcurrentHashMap在HashMap的底蕴中将数据分为四个segment,暗中认可14个,然后每一回操作对三个segment加锁,防止多线程锁的可能率,升高并发功用。

1. HashMap的数据布局

HashMap底层正是二个数组布局,数组中寄放的是一个Entry对象,如果产生的hash冲突,这个时候该岗位存储的正是叁个链表了。HashMap中Entry类的代码:

static class Entry<K,V> implements Map.Entry<K,V> {

        final K key;

        V value;

        Entry<K,V> next;

        final int hash;

        /**

         * Creates new entry.

         */

        Entry(int h, K k, V v, Entry<K,V> n) {

            value = v;

            next = n; // hash值矛盾后存放在链表的下二个

            key = k;

            hash = h;

        }

        ………

}

HashMap其实正是多个Entry数组,Entry对象中蕴藏了键和值,当中next也是三个Entry对象,它正是用来拍卖hash冲突的,产生二个链表。

2. HashMap源码解析

上面是HashMap类中的一些尤为重要品质:

transient Entry[] table; // 存款和储蓄元素的实体数组

transient int size; // 贮存成分的个数

int threshold; // 临界角,当实际尺寸超过临界角时,会开展扩大容积,threshold
= loadFactor * 容量

final float loadFactor; // 加载因子

transient int modCount; // 被改变的次数

倘使机器内部存款和储蓄器丰盛,並且想要升高查询速度的话能够将加载因子设置小一些;相反借使机器内部存款和储蓄器恐慌,並且对查询速度未有啥样要求的话能够将加载因子设置大学一年级些。然则貌似大家都不用去设置它,让它取暗许值0.75就好了。

下边是HashMap的多少个构造方法:

1     public HashMap(int initialCapacity, float loadFactor) {

 2         // 确认保证数字合法

 3         if (initialCapacity < 0)

 4             throw new IllegalArgumentException(“Illegal initial
capacity: ” +

 5                                                initialCapacity);

 6         if (initialCapacity > MAXIMUM_CAPACITY)

 7             initialCapacity = MAXIMUM_CAPACITY;

 8         if (loadFactor <= 0 || Float.isNaN(loadFactor))

 9             throw new IllegalArgumentException(“Illegal load factor:
” +

10                                                loadFactor);

11

12         // Find a power of 2 >= initialCapacity

13         int capacity = 1;   // 开始容积

14         while (capacity < initialCapacity卡塔尔   //
确认保障体量为2的n次幂,使capacity为超过initialCapacity的小小的2的n次幂

15             capacity <<= 1;

16

17         this.loadFactor = loadFactor;

18         threshold = (int)(capacity * loadFactor);

19         table = new Entry[capacity];

20         init();

21     }

22

23     public HashMap(int initialCapacity) {

24         this(initialCapacity, DEFAULT_LOAD_FACTOR);

25     }

26

27     public HashMap() {

28         this.loadFactor = DEFAULT_LOAD_FACTOR;

29         threshold = (int)(DEFAULT_INITIAL_CAPACITY *
DEFAULT_LOAD_FACTOR);

30         table = new Entry[DEFAULT_INITIAL_CAPACITY];

31         init();

32     }

暗许起始体积为16,加载因子为0.75。上边代码中13-15行,这段代码的功用是保证容积为2的n次幂,使capacity为超越initialCapacity的蝇头的2的n次幂。

上边看看HashMap存款和储蓄数据的长河是怎样的,首先拜见HashMap的put方法:

1 public V put(K key, V value) {

 2         if (key == null卡塔尔 //
要是键为null的话,调用putForNullKey(value卡塔尔

 3             return putForNullKey(value);

 4         int hash = hash(key.hashCode(卡塔尔State of Qatar; //
依据键的hashCode总括hash码

 5         int i = indexFor(hash, table.length);

 6         for (Entry<K,V> e = table[i]; e != null; e = e.next卡塔尔国{ // 管理冲突的,如若hash值相符,则在该地点用链表存款和储蓄

 7             Object k;

 8             if (e.hash == hash && ((k = e.key卡塔尔(قطر‎ == key ||
key.equals(k卡塔尔(قطر‎State of Qatar卡塔尔国 { //假如key相仿则覆盖并赶回旧值

 9                 V oldValue = e.value;

10                 e.value = value;

11                 e.recordAccess(this);

12                 return oldValue;

13             }

14         }

15

16         modCount++;

17         addEntry(hash, key, value, i);

18         return null;

19 }

当大家往HashMap中put成分的时候,先依据key的hash值获得这么些成分在数组中的地点,然后就能够把那些因素放到对应的地点中了。假若这几个成分所在的坐席上早就寄存有其余因素了,那么在同三个座席上的成分将以链表的样式寄放,新到场的坐落于链头,最早加入的放在链尾。从HashMap中get成分时,首先计算key的hashcode,找到数组中对应地点的某一因素,然后经过key的equals方法在对应地点的链表中找到需求的要素。具体的兑现是:当您的key为null时,会调用putForNullKey,HashMap允许key为null,那样的对象是坐落table[0]中。即使不为空,则调用int
hash =
hash(key.hashCode(卡塔尔(قطر‎卡塔尔(قطر‎;这是HashMap的叁个自定义的hash方法,在key.hashCode(卡塔尔(قطر‎功底上实行二回hash,源码如下:

static int hash(int h) {

      h ^= (h >>> 20) ^ (h >>> 12);

      return h ^ (h >>> 7) ^ (h >>> 4);

}

获得hash码之后就能够因此hash码去计算出相应积攒在数组中的索引,总括索引的函数如下:

static int indexFor(int h, int length) {

    return h & (length-1);

}

它通过 h &
(table.length-1State of Qatar 来得到该目的的保存位,而HashMap底层数组的长度总是 2 的n 次方,那是HashMap在进度上的优化。当length总是 2 的n次方时,h
& (length-1State of Qatar运算等价于对length取模,也正是h %
length,可是&比%怀有越来越高的功能。当数老板度为2的n次幂的时候,不相同的key算出的index相似的概率极小,那么数量在数组上布满就相比较均匀,也正是说碰撞的概率小,绝没错,查询的时候就毫无遍历有个别地方上的链表,这样查询功用也就较高了。

下边继续回来put方法里面,前边已经总括出索引的值了,见到第6到14行,如若数组中该索引的职位的链表已经存在key相近的指标,则将其遮住掉并赶回原先的值。若无与key相近的键,则调用addEntry方法创造一个Entry对象,addEntry方法如下:

1 void addEntry(int hash, K key, V value, int bucketIndex) {

2         Entry<K,V> e = table[bucketIndex]; //
假若要出席的职位有值,将该职位原先的值设置为新entry的next,也等于新entry链表的下一个节点

3         table[bucketIndex] = new Entry<>(hash, key, value, e);

4         if (size++ >= threshold卡塔尔(قطر‎ // 借使超过临界点就扩大容积

5             resize(2 * table.length卡塔尔国; // 以2的倍数扩大容积

6 }

参数bucketIndex正是indexFor函数总计出来的索引值,第2行代码是获取数组中索引为bucketIndex的Entry对象,第3行便是用hash、key、value营造三个新的Entry对象放置索引为bucketIndex的职位,何况将该地方原先的指标设置为新对象的next构成链表。第4行和第5行便是判断put后size是不是达到规定的标准了临界角threshold,假如到达了临界点将在开展扩大体积,HashMap扩大容积是扩为原本的两倍。resize(卡塔尔(قطر‎方法如下:

1 void resize(int newCapacity) {

 2         Entry[] oldTable = table;

 3         int oldCapacity = oldTable.length;

 4         if (oldCapacity == MAXIMUM_CAPACITY) {

 5             threshold = Integer.MAX_VALUE;

 6             return;

 7         }

 8

 9         Entry[] newTable = new Entry[newCapacity];

10         transfer(newTable卡塔尔国; //
用来将原先table的成分全体移到newTable里面

11         table = newTable;  // 再将newTable赋值给table

12         threshold = (int)(newCapacity * loadFactor卡塔尔; //
重新总结临界点

13 }

扩大容积是供给举办数组复制的,上边代码中第10展现复制数组,复制数组是特别消耗质量的操作,所以借使大家曾经预见HashMap中成分的个数,那么预设成分的个数能够有效的拉长HashMap的品质。上边是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; // 否则,返回null

}

HashMap本质是数组加链表,依照key得到hash值,然后总计出数组下标,假设八个key对应到同一…

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

正文

要明了HashMap, 就必定要明了精通其底层的贯彻,
而底层实现里最器重的便是它的数据构造了,HashMap实际上是贰个“链表散列”的数据布局,即数组和链表的结合体。

在拆解解析要精晓HashMap源码前有不可缺乏对hashcode进行表达。

以下是关于HashCode的合英语档定义:

hashcode方法重临该目标的哈希码值。援救该方法是为哈希表提供部分独特的地方,比方,java.util.Hashtable
提供的哈希表。

hashCode 的健康协定是:

在 Java 应用程序实践时期,在相仿对象上每每调用 hashCode
方法时,必需一致地赶回相通的整数,前提是指标上 equals
相比较中所用的消息没有被更正。从某一应用程序的一回实施到相通应用程序的另壹次试行,该整数没有必要保持一致。

设若根据 equals(Object卡塔尔方法,四个目的是非常的,那么在七个对象中的各类对象上调用 hashCode
方法都必需更换相同的子弹头结果。

以下境况不 是必得的:假使依据 equals(java.lang.Object)方法,八个对象不对等,那么在五个目的中的任一对象上调用 hashCode
方法必定会生成分歧的整数结果。不过,程序猿应该掌握,为不等于的靶子生成差异整数结果能够做实哈希表的习性。

实在,由 Object 类定义的 hashCode
方法确实会指向分歧的目标回来不一致的卡尺头。(那平日是通过将该对象的此中地址调换到叁个子弹头来完毕的,不过JavaTM 编制程序语言不供给这种完毕技术。)

当equals方法被重写时,常常常有必不可少重写 hashCode 方法,以有限支撑 hashCode
方法的平常化协定,该协定表明相等对象必得有所特别的哈希码。

以上这段官方文书档案的定义,我们能够抽取成以下多少个关键点:

  1. hashCode的存在根本是用以查找的急迅性,如Hashtable,HashMap等,hashCode是用来在散列存款和储蓄构造中规定目的的囤积地方的;

  2. 若果八个对象相近,便是适用于equals(java.lang.Object卡塔尔(قطر‎方法,那么那多个目的的hashCode必定要平等;

  3. 借使指标的equals方法被重写,那么对象的hashCode也尽量重写,而且发生hashCode使用的指标,必供给和equals方法中运用的一致,不然就能背离地方提到的第2点;

  4. 三个对象的hashCode相符,并不一定表示八个目的就相近,也等于不料定适用于equals(java.lang.Object卡塔尔方法,只好够评释那八个指标在散列存款和储蓄布局中,如Hashtable,他们“贮存在同二个篮子里”

再汇总一下就是hashCode是用以查找使用的,而equals是用于相比较八个指标的是还是不是等于的。以下这段话是从外人帖子回复拷贝过来的:

1.hashcode是用来查找的,假设您学过数据结构就活该知道,在寻找和排序这一章有

举个例子内部存款和储蓄器中有与此相类似的任务

0 1 2 3 4 5 6 7

而作者有个类,这几个类有个字段叫ID,笔者要把那个类存放在以上8个地方之一,假设不用hashcode而任性贮存,那么当查找时就须求到那多少个任务里挨个去找,也许用二分法一类的算法。

但一旦用hashcode那就能使作用拉长广大。

笔者们这么些类中有个字段叫ID,那么大家就定义大家的hashcode为ID%8,然后把大家的类寄放在获得得余数那么些地点。举例大家的ID为9,9除8的余数为1,那么大家就把该类存在1以此职分,假诺ID是13,求得的余数是5,那么大家就把该类放在5这几个地方。那样,未来在检索该类时就可以透过ID除
8求余数直接找到存放的岗位了。

2.但是即使五个类有相符的hashcode如何做那(我们如若上边的类的ID不是独一的),举例9除以8和17除以8的余数都以1,那么那是或不是官方的,回答是:能够如此。那么如何判别呢?在此个时候就要求定义
equals了。

也正是说,大家先经过
hashcode来推断八个类是或不是贮存有些桶里,但那个桶里也许有为数不菲类,那么大家就须要再经过
equals 来在此个桶里找到大家要的类。

那正是说。重写了equals(State of Qatar,为何还要重写hashCode(卡塔尔(قطر‎呢?

想想,你要在一个桶里找东西,你必得先要找到那么些桶啊,你不经过重写hashcode(卡塔尔(قطر‎来找到桶,光重写equals(State of Qatar有如何用啊

一.概述

在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(State of Qatar将其映射到整数的区间中,由于在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做一些拍卖)。

HashMap简介

二.源码剖析

连带属性 首先分明是急需叁个数组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-1State of Qatar就等价于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重返。

HashMap定义

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap 是一个散列表,它存款和储蓄的内容是键值对(key-value卡塔尔(قطر‎映射。

HashMap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。

HashMap
的达成不是一路的,那意味它不是线程安全的。它的key、value都可感到null。此外,HashMap中的映射不是板上钉钉的。

HashMap属性

// 默认初始容量为16,必须为2的n次幂
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 最大容量为2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认加载因子为0.75f
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // Entry数组,长度必须为2的n次幂
    transient Entry[] table;  //1.8:      transient Node<K,V>[] table;

    // 已存储元素的数量
    transient int size ;

    // 下次扩容的临界值,size>=threshold就会扩容,threshold等于capacity*load factor
    int threshold;

    // 加载因子
    final float loadFactor ;

HashMap是通过”拉链法”实现的哈希表。它回顾多少个主要的成员变量:table,
size, threshold, loadFactor, modCount。

  • table是一个Entry[]数组类型,而Entry实际上正是三个单向链表。哈希表的”key-value键值对”都以储存在Entry数组中的。

  • size是HashMap的分寸,它是HashMap保存的键值没有错数目。

  • threshold是HashMap的阈值,用于决断是不是须求调动HashMap的体积。threshold的值=”容积*加载因子”,当HashMap中积累数据的数目到达threshold时,就供给将HashMap的容积加倍。

  • loadFactor就是加载因子。

  • modCount是用来促成fail-fast机制的。

能够看来HashMap底层是用Entry数组存款和储蓄数据,同一时间定义了启幕容积,最大体积,加载因子等参数,至于为何容积必得是2的幂,加载因子又是什么样,上面再说,先来看一下Entry的定义。

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key ; 
        V value;
        Entry<K,V> next; // 指向下一个节点
        final int hash;

        Entry( int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key ;
        }

        public final V getValue() {
            return value ;
        }

        public final V setValue(V newValue) {
           V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return (key ==null   ? 0 : key.hashCode()) ^
                   ( value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        // 当向HashMap中添加元素的时候调用这个方法,这里没有实现是供子类回调用
        void recordAccess(HashMap<K,V> m) {
        }

        // 当从HashMap中删除元素的时候调动这个方法 ,这里没有实现是供子类回调用
        void recordRemoval(HashMap<K,V> m) {
        }
}

下方为1.8的method:
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;  // 指向下一个节点

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value); 
        }
    //比如二进制 1001 ^ 1100 = 0101   //亦或,相同为为假,不同为真

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

Entry是HashMap的内部类,它三番一遍了Map中的Entry接口,它定义了键(key卡塔尔国,值(value卡塔尔(قطر‎,和下两个节点的援用(next卡塔尔,以及hash值。很醒目标能够看出Entry是怎么样组织,它是单线链表的三个节点。也等于说HashMap的平底布局是一个数组,而数组的元素是二个单向链表。

图片 2

image.png

为啥会犹如此的布署?早先介绍的List中询问时索要遍历全部的数组,为精晓决那几个题目HashMap接纳hash算法将key散列为三个int值,那些int值对应到数组的下标,再做询问操作的时候,获得key的散列值,依照数组下标就能够平素找到存款和储蓄在数组的要素。不过由于hash可能会不由自主相仿的散列值,为了化解冲突,HashMap接纳将一律的散列值存款和储蓄到二个链表中,也正是说在一个链表中的元素他们的散列值相对是一律的。找到数组下标收取链表,再遍历链表是还是不是比遍历整个数组功能好的多吗?

咱俩来看一下HashMap的有声有色贯彻。

HashMap布局函数

/**
     * 构造一个指定初始容量和加载因子的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);

        // Find a power of 2 >= initialCapacity
        // 确保容量为2的n次幂,是capacity为大于initialCapacity的最小的2的n次幂
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        // 赋值加载因子
        this.loadFactor = loadFactor;
        // 赋值扩容临界值
        threshold = (int)(capacity * loadFactor);
        // 初始化hash表
        table = new Entry[capacity];
        init();
    }

    /**
     * 构造一个指定初始容量的HashMap
     */
    public HashMap( int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 构造一个使用默认初始容量(16)和默认加载因子(0.75)的HashMap
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

    /**
     * 构造一个指定map的HashMap,所创建HashMap使用默认加载因子(0.75)和足以容纳指定map的初始容量。
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        // 确保最小初始容量为16,并保证可以容纳指定map
        this(Math.max(( int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY ), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
}

下方为1.8的method:

    //构造一个指定初始容量和加载因子的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;   // 赋值加载因子
        this.threshold = tableSizeFor(initialCapacity);  // 赋值扩容临界值
    }

//threshold是作为扩容的阈值而存在的,它是由负载银子决定的。下面的方法是返回
与给定数值最接近的2的n次方的值:
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;
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

HashMap提供了五个布局函数:

  • HashMap(卡塔尔(قطر‎:布局二个持有暗许初始容积 (16卡塔尔国 和私下认可加载因子 (0.75卡塔尔(قطر‎ 的空
    HashMap。

  • HashMap(int initialCapacity卡塔尔(قطر‎:结构叁个带钦赐初步容积和暗许加载因子
    (0.75卡塔尔 的空 HashMap。

  • HashMap(int initialCapacity, float
    loadFactorState of Qatar:布局二个带钦赐最初容积和加载因子的空 HashMap。

  • public HashMap(Map<? extends K, ? extends V>
    mState of Qatar:包涵“子Map”的构造函数

在此间涉及了多个参数:初步容积,加载因子。那八个参数是震慑HashMap性能的第一参数,当中容积表示哈希表中桶的多寡,早先容积是创立哈希表时的容积,加载因子是哈希表在其容积自动增添早前能够高达多满的一种口径,它衡量的是一个散列表的空中的施用程度,负载因子越大表示散列表的回填程度越高,反之愈小。对于使用链表法的散列表来讲,查找二个因素的平均时间是O(1+a卡塔尔国,由此一旦负载因子越大,对空中的使用更丰硕,然则结果是研究功能的下降;假若负载因子太小,那么散列表的数码将过于萧条,对空间产生凄惨浪费。系统暗中认可负载因子为0.75,平日景观下我们是没有必要校订的。

API方法摘要

图片 3

image.png

HashMap源码剖析(基于JDK1.6.0_45)

put方法

HashMap会对null值key进行特殊管理,总是放到table[0]位置

put进度是先总计hash然后因此hash与table.length取摸总结index值,然后将key放到table[index]位置,当table[index]已存在别的成分时,会在table[index]地方产生贰个链表,将新加上的因素放在table[index],原本的因素通过Entry的next进行链接,那样以链表方式化解hash冲突难点,当元素数量达来临界角(capactiyfactorState of Qatar时,则开展扩大体量,是table数主任度变为table.length2

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value); //处理null值
        int hash = hash(key.hashCode());//计算hash
        int i = indexFor(hash, table.length);//计算在数组中的存储位置
    //遍历table[i]位置的链表,查找相同的key,若找到则使用新的value替换掉原来的oldValue并返回oldValue
        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;
            }
        }
    //若没有在table[i]位置找到相同的key,则添加key到table[i]位置,新的元素总是在table[i]位置的第一个元素,原来的元素后移
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
    private V putForNullKey(V value) {
        // 取出数组第1个位置(下标等于0)的节点,如果存在则覆盖不存在则新增,和上面的put一样不多讲,
        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++;
        // 如果key等于null,则hash值等于0
        addEntry(0, null, value, 0);
        return null;
    }

    void addEntry(int hash, K key, V value, int bucketIndex) {
    //添加key到table[bucketIndex]位置,新的元素总是在table[bucketIndex]的第一个元素,原来的元素后移
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //判断元素个数是否达到了临界值,若已达到临界值则扩容,table长度翻倍
        if (size++ >= threshold)
            resize(2 * table.length);
    }

get方法

相通当key为null时会举行超过常规规处理,在table[0]的链表上索求key为null的要素

get的进度是先总括hash然后透过hash与table.length取摸总结index值,然后遍历table[index]上的链表,直到找到key,然后回来

public V get(Object key) {
        if (key == null)
            return getForNullKey();//处理null值
        int hash = hash(key.hashCode());//计算hash
    //在table[index]遍历查找key,若找到则返回value,找不到返回null
        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;
}

remove方法

remove方法和put
get雷同,总括hash,总括index,然后遍历查找,将找到的成分从table[index]链表移除

/**
     * 根据key删除元素
     */
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e. value);
    }

    /**
     * 根据key删除链表节点
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        // 计算key的hash值
        int hash = (key == null) ? 0 : hash(key.hashCode());
        // 根据hash值计算key在数组的索引位置
        int i = indexFor(hash, table.length );
        // 找到该索引出的第一个节点
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        // 遍历链表(从链表第一个节点开始next),找出相同的key,
        while (e != null) {
            Entry<K,V> next = e. next;
            Object k;
            // 如果hash值和key都相等,则认为相等
            if (e.hash == hash &&
                ((k = e. key) == key || (key != null && key.equals(k)))) {
                // 修改版本+1
                modCount++;
                // 计数器减1
                size--;
                // 如果第一个就是要删除的节点(第一个节点没有上一个节点,所以要分开判断)
                if (prev == e)
                    // 则将下一个节点放到table[i]位置(要删除的节点被覆盖)
                    table[i] = next;
                else
                 // 否则将上一个节点的next指向当要删除节点下一个(要删除节点被忽略,没有指向了)
                    prev. next = next;
                e.recordRemoval( this);
                // 返回删除的节点内容
                return e;
            }
            // 保存当前节点为下次循环的上一个节点
            prev = e;
            // 下次循环
            e = next;
        }

        return e;
}

clear()方法

clear方法特简单,正是遍历table然后把各样地方置为null,同期改良成分个数为0

急需小心的是clear方法只会分晓里边的因素,并不会重新初始化capactiy

public void clear() {
        modCount++;
        Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
            tab[i] = null;
        size = 0;
}

resize方法

resize方法在hashmap中并不曾明白,那个情势完毕了非常主要的hashmap扩大容积,具体经过为:先创设贰个容积为table.length2的新table,改正临界点,然后把table里面成分总计hash值并动用hash与table.length2再一次总结index放入到新的table里面

此间供给潜心下是用每个成分的hash全体再度计算index,并非轻易的把原table对应index地方成分简单的移动到新table对应地方

void resize( int newCapacity) {
        // 当前数组
        Entry[] oldTable = table;
        // 当前数组容量
        int oldCapacity = oldTable.length ;
        // 如果当前数组已经是默认最大容量MAXIMUM_CAPACITY ,则将临界值改为Integer.MAX_VALUE 返回
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        // 使用新的容量创建一个新的链表数组
        Entry[] newTable = new Entry[newCapacity];
        // 将当前数组中的元素都移动到新数组中
        transfer(newTable);
        // 将当前数组指向新创建的数组
        table = newTable;
        // 重新计算临界值
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        // 当前数组
        Entry[] src = table;
        // 新数组长度
        int newCapacity = newTable.length ;
        // 遍历当前数组的元素,重新计算每个元素所在数组位置
        for (int j = 0; j < src. length; j++) {
            // 取出数组中的链表第一个节点
            Entry<K,V> e = src[j];
            if (e != null) {
                // 将旧链表位置置空
                src[j] = null;
                // 循环链表,挨个将每个节点插入到新的数组位置中
                do {
                    // 取出链表中的当前节点的下一个节点
                    Entry<K,V> next = e. next;
                    // 重新计算该链表在数组中的索引位置
                    int i = indexFor(e. hash, newCapacity);
                    // 将下一个节点指向newTable[i]
                    e. next = newTable[i];
                    // 将当前节点放置在newTable[i]位置
                    newTable[i] = e;
                    // 下一次循环
                    e = next;
                } while (e != null);
            }
        }
}

transfer方法中,由于数组的容量已经变大,也就引致hash算法indexFor已经发生变化,原先在一个链表中的元素,在新的hash下也许会生出不相同的散列值,so全部成分都要重新总括后安置一番。注目的在于do
while循环的长河中,每一回循环都以将下个节点指向newTable[i]
,是因为假若有相近的散列值i,上个节点已经停放在newTable[i]职位,这里依然下三个节点的next指向上二个节点(不知晓这里是否能明白,画个图掌握下吧)。

Map中的成分越来越多,hash冲突的可能率也就越大,数高管度是定点的,所以招致链表越来越长,那么查询的成效当然也就越低下了。还记不记得还要数组容器的ArrayList咋办的,扩容!而HashMap的扩大容积resize,要求将具有的要素重新总结后,三个个重新排列到新的数组中去,那是可怜低效的,和ArrayList一样,在能够预感容积大小的动静下,提前预设容积会促销扣HashMap的扩大容积,提升质量。

再来看看加载因子的功能,假诺加载因子越大,数组填充的越满,那样能够使得的使用空间,但是有贰个害处便是唯恐会招致冲突的加大,链表过长,反过来却又会促成内部存款和储蓄器空间的浪费。所以不能不必要在空竹秋岁月首找叁个平衡点,那就是安装有效的加载因子。我们明白,很多时候为了压实查询功效的做法都是就义空间换取时间,到底该怎么选拔,那将在具体深入分析了。

containsKey方法

containsKey方法是先总结hash然后选择hash和table.length取摸获得index值,遍历table[index]要素查找是还是不是富含key相通的值

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

final Entry<K,V> getEntry(Object key) {
    // 获取哈希值
    // HashMap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值
    int hash = (key == null) ? 0 : hash(key.hashCode());
    // 在“该hash值对应的链表”上查找“键值等于key”的元素
    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;
}

getEntry(State of Qatar的效果就是归来“键为key”的键值对,它的落到实处源码中一度扩充了验证。

那边必要强调的是:HashMap将“key为null”的因素都位居table之处0处,即table[0]中;“key不为null”的坐落于table的别的地点!

containsValue方法

containsValue方法就超粗大暴了,便是平昔遍历全部因素直到找到value,简来讲之HashMap的containsValue方法本质上和平常数组和list的contains方法没什么差异,你别期望它会像containsKey那么急迅

public boolean containsValue(Object value) {
    // 若“value为null”,则调用containsNullValue()查找
    if (value == null)
        return containsNullValue();

    // 若“value不为null”,则查找HashMap中是否有值为value的节点。
    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}

containsNullValue() 的作用剖断HashMap中是还是不是含有“值为null”的成分

private boolean containsNullValue() {
    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (e.value == null)
                return true;
    return false;
}

entrySet()、values()、keySet()方法

它们3个的原理形似,这里以entrySet(卡塔尔(قطر‎为例来注解。

entrySet(卡塔尔国的功力是归来“HashMap中全数Entry的成团”,它是贰个相会。金玉锦绣代码如下:

// 返回“HashMap的Entry集合”
public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}

// 返回“HashMap的Entry集合”,它实际是返回一个EntrySet对象
private Set<Map.Entry<K,V>> entrySet0() {
    Set<Map.Entry<K,V>> es = entrySet;
    return es != null ? es : (entrySet = new EntrySet());
}

// EntrySet对应的集合
// EntrySet继承于AbstractSet,说明该集合中没有重复的EntrySet。
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

HashMap是通过拉链法完毕的散列表。表今后HashMap包蕴广大的Entry,而每二个Entry本质上又是三个单向链表。那么HashMap遍历key-value键值没有错开上下班时间候,是什么样各种去遍历的啊?

上边大家就看看HashMap是何许通过entrySet(卡塔尔(قطر‎遍历的。

entrySet(卡塔尔(قطر‎实际上是通过newEntryIterator(卡塔尔达成的。 下边大家看看它的代码:

// 返回一个“entry迭代器”
Iterator<Map.Entry<K,V>> newEntryIterator()   {
    return new EntryIterator();
}

// Entry的迭代器
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}

// HashIterator是HashMap迭代器的抽象出来的父类,实现了公共了函数。
// 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
private abstract class HashIterator<E> implements Iterator<E> {
    // 下一个元素
    Entry<K,V> next;
    // expectedModCount用于实现fast-fail机制。
    int expectedModCount;
    // 当前索引
    int index;
    // 当前元素
    Entry<K,V> current;

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            // 将next指向table中第一个不为null的元素。
            // 这里利用了index的初始值为0,从0开始依次向后遍历,直到找到不为null的元素就退出循环。
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    // 获取下一个元素
    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        // 注意!!!
        // 一个Entry就是一个单向链表
        // 若该Entry的下一个节点不为空,就将next指向下一个节点;
        // 否则,将next指向下一个链表(也是下一个Entry)的不为null的节点。
        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }

    // 删除当前元素
    public void remove() {
        if (current == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Object k = current.key;
        current = null;
        HashMap.this.removeEntryForKey(k);
        expectedModCount = modCount;
    }

}

当我们透过entrySet(卡塔尔获取到的Iterator的next(卡塔尔(قطر‎方法去遍历HashMap时,实际上调用的是
nextEntry(卡塔尔(قطر‎。而nextEntry(卡塔尔(قطر‎的达成形式,先遍历Entry(依照Entry在table中的序号,从小到大的遍历卡塔尔国;然后对种种Entry(即每个单向链表卡塔尔(قطر‎,每一个遍历。

hash和indexFor

indexFor中的h &
(length-1卡塔尔(قطر‎就一定于h%length,用于总结index相当于在table数组中的下标

hash方法是对hashcode进行三次散列,以赢得更加好的散列值

为了更加好精通这里我们得以把这两个主意简化为 int index=
key.hashCode(State of Qatar/table.length,以put中的方法为例能够如此替换

int hash = hash(key.hashCode());//计算hash
int i = indexFor(hash, table.length);//计算在数组中的存储位置
//上面这两行可以这样简化
int i = key.key.hashCode()%table.length;

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);
}
static int indexFor(int h, int length) {
    return h & (length-1);
}

HashMap示例

上面通过一个实例学习怎么样行使HashMap

public class MapDemo02 {
    public static void main(String[] args) {
        Map m=new HashMap();
        System.out.println("添加put方法:(1,'a'),(2,'b'),(3,'c'),(4,'d')");
        m.put("1","a");
        m.put("2","b");
        m.put("3","c");
        m.put("4","d");
        System.out.println("打印添加后的map"+m);
        System.out.println("删除第四个4元素");
        m.remove("4");
        System.out.println("打印map"+m);

        // containsKey(Object key) :是否包含键key
        System.out.println("contains key 1 : "+m.containsKey("1"));
        // containsValue(Object value) :是否包含值value
        System.out.println("contains value a : "+m.containsValue("a"));
        // 通过Iterator遍历key-value
        Iterator iterator = m.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry entry = (Map.Entry)iterator.next();
            System.out.println("next : "+ entry.getKey() +" - "+entry.getValue());
        }
        // clear() : 清空HashMap
        m.clear();
        // isEmpty() : HashMap是否为空
        System.out.println((m.isEmpty()?"map is empty":"map is not empty") );
    }
}

输出:

添加put方法:(1,'a'),(2,'b'),(3,'c'),(4,'d')
打印添加后的map{3=c, 2=b, 1=a, 4=d}
删除第四个4元素
打印map{3=c, 2=b, 1=a}
contains key 1 : true
contains value a : true
next : 3 - c
next : 2 - b
next : 1 - a
map is empty

总结

HashMap和Hashtable的区别

  1. 两边最要害的界别在于Hashtable是线程安全,而HashMap则非线程安全

    Hashtable的贯彻格局里面都加多了synchronized关键字来保管线程同步,因而相对来说HashMap品质会高级中学一年级些,大家平常利用时若无特殊须要建议接受HashMap,在八线程碰着下若采纳HashMap须求运用Collections.synchronizedMap(State of Qatar方法来取得叁个线程安全的集合(Collections.synchronizedMap(卡塔尔(قطر‎实现原理是Collections定义了四个SynchronizedMap的中间类,那个类实现了Map接口,在调用方法时接受synchronized来作保线程同步,当然了事实上操作的要么我们传入的HashMap实例,简单的说正是Collections.synchronizedMap(卡塔尔国方法帮大家在操作HashMap时自动增添了synchronized来完结线程同步,肖似的任何Collections.synchronizedXX方法也是周边原理)

  2. HashMap能够行使null作为key,而Hashtable则不许null作为key

    纵然HashMap扶助null值作为key,然则建议照旧尽量防止那样使用,因为只要十分的大心使用了,若因而吸引部分主题素材,每个核实起来卓殊麻烦

    HashMap以null作为key时,总是存款和储蓄在table数组的第一个节点上

  3. HashMap是对Map接口的达成,HashTable完毕了Map接口和Dictionary抽象类

  4. HashMap的最早容积为16,Hashtable起初容积为11,两个的填写因子暗中同意都以0.75

    HashMap扩大体量时是前段时间体量翻倍即:capacity2,Hashtable扩大体量时是容量翻倍+1即:capacity2+1

  5. HashMap和Hashtable的底层完成都以数组+链表构造实现

  6. 相互总结hash的章程差别

    Hashtable计算hash是一向运用key的hashcode对table数组的长度直接进行取模

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap总计hash对key的hashcode进行了三遍hash,以博得越来越好的散列值,然后对table数老板度取摸

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

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

参考

该文为自个儿学习的笔记,方便现在自个儿跳槽前复习。参照他事他说加以考察互连网各大帖子,取其精髓整合和睦的领会而成。集合框架源码面试经常会问,所以解读源码十一分必要,希望对你有用。

java提高篇(二三)—–HashMap

Java 集结类别10之
HashMap详细介绍(源码解析卡塔尔和应用示例

浓烈Java集合学习种类:HashMap的完结原理

给jdk写注释种类之jdk1.6容器(4卡塔尔(قطر‎-HashMap源码拆解深入分析

深刻Java会集学习种类:HashMap的得以完成原理

收拾的聚焦框架思维导图

图片 4

image.png

HashMap1.8

原稿链接:http://www.jianshu.com/p/e6536af1018f

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图