一、Map体系的继承树

20160804204055369.jpg

二、HashMap

1.概述:

HashMap 是基于哈希表的 Map 接口的实现,以 Key-Value 的形式存在,即存储的对象是 Entry (同时包含了 Key 和 Value) 。在HashMap中,其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地,HashMap最多只允许一条Entry的键为Null(多条会覆盖),但允许多条Entry的值为Null。此外,HashMap 是 Map 的一个非同步的实现。 

2.构造函数

HashMap()

1、HashMap() //该构造函数意在构造一个具有> 默认初始容量 (16) 和 默认负载因子(0.75) 的空 HashMap,是 Java Collection Framework 规范推荐提供的,其源码如下:
 
    public HashMap() {
 
        this.loadFactor = DEFAULT_LOAD_FACTOR;  //负载因子:用于衡量的是一个散列表的空间的使用程度
 
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); //HashMap进行扩容的阈值,它的值等于 HashMap 的容量乘以负载因子
 
        table = new Entry[DEFAULT_INITIAL_CAPACITY]; // HashMap的底层实现仍是数组,只是数组的每一项都是一条链
 
        init();
    }

HashMap(int initialCapacity, float loadFactor)

2、HashMap(int initialCapacity, float loadFactor)  //该构造函数意在构造一个 指定初始容量 和 指定负载因子的空 HashMap,其源码如下:
 
    public HashMap(int initialCapacity, float loadFactor) {
        
        if (initialCapacity < 0) //初始容量不能小于 0
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
 
        if (initialCapacity > MAXIMUM_CAPACITY) ////初始容量不能超过 2^30
            initialCapacity = MAXIMUM_CAPACITY;
            
        if (loadFactor <= 0 || Float.isNaN(loadFactor))  //负载因子不能小于 0
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
         
        int capacity = 1;  //// HashMap 的容量必须是2的幂次方,超过 initialCapacity 的最小 2^n
        while (capacity < initialCapacity)
            capacity <<= 1;   
 
        this.loadFactor = loadFactor; //负载因子
 
        threshold = (int)(capacity * loadFactor);//设置HashMap的容量极限,当HashMap的容量达到该极限时就会进行自动扩容操作
 
        table = new Entry[capacity];  // HashMap的底层实现仍是数组,只是数组的每一项都是一条链
        init();
    }

 在这里,我们提到了两个非常重要的参数:初始容量 和 负载因子,这两个参数是影响HashMap性能的重要参数。其中,容量表示哈希表中桶的数量 (table 数组的大小),初始容量是创建哈希表时桶的数量;负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。

       对于使用 拉链法(下文会提到)的哈希表来说,查找一个元素的平均时间是 O(1+a),a 指的是链的长度,是一个常数。特别地,若负载因子越大,那么对空间的利用更充分,但查找效率的也就越低;若负载因子越小,那么哈希表的数据将越稀疏,对空间造成的浪费也就越严重。系统默认负载因子为 0.75,这是时间和空间成本上一种折衷,一般情况下我们是无需修改的。

3.数据结构

20170317181650025.png

从上图中,我们可以形象地看出HashMap底层实现还是数组,只是数组的每一项都是一条链。其中参数initialCapacity 就代表了该数组的长度,也就是桶的个数。前面们已经了解了HashMap 的默认构造函数的源码,可以看出,每次新建一个HashMap时,都会初始化一个Entry类型的table数组,

其中 Entry类型的定义如下:

static class Entry<K,V> implements Map.Entry<K,V> {
 
    final K key;     // 键值对的键
    V value;        // 键值对的值
    Entry<K,V> next;    // 下一个节点
    final int hash;     // hash(key.hashCode())方法的返回值
 
    Entry(int h, K k, V v, Entry<K,V> n) {     // Entry 的构造函数
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    ......
}

其中,Entry为HashMap的内部类,实现了 Map.Entry 接口,其包含了键key、值value、下一个节点next,以及hash值四个属性。事实上,Entry 是构成哈希表的基石,是哈希表所存储的元素的具体形式。

4.HashMap 中的哈希策略(算法)

 HashMap 中的哈希策略,hash() 方法用于对Key的hashCode进行重新计算,而 indexFor() 方法用于生成这个Entry对象的插入位置。当计算出来的hash值与hashMap的(length-1)做了&运算后,会得到位于区间[0,length-1]的一个值。特别地,这个值分布的越均匀, HashMap 的空间利用率也就越高,存取效率也就越好。

我们首先看 hash() 方法,该方法为一个纯粹的数学计算,用于进一步计算key的hash值,

源码如下:

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

正如JDK官方对该方法的描述那样,使用hash()方法对一个对象的hashCode进行重新计算是为了防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的幂次,通过右移可以使低位的数据尽量的不同,从而使hash值的分布尽量均匀 

通过上述hash()方法计算得到 Key 的 hash值 后,怎么才能保证元素均匀分布到table的每个桶中呢?我们会想到取模,但是由于取模的效率较低,HashMap 是通过调用indexFor()方法处理的,其不但简单而且效率很高,

对应源码如下所示:

static int indexFor(int h, int length) {
        return h & (length-1);  // 作用等价于取模运算,但这种方式效率更高
    }

我们知道,HashMap的底层数组长度总是2的n次方。当length为2的n次方时,h&(length - 1)就相当于对length取模,而且速度比直接取模要快得多,这是HashMap在速度上的一个优化。至于HashMap的底层数组长度为什么是2的n次方,下一节将给出解释。

 总而言之,上述的hash()方法和indexFor()方法的作用只有一个:保证元素均匀分布到table的每个桶中以便充分利用空间。

4. HashMap 的扩容:resize() 

随着HashMap中元素的数量越来越多,发生碰撞的概率将越来越大,所产生的子链长度就会越来越长,这样势必会影响HashMap的存取速度。为了保证HashMap的效率,系统必须要在某个临界点进行扩容处理,该临界点就是HashMap中元素的数量在数值上等于threshold(table数组长度*加载因子)。但是,不得不说,扩容是一个非常耗时的过程,因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。所以,如果我们能够提前预知HashMap 中元素的个数,那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能。

我们直接看其源码:

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
 
        // 若 oldCapacity 已达到最大值,直接将 threshold 设为 Integer.MAX_VALUE
        if (oldCapacity == MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;
            return;             // 直接返回
        }
 
        // 否则,创建一个更大的数组
        Entry[] newTable = new Entry[newCapacity];
 
        //将每条Entry重新哈希到新的数组中
        transfer(newTable);
 
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);  // 重新设定 threshold
    }

5. HashMap 的重哈希:transfer()

重哈希的主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程,

我们直接看其源码:

void transfer(Entry[] newTable) {
 
        // 将原数组 table 赋给数组 src
        Entry[] src = table;
        int newCapacity = newTable.length;
 
        // 将数组 src 中的每条链重新添加到 newTable 中
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;   // src 回收
 
                // 将每条链的每个元素依次添加到 newTable 中相应的桶中
                do {
                    Entry<K,V> next = e.next;
 
                    // e.hash指的是 hash(key.hashCode())的返回值;
                    // 计算在newTable中的位置,注意原来在同一条子链上的元素可能被分配到不同的子链
                    int i = indexFor(e.hash, newCapacity);   
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

特别需要注意的是,在重哈希的过程中,原属于一个桶中的Entry对象可能被分到不同的桶,因为HashMap 的容量发生了变化,那么 h&(length - 1) 的值也会发生相应的变化。极端地说,如果重哈希后,原属于一个桶中的Entry对象仍属于同一桶,那么重哈希也就失去了意义

三. HashMap 的底层数组长度为何总是2的n次方?

我们知道,HashMap的底层数组长度总是2的n次方,原因是 HashMap 在其构造函数 HashMap(int initialCapacity, float loadFactor) 中作了特别的处理,如下面的代码所示。当底层数组的length为2的n次方时, h&(length - 1) 就相当于对length取模,其效率要比直接取模高得多,这是HashMap在效率上的一个优化。

// HashMap 的容量必须是2的幂次方,超过 initialCapacity 的最小 2^n 
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;  

在上文已经提到过,HashMap 中的数据结构是一个数组链表,我们希望的是元素存放的越均匀越好。最理想的效果是,Entry数组中每个位置都只有一个元素,这样,查询的时候效率最高,不需要遍历单链表,也不需要通过equals去比较Key,而且空间利用率最大。

  那如何计算才会分布最均匀呢?正如上一节提到的,HashMap采用了一个分两步走的哈希策略:

  • 使用 hash() 方法用于对Key的hashCode进行重新计算,以防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的倍数,通过右移可以使低位的数据尽量的不同,从而使Key的hash值的分布尽量均匀;
  • 使用 indexFor() 方法进行取余运算,以使Entry对象的插入位置尽量分布均匀(下文将专门对此阐述)。

对于取余运算,我们首先想到的是:哈希值%length = bucketIndex。但当底层数组的length为2的n次方时, h&(length - 1) 就相当于对length取模,而且速度比直接取模快得多,这是HashMap在速度上的一个优化。除此之外,HashMap 的底层数组长度总是2的n次方的主要原因是什么呢?我们借助于 chenssy 在其博客《java提高篇(二三)—–HashMap》中的关于这个问题的阐述:

  这里,我们假设length分别为16(2^4) 和 15,h 分别为 5、6、7。

20170317222404822.jpg

我们可以看到,当n=15时,6和7的结果一样,即它们位于table的同一个桶中,也就是产生了碰撞,6、7就会在这个桶中形成链表,这样就会导致查询速度降低。诚然这里只分析三个数字不是很多,那么我们再看 h 分别取 0-15时的情况。

20170317222422033.jpg

从上面的图表中我们可以看到,当 length 为15时总共发生了8次碰撞,同时发现空间浪费非常大,因为在 1、3、5、7、9、11、13、15 这八处没有存放数据。这是因为hash值在与14(即 1110)进行&运算时,得到的结果最后一位永远都是0,即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。这样,空间的减少会导致碰撞几率的进一步增加,从而就会导致查询速度慢。

  而当length为16时,length – 1 = 15, 即 1111,那么,在进行低位&运算时,值总是与原来hash值相同,而进行高位运算时,其值等于其低位值。所以,当 length=2^n 时,不同的hash值发生碰撞的概率比较小,这样就会使得数据在table数组中分布较均匀,查询速度也较快。

 因此,总的来说,HashMap 的底层数组长度总是2的n次方的原因有两个,即当 length=2^n 时:

  • 不同的hash值发生碰撞的概率比较小,这样就会使得数据在table数组中分布较均匀,空间利用率较高,查询速度也较快;
  • h&(length - 1) 就相当于对length取模,而且在速度、效率上比直接取模要快得多,即二者是等价不等效的,这是HashMap在速度和效率上的一个优化。

最后,由于HashMap在多线程中是不安全的,可以移步HashMap的死循环

面试——谈谈HashMap的底层实现

HashMap 是基于哈希表的 Map 接口的实现,以 Key-Value 的形式存在,即存储的对象是 Entry (同时包含了 Key 和 Value) 。

HashMap的构造函数中有两个影响HashMap性能的重要参数,初始容量 和 负载因子,系统默认负载因子为 0.75,这是时间和空间成本上一种折衷

HashMap的底层是哈希表实现的,结合了数组寻址容易以及链表插入和删除容易的特点

碰撞处理:常用的有两种方式,一种是open hashing,即 >拉链法;另一种就是 closed hashing,即开地址法(opened addressing)。

HashMap查找效率很高,但是多线程中是非安全的,jdk1.8后使用红黑树替代了链表。

以下来自转载

先来些简单的问题

“你用过HashMap吗?” “什么是HashMap?你为什么用到它?”

几乎每个人都会回答“是的”,然后回答HashMap的一些特性,譬如HashMap可以接受null键值和值,而Hashtable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对等等。这显示出你已经用过HashMap,而且对它相当的熟悉。

但是面试官来个急转直下,从此刻开始问出一些刁钻的问题,关于HashMap的更多基础的细节。面试官可能会问出下面的问题:

“你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”

你也许会回答“我没有详查标准的Java API,你可以看看Java源代码或者Open JDK。”“我可以用Google找到答案。”

但一些面试者可能可以给出答案,“HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点,或者错误的认为仅仅只在bucket中存储值的话,你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确,也显示出面试者确实知道hashing以及HashMap的工作原理。但是这仅仅是故事的开始,当面试官加入一些Java程序员每天要碰到的实际场景的时候,错误的答案频现。

下个问题可能是关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法:

“当两个对象的hashcode相同会发生什么?” 从这里开始,真正的困惑开始了,一些面试者会回答因为hashcode相同,所以两个对象是相等的,HashMap将会抛出异常,或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法,并告诉他们两个对象就算hashcode相同,但是它们可能并不相等。一些面试者可能就此放弃,而另外一些还能继续挺进,他们回答“因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理,虽然有很多种处理碰撞的方法,这种方法是最简单的,也正是HashMap的处理方法。

但故事还没有完结,面试官会继续问:

“如果两个键的hashcode相同,你如何获取值对象?” 面试者会回答:当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket,他给出答案:将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较,你是如何确定确定找到值对象的?除非面试者直到HashMap在链表中存储的是键值对,否则他们不可能回答出这一题。

其中一些记得这个重要知识点的面试者会说,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。完美的答案!

许多情况下,面试者会在这个环节中出错,因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现,而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。

如果你认为到这里已经完结了,那么听到下面这个问题的时候,你会大吃一惊。“如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?”除非你真正知道HashMap的工作原理,否则你将回答不出这道题。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

如果你能够回答这道问题,下面的问题来了:“你了解重新调整HashMap大小存在什么问题吗?”你可能回答不上来,这时面试官会提醒你当多线程的情况下,可能产生条件竞争(race condition)。

当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?

Last modification:December 25th, 2019 at 01:39 pm
如果觉得我的文章对你有用,请随意赞赏
评论打卡也可以哦,您的鼓励是我最大的动力!