我的入门学习-阿里云开发者社区

开发者社区> 开发与运维> 正文

我的入门学习

简介: 我的入门学习

我们知道在Java 8中对于HashMap引入了红黑树从而提高操作性能,由于在上一节我们已经通过图解方式分析了红黑树原理,所以在接下来我们将更多精力投入到解析原理而不是算法本身,HashMap在Java中是使用比较频繁的键值对数据类型,所以我们非常有必要详细去分析背后的具体实现原理,无论是C#还是Java原理解析,从不打算一行行代码解释,我认为最重要的是设计思路,重要的地方可能会多啰嗦两句。

HashMap原理分析
我们由浅入深,循序渐进,首先了解下在HashMap中定义的几个属性,稍后会进一步讲解为何要定义这个值,难道是靠拍脑袋吗。

public class HashMap extends AbstractMap

implements Map, Cloneable, Serializable {

//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

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

//链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;

//取消阈值
static final int UNTREEIFY_THRESHOLD = 6;

//最小树容量
static final int MIN_TREEIFY_CAPACITY = 64;
}
构造函数分析

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR; 

}
当实例化HashMap时,我们不指定任何参数,此时定义负载因子为0.75f

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}
当实例化HashMap时,我们也可以指定初始化容量,此时默认负载因子仍为0.75f。

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

}
当实例化HashMap时,我们既指定默认初始化容量,也可指定负载因子,很显然初始化容量不能小于0,否则抛出异常,若初始化容量超过定义的最大容量,则将定义的最大容量赋值与初始化容量,对于负载因子不能小于或等于0,否则抛出异常。接下来根据提供的初始化容量设置阈值,我们接下来看看上述tableSizeFor方法实现。

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;

}
这个方法是在做什么处理呢?阈值 = 2的次幂大于初始化容量的最小值。 到学习java目前为止,我们接触到了模运算【%】、按位左移【<<】、按位右移【>>】,这里我们将学习到按位或运算【|】、无符号按位右移【>>>】。按位或运算就是二进制有1,结果就为1,否则为0,而无符号按位右移只是高位无正负之分而已。不要看到上述【n | = n >>> 1】一脸懵,实际上就是【n = n | n >>> 1】,和我们正常进行四则运算一个道理,只不过是逻辑运算和位运算符号不同而已罢了。我们通过如下例子来说明上述结论,假设初始化容量为5,接下来我们进行如上运算。

0000 0000 0000 0000 0000 0000 0000 0101 cap = 5

0000 0000 0000 0000 0000 0000 0000 0100 n = cap - 1

    0000 0000 0000 0000 0000 0000 0000 0010 n >>> 1

    0000 0000 0000 0000 0000 0000 0000 0110 n |= n >>> 1

    0000 0000 0000 0000 0000 0000 0000 0001 n >>> 2

    0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 2

    0000 0000 0000 0000 0000 0000 0000 0000 n >>> 4

    0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 4

    0000 0000 0000 0000 0000 0000 0000 0000 n >>> 8

    0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 8

    0000 0000 0000 0000 0000 0000 0000 0000 n >>> 16

    0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 16
如上最终算出来结果为7,然后加上最初计算时减去的1,所以对于初始化容量为5的最小2次幂为8,也就是阈值为8,要是初始化容量为8,那么阈值也为8。接下来到了我们的重点插入操作。

插入原理分析
public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}
上述插入操作简短一行代码,只不过是调用了putVal方法,但是我们注意到首先计算了键的哈希值,我们看看该方法实现。

static final int hash(Object key) {

int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}
直接理解方法大意是:若传入的键为空,则哈希值为0,否则直接调用键的本地hashCode方法获取哈希值,然后对其按位向右移16位,最后进行按位异或(只要不同结果就为1)操作。好像还是不懂,我们暂且搁置一下,我们继续看看插入方法具体实现。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

           boolean evict) {
Node[] tab; Node p; int n, i;

// 步骤【1】:tab为空扩容
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    
// 步骤【2】:计算index,并对null做处理     
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node e; K k;
    
    // 步骤【3】:键存在,直接覆盖值    
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
        
    // 步骤【4】:若为红黑树    
    else if (p instanceof TreeNode)
        e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    else {
        
        // 步骤【5】:若为链表
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                
                //若链表长度大于8则转换为红黑树进行处理
                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) {
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
++modCount;

// 步骤【6】:超过最大容量进行扩容
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

}
我们首先来看来步骤【2】,我们待会再来看步骤【1】实现,我们首先摘抄上述获取键的索引逻辑

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

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

上述通过计算出键的哈希值并与数组的长度按位与运算,散列算法直接决定键的存储是否分布均匀,否则会发生冲突或碰撞,严重影响性能,所以上述【 (n - 1) & hash 】是发生碰撞的关键所在,难道我们直接调用键的本地hashCode方法获取哈希值不就可以了吗,肯定是不可以的,我们来看一个例子。假设我们通过调用本地的hashCode方法,获取几个键的哈希值为31、63、95,同时默认初始化容量为16。然后调用(n-1 & hash),计算如下:

0000 0000 0000 0000 0000 0000 0001 1111 hash = 31
0000 0000 0000 0000 0000 0000 0000 1111 n - 1
0000 0000 0000 0000 0000 0000 0000 1111 => 15

0000 0000 0000 0000 0000 0000 0011 1111 hash = 63
0000 0000 0000 0000 0000 0000 0000 1111 n - 1
0000 0000 0000 0000 0000 0000 0000 1111 => 15

0000 0000 0000 0000 0000 0000 0111 1111 hash = 95
0000 0000 0000 0000 0000 0000 0000 1111 n - 1
0000 0000 0000 0000 0000 0000 0000 1111 => 15
因为(2 ^ n-1)的低位始终都是1,再按照按位运算(0-1始终为0)所有最终结果都有1111,这就是为什么返回相同索引的原因,因此,尽管我们具有不同的哈希值,但结果却是存储到哈希桶数组相同索引位置。所以为了解决低位根本就没有参与到运算中的问题:通过调用上述hash方法,按位右移16位并异或,解决因低位没有参与运算导致冲突,提高性能。我们继续回到上述步骤【1】,当数组为空,内部是如何进行扩容的呢?我们来看看resize方法实现。

final Node[] resize() {

Node[] 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;
}
else if (oldThr > 0) 
    newCap = oldThr;
else {               
    newCap = DEFAULT_INITIAL_CAPACITY;
    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;
......

}
由上可知:当实例化HashMap并无参时,此时默认初始化容量为16,默认阈值为12,负载因子为0.75f,当指定参数(初始化容量比如为5),此时初始化容量为8,阈值为8,负载因子为0.75f。否则也指定了负载因子,则以指定负载因子为准。同时当超过容量时,扩容后的容量为原容量的2倍。到这里我们发现一个问题:hashTable中的容量可为奇或偶数,而HashMap中的容量永远都为2的次幂即偶数,为何要这样设计呢?

int index = (n - 1) & hash;
如上为HashMap计算在哈希桶数组中的索引位置,若HashMap中的容量不为2的次幂,此时通过按与运算,索引只能为16或0,这也就意味着将发生更多冲突,也将导致性能很差,本可通过O(1)进行检索,现在需要O(log n),因为发生冲突时,给定存储桶中的所有节点都将存储在红黑树中,若容量为2的次幂,此时按与运算符将和hashTable中计算索引存储位置的方式等同,如下:

int index = (hash & 0x7FFFFFFF) % tab.length;
按照HashMap计算索引的方式,当我们从2的次幂中减去1时,得到的是一个二进制末位全为1的数字,例如默认初始化容量为16,如果从中减去1,则得到15,其二进制表示形式是1111,此时如果对1111进行任意数字的按位与运算,我们将得到整数的最后4位,换句话说,等价于对16取模,但是除法运算通常是昂贵的运算,也就是说按位运算比取模运算效率更高。到此我们知道HashMap中容量为2的次幂的原因在于:哈希桶数组索引存储采取按位运算而非取模运算,因其效率比取模运算更高。进行完上述扩容后容量、阈值重新计算后,接下来则需要对哈希桶数组重新哈希(rehash),请继续往下看。

影响HashMap性能因素分析
在讲解上述重新哈希之前,我们需要重头开始进行叙述,直到这里,我们知道HashMap默认初始化容量为16,假如我们有16个元素放入到HashMap中,如果实现了很好的散列算法,那么在哈希桶数组中将在每个存储桶中放入1个元素,在此种情况下,查找元素仅需要1次,如果是HashMap中有256元素,如果实现了很好的散列算法,那么在哈希桶数组中将在每个存储桶中放入16个元素,同理,在此种情况下,查找任何一个元素,最多也只需要16次,到这里我们可以知道,如果HashMap中的哈希桶数组存储的元素增加一倍或几倍,那么在每个存储桶中查找元素的最大时间成本并不会很大,但是,如果持续维持默认容量即16不变,如果每个存储桶中有大量元素,此时,HashMap的映射性能将开始下降。比如现在HashMap中有一千六百万条数据,如果实现了很好的散列算法,将在每个存储桶中分配一百万个元素,也就是说,查找任意元素,最多需要查找一百万次。很显然,我们将存储的元素放大后,将严重影响HashMap性能,那么对此我们有何解决方案呢?让我们回到最初的话题,因为默认存储桶大小为16且当存储的元素条目少时,HashMap性能并未有什么改变,但是当存储桶的数量持续增加时,将影响HashMap性能,这是由于什么原因导致的呢?主要是我们一直在维持容量固定不变,我们却一直增加HashMap中哈希桶数组中存储元素的大小,这完全影响到了时间复杂度。如果我们增加存储桶大小,则当每个存储桶中的总项开始增加时,我们将能够使得每个存储桶中的元素个数保持恒定,并对于查询和插入操作保持O(1)的时间复杂度。那么增加存储桶大小也就是容量的时机是什么时候呢?存储桶的大小(容量)由负载因子决定,负载因子是一种度量,它决定着何时增加存储桶的大小(容量),以便针对查询和插入操作保持O(1)的时间复杂度,因此,何时增加容量的大小取决于乘积(初始化容量 负载因子),所以容量和负载因子是影响HashMap性能的根本因素。我们知道默认负载因子是0.75,也就是百分之75,所以增加容量大小的值为(16 0.75)= 12,这个值我们称之为阈值,也就意味着,在HashMap中存储直到第12个键值对时,都将保持容量为16,等到第13个键值对插入到HashMap中时,其容量大小将由默认的16变为( 16 * 2)= 32。通过上述计算增加容量大小即阈值的公式,我们从反向角度思考:负载因子比率 = 哈希桶数组中元素个数 / 哈希桶数组桶大小,举个栗子,若默认桶大小为16,当插入第一个元素时,其负载因子比率 = 1 / 16 = 0.0625 > 0.75 吗?若为否无需增加容量,当插入第13个元素时,其负载因子比率 = 13 / 16 = 0.81 > 0.75吗?若为是则需增加容量。讲完这里,我们再来看看重哈希,在讲解为什么要进行重哈希之前,我们需要了解重哈希的概念:重新计算已存储在哈希桶数组中元素的哈希码的过程,当达到阈值时,将其移动到另外一个更大的哈希桶数组中。当存储到哈希桶数组中的元素超过了负载因子的限制时,此时将容量增加一倍并进行重哈希。那么为何要进行重哈希呢?因为容量增加一倍后,如若不处理已存在于哈希桶数组中键值对,那么将容量增加一倍则没有任何意义,同时呢,也是为了保持每一个存储桶中元素保持均匀分布,因为只有将元素均匀的分布到每一个存储桶中才能实现O(1)时间复杂度。接下来我们继续进行重哈希源码分析

总结
本节我们详细讲解了HashMap实现原理细节,一些比较简单的地方就没有再一一分析,文中若有叙述不当或理解错误之处,还望指正,感谢您的阅读

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

集结各类场景实战经验,助你开发运维畅行无忧

其他文章