HashMap与HashSet的底层实现原理

2年前 (2022) 程序员胖胖胖虎阿
210 0 0

⭐️前面的话⭐️

本篇文章将介绍Java中HashMap的底层实现原理,有关HashMap为数组开辟内存的时期,默认的容量,默认负载因子,树化的条件,HashMap的扩容机制,put方法的过程以及HashMap中的哈希函数。

小贴士:博主推荐->学习面试刷题必用工具

📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创,CSDN首发!
📆首发时间:🌴2022年8月14日🌴
✉️坚持和努力一定能换来诗与远方!
💭推荐书籍:📚《数据结构》,📚《算法导论》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!


📌导航小助手📌

  • 1.HashMap以及HashMap的基本原理
    • 1.1什么是HashMap?
    • 1.2HashMap的属性
    • 1.3HashMap的构造方法
    • 1.4HashMap开辟数组的时机
    • 1.5HashMap中的put
    • 1.6HashMap中的哈希函数
    • 1.7HashMap的扩容机制
  • 2.HashSet的基本实现原理
  • 3.有关HashMap其他的面试题
    • 3.1HashMap是否是线程安全的?有没有线程安全的"HashMap"?
    • 3.2HashMap有什么特点?

注意事项:博主安利一款刷题面试的神器,如果有小伙伴还没有注册牛客,可以点击下方链接进行注册,注册完就能立即刷题了。不仅是刷题,上面还有很多有关就业的面经,面试题库,以及名企的模拟面试,我非常推荐它,博主自己用的也很多,也刷了不少题了!下图可以作证:
HashMap与HashSet的底层实现原理

注册地址:牛客网

HashMap与HashSet的底层实现原理

有关任何问题都可以与博主交流,你可以在评论区留言,也可以私信我,更可以加上博主的vx与博主一对一交流(文章最下方有)。

HashMap与HashSet的底层实现原理


1.HashMap以及HashMap的基本原理

1.1什么是HashMap?

HashMap是Java集合框架中Map容器的一个实现类,它的底层是使用哈希表实现的,更加具体地说在jdk7中采用数组+链表实现,在jdk8中采用数组+链表+红黑树实现。

Map代表具有映射关系(key-value)的集合,其所有的key是一个Set集合(key值不能重复),即key无序且不能重复,而HashMap就是Map接口下的一个实现类,HashMap是一个储存键值对(EntrySet)的集合,并且支持储存key/value为null的元素。

下面我们基于jdk8来说一说HashMap的基本原理。

1.2HashMap的属性

HashMap对象被构造时,初始的默认容量为1<<4,也就是16,并且必须是2的幂(这与哈希函数有关)。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

HashMap最大的容量为1<<30,也就是

2

30

2^{30}

230

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap默认的负载因子为0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表树化的最小链表大小阈值8,当HashMap中数组大于64,数组所挂链表的大小超过8才会将数组所挂的链表转换为红黑树。

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

红黑树链表化的的阈值是6,当红黑树结点个数小于6时,就会转换为链表。

static final int UNTREEIFY_THRESHOLD = 6;

HashMap底层的数组,是一个链表数组:

transient Node<K,V>[] table;

元素个数阈值,当HashMap的size大于threshold时会执行resize操作,threshold=capacity*loadFactor,其中capacity表示数组的容量。

int threshold;

1.3HashMap的构造方法

HashMap最常用的构造方法,一个是无参的构造方法,使用无参构造方法构造HashMap时,默认的构造容量是16,但是此时不会真的去申请一个大小为16的数组,还有一个指定容量的构造方法也是如此,并且所取容量为大于或等于指定容量的一个最接近的2次幂数,日指定容量为19,那实际数组容量为32

源码:

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

除此之外,还有指定容量和负载因子的构造方法,其中tableSizeFor(initialCapacity)方法会生成比initialCapacity大并最接近initialCapacity的一个2次幂。

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

从源码可以看出其实在使用以上三种构造方法进行对象构造的时候,并没有为数组分配空间,只是确定负载因子,容量等属性。

最后还有一个根据其他的Map对象构造HashMap的构造方法,使用这种方式构造,只要传入的参数有元素,那么数组空间肯定已经申请好了,否则也是没有去申请的。

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

所以我们可以得到一个结论:当HashMap对象创建时,内部的数组并没有分配内存。

1.4HashMap开辟数组的时机

真正为数组分配内存是在第一次put操作的时候,其中源码如下:

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

意思就是通过哈希函数hash生成对应数组的下标值,找到对应的位置进制插入。
如果是第一次插入,就会对链表数组进行扩容,也是正式地为数组初始化:
HashMap与HashSet的底层实现原理
我们就不继续深入看了,在resize方法中,会为数组分配内存,并且大小为2的幂,至于为什么是这个值,这与HashMap中的哈希函数有关。

1.5HashMap中的put

如果是首次扩容,先判断数组是否为空,若数组为空则进行第一次扩容(resize),会为HashMap对象申请一个默认容量大小16的数组。

第一步,通过hash()方法计算索引,通过hash算法,计算键值对在数组中的索引,并通过索引找到在数组中的位置。
第二步,插入数据,分以下几种情况:

  • 如果当前位置元素为空,则直接插入数据;
  • 如果当前位置元素非空,遍历链表或红黑树,如果key已存在,则直接覆盖其value;
  • 如果当前位置元素非空,遍历链表或红黑树,如果key不存在,则将数据链尾插(jdk7是头插)到链表;
  • 若链表长度达到8,并且HashMap中的table数组大小达到64,则将链表转换成红黑树,并将数据插入树中,如果链表长度达到8但是table数组大小没有64则将数组扩容;

第三步,检查存储的元素个数,如果超过阈值threshold,则扩容。这一步其实也就是检查负载因子是否超过默认值,超过就扩容。

1.6HashMap中的哈希函数

前面我们说到了hash方法,HashMap中的hash方法是与我们直接根据key生成hashCode值再取模的方式不同,在HashMap中的hash算法中,首先会key计算出hashCode值,然后再将hashCode值与右移16为的hashCode值进行按位异或操作,得到一个新的哈希值,这样做的目的其实就是为了增强哈希值的随机性,这个方法也叫做“扰动方法”。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

在进行put等需要找到某个key所对应的数组索引的时候,HashMap不是通过直接取数组长度的模来得到对应的下标,取而代之的是使用按位与&运算来进行下标的计算,毕竟位运算的效率是大于取模%操作的。假设HashMap底层数组table的长度为length,不妨记n=length-1key对应的哈希值为h

在jdk8源码中,使用h&(n-1)来获取对应table数组的索引(下标),这也解释了为什么HashMap当中的数组长度一定是2的幂。

因为使用2的幂再减去一个1,得到的数n它的所有有效二进制位均为1,如64的二进制数为1000000,减去1得到n,它的值为0111111,数组的长度的二进制有效位是7位,因为数组长度是二的幂,数组下标最大下标有效位一定是6位,并且全为1,我们知道0与任何数按位与得到的均为0,而1与任何数运算得到的结果可能是1也可能是0,这就保证了在使用&操作时,每一位有效位的值都有可能是01,进一步就保证了数组table的所有下标均有可能被映射到,反之如果存在含有0的二进制有效位,则那一位按位与的操作结果一定是0,这样的话,一定存在数组table中某些下标无法被映射,增大了哈希冲突的可能性。

HashMap与HashSet的底层实现原理

做个小总结,HashMap中计算的哈希值是通过hashCode值与右移16位hashCode值按位异或的结果,这个目的就是为了增强哈希值的随机性。HashMap确定索引的方法是将n&h,毕竟按位与的效率大于取模,为了数组每个下标都可能被映射到,则n的每一位二进制有效位均得为1,所以数组的长度必须为2的幂,因为只有2的幂减1得到的有效二进制位均为1

其中n表示数组长度减去一个1h表示通过hash方法得到的哈希值。

1.7HashMap的扩容机制

HashMap中table数组初始默认大小为16,根据上述对hash方法的分析,数组table长度一定得是2的幂,从这里就不难猜出,HashMap极有可能是2倍扩容,毕竟2倍扩容比较合理,并且它能够保证扩容后的数组大小也是2的幂。

在jdk8中,HashMap的扩容,确实是采用了2倍扩容。
HashMap与HashSet的底层实现原理

当HashMap对象中元素个数size大于threshold或者数组为null时会触发扩容resize

为了解决哈希冲突,jdk8采用了数组+链表+红黑树的方式实现,当数组中某链表的长度大于8,并且数组table的长度达到64,就会将链表转换为红黑树来提高效率,当数组中某链表长度大于8但是数组table长度没有达到64,此时就会进行扩容。
HashMap与HashSet的底层实现原理

HashMap与HashSet的底层实现原理
当红黑树结点个数小于6时,就会将红黑树转换回链表。

在扩容的时候,会将所有的元素遍历,全部重新计算哈希值并全部重新确定在数组中的位置。

2.HashSet的基本实现原理

HashSet是基于HashMap实现的,默认构造函数是构建一个初始容量为16,负载因子为0.75 的HashMap。它封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。
HashMap与HashSet的底层实现原理

3.有关HashMap其他的面试题

3.1HashMap是否是线程安全的?有没有线程安全的"HashMap"?

HashMap不能保证线程安全,因为在并发的情况下进行put操作,可能会导致数组中链表死循环。
线程安全的“HashMap”有HashTable,它相比于HashMap,给关键的方法加上了锁,那么给方法加锁本质上就是给对象加锁,那么每种操作都需要拿对象锁,这样会造成激烈的锁竞争。
相比于HashTable,更推荐使用CurrentHashMap,在jdk7中,它是给每一个数组中的元素都加上了锁,或者说创建了一个新的数组Segment,这个数组用于实现加锁操作,每个 Segment 里包含一个 HashEntry 数组,Segment 中元素的结构和 HashMap 类似,是一个数组和链表结构。
在jdk8中,已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 Synchronized 和 CAS 来操作,整个看起来就像是优化过且线程安全的 HashMap,简单说,在HashMap的基础上,就是给每个数组中的元素加锁,来保证线程安全,并且由于每个数组元素都有锁,所以相比于HashTable锁竞争的激烈程度小得多。

3.2HashMap有什么特点?

  1. HashMap是线程不安全的,支持序列化。
  2. HashMap可以使用null作为key或value。
  3. HashMap查找的效率可达到O(1)。
  4. HashMap遍历方式比较单一,主要使用EntrySet 和 KeySet进行遍历,遍历方式有增强for循环和迭代器。
  5. HashMap是Map容器的一种实现,是无序的键值对集合。

下期预告:反射枚举lambda表达式

到文章最后,再来安利一下吧,博主也是经常使用,并且也经常在牛客上刷题,题库也非常丰富:学习,刷题,面试,内推都有。也欢迎与博主交流有关刷题,技术方面,以及与博主聊聊天,交个朋友也好啊,毕竟有朋自远方来!


觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!

HashMap与HashSet的底层实现原理

版权声明:程序员胖胖胖虎阿 发表于 2022年10月31日 下午1:48。
转载请注明:HashMap与HashSet的底层实现原理 | 胖虎的工具箱-编程导航

相关文章

暂无评论

暂无评论...