欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【JAVA】HashMap底层实现原理浅谈

程序员文章站 2022-03-03 23:24:07
...

                                  HashMap底层实现原理浅谈

不论是实习还是正式工作,HashMap的底层实现原理一直是问地频率最高的一个内容,今天记录一下自己对HashMap的理解,如有不当之处,还请各位大佬指正。


一、前置名词解释

(1)哈希表

哈希表的主体躯干就是数组,我们可以利用下标对元素进行快速索引。新增一个元素时,元素的插入位置由哈希函数来定。

(2)哈希算法/哈希函数

哈希函数的作用是将一个不固定长度的二进制值经过运算,转化为一个固定长度的二进制值。将插入元素的key进行运算后,得到某个index值,从而确定在数组中的存储位置。但多个不相同的元素,经过哈希函数运算后,可能得到相同的index,这就出现了哈希冲突。

(3)哈希冲突/哈希碰撞

再好的哈希算法在有限长度的哈希表上,都会造成哈希冲突。那么怎么解决冲突呢?有多种解决方案

【1】开放地址法:放弃本次运算得到的index,继续寻找下一块未被占用的空间

【2】再散列法

【3】链地址法:采用数组(哈希表主体)+链表(为了解决哈希冲突而存在)的形式,哈希表中存储数组,数组中的元素空间存储链表的头结点。当发生冲突时,将相应的index位置上旧元素的指针next指向新元素即可。HashMap采用的就是这种方法


二、HashMap的特点

(1)允许存放null键和null值,而HashTable都不允许

(2)不是线程安全的,而HashTable是线程安全的,当然我们可以使用ConcurrentHashMap来代替HashTable,而且ConcurrentHashMap的性能更好,因为它只对数组的一部分进行上锁,即分段锁,而不是锁住整个数组。

(3)数组的默认大小为16,源码中没有直接写16,而是1<<4。

  /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

(4)默认的负载因子是0.75,表示的是,如果数组中已经存储的元素个数大于数组长度的75%,将会引发扩容操作。

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

(5)扩容后,新数组的长度为原来数组的两倍。数组的默认大小与扩容倍数共同决定了数组长度永远是一个2的幂。


三、HashMap的实现原理

(1)HashMap的主干

HashMap的主干是一个Entry数组,里面存放Entry对象,每一个Entry对象包含(key,value)键值対和next指针以及对应的hash值。[jdk1.8之前用的是Entry,jdk1.8之后用的是Node,两者基本等价]

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
      .........
 }

(2)put(key,value)的过程

【1】由key计算哈希值

【2】由哈希值计算在数组中的索引

【3】如果索引处的Entry为null的话,则直接在此处插入元素。如果索引出的Entry不为null的话,通过循环不断遍历链表查找是否有相同哈希值的key,如果有,再比较两个key的是否相同,当哈希值与key都相同时,则认为是同一个Entry对象并覆盖原对象的value值。当哈希值相同而key不相同时,则认为不是同一个Entry对象,那么在链表尾部新增元素。[jdk1.8之前插入链表头部,jdk1.8之后插入链表尾部]

当索引位置相同的key超过8个时,即链表长度大于8时,jdk1.8会将此链表转化为红黑树。


(3)get(key)的过程

【1】由key计算哈希值

【2】由哈希值计算在数组中的索引

【3】循环遍历链表,如果有某一个Entry的key与哈希值与搜索的key、哈希值都相同的话,则取出此key对应的value。


(4)扩容的过程

当数组中已经存储的元素个数大于数组长度的负载因子倍数时,将会引发扩容操作。

【1】创建一个长度为原来数组长度两倍的新数组。

【2】重新对原数组中的Entry对象进行哈希运算,以确定他们各自在新数组中的新位置。

当然扩容的过程也会有很多问题,比如在多线程的情况下,多个线程同时对数组进行扩容时,有可能会造成条件竞争,就会发生意料之外的结果。因此在多线程的情况下,还是得使用线程安全的HashMap,比如ConcurrentHashMap,或者是经过Collections.synchronized(HashMap<K,V>)封装后的HashMap。


四,总结

HashMap可以用在缓存处理,动态规划中的备忘录等,需要注意的是,HashMap不是线程安全的。

碍于博主才疏学浅,谈到的HashMap原理非常的粗浅,博主定会在日后的学习与工作中,不断的完善博文,努力提高博客的水准。

相关标签: HashMap