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

HashMap的底层实现原理基于jdk1.8

程序员文章站 2022-07-12 20:19:21
...

本文参考了知乎大佬清浅池塘和程序员小灰的文章,把两位的精华搬运过来,主要是想巩固一下自己的记忆,链接:https://zhuanlan.zhihu.com/p/28501879
https://zhuanlan.zhihu.com/p/31610616
当我们面试大厂的时候,通常都会问到这个问题,最近也在准备面试所以就着重看了下,平时工作学习还是要多看些源码,多思考的。

map有这么几中,TreeMap,HashMap,LinkedHashMap,HashTable(已被废弃),ConcurrentHashMap, HashMap,HashTable,ConcurrentHashMap是基于hash表的实现,HashMap是非线程安全的,ConcurrentHashMap是线程安全的,会锁Map的部分结构,HashTable也是线程安全的,但性能比ConcurrentHashMap查,HashTable会锁整个map对象。

HashMap是一个用于存储key-value键值对的集合,每一个键值对也叫做Entry,这些键值对(Entry)分散存储在一个数组当中,整个数组就是HashMap的主干,HashMap数组每个元素的初始值都是NUll

先来看一段代码吧

public static void main(String[] args){
	// 实例化一个HashMap,这里说一下,HashMap默认初始长度是16,并且每次扩展或手动初始化时,长度必须是2的幂(原因下面解释)
	Map<String, Object> map = new HashMap();
    // 向map中添加元素(put原理下面会讲到)
    map.put("张三key","张三value");
    map.put("李四key","李四value");
    map.put("王五key","王五value");
    map.put("赵六key","赵六value");
	
	System.out.println("map.size() : " + map.size());
	// 通过get方法获取map中“李四key”对应的value值
	System.out.println("李四key: " + map.get("李四key"));
}

执行构造函数,当我们看到new时,应该就能想到在内存中开辟了一块空间
Map<String, Object> map = new HashMap();

构造函数源码如下:
HashMap的底层实现原理基于jdk1.8
初始化了一个负载因子,负载因子默认为0.75,为啥是0.75
HashMap的底层实现原理基于jdk1.8
看到这里明白了,原来HashMap是数组,数组里的对象是Node
HashMap的底层实现原理基于jdk1.8
下面我们看看Node是什么,这里是部分源码

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;	//key,value用来存储put时的key,value
        V value;
        Node<K,V> next; //next 用来标记下一个元素,这个跟链表很像

		// Node的构造函数
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

接下来我们看看他的两个成员变量,size是map的长度,modCount用来记录修改次数
HashMap的底层实现原理基于jdk1.8
现在我们来总结一下一个HashMap对象总包含哪些东西,包含了一个Node类型的数组,一个记录长度的size,一个负载因子default_load_factor,还有一个记录修改次数的modCount

来看一下HashMap初始化的图吧
HashMap的底层实现原理基于jdk1.8
HashMap初始化好后,成员变量table数组默认为null,size默认为0,负载因子默认为0.75,往里添加元素,使用的是put()方法,我们来看下源码

public V put(K key, V value) {

	// 调用了putVal方法,key,value是传入的
    return putVal(hash(key), key, value, false, true);
}

// putVal方法的源码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
		// 放入第一个元素时,tab为空,触发resize方法
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

resize方法比较复杂,就不完全贴出来了,当放入第一个元素时,会触发resize方法的以下关键代码(当放入第一个元素时,如果底层数组还是null,系统会初始化一个长度为16的Node数组)

// 将HashMap的长度设为默认长度
newCap = DEFAULT_INITIAL_CAPACITY;

// HashMap的默认长度,“<<” 位移运算法,1<<4相当于16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 将new出来的数组返回,虽然数组长度为16,但是HashMap的逻辑长度仍然是0,这只表示他的容量为16
return newTab;

接着看图
HashMap的底层实现原理基于jdk1.8
继续看putVal的方法
HashMap的底层实现原理基于jdk1.8

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

这段代码看着比较费劲,可以重写下

i = (n - 1) & hash;  // hash是传过来的,n是底层数组的长度,用&运算符计算出i的值
p = tab[i];  //从数组中取元素
if(p == null){ 
// 如果这个元素为null,用key,value构造一个Node对象放入数组下标为i的位置
	tab[i] = new Node(hash,key,value,null);
}

hash值是key的hashCode方法与HashMap提供的hash()方法共同计算出来的记过,其中n是数组的长度,目前这个数组的长度为16,不管这个hash值是多少,经过(n-1) & hash计算出阿里的值一定在n-1之间,用这个i作为下标,去取值,如果为null,创建一个Node放到数组下标为i的位置。

hash部分的源码

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

继续添加元素,李四,王五,赵六一切正常,key:“李四”经过(n-1)&hash算出来的数组下标为1,王五为7,赵六为9,如图:
HashMap的底层实现原理基于jdk1.8
继续添加“孙七”,通过(n-1)&hash计算“孙七”这个key时,计算出来的下标值是1,而数组下标1这个位置已经被“李四”占了,产生了冲突,下面我们看看HashMap是怎么解决冲突的

HashMap的底层实现原理基于jdk1.8
上图红框里就是冲突的处理逻辑,这一句是关键

  p.next = newNode(hash, key, value, null);

也就是说new一个新的Node对象,并把当前Node的next引用指向该对象,也就是说原来该位置上只有一个元素对象,现在转成了单链表,接着看图
HashMap的底层实现原理基于jdk1.8
红框中海油两行比较重要的代码

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      treeifyBin(tab, hash);

// 可以看下TREEIFY_THRESHOLD的值
static final int TREEIFY_THRESHOLD = 8;

当链表长度到8时,将链表转化为红黑树来处理,接着看图
HashMap的底层实现原理基于jdk1.8
在jdk1.7及以前的版本中,HashMap中没有红黑树的实现,在jdk1.8中加入了红黑树是为了防止哈希表碰撞共计,当链表长度为8时及时转为红黑树,提高map的效率。

这里来说下为啥HashMap数组的长度应该为16或2的幂,而不是10或者其他值

i = (n - 1) & hash
当长度不是16或2的幂的时候,有的index结果出现的几率会更大,而有些index永远不会出现,不符合hash算法均匀分布的原则。

如果长度为16或2的幂,length-1的值是所有二进制位全为1,这种情况下,index的结果就等同于HashCode后几位的值,只要输入的hashCode本身分布均匀,hash算法的结果就是均匀的。
详细的解释大家可以看程序员小灰的文章,奉上连接:
https://zhuanlan.zhihu.com/p/31610616

让我们来假设下面试场景

面试官:你能说说Java的常用数据结构-HashMap的底层实现原理么?
答: HashMap是由key,value键值对 数组组成的,默认长度为16,也可以自己设置,可以通过put方法来存放元素,get方法获取元素
put方法,根据key 的hash值来计算该key,value在数组中的index,假设我们存储key为a的元素,hash(a)的值为1,那么就会把她存储在index=1的位置,接着存储key为b的元素,我们假设hash(b)的值也为1,index重复后,该位置会存储链表,将b插入到单向链表的头元素,并头节点的next指针指向a,当链表长度达到8时,在jdk8中又会转为红黑树,来提高map存储和读取的效率;
get方法,根据key的hash值为来计算index,从数组中获取元素,如果该元素存储的就是该key,value,那么取出,如果是链表则查看头元素是不是,如果不是就根据next向下寻找,链表没找到的话,根据红黑树的规则来找(左节点一律小于父节点,右节点一律大于父节点,节点为红色,黑色,不能有连续的红色,红色节点的子节点都为黑色,任一节点到其叶子节点的路径上黑色节点的数量一样)。

面试官:hashMap的默认长度为什么是16
答:HashMap的默认长度为16,而且我们一般建议如果设置长度的话设为2的幂次方,原因是len-1的所有二进制位全为1,这种情况下hash(key) &(len-1) 的结果等同于HashCode的后几位,只要输入的hashCode均匀些,index就会均匀些,而其他值就有可能会出现有的index出现的几率大,有的几乎不出现;

面试官:说下高并发下HashMap可能存在哪些问题吧?
答:哇,这个超纲了,等我看了程序员小灰的文章再来回答吧。。。
面试官:嗯???