HashMap中的put()方法

一. HashMap底层结构

HashMap底层是由哈希表(数组),链表,红黑树构成,哈希表存储的类型是一个节点类型,哈希表默认长度为16,它不会每个位置都用,当哈希表中的元素个数大于等于负载因子(0.75)*哈希表长度就会扩容到原来的2倍

二. 底层的一些常量

三. HashMap的put()方法

当插入一个元素时,先利用hash(key)计算该元素的hash值

这是计算哈希值的具体实现,如果该对象为空哈希值为0,否则调用这个对象重写的hashCode方法在和其向右无符号右移16位做异或运算,这样做的目的是减少hash冲突

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//tab是底层的哈希表,p是要遍历链表或红黑树的一个引用,n是哈希表长度Node<K,V>[] tab; Node<K,V> p; int n, i;//如果哈希表为空或哈希表的长度位0,则调用resize()方法初始化哈希表,并将长度赋给nif ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//用(n-1)&hash来定位该元素要存放在哈希表中的哪个位置//如果该位置为空,则表示之前没有存放过元素,不存在元素重复的情况,直接放入该位置即可if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);//否则,该位置不为空,表示之前存放有元素else {//e是用来标记重复元素的Node<K,V> e; K k;//这里是判断是否是重复元素,只判断第一个位置是否是重复元素//p表示哈希表中的元素//如果两者的hash值相同且两个元素的地址相同,那么肯定是重复元素//如果两者的hash值相同,地址不同,但equals()比较的内容相同,则是重复元素if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//记录重复元素e = p;//否则如果第一个元素不是重复元素,且p的类型是红黑树结构,则调用红黑树的put方法进行插入else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//否则第一个元素不是重复元素且hash表中是链表结构//一次遍历链表后面的元素,看是否还有重复元素,有就标记,到尾部没有就插入else {for (int binCount = 0; ; ++binCount) {//判断p的下一个是不是空,并将p的下一个赋值给eif ((e = p.next) == null) {//找到链表尾部进行插入p.next = newNode(hash, key, value, null);//binCount用来记录链表中的元素个数,插入后判断链表个数//如果大于等于7(这里从0开始,其实实际个数超过8),则链表转为红黑树if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);break;}//如果当前要比较的元素(e)不是尾部元素,则判断是否是重复元素if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//e是重复元素就跳出循环p = e;//不是重复元素就将e赋值给p,相当于继续往下走去判断后面的元素}}//e不为空代表有重复元素if (e != null) { // existing mapping for keyV oldValue = e.value;//用重复元素后面出现的值替换原本的值if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();//如果哈希表中的元素大于负载因子(0.75)*哈希表长度,则哈希表进行扩容afterNodeInsertion(evict);return null;}