HashMap源码分析笔记

本文主要是介绍HashMap源码分析笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前提：

以下内容仅为自身理解，请辩证理解。尽信书不如无书~
为了方便自己理解，自己加入了一些定义。

索引位： hashmap的底层是数组，我称数组的0,1,2,3等的下标所对应的位置为索引位。

简述：

HashMap底层是一个数组，每个元素通过hash(key) & table.length计算的结果就是这个元素应该落入数组table的哪个索引位。

由于会出现hash冲突，也就是多个不同的元素会落入同一个索引位，为了保存这些元素，则会以链表的形式进行存储同一个索引位的元素。

在1.8中，当链表达到一定长度后会变为红黑树

变为红黑树的原因是链表的遍历是O(n)，而红黑树的遍历为O(log(n))。就读取效率而言，红黑树的效率肯定是比链表要高的。

对象的hashcode() 决定了hash冲突的程度，如果一个对象的hash冲突过高，则会导致大量对象堆积在一个索引位，这样让hash表的O(1)变为了O(log(n))或者O(n)。所以当hash冲突过高时，可以适当重写hashcode方法，当然，垃圾的hashcode写法会进行反向操作。

红黑树会进行排序，那么排序规则是根据hashcode，其次是对象的compareTo方法进行排序

1. 为什么不直接用红黑树而要先用链表？

因为TreeNode结构比Node的结构复杂，占用内存更大，所以只有一个索引位的元素达到一定个数时，才会使用链表。临界值设置在成员变量TREEIFY_THRESHOLD中，默认为8。

2.红黑树与链表的转换时机？

当一个索引位的节点超过8时，会由链表转化为红黑树。当发生移除或者扩容导致一个索引位的元素少于8个时，红黑树又会转化为链表。

3.为啥这个长度是8

嗯，这么问问题，我感觉应该会被打死。

通常情况下，均匀分布的hashcode是很少会使用到红黑树的。

源码的注释里有些，在hashCode完全随机的情况下，则元素在数组里呈现泊松分布。而落在一个索引位的概率为0.5，则8个元素落在同一个索引位的概率为0.00000006。即亿分之六的概率。

4.对象重写hashcode，hashcode与成员变量有关，如果该对象作为键已经进入HashMap，那么再修改成员变量会改变该对象的位置吗？

不会，在进入HashMap的时候会计算一次hashcode，然后会把这个值保存在节点中，在后续其他的内部方法调用时，会直接使用这个值而不是重新计算。但是，你通过get找不到了，气不气。

5.HashMap中的数结构是继承自的LinkedHashMap的内部类

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>

6.重要的成员变量

// 默认容量大小16，容量大小必须为2的倍数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// DEFAULT_LOAD_FACTOR 触发扩容阈值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// map的底层结构是数组，数组里的每个元素是链表节点或者树节点
transient Node<K,V>[] table;

// 当前table中包含多少个key-value 键值对
transient int size;

// 触发扩容的阈值
//if (++size > threshold)
//            resize();
int threshold;

// 负载因子 扩容阈值比例
final float loadFactor;

7.链表类型

// 记录了hash值，单向链表
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

8.hash算法

static final int hash(Object key) {
        int h;
				// 先计算对象的hashCode，然后再
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

int 占 4个字节， 总共32个bit位。

上面的算法：

1.先通过hashCode获得key的hash值

2.将hash值进行向右位移16位

3.将key的hash值与key的高16位进行异或运算（不同为1， 相同为0）

// 计算hash值在hash表中索引位置
i = (n - 1) & hash

从这里我们可以看到是用的hash表的长度来与hash值进行位与运算。hash表的长度一半都不会太大，那么实际上就会造成只有int的低bit位会参与位运算，高位则被忽略，这也就是为什么计算hash值时，要进行高低位异或运算了。这样可以降低hash冲突的概率。

9.解析put(key,value）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab;  // hash表
				Node<K,V> p;  // hash值对应的索引位上的元素
				int n, i;
        if ((tab = table) == null || (n = tab.length) == 0){
            // 在第一put的时候才会创建hash表
						n = (tab = resize()).length;
				}
        if ((p = tab[i = (n - 1) & hash]) == null)
						//索引位上没有元素的时候直接创建节点写入
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; // 相同hash，相同key的旧节点对象
						K k; // 
						// 索引位的第一个节点与当前节点比较
            if (p.hash == hash && 
                ((k = p.key) == key  
								|| (key != null && key.equals(k)))) 
                e = p; // 该节点赋值给e， e是用于返回对应key的旧值的
            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);
												// 这里进行减一的目的是因为 p.next是从第二个元素开始的
												// 索引是超过8个元素后开始变形
                        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;
                }
            }
						// key在table中已存在时，进行替换
            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;
    }

结论：

1.第一次put的时候才会创建hash表

if ((tab = table) == null || (n = tab.length) == 0){
            // 在第一put的时候才会创建hash表
						n = (tab = resize()).length;
				}

2.超过8个元素开始进行链表转树treeifyBin(tab, hash);

// 当binCount = 0 时，走到binCount >= TREEIFY_THRESHOLD - 1 这一步时，链表已经有2个对象了，
// 当binCount = 7时，链表应该有9个元素了，触发扩容
for (int binCount = 0; ; ++binCount)
if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
		// 这里进行减一的目的是因为 p.next是从第二个元素开始的
		// 索引是满8个元素后开始变形
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      // 链表转树  
			treeifyBin(tab, hash);
    break;
}

3.当hashMap容量大于threshold时，触发扩容
4.计算索引位时，使用位运算的原因是，性能高，相当于取模的效果。
5. 相同key进行覆盖

10 为啥每次扩容都是2的倍数呢？

2^n-1的比特位形式是啥？前面全是0 ，后面全是1

而与运算两个都为1才为1，否则为0

所以为啥用2的倍数，就是为了实现取模的效果。

长度为16的hashmap索引位计算：

(16-1) 0000 0000 0000 1111

key 0010 1010 1001 0101

位与运算 0000 0000 0000 0101

从结果中可以看到key的hash值是直接取后面的位数的，二进制取模

11 链表转树treeifyBin

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
						// 当hash表的长度小于64时，只触发扩容，不触发链表转树
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

步骤：

1.hash表的长度小于64时，只触发扩容，不触发链表转树

2.将单向链表转为以TreeNode为节点的双向链表

3. 执行 hd.treeify(tab) 将双向链表转为红黑树（不想看，等我研究研究算法再说）

12. 扩容的精髓

索引位的计算是按位与运算

比如：

容量为16 ，hash值为10

计算索引位：

容量（16-1）： 0000 0000 0000 1111

hash ： 0000 0000 0000 1010

按位与运算 ： 0000 0000 0000 1010

索引位为10

如果hash为26：

容量（16-1）： 0000 0000 0000 1111

hash ： 0000 0000 0001 1010

按位与运算 ： 0000 0000 0000 1010

此时索引也是10

当发生扩容时

容量变为32

则hash为10的索引位：

容量（32-1）： 0000 0000 0001 1111

hash ： 0000 0000 0000 1010

按位与运算 ： 0000 0000 0000 1010

索引位为10

如果hash为26：

容量（32-1）： 0000 0000 0001 1111

hash ： 0000 0000 0001 1010

按位与运算 ： 0000 0000 0001 1010

此时索引位变为16+10 = 26

这也就是为什么扩容时当(e.hash & oldCap) == 0 时 ，直接放在当钱索引链表下，

否则放在newTab[j + oldCap]链表下的原因

这里还要说明一下

容量是2的n次方，16 表示为 0000 0000 0001 0000

e.hash & oldCap == 0 说明 e.hash的二进制比特位倒数第五位一定是0，那么由16扩容到32位时

由于e.hash第五位是0，

则 索引位(32 - 1) & hash 计算：

容量（32-1） ： 0000 0000 0001 1111

第五位为0的hash ： 0001 0100 1100 1010

按位与运算 ： 0000 0000 0000 1010

同样也是只有后四位能在0,1之间变化。那么扩容前后没有变化。

如果e.hash的二进制比特位倒数第五位为1，则从16位扩容到32位时，则位运算后第五位一定为1

也就是原来计算结果1010基础上加上了2^5 = 26。

其实这也是为什么hash表每次扩容是2的倍数，因为这样做会让同一个位置上的索引最多分配到2个索引位上，减少索引位计算，也减少了多索引位冲突问题。一举多得。

这篇关于HashMap源码分析笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！