【Java源码分析】HashMap分析

男娘i 2022-05-26 08:15 249阅读 0赞

听说大牛们都看过HashMap的源码，今天闲来无事，也想学习下前辈们，硬着头皮看了一段。只能说，我道行太浅，看的我真的难受，先记录下一部分，以后慢慢学习补充。

# 1. 类注释 #

在类注释上，官方对HashMap的介绍还是非常受用的。

HashMap是允许null的key和value的，不保证有序，是线程不安全的

get和put是花费常量时间， 假设是分散在各个桶中的，初始容量capacity和负载因子load factor影响性能，  
    初始容量不要太高，负载因子不要太低  
   
    capacity表示桶的数量

load factor表示HashMap允许多满

如果hashmap中的entry超过了 capacity和load factor的乘积，那么hashmap将会rehashed，也就是触发扩容机制

默认值load factor (.75) 是在时间和空间上权衡后设置的

如果我们要存储很多的entry,最好设置一个足够大的catacity

hash冲突影响性能

remove元素的时候请使用iterator

不要依赖ConcurrentModificationException编程

# 2.变量 #

1.成员变量

/**
         * 默认长度16，这不是巧合
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * 最大容量
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * 负载因子，表示我们实际可以用的空间是0.75，也就是3/4；
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /**
         *树形和列表的阈值，该值必须大于2，最好大于8，大于该值时，该槽（bucket）内由链式改为树形
         */
        static final int TREEIFY_THRESHOLD = 8;
    
        /**
         * 由树形转换回链式的阈值，应该小于treeify_threshold,最大为6
         */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /**
         * 转换树形后表格最小容量，至少是treeify_threshold的四倍 
         */
        static final int MIN_TREEIFY_CAPACITY = 64;
    
        /* ---------------- Fields -------------- */
    
    
        /**
         * 第一次使用的时候初始化，可以调整大小，长度总是2的幂，可以是0
         */
        transient Node<K,V>[] table;
    
    
        /**
         * 注意，AbstractMap域用于keyset()和values()。
         */
        transient Set<Entry<K,V>> entrySet;
    
    
        /**
         * 键值对的数量
         */
        transient int size;
    
    
        /**
         * 操作次数
         */
        transient int modCount;
    
    
        /**
         * 下一次重新分配空间resize()时table数组的大小 
         */
        
        int threshold;
    
    
        /**
         * 负载因子
         */
        final float loadFactor;

2.内部类

/**
         *  基本哈希容器结点Node（实现Map.Entry接口） 
         */
        static class Node<K,V> implements Entry<K,V> {
            final int hash;      //不可变的哈希值————由关键字key得来 
            final K key;        //关键字不可变   
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            public final int hashCode() {   //Entry对象的hashCode()由关键字key的hashCode()与值value的hashCode()做异或运算  
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {      //对象相同或同类型且key-value均相同，则返回true
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Entry<?,?> e = (Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

# 3.构造函数 #

构造函数我们就不细说了。

/**
         *
         * @param  初始化容量
         * @param  负载因子
         */
        public HashMap(int initialCapacity, float loadFactor) {}
    
    /**
         * @param  初始化容量
         */
        public HashMap(int initialCapacity) {}
    
     /**
         * 空参构造
         */
        public HashMap() {}
        //参数是Map
        public HashMap(Map<? extends K, ? extends V> m) {}

# 4. put方法 #

我们主要讲一下这个我们最常用的方法之一，put方法。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;        //第一次放值的时候初始化桶，resize方法有初始化和扩容的作用
            if ((p = tab[i = (n - 1) & hash]) == null)         //这里与操作相当于取余（在数组里放值），这也是为什么数组大小必须是2的N次幂的原因（默认大小是16，16-1=15=01111，假设数组大小不是2的n次幂，比如说是15，那么n=14=01110，与操作的时候最低位无论如何结果都是0，就会有错误（相当于缩小了空间））。这里也是高位变低位的原因（充分hash，减少hash碰撞）
                tab[i] = newNode(hash, key, value, null);//如果当前位置是空的，就存入
            else {          //当前位置不是空
                Node<K,V> e; K k;
                if (p.hash == hash &&           //hash值相等并且key相等，那么就是覆盖操作
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;      //覆盖操作，404行返回旧值
                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);   //如果链表下一个位置是空，直接插入？？？ 没错，看398行代码，已经在不等于空的时候做过判断了
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st        //如果到TREEIFY_THRESHOLD临界值，就要转成红黑树了（在判断第8个是否为空的时候，这里的binCount等于7，因为是从0开始的吗）
                                treeifyBin(tab, hash);
                            break;          //注意这个break语句，是在if条件之外的
                        }
                        if (e.hash == hash &&           //如果是不等于null的时候，判断hash和key是否是相等的，如果相等就跳出（该行是398行）
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;                 //这个break跳到了404行，（跳出是因为相等，需要执行覆盖操作）
                        p = e;                  //如果不想等，p指向下一个
                    }
                }
                if (e != null) { // existing mapping for key  //说明想要进行覆盖操作，返回原来的值（该行为404行，覆盖操作统一处理）
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)     //如果当前容量超过了threshold，那么就进行扩容处理
                resize();
            afterNodeInsertion(evict);
            return null;
        }

# 5. 扰动函数 #

扰动函数：

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

![Center][]

HashMap的hash方法是key的hashCode的低16位与高16位做与运算。也叫做扰动函数

为什么要有扰动函数？扰动函数有什么用？

从HashMap源码中我们可以知道。key的hashCode是一个32位的int数据，范围这么广，我们如何放到hashMap中的桶中呢，

源码中做了个把hash值和数组长度减1进行与的操作（ 相当于是取余的动作）

重点来了：注意如果仅仅是一个hashCode值来进行与操作的话。我们假设有两个key，他们的低四位（我们暂且假定桶的数量是默认大小16）碰撞的几率非常大（1/16 \* 1/ 16）。那么如果是扰动之后低位附带了高位的特征（异或），加大了低位的不确定性，从而减少了低位的碰撞几率，这也是经过试验证明的。

Peter Lawley的一篇专栏文章《An introduction to optimising a hashing strategy》里的的一个实验：他随机选取了352个字符串，在他们散列值完全没有冲突的前提下，对它们做低位掩码，取数组下标。    结果显示，当HashMap数组长度为512的时候，也就是用掩码取低9位的时候，在没有扰动函数的情况下，发生了103次碰撞，接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%。

# 7. 待补充（resize扩容） #

[Center]: /images/20220526/6bbb2754b3e1475aa1648a31d54388ea.png