HashMap源码笔记(一)

港控/mmm° 2022-11-29 12:39 205阅读 0赞

小白一个多多关照，有写的不对的地方可以评论提出，共同进步。

--------------------

### 文章目录 ###

*  前言
 *  一、HashMap的继承关系
 *  二、HashMap参数
 *  2.一些方法
 *  HashMap的构造函数

--------------------

# 前言 #

HashMap是在面试的时候被经常问到的，而且在工作当中也是不可缺少的存在。我在上班划水的时候看了看HashMap的源码，发现还是有很多看不懂（小白一个）就在网上百度查了下，总结总结。

--------------------

# 一、HashMap的继承关系 #

![在这里插入图片描述][20200820214745790.png_pic_center]  
看源码可以看出HashMap继承了AbstractMap 实现了Map、Cloneable、Serializable 接口。所以HashMap可以实现序列化和克隆。

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
        }

# 二、HashMap参数 #

这表示默认初始化长度为16 ，这是 1<< 4 就是 1\* 2^4 所以是16.。

/*
         * The default initial capacity - MUST be a power of two.
         	默认初始化容量-必须为2的幂次方:为啥是2的幂次方呢? 
         */
      static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

这是因为在java8中在链表分布时进行了优化运算

static int indexFor(int h, int length) {
        
    
            return h & (length-1);
    
     }

这样就是按位与运算,当转化为二进制后进行对比,当同一位置都是为1时就是1,其他的都是0。  
**举个例子: 3&8  
0000 0011  
0000 1000 结果就是: 0000 0000 得到的结果就是0**

这样就知道了为啥必须是二进制了吧,因为如果不是必须是2的幂次方的时候只有第一个是1 后面全部是0,如果这个1和对比的没有对应上那么得到的结果就是0,这样0的位置上就会有很多的元素。但是我们减一后就转换成十六位二禁止全部都是1这样再按位与运算的话就会减少元素的碰撞了。

**总而言之一句话就是为了减少元素碰撞，所以就是必须是2的幂次方。**

/**
         * The maximum capacity, used if a higher value is implicitly specified
         * by either of the constructors with arguments.
         * MUST be a power of two <= 1<<30.
         	最大容量，当初始化容量的时候，如果大于这个数，
         	则就使用这个数。而且我发现这个最大容量就是int类型正数的最大值。
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;

/**
         * The load factor used when none specified in constructor.
         * 在构造函数未指定的情况下使用的加载因子。
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子是0.75，默认初始化长度是16，当16*0.75 = 12 的时候就会自动扩容，扩容大小是原来长度的2倍，对我好像记得hashTable扩容的长度是原来的2+1倍。

/**
         * The bin count threshold for using a tree rather than list for a
         * bin.  Bins are converted to trees when adding an element to a
         * bin with at least this many nodes. The value must be greater
         * than 2 and should be at least 8 to mesh with assumptions in
         * tree removal about conversion back to plain bins upon
         * shrinkage.
         * 
         */
        static final int TREEIFY_THRESHOLD = 8;

这个是单向链表转换为红黑树的阈值，当阈值为8的时候就会转换为红黑树。我曾经想过为啥不直接就是红黑树呢，为啥要用链表呢。看了源码后才知道红黑树的节点是链表节点的2倍，这些运算好像还是经过时间和空间的相互运算得出来的结果。  
**那么为什么是8呢**？  
我在下面的注释中找到了答案：

Because TreeNodes are about twice the size of regular nodes, we
         * use them only when bins contain enough nodes to warrant use
         * (see TREEIFY_THRESHOLD). And when they become too small (due to
         * removal or resizing) they are converted back to plain bins.  In
         * usages with well-distributed user hashCodes, tree bins are
         * rarely used.  Ideally, under random hashCodes, the frequency of
         * nodes in bins follows a Poisson distribution
         * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
         * parameter of about 0.5 on average for the default resizing
         * threshold of 0.75, although with a large variance because of
         * resizing granularity. Ignoring variance, the expected
         * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
         * factorial(k)). The first values are:
         *
         * 0:    0.60653066
         * 1:    0.30326533
         * 2:    0.07581633
         * 3:    0.01263606
         * 4:    0.00157952
         * 5:    0.00015795
         * 6:    0.00001316
         * 7:    0.00000094
         * 8:    0.00000006
         * more: less than 1 in ten million

这就是链表长度的概率：显而易见就是当为8的时候是蛮小的，虽然7也是很小，但是7被作为了用作过度点这样只有8是最好的了，所以选8，当然了这是JDK经过算法得出来的结果。具体怎么得出我就不知道了。

--------------------

/**
         * The bin count threshold for untreeifying a (split) bin during a
         * resize operation. Should be less than TREEIFY_THRESHOLD, and at
         * most 6 to mesh with shrinkage detection under removal.
         */
        static final int UNTREEIFY_THRESHOLD = 6;

**这是红黑树转换为链表的阈值。在网上看到很多问为啥不是7呢，为什么偏偏是6呢，我看到很多的评论就总结下：**

*  链表和红黑树转化需要一个过渡点，如果是7的话，在极端情况下进行put和remove的时候回频繁的进行链表和红黑树的转换，这样是比较耗费时间和浪费资源的。

--------------------

/**
         * The smallest table capacity for which bins may be treeified.
         * (Otherwise the table is resized if too many nodes in a bin.)
         * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
         * between resizing and treeification thresholds.
         * 将链表转换为红黑树的最小阈值，如果bin(链表)的节点过多，则会进行扩容，扩容到 4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值发生冲突。 
         */
        static final int MIN_TREEIFY_CAPACITY = 64;

--------------------

# 2.一些方法 #

/**
         * Basic hash bin node, used for most entries.  (See below for
         * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
         */
        static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            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() {
                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) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂，至于为什么这么做，后面会有详细分析。
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

这是HashMap的主干数组：Node<K,V>就是数组的每个元素节点：

*  final int hash：就是HashMap Key的hashCode值，存储到Entry上的
 *  final K key：就是key
 *  V value：就是value
 *  Node<K,V> next; Node<K,V> 存储指向下一个Entry的位置

--------------------

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

index = Key.hashCode() & (n - 1) // n是长度

如果是自己实现hash算法的话，最简单的话就是直接用hasCode对取余

index = key.hashCode() % n // n是长度

在HashMap的实现中要求n的长度为2的n次幂  
对于2的n次幂取余，可以用更加高效的方法

index = key.hasCode() & (n-1)

上面两种方法都存在一种缺陷，就是取余的计算结果对高位是无效的，只是对低位有效，当计算出来的hasCode()只有高位有变化时，取余的结果还是一样的。

例如:

int hashCode1 = 01110101
    int hasdCode2 = 01010101
    
    int index1 = 01110101 & 1111 -> 0101
    int index2 - 01010101 & 1111 -> 0101
    
    //十进制翻译
    int hashCode1 = 117
    int hashCode2 = 85
    
    int index1 = 117 % 16  -> 5
    int index2 = 85 % 16  -> 5

从上面的例子可以看出来，当key计算出来的hashCode()只有高位变化时，最终算出来的index索引就会引起hash冲突，如果冲突太多的话，HashMap的效率就会非常低下了。

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

再来看看这段代码，对key的hashCode值进行再一次计算。在java中，hashCode是32位的。

首先，对hashCode进行16位的无符号右移。

（我们的例子就假设hashCode是8位的）

int hashCode1 = 01110101 >>> 4
    --> hashCode1 = 00000111
    
    int hasCode2 = 01010101 >>> 4
    -->hasCode2 = 00000101

然后，对自身进行与或运算。

hashCode1 = 01110101 ^ 00000111
    --> hashCode1 = 01110010
    
    hashCode2 = 01010101 ^ 00000101
    --> hashCode2 = 01010000

最后，取余

hashCode1 = 01110010 & 1111 = 0010
    hashCode2 = 01010000 & 1111 = 0000

通过上面的分析，hash的再次计算能够把高位的变化影响到了低位的变化，真的很神奇啊  
一句神奇的代码，大大减少了hash冲突，牛逼！

不正之处，欢迎指正。

[这段是我在简书上看到的链接就放上去了:][Link 1]

# HashMap的构造函数 #

/**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         * 使用默认的加载因子（0.75）和 使用默认的初始化长度（16）
         */
        public HashMap() {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

--------------------

/**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and load factor.
         *
         * @param  initialCapacity the initial capacity ：初始化容量
         * @param  loadFactor      the load factor ：负载系数
         * @throws IllegalArgumentException if the initial capacity is negative ：如果传入的初始化容量为负数和负载系数为正都会抛出此异常。
         *         or the load factor is nonpositive
         */
        public HashMap(int initialCapacity, float loadFactor) {
        
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }

看代码可以看出，如果初始化长度为负数抛出异常。如果初始化长度大于最大长度，设置为最大长度（2^30）

/**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
        
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

构造一个空的HashMap默认的加载因子为0.75，如果初始化长度为负数则抛出IllegalArgumentException异常。

代码如下（示例）：

/**
         * Constructs a new <tt>HashMap</tt> with the same mappings as the
         * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
         * default load factor (0.75) and an initial capacity sufficient to
         * hold the mappings in the specified <tt>Map</tt>.
         *
         * @param   m the map whose mappings are to be placed in this map
         * @throws  NullPointerException if the specified map is null
         */
        public HashMap(Map<? extends K, ? extends V> m) {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR; // 使用默认的负载因子
            putMapEntries(m, false);
        }

创建一个HashMap的时候可以参数可以放一个HashMap如果放入的HashMap是null的话则会报空指针异常。使用默认的负载因子。

/**
         * The load factor for the hash table.
         * Hash表的加载因子
         * @serial
         */
        final float loadFactor;

/**
         * Implements Map.putAll and Map constructor
         *
         * @param m the map
         * @param evict false when initially constructing this map, else
         * true (relayed to method afterNodeInsertion).
         */
         // 把oldMap存入到new Map 中
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        
            int s = m.size(); // oldMap 的大小
            if (s > 0) {
        // size大于0的时候
            //如果HashMap没有被初始化
                if (table == null) {
         // pre-size 
                // oldMap 获取容量并向上取整。获得最大负载容量
                    float ft = ((float)s / loadFactor) + 1.0F;
                   	// 如果大于最大容量就使用最大容量，如果小于最大容量就使用最大负载容量
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                    if (t > threshold)
                        threshold = tableSizeFor(t);
                }
                else if (s > threshold)
                    resize();
                for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
        
                    K key = e.getKey();
                    V value = e.getValue();
                    putVal(hash(key), key, value, false, evict);
                }
            }
        }

/**
         * The table, initialized on first use, and resized as
         * necessary. When allocated, length is always a power of two.
         * (We also tolerate length zero in some operations to allow
         * bootstrapping mechanics that are currently not needed.)
         * 该表在首次使用时初始化，并根据需要调整大小。分配时，长度始终是2的幂。 *（我们在某些操作中也允许长度为零，以允许*当前不需要的引导机制。）
         */
        transient Node<K,V>[] table;

代码如下（示例）：

data = pd.read_csv(
        'https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
    print(data.head())

--------------------

[20200820214745790.png_pic_center]: /images/20221124/39c51bf613e84413907f45d8c2493928.png
[Link 1]: https://www.jianshu.com/p/e1d3ba0c733a