jdk1.7 -＞ jdk 1.8 -＞ jdk 17 HashMap 源码剖析

落日映苍穹つ 2024-02-20 08:53 81阅读 0赞

JDK7（7 U80）比较靠近8的版本。

HashMap<String,Integer> map = new HashMap<>();

创建一个HashMap对象，首先调用构造器HashMap();

public HashMap() {
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        }

在构造器中调用HashMap(int initialCapacity, float loadFactor）构造方法进行初始化；

其中initialCapacity是初始容量，loadFactor 是影响因子。

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;
            threshold = initialCapacity;
            init();
        }

// 初始化容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 初始影响因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

完成上述操作后创建对象的操作就完成了，可以看到并没有创建Entry数组(JDK7中维护的是一个Entry数组，等到8的时候就改名为Node)。

接着向map中put()看看如何执行

map.put("AA",12);

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }
    
            // 1，当table为空时,即当创建map后第一次插入时，调用inflateTable(threshold)创建entry数组
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
           // threshold 在上文创建map对象时，将initialCapacity赋值给了threshold
    
           
            private void inflateTable(int toSize) {
                // Find a power of 2 >= toSize
                // 返回创建数组的大小
                int capacity = roundUpToPowerOf2(toSize);
    
                // 
                threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
                table = new Entry[capacity];
                initHashSeedAsNeeded(capacity);
            }
    
            private static int roundUpToPowerOf2(int number) {
                // assert number >= 0 : "number must be non-negative";
                return number >= MAXIMUM_CAPACITY
                        ? MAXIMUM_CAPACITY
                        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
            }
    ```
    
    ```java
            // 当所传的key值是空时，调用putForNullKey(value)方法，将key为空的entry对象放在数组的最头部。如果头部有数据，则往下一个找，直到找到一个为空的位置，或者找到一个key为null的更换value值。
    
            if (key == null)
                return putForNullKey(value);
    ```
    
    ```java
    1,根据key1.hashCode()计算出key1的哈希值1，在根据hash()算出哈希值2 hash，在根据哈希值2和算法算出key1要插入数组的下标i。
            int hash = hash(key);
            int i = indexFor(hash, table.length);
        
    2，若key1要插入的数组位置i没有元素，直接插入
        若有数据，则比较两个key的哈希2的值，若相等，比较key1==key 或者比较 key1.equals(k) 若符合条件就替换value值
                                       若一直没找到一样的就添加(key1,value)
        
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        
        
    ```

总结：

添加/修改过程：

将（key1,value1）添加到当前的map中

1.1首先，需要调用key1所在类的hashCode()方法，计算key1对应的哈希值1，此哈希值1经过某种（hash()）之后，得到哈希值2.哈希值2再经过某种算法（indexFor()）之后就确定了（key1,value1）在数组种的索引位置i --------> 情况A

1.2 如果此索引位置i的数组上有元素（key2,value2）,则需要比较key和key2的哈希值 --->哈希冲突

2.1 如果key1的哈希值2与key2的哈希值2不相同，则（key1,value1）添加成功。------->情况B

2.2 如果key1的哈希值与key2的哈希值2相同，则需要继续比较key1与key2的equals（）。要调用key1所在类的equals(),将key2作为参数传递进去

3.1. 调用equals(),返回false:则（key1,value1）添加成功。------->情况B

3.2 调用equals(),返回true:则认为key1和key2是相同的。默认情况下，value1替换原有的values2。

情况A 放到数组的i位置

情况B

jdk8 与 jdk 7 的不同之处。

![9aa3373305a64664bed4bcfb2431037a.png][]

jdk8源码

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);
        }
    
        /**
         * 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);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
    
    
      public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
        /**
         * Implements Map.put and related methods.
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        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;
            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;
        }

jdk17 源码

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);
        }
    
        /**
         * Constructs an empty {@code HashMap} 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);
        }
    
        /**
         * Constructs an empty {@code HashMap} with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
        /**
         * Constructs a new {@code HashMap} with the same mappings as the
         * specified {@code Map}.  The {@code HashMap} is created with
         * default load factor (0.75) and an initial capacity sufficient to
         * hold the mappings in the specified {@code Map}.
         *
         * @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);
        }    
    
    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;
            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;
        }

[9aa3373305a64664bed4bcfb2431037a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/d1a25d0907f14a5da3502b584c443e35.png

发表评论取消回复

表情：

评论列表（有 0 条评论，81人围观）

还没有评论，来说两句吧...

相关阅读

相关 jdk1.7 -＞ jdk 1.8 -＞ jdk 17 HashMap 源码剖析

JDK7（7 U80）比较靠近8的版本。 HashMap<String,Integer> map = new HashMap<>(); 创建一个HashMap对象，

落日映苍穹つ/ 2024年02月20日 08:53/ 0 赞/ 82 阅读

相关 CentOS安装JDK17

目录 1、卸载系统自带安装包： 2、安装需要的jdk版本：编辑 -------------------- 1、卸载系统自带安装包：通过命令查看系统已安装的j

迷南。/ 2024年02月18日 11:05/ 0 赞/ 101 阅读

相关 idea中切换JDK8、JDK11、JDK17

有时候，我们可能需要在不同的Java版本中去测试或者查看源码，idea可以让我们修改Java的版本。前提：你必须下载安装好对应的Java版本，可参考文章【windows下切

我就是我/ 2024年02月05日 20:22/ 0 赞/ 84 阅读

相关 windows下切换JDK8、JDK11、JDK17

问题背景：需要同时使用不同版本的JDK进行开发和运行，可通过下述操作改变JDK版本。一、java分类以及JDK、JRE、JVM的联系 1、JAVA分类 JA

超、凢脫俗/ 2024年02月05日 18:31/ 0 赞/ 75 阅读

相关 JDK8-JDK17新特性总结

前言：最近写项目用到了Spring3.0，JDK8不行了，一看原来JDK已经更新到了22了，下面是我总结的一些新特性具体可以参考：[openjdk.org/projects/

女爷i/ 2023年10月13日 09:29/ 0 赞/ 96 阅读

相关从jdk8升级到jdk17

文章目录写在前面 1、JDK17的安装与java环境变量 1.1、第一种：把jdk1.8更换为jdk17 1.2、第二种jdk1.

悠悠/ 2023年10月08日 17:04/ 0 赞/ 73 阅读

相关 JDK17会代替JDK8吗？

俗话说：“它发认它发，我用Java8”。但是随着Spring 6.0以及SpringBoot 3.0的发布，JDK17似乎大有取代JDK8的趋势了。 > Spring B

我不是女神ヾ/ 2023年09月25日 18:42/ 0 赞/ 84 阅读

相关 JDK17新特性

JDK17和JDK11一样也是长支持（LTS）的java版本，其带来了14项JEP(JDK增强建议）更新。同时，最新的JDK更快，高吞吐量垃圾回收器比低延迟垃圾回收器更快。

- 日理万妓/ 2023年09月24日 23:58/ 0 赞/ 256 阅读

相关 JDK8HashMap源码

> 进入这篇文章之前，我想清楚的说一说怎么去理解`HashMap`源码。它先是使用的`hash`算法，那么哈希算法需要注意的那就是怎么`hash`，怎么减少冲突，怎么避免冲突。

爱被打了一巴掌/ 2023年06月18日 03:57/ 0 赞/ 25 阅读

相关 jdk源码-HashMap

AbstractMap AbstractMap是Map接口的抽象实现类，通过抽象方法`keySet()`实现了`get(key)`，`remove(key)`，`cont

雨点打透心脏的1/2处/ 2022年02月17日 02:09/ 0 赞/ 369 阅读