• 【JavaSE】Map接口--深入源码解读HashMap与HashTable


    💁 个人主页:黄小黄的博客主页
    ❤️ 支持我:👍 点赞 🌷 收藏 🤘关注
    🎏 格言:All miracles start from sometime somewhere, make it right now.
    本文来自专栏:JavaSE从入门到精通
    在这里插入图片描述


    1 Map接口

    1.1 Map接口简介及说明

    相较于前面所学的Set接口,Map接口的元素也是由k-v键值对组成的,只不过在Set接口中,value使用的是present常量进行占位。

    Map接口常见的实现类如下图所示:
    在这里插入图片描述
    🐰 Map接口的说明:

    1. Map与Collection并列存在。用于保存具有映射关系的数据:key-value;
    2. Map中的key与value可以是任何引用数据类型,会封装到HashMap$Node对象中;
    3. Map中的key不重复,原理与之前分析的Set源码相同,不再赘述;
    4. Map中的value可以重复;
    5. Map中的key、value都可以为null,但是key只能有一个为null;
    6. 常用String作为Map的key;
    7. key与value存在着单向一对一关系,可以通过key找到对应的value。

    需要特别注意的是,在Map中如果key相同,则会将相应的value进行更新, 具体案例如下:

    import java.util.HashMap;
    import java.util.Map;
    
    public class MapTest01 {
        public static void main(String[] args) {
            Map map = new HashMap();
            map.put("nezuko", "祢豆子");
            map.put("temp1", "祢豆子");
            map.put("temp2", "祢豆子");
            map.put("nezuko", "黄小黄");
            System.out.println(map);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    在这里插入图片描述

    当我们对上述代码进行debug,追进源码,可以得到如下 重要结论:

    1. k-v 最后的存在形式为 HashMap$Node node = newNode(hash,key,value,null);
    2. k-v 为了方便程序员的遍历,还会创建一个 EntrySet 集合,该集合存放的元素类型为 Entry,即 transient Set> entrySet;
    3. 虽然在 entrySet 中,定义的类型是 Map.Entry,但是实际上存放的是 HashMap $ Node ,因为,HashMap$Node implement Map.Entry。

    1.2 Map接口的常用方法

    方法名作用
    put(K,V)添加键值对
    remove()根据键值删除映射关系
    get()根据键值获取值
    size()获取元素个数
    isEmpty()判断个数是否为0
    clear()清除k-v
    containsKey()查找键是否存在
    keySet()获取所有的键
    entrySet()获取所有的关系k-v
    values()获取所有的值

    1.3 Map的常用遍历方式

    存储案例代码如下:

    import java.util.HashMap;
    import java.util.Map;
    
    
    public class MapTest01 {
        public static void main(String[] args) {
            Map map = new HashMap();
            map.put("红色", "red");
            map.put("绿色", "green");
            map.put("黑色", "black");
            map.put(null, "未知");
            map.put("未知", null);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    1️⃣ 先取出所有的 key,然后通过 key 取值:

    		Set keySet = map.keySet();
            // (1)for
            for (Object key :
                    keySet) {
                System.out.println(key + "-" + map.get(key));
            }
            // (2)迭代器
            Iterator iterator = keySet.iterator();
            while (iterator.hasNext()){
                Object key = iterator.next();
                System.out.println(key + "-" + map.get(key));
            }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    2️⃣ 直接取出所有的 values:

            Collection values = map.values();
            //  (1)for
            for (Object value :
                    values) {
                System.out.println(value);
            }
            //  (2)迭代器
            Iterator iterator = values.iterator();
            while (iterator.hasNext()){
                Object value = iterator.next();
                System.out.println(value);
            }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    3️⃣ 通过EntrySet 来获取 k-v:

            Set entrySet = map.entrySet();
            //  (1)for
            for (Object entry:
                 entrySet) {
                // 将 entry 转成 Map.Entry
                Map.Entry m = (Map.Entry)entry;
                System.out.println(m.getKey() + "-" + m.getValue());
            }
            //  (2)迭代器
            Iterator iterator = entrySet.iterator();
            while (iterator.hasNext()){
                Object next = iterator.next();
                Map.Entry m = (Map.Entry)next;
                System.out.println(m.getKey() + "-" + m.getValue());
            }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2 HashMap

    2.1 HashMap简介

    🐰说明:

    1. 如果添加相同的key,则会覆盖原来的k-v,等同于修改;
    2. 与HashSet一样,不保证映射的顺序,底层的由hash表的方式存储;
    3. HashMap没有实现同步,线程不安全;
    4. jdk7.0的hashmap底层(数组+链表),jdk8.0底层(数组+链表+红黑树)。

    2.2 HashMap底层机制与源码解读

    🦁 hashmap结构示意图:
    在这里插入图片描述

    🐰 扩容机制:

    1. HashMap底层维护了Node类型的数组table,默认为null;
    2. 当创建的对象的时候,加载因子(loadfactor)初始化为0.75;
    3. 当添加key-val时,通过key的哈希值得到在table的索引,然后判断该索引处是否有元素。如果没有元素则直接添加,如果有元素,则继续判断该元素的key是否与准备添加的key相等。如果相等,则将val进行替换;如果不相等,需要判断该位置是树结构还是链表结构,进行相应的添加元素处理。如果添加时发现容量不够,则需要进行扩容;
    4. 第1次添加,table初始容量扩容为16,临界值(threshold)为12;
    5. 以后需要扩容的时候,每次将table扩容为原来大小的2倍,临界值为原来的2倍,即24,以此类推;
    6. 在Java8 中,如果一条链表的元素个数超过 TREEIFY_THRESHOLD(默认是8),并且table的大小>= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树);
    7. 若已经树化,当树的结点 < 8,则会通过剪枝重新变回链表。

    🐴 源码解读:

    下面我们通过debug该段代码,追进jdk源码,来进行源码解读:

    import java.util.HashMap;
    
    /**
     * @author 兴趣使然黄小黄
     * @version 1.0
     */
    public class HashMapTest {
        public static void main(String[] args) {
            HashMap hashMap = new HashMap();
            hashMap.put("java", 10);
            hashMap.put("python", 10);
            hashMap.put("java", 20);
        }
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    1️⃣ 执行构造器 new HashMap() ,初始化了加载因子loadFactor = 0.75,并且table表 HashMap $ Node[] table = null;
    在这里插入图片描述
    2️⃣执行第一个put方法,在put方法内部会调用 hash 方法,计算key的hash值,在HashSet源码解读中已经阐述,这里不再赘述:
    在这里插入图片描述

    3️⃣重要的一步, 执行 putVal 方法,源码及步骤解析(注释)如下:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //如果底层的 table 数组为 null,或者 length = 0,就扩容到16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //取出hash值对应的table的索引位置的Node
            //如果为null,就直接把加入的k-v创建成一个Node,加入该位置
            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;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    4️⃣ 执行第二个put时,重复了上述步骤,索引可能位置不同,最终结果是创建了一个新的结点,加入到了HashMap中;

    5️⃣ 关键来啦! 执行第三个put时,由于key值相同,因此通过hash算法求得的hash值相同,所在hash表的索引位置也相同,因此,就会进入源码的else代码块 (与该索引位置上的所有结点逐个比较,如果key相同,则替换val,否则,直接添加), 具体看源码注释:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //如果底层的 table 数组为 null,或者 length = 0,就扩容到16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //取出hash值对应的table的索引位置的Node
            //如果为null,就直接把加入的k-v创建成一个Node,加入该位置
            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 &&  //如果table的索引位置的key的hash值与新的key索引位置的hash值相同
                //并且满足现有的key与添加的key是同一对象 或者 equals返回真
                //就认为不能加入
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)  //如果当前table已有的Node已经是红黑树,则按照树的逻辑操作
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                //如果找到的结点后面是链表,则逐个结点比较
                    for (int binCount = 0; ; ++binCount) {  //死循环
                        if ((e = p.next) == null) {  //如果整个链表没有与它相同的key,就加在该链表的最后
                            p.next = newNode(hash, key, value, null);
                            //加入后判断是否到达8个,如果到达,则进行树化
                            //调用 treeifyBin 方法进行红黑树的转化
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&  //如果发现有相同的,就不添加,break,简单替换val
                            ((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;  //替换,key
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;  //每增加一个Node,就size++
            if (++size > threshold)  //size大于临界值,就进行扩容
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    6️⃣ 树化的要求, table表为空,或者大小未到达64,就暂时不树化,先进行扩容:
    在这里插入图片描述


    3 HashTable

    3.1 HashTable简介

    🐰说明:

    1. 存放的元素依然是键值对 k-v;
    2. hashtable的键和值都不能为null;
    3. HashTable是线程安全的;
    4. HashTable使用的方法基本上和HashMap一样。

    3.2 HashTable扩容机制与源码解读

    🐰 底层机制解读:

    1. 底层有数组 HashTable $ Entry[] 初始化大小为11;
    2. 临界值threshold = 8 = 11 * 0.75;
    3. 扩容:按照HashTable扩容机制进行扩容,首次扩容情况为 count > 8。

    🦁 扩容源码解读:
    对下面代码进行debug,断点打在第9个put前:

    import java.util.Hashtable;
    
    /**
     * @author 兴趣使然黄小黄
     * @version 1.0
     */
    public class HashTableTest {
        public static void main(String[] args) {
            Hashtable hashtable = new Hashtable();
            hashtable.put("java1", 100);
            hashtable.put("java2", 100);
            hashtable.put("java3", 100);
            hashtable.put("java4", 100);
            hashtable.put("java5", 100);
            hashtable.put("java6", 100);
            hashtable.put("java7", 100);
            hashtable.put("java8", 100);
            hashtable.put("java9", 100);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    1️⃣ 在debug开始时,HashTable容量已经为11,此时,table里有8个元素:
    在这里插入图片描述

    2️⃣先进行装箱,然后判断put的值是否为null,如果为null就抛出异常:
    在这里插入图片描述

    3️⃣ 对于中间求hash值的步骤我们暂时不关心,追进addEntry方法,该法方法用于添加 k-v 封装到 Entry。在该方法中,当count大于等于临界值时,就会调用rehash方法进行扩容。
    在这里插入图片描述

    4️⃣ 追进rehash方法,发现,扩容后的容量 newCapacity = (oldCapacity << 1) + 1,相当于原来的容量✖ 2 + 1,相关源码如下:

        protected void rehash() {
            int oldCapacity = table.length;
            Entry<?,?>[] oldMap = table;
    
            // overflow-conscious code
            int newCapacity = (oldCapacity << 1) + 1;
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                if (oldCapacity == MAX_ARRAY_SIZE)
                    // Keep running with MAX_ARRAY_SIZE buckets
                    return;
                newCapacity = MAX_ARRAY_SIZE;
            }
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
            modCount++;
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            table = newMap;
    
            for (int i = oldCapacity ; i-- > 0 ;) {
                for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                    Entry<K,V> e = old;
                    old = old.next;
    
                    int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                    e.next = (Entry<K,V>)newMap[index];
                    newMap[index] = e;
                }
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    4 小结

    • HashTable 与 HashMap 简单对比:
    版本线程安全效率允许null键null值
    HashMap1.2不安全允许
    HashTable1.0安全较低不允许

    写在最后

    🌟以上便是本文的全部内容啦,后续内容将会持续免费更新,如果文章对你有所帮助,麻烦动动小手点个赞 + 关注,非常感谢 ❤️ ❤️ ❤️ !
    如果有问题,欢迎私信或者评论区!
    在这里插入图片描述

    共勉:“你间歇性的努力和蒙混过日子,都是对之前努力的清零。”
    在这里插入图片描述

  • 相关阅读:
    【云原生|Docker】Docker镜像操作
    tiup dm deploy
    Mysql学习(一)之Mysql的介绍和安装
    Golang 基础之基础语法梳理 (三)
    天天写业务代码,我给撸了一个业务处理框架
    【图像分类】Efficientnet的学习
    每一次只可跨1阶或2阶,爬100阶的楼梯可有多少种走法题解
    使用kaggle运行机器学习代码的几点注意事项(超重要!!!)
    ASF之InSAR云计算(成果包括DEM、缠绕影像、形变图)
    Qt 二维码生成与识别
  • 原文地址:https://blog.csdn.net/m0_60353039/article/details/126229259