当前位置： 首页 > article >正文

HashMap底层结构和源码分析

article 2024/11/15 22:58:15

目录

HashMap底层机制

HashMap源码分析和结论

源码分析：

HashMap树化扩容触发

HashMap底层机制

1.（k,v)是一个Node实现了Map.Entry<K，V>，查看 HashMap的源码可以看到

2.jdk7.0的hashmap底层实现[数组+链表]，jdk8.0底层[数组+链表+红黑树]

HashMap源码分析和结论

 扩容机制 [和HashSet相同]

1.HashMap底层维护了Node类型的数组table，默认为null

2)当创建对象时，将加载因子(loadfactor)初始化为0.75.

3)当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key相是否等，如果相等，则直接替换val；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。

4)第1次添加，则需要扩容table容量为16，临界值(threshold)为12(16*0.75)

5)以后再扩容，则需要扩容table容量为原来的2倍(32)，临界值为原来的2倍，即24，依次类推.

6)在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8），并且table的大小>=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）

代码演示：

源码分析：

/*
HashMap源码分析
1. 执行构造器 new HashMap()
   初始化加载因子 loadfactor = 0.75
   HashMap$Node[] table = null

2. 执行put 调用 hash方法，计算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16)
    public V put(K key, V value) {//K = "java" value = 10
        return putVal(hash(key), key, value, false, true);
    }
 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数组等于空或者长度为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;//辅助变量
        // 如果table的索引位置的key的hash相同和新的key的hash值相同，
         // 并 满足(table现有的结点的key和准备添加的key是同一个对象 或者是  他们的内容相同，也就是equals返回真)
         // 就认为不能加入新的k-v
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                //如果发现p的运行类型是TreeNode 那么就按照这个方式来扩容e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else if (p instanceof TreeNode)//如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
            //转成红黑树的条件是 table中的一条链表的长度大于8，并且table数组的长度大于64才会进行树化，否则就是对数组进行扩容来解决
                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);
                        //加入后，判断当前链表的个数，是否已经到8个，到8个，后
                        //就调用 treeifyBin 方法进行红黑树的转换
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash && //如果在循环比较过程中，发现有相同,就break,就只是替换value
                        ((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对应value
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//每增加一个Node ,就size++
        if (++size > threshold[12-24-48])//如size > 临界值，就扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

      5. 关于树化(转成红黑树)
      //如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容.
      //否则才会真正的树化 -> 剪枝
      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)
            resize();

    }
 */
package idea.chapter14.map_;


import java.util.HashMap;

/**
 * HashMap源码分析
 */
@SuppressWarnings({"all"})
public class HashMapSource {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("java", 10);//ok
        map.put("php", 10);//ok
        map.put("java", 20);//替换value

        System.out.println("map=" + map);//

        /*HashMap源码分析
        1. 执行构造器 new HashMap()
           初始化加载因子 loadfactor = 0.75
           HashMap$Node[] table = null
           
        2. 执行put 调用 hash方法，计算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16)
            public V put(K key, V value) {//K = "java" value = 10
                return putVal(hash(key), key, value, false, true);
            }
         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数组等于空或者长度为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;//辅助变量
                // 如果table的索引位置的key的hash相同和新的key的hash值相同，
                 // 并 满足(table现有的结点的key和准备添加的key是同一个对象 或者是  他们的内容相同，也就是equals返回真)
                 // 就认为不能加入新的k-v
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                        //如果发现p的运行类型是TreeNode 那么就按照这个方式来扩容e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else if (p instanceof TreeNode)//如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
                    //转成红黑树的条件是 table中的一条链表的长度大于8，并且table数组的长度大于64才会进行树化，否则就是对数组进行扩容来解决
                        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);
                                //加入后，判断当前链表的个数，是否已经到8个，到8个，后
                                //就调用 treeifyBin 方法进行红黑树的转换
                                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            if (e.hash == hash && //如果在循环比较过程中，发现有相同,就break,就只是替换value
                                ((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对应value
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;//每增加一个Node ,就size++
                if (++size > threshold[12-24-48])//如size > 临界值，就扩容
                    resize();
                afterNodeInsertion(evict);
                return null;
            }

              5. 关于树化(转成红黑树)
              //如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容.
              //否则才会真正的树化 -> 剪枝
              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)
                    resize();

            }
         */
    }
}

HashMap树化扩容触发

代码演示：

只有当table数组的长度达到64,并且其中一条链表的长度达到8，那么才会进行树化，这两个条件要通时满足，否则不会进行树化

package idea.chapter14.map_;

import java.util.HashMap;

/**
 * 演示HashMap树化的扩容机制
 */
@SuppressWarnings({"all"})
public class HashMapSource2 {
    public static void main(String[] args) {


        HashMap hashMap = new HashMap();
        for (int i = 1; i <= 12; i++) {
            //这个节点的长度超过了8并且就会有可能树化，但是还有一个条件就是table数组的长度要大于64才这两个条件满足才会进行树化 反之就是扩容数组
            //当这个链表的长度已经过了8每增加一次，就会尝试进行一次树化，只有当两个条件都满足了就真的树化
            hashMap.put(i, "hello");
        }

        hashMap.put("aaa", "bbb");

        System.out.println("hashMap=" + hashMap);//12个 k-v

        //布置一个任务，自己设计代码去验证，table 的扩容
        //0 -> 16(12) -> 32(24) -> 64(64*0.75=48)-> 128 (96) ->
        //自己设计程序，验证-》 增强自己阅读源码能力. 看别人代码.

    }
}

class A {
    private int num;

    public A(int num) {
        this.num = num;
    }

    //所有的A对象的hashCode都是100
//    @Override
//    public int hashCode() {//重写hashcode方法使得加入的元素都在同一条列表上
//        return 100;
//    }

    @Override
    public String toString() {
        return "\nA{" +
                "num=" + num +
                '}';
    }
}


http://www.kler.cn/a/17568.html

相关文章：

  • 删库跑路，启动！
  • unity 一个物体随键盘上下左右旋转和前进的脚本
  • Vulnhub靶场案例渗透[8]- HackableII
  • Ps：OpenColorIO 设置
  • FluentUI使用
  • 如何进行产线高阶能耗数据的计算和可视化?
  • 爬取景区源码
  • 【Maven笔记1】Maven介绍
  • ConcurrentHashMap底层实现原理
  • Java时间类（四）-- DateTimeFormatter类
  • PostgreSQL 基础知识：psql 入门
  • ChatGPT诞生的新岗位：提示工程师（Prompt Engineer）
  • 发展文旅夜游项目有哪些好处
  • Python实现哈里斯鹰优化算法(HHO)优化随机森林分类模型(RandomForestClassifier算法)项目实战
  • 章节3：02-Apache Commons Collections反序列化漏洞
  • 宝塔windows面板提权获取系统管理员权限方法！（非漏洞BUG）
  • JavaEE阶段测试复习
  • 京东数据分析：2023年Q1白酒电商整体动销增长，中低端酒企压力大
  • 国民技术N32G430开发笔记（14）-IAP升级 usart2接收数据
  • MySQL知识学习03（三大日志详解 binlog、redo log、undo log）
  • Python3 简介
  • Android 9.0 系统systemui下拉通知栏的通知布局相关源码分析
  • 05.rabbitMQ之搭建的各种坑
  • 基于DSP+FPGA+AD9238的冲击波超压测试系统设计与实现
  • 手搓GPT系列之 - chatgpt + langchain 实现一个书本解读机器人
  • Ajax -- from表单与模板引擎