史上最全的Java容器集合之HashMap(源码解读)(一)

简介: 史上最全的Java容器集合之HashMap(源码解读)(一)

一 什么是Map

  • Map是一个接口,他是key-value的键值对,一个map不能包含重复的key,并且每一个key只能映射一个value;
  • Map接口提供了三个集合视图:key的集合,value的集合,key-value的集合;
  • Map内元素的顺序取决于Iterator的具体实现逻辑,获取集合内的元素实际上是获取一个迭代器,实现对其中元素的遍历;
  • Map接口的具体实现中存在三种Map结构,其中HashMap和TreeMap都允许存在null值,而HashTable的key不允许为空,但是HashMap不能保证遍历元素的顺序,TreeMap能够保证遍历元素的顺序。

二 HashMap中的几个概念

什么是哈希表

哈希表(HashTable,散列表)是根据key-value进行访问的数据结构,他是通过把key映射到表中的一个位置来访问value,加快查找的速度,其中映射的函数叫做散列函数,存放value的数组叫做散列表,哈希表的主干是数组。


image.png


上面的图中就是一个值插入哈希表中的过程,那么存在的问题就是不同的值在经过hash函数之后可能会映射到相同的位置上,当插入一个元素时,发现该位置已经被占用,这时候就会产生冲突,也就是所谓的哈希冲突,因此哈希函数的设计就至关重要,一个好的哈希函数希望尽可能的保证计算方法简单,但是元素能够均匀的分布在数组中,但是数组是一块连续的且是固定长度的内存空间,不管一个哈希函数设计的多好,都无法避免得到的地址不会发生冲突,因此就需要对哈希冲突进行解决。 (1)开放定址法:当插入一个元素时,发生冲突,继续检查散列表的其他项,直到找到一个位置来放置这个元素,至于检查的顺序可以自定义;

(2)再散列法:使用多个hash函数,如果一个发生冲突,使用下一个hash函数,直到找到一个位置,这种方法增加了计算的时间;

(3)链地址法:在数组的位置使用链表,将同一个hashCode的元素放在链表中,HashMap就是使用的这种方法,数组+链表的结构。

关于 HashMap 源码中提到的几个重要概念

  • 哈希桶(buckets):在 HashMap 的注释里使用哈希桶来形象的表示数组中每个地址位置。注意这里并不是数组本身,数组是装哈希桶的,他可以被称为哈希表。
  • 初始容量(initial capacity) : 这个很容易理解,就是哈希表中哈希桶初始的数量。如果我们没有通过构造方法修改这个容量值默认为DEFAULT_INITIAL_CAPACITY = 1<<4 即16。值得注意的是为了保证 HashMap 添加和查找的高效性,HashMap 的容量总是 2^n 的形式。
  • 加载因子(load factor):加载因子是哈希表(散列表)在其容量自动增加之前被允许获得的最大数量的度量。当哈希表中的条目数量超过负载因子和当前容量的乘积时,散列表就会被重新映射(即重建内部数据结构),重新创建的散列表容量大约是之前散列表哈系统桶数量的两倍。默认加载因子(0.75)在时间和空间成本之间提供了良好的折衷。加载因子过大会导致很容易链表过长,加载因子很小又容易导致频繁的扩容。所以不要轻易试着去改变这个默认值。
  • 扩容阈值(threshold):其实在说加载因子的时候已经提到了扩容阈值了,扩容阈值 = 哈希表容量 * 加载因子。哈希表的键值对总数 = 所有哈希桶中所有链表节点数的加和,扩容阈值比较的是是键值对的个数而不是哈希表的数组中有多少个位置被占了。
  • 树化阀值(TREEIFY_THRESHOLD) :这个参数概念是在 JDK1.8后加入的,它的含义代表一个哈希桶中的节点个数大于该值(默认为8)的时候将会被转为红黑树行存储结构。
  • 非树化阀值(UNTREEIFY_THRESHOLD): 与树化阈值相对应,表示当一个已经转化为数形存储结构的哈希桶中节点数量小于该值(默认为 6)的时候将再次改为单链表的格式存储。导致这种操作的原因可能有删除节点或者扩容。
  • 最小树化容量(MIN_TREEIFY_CAPACITY): 经过上边的介绍我们只知道,当链表的节点数超过8的时候就会转化为树化存储,其实对于转化还有一个要求就是哈希表的数量超过最小树化容量的要求(默认要求是 64),且为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD);在达到该有求之前优先选择扩容。扩容因为因为容量的变化可能会使单链表的长度改变。

HashMap的类图

image.png

HashMap继承自AbstractMap,实现了Map接口,Map接口定义了所有Map子类必须实现的方法。AbstractMap也实现了Map接口,并且提供了两个实现Entry的内部类:SimpleEntry和SimpleImmutableEntry。

HashMap是基于哈希表的Map接口的实现,提供所有可选的映射操作,允许使用null值和null键,存储的对象时一个键值对对象Entry<K,V>, 是基于数组+链表的结构实现,在内部维护这一个数组table,数组的每个位置保存着每个链表的表头结点,查找元素时,先通过hash函数得到key值对应的hash值,再根据hash值得到在数组中的索引位置,拿到对应的链表的表头,最后去遍历这个链表,得到对应的value值。

image.png

HashMap类中的主要方法

常量

 // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组,总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数,注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
复制代码

HashMap的Node实体

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; // 哈希值,存放元素到hashmap中时用来与其他元素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; }
    // 重写hashCode()方法
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    // 重写 equals() 方法
    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;
    }
}
复制代码

其中key值定义的为final,因此在定义之后就无法进行修改,key和value就是在调用map时对应的键值对,next存储的是链表中的下一个节点,他是一个单链表,hash是对key的hashcode再次进行哈希运算之后得到的值,存储起来是为了避免重复计算。

HashMap的构造方法

/**
*使用默认的容量及装载因子构造一个空的HashMap
*/
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**
* 根据给定的初始容量和装载因子创建一个空的HashMap
* 初始容量小于0或装载因子小于等于0将报异常 
*/
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;
    //这个方法就是把容量控制在2的倍数
        this.threshold = tableSizeFor(initialCapacity);
}
/**
*根据指定容量创建一个空的HashMap
*/
public HashMap(int initialCapacity) {
    //调用上面的构造方法,容量为指定的容量,装载因子是默认值
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//通过传入的map创建一个HashMap,容量为默认容量(16)和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者,装载因子为默认值
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
复制代码

HashMap提供了四种构造方法:

(1)使用默认的容量及装载因子构造一个空的HashMap;

(2)根据给定的初始容量和装载因子创建一个空的HashMap;

(3)根据指定容量创建一个空的HashMap;

(4)通过传入的map创建一个HashMap。

第三种构造方法会调用第二种构造方法,而第四种构造方法将会调用putMapEntries方法将元素添加到HashMap中去。

putMapEntries方法是一个final方法,不可以被修改,该方法实现了将另一个Map的所有元素加入表中,参数evict初始化时为false,其他情况为true,我们来看看这个方法吧

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { 
        //根据m的元素数量和当前表的加载因子,计算出阈值
        float ft = ((float)s / loadFactor) + 1.0F;
        //修正阈值的边界 不能超过MAXIMUM_CAPACITY
        int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);
        //如果新的阈值大于当前阈值
        if (t > threshold)
            //返回一个>=新的阈值的 满足2的n次方的阈值
            threshold = tableSizeFor(t);
        }
        //如果当前元素表不是空的,但是 m的元素数量大于阈值,说明一定要扩容。
        else if (s > threshold)
            resize();
        //遍历 m 依次将元素加入当前表中。
        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);
        }
    }
}
复制代码

从中可以看出,它这个涉及了2个操作,一个是计算新的阈值,另一个是扩容方法

如果新的阈值大于当前阈值,需要返回一个>=新的阈值的 满足2的n次方的阈值,这涉及到了tableSizeFor:

  static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
复制代码

如果当前元素表不是空的,但是 m的元素数量大于阈值,说明一定要扩容。这涉及到了扩容方法resize。最复杂的方法之一

final Node<K,V>[] resize() {
    //oldTab 为当前表的哈希桶
    Node<K,V>[] oldTab = table;
    //当前哈希桶的容量 length
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //当前的阈值
    int oldThr = threshold;
    //初始化新的容量和阈值为0
    int newCap, newThr = 0;
    //如果当前容量大于0
    if (oldCap > 0) {
        //如果当前容量已经到达上限
        if (oldCap >= MAXIMUM_CAPACITY) {
            //则设置阈值是2的31次方-1
            threshold = Integer.MAX_VALUE;
            //同时返回当前的哈希桶,不再扩容
            return oldTab;
        }//否则新的容量为旧的容量的两倍。 
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
            //如果旧的容量大于等于默认初始容量16
            //那么新的阈值也等于旧的阈值的两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果当前表是空的,但是有阈值。代表是初始化时指定了容量、阈值的情况
    else if (oldThr > 0) 
        newCap = oldThr;//那么新表的容量就等于旧的阈值
    else {    
    //如果当前表是空的,而且也没有阈值。代表是初始化时没有任何容量/阈值参数的情况               
        newCap = DEFAULT_INITIAL_CAPACITY;//此时新表的容量为默认的容量 16
    //新的阈值为默认容量16 * 默认加载因子0.75f = 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        //如果新的阈值是0,对应的是  当前表是空的,但是有阈值的情况
        float ft = (float)newCap * loadFactor;//根据新表容量 和 加载因子 求出新的阈值
        //进行越界修复
        newThr = (newCap < MAXIMUM_CAPACITY && ft <(float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    //更新阈值 
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //根据新的容量 构建新的哈希桶
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //更新哈希桶引用
    table = newTab;
    //如果以前的哈希桶中有元素
    //下面开始将当前哈希桶中的所有节点转移到新的哈希桶中
    if (oldTab != null) {
        //遍历老的哈希桶
        for (int j = 0; j < oldCap; ++j) {
        //取出当前的节点 e
        Node<K,V> e;
        //如果当前桶中有元素,则将链表赋值给e
        if ((e = oldTab[j]) != null) {
            //将原哈希桶置空以便GC
            oldTab[j] = null;
            //如果当前链表中就一个元素,(没有发生哈希碰撞)
            if (e.next == null)
            //直接将这个元素放置在新的哈希桶里。
            //注意这里取下标 是用 哈希值 与 桶的长度-1 。 由于桶的长度是2的n次方,这么做其实是等于 一个模运算。但是效率更高
            newTab[e.hash & (newCap - 1)] = e;
            //如果发生过哈希碰撞 ,而且是节点数超过8个,转化成了红黑树
            else if (e instanceof TreeNode)
                 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            //如果发生过哈希碰撞,节点数小于8个。则要根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置。
            else {
                //因为扩容是容量翻倍,所以原链表上的每个节点,现在可能存放在原来的下标,即low位,或者扩容后的下标,即high位。high位=low位+原哈希桶容量
                //低位链表的头结点、尾节点
                Node<K,V> loHead = null, loTail = null;
                //高位链表的头节点、尾节点
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;//临时节点 存放e的下一个节点
                do {
                    next = e.next;
                &emsp;&emsp;//利用位运算代替常规运算:利用哈希值与旧的容量,可以得到哈希值去模后,是大于等于oldCap还是小于oldCap,等于0代表小于oldCap,应该存放在低位,否则存放在高位
                    if ((e.hash & oldCap) == 0) {
                        //给头尾节点指针赋值
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }//高位也是相同的逻辑
                    else {
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                        }//循环直到链表结束
                    } while ((e = next) != null);
                    //将低位链表存放在原index处
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //将高位链表存放在新index处
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
复制代码


resize的操作主要涉及以下几步操作:

  • 如果到达最大容量,那么返回当前的桶,并不再进行扩容操作,否则的话扩容为原来的两倍,返回扩容后的桶;
  • 根据扩容后的桶,修改其他的成员变量的属性值;
  • 根据新的容量创建新的扩建后的桶,并更新桶的引用;
  • 如果原来的桶里面有元素就需要进行元素的转移;
  • 在进行元素转移的时候需要考虑到元素碰撞和转红黑树操作;
  • 在扩容的过程中,按次从原来的桶中取出链表头节点,并对该链表上的所有元素重新计算hash值进行分配;
  • 在发生碰撞的时候,将新加入的元素添加到末尾;
  • 在元素复制的时候需要同时对低位和高位进行操作。

这段是借鉴人家的,确实很复杂,各种if else ,一点点去跟,也很累,但是大家至少也要知道它是怎么扩容的,几个重要的步骤要能说出来,面试的时候会问。

目录
相关文章
|
6天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
14 1
|
8天前
|
存储 安全 Java
Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
【10月更文挑战第17天】Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
23 2
|
1天前
|
JavaScript Java 项目管理
Java毕设学习 基于SpringBoot + Vue 的医院管理系统 持续给大家寻找Java毕设学习项目(附源码)
基于SpringBoot + Vue的医院管理系统,涵盖医院、患者、挂号、药物、检查、病床、排班管理和数据分析等功能。开发工具为IDEA和HBuilder X,环境需配置jdk8、Node.js14、MySQL8。文末提供源码下载链接。
|
5天前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
19 5
|
4天前
|
移动开发 前端开发 JavaScript
java家政系统成品源码的关键特点和技术应用
家政系统成品源码是已开发完成的家政服务管理软件,支持用户注册、登录、管理个人资料,家政人员信息管理,服务项目分类,订单与预约管理,支付集成,评价与反馈,地图定位等功能。适用于各种规模的家政服务公司,采用uniapp、SpringBoot、MySQL等技术栈,确保高效管理和优质用户体验。
|
6天前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
20 3
|
6天前
|
存储 缓存 安全
在Java的Map家族中,HashMap和TreeMap各具特色
【10月更文挑战第19天】在Java的Map家族中,HashMap和TreeMap各具特色。HashMap基于哈希表实现,提供O(1)时间复杂度的高效操作,适合性能要求高的场景;TreeMap基于红黑树,提供O(log n)时间复杂度的有序操作,适合需要排序和范围查询的场景。两者在不同需求下各有优势,选择时需根据具体应用场景权衡。
12 2
|
6天前
|
存储 安全 Java
Java Map新玩法:深入探讨HashMap和TreeMap的高级特性
【10月更文挑战第19天】Java Map新玩法:深入探讨HashMap和TreeMap的高级特性,包括初始容量与加载因子的优化、高效的遍历方法、线程安全性处理以及TreeMap的自然排序、自定义排序、范围查询等功能,助你提升代码性能与灵活性。
14 2
|
3天前
|
监控 安全 Java
在 Java 中使用线程池监控以及动态调整线程池时需要注意什么?
【10月更文挑战第22天】在进行线程池的监控和动态调整时,要综合考虑多方面的因素,谨慎操作,以确保线程池能够高效、稳定地运行,满足业务的需求。
70 38
|
4天前
|
Java 调度
[Java]线程生命周期与线程通信
本文详细探讨了线程生命周期与线程通信。文章首先分析了线程的五个基本状态及其转换过程,结合JDK1.8版本的特点进行了深入讲解。接着,通过多个实例介绍了线程通信的几种实现方式,包括使用`volatile`关键字、`Object`类的`wait()`和`notify()`方法、`CountDownLatch`、`ReentrantLock`结合`Condition`以及`LockSupport`等工具。全文旨在帮助读者理解线程管理的核心概念和技术细节。
18 1
[Java]线程生命周期与线程通信