HashMap

默语

发布于 2024-11-25 15:04:46

5000

代码可运行

文章被收录于专栏：JAVAJAVA

运行总次数：0

代码可运行

HashMap

博主默语带您 Go to New World. ✍ 个人主页—— 默语的博客👦🏻 优秀内容 《java 面试题大全》 《java 专栏》 《idea技术专区》 《spring boot 技术专区》 《MyBatis从入门到精通》 《23种设计模式》 《经典算法学习》 《spring 学习》 《MYSQL从入门到精通》数据库是开发者必会基础之一~ 🍩惟余辈才疏学浅，临摹之作或有不妥之处，还请读者海涵指正。☕🍭 🪁 吾期望此文有资助于尔，即使粗浅难及深广，亦备添少许微薄之助。苟未尽善尽美，敬请批评指正，以资改进。！💻⌨

默语是谁？

大家好，我是默语，别名默语博主，擅长的技术领域包括Java、运维和人工智能。我的技术背景扎实，涵盖了从后端开发到前端框架的各个方面，特别是在Java 性能优化、多线程编程、算法优化等领域有深厚造诣。

目前，我活跃在CSDN、掘金、阿里云和 51CTO等平台，全网拥有超过10万的粉丝，总阅读量超过1400 万。统一 IP 名称为默语或者默语博主。我是 CSDN 博客专家、阿里云专家博主和掘金博客专家，曾获博客专家、优秀社区主理人等多项荣誉，并在 2023 年度博客之星评选中名列前 50。我还是 Java 高级工程师、自媒体博主，北京城市开发者社区的主理人，拥有丰富的项目开发经验和产品设计能力。希望通过我的分享，帮助大家更好地了解和使用各类技术产品，在不断的学习过程中，可以帮助到更多的人，结交更多的朋友.

我的博客内容涵盖广泛，主要分享技术教程、Bug解决方案、开发工具使用、前沿科技资讯、产品评测与使用体验。我特别关注云服务产品评测、AI 产品对比、开发板性能测试以及技术报告，同时也会提供产品优缺点分析、横向对比，并分享技术沙龙与行业大会的参会体验。我的目标是为读者提供有深度、有实用价值的技术洞察与分析。

名称解释

Hash：
- 一般翻译为散列，直译为哈希
Hashing: 散列法
- 把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。是一种典型的“空间换时间”的做法。
负载因子
- 比如我们存储70个元素，但我们可能为这70个元素申请了100个元素的空间。70/100=0.7，这个数字称为负载因子
哈希冲突（碰撞）
- 由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突
- 解决方案：开放寻址法、拉链法。HashMap处理方案就是拉链法

先整体把握HashMap的存储数据结构图

关键源码解释

类声明：（了解实现的接口）

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

类属性：（了解决定性能的参数）

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;             // 默认的初始化容量 2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30;                    // 最大容量  2^30=1073741824
static final float DEFAULT_LOAD_FACTOR = 0.75f;                 // 默认负载因子 0.75
static final int TREEIFY_THRESHOLD = 8;                         // 存储结构转链表结构转换为树状结构的阈值 =8
static final int UNTREEIFY_THRESHOLD = 6;                       // 存储结构由树状结构转换为链表结构的阈值=6 
static final int MIN_TREEIFY_CAPACITY = 64;                     // 树状结构的最小容量=64   

int threshold;                                                  // 阈值,当实际大小（容量*负载因子）大于该值时会进行扩容
final float loadFactor;                                         // 负载因子
transient int size;                                             // 存储元素总数
transient int modCount;                                         // 被修改的次数（用于fast-fail机制）

初始化：（了解初始化方式，指定入参来构建Map）

// 使用指定初始容量以及负载因子来初始化，参数均可使用默认值
public HashMap(int initialCapacity, float loadFactor) {
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);  // 返回比输出值大的最近的2的整数次幂运算值，例如11的最近是16
}


// 使用Map数据来初始化
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

Hash定位：（了解hash的处理方式，注意入参是Object）

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

散列值理论上是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
Object.hashCode（）是一个Native方法，使用和当前线程相关的随机数和其他值最终通过Marsaglia’s xorshift scheme随机算法产生一个随机数
hashCode无符号右移16位，即先将32位的int的低位舍弃，高位补0，然后再与hashCode进行（位）异或运算，使得高位不受影响，低位与高位进行运算（这部分为扰动，真正参与运算的还是低位）

Put方法：（了解存储数据的key是怎么确定的）

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);  // 先对key进行了一次Hash运算
}

/**
 * @param hash            key的hash值
 * @param key             the key
 * @param value           the value to put
 * @param onlyIfAbsent    true时，表示不修改已存在的值
 * @param evict           false时，表示是在初始化HashMap
 */
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数组为空，需要resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 确定key要插入的数组位置的元素p，如果不存在则直接放入，(n - 1) & hash==hash%n ，前者效率更高
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 插入的位置元素已存在，则说明发生了hash碰撞（1.key是一样的，覆盖value,2,key不一样，存储在链表或者树中） 
    else {
        Node<K,V> e; K k;
        // 检查数组节点p是否和新插入的节点相等（比较key） 
        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 {
            // 死循环，通过break来终止，这里为寻找下一个链表节点的过程
            for (int binCount = 0; ; ++binCount) {
                // 判断当前节点的下一个节点是null的，则占位，如果发现需要转为树结构，则转换，binCount统计链表长度，从0开始
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
               // 下一个节点不是空，则判断是否和新节点相等（key比较），相等则该位置为要找的位置
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 下一个节点变为当前节点，继续循环
                p = e;
            }
        }
        // 要放入的位置确定后，判断位置上的元素是否存在，如果存在则判断是否替换
        if (e != null) { 
            V oldValue = e.value;
            // 满足替换条件才替换
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断是否需要扩容
    if (++size > threshold)
        resize();
    // 插入后的后续处理，HashMap默认=false,不需要
    afterNodeInsertion(evict);
    return null;
}

关键方法，比较key是否相等

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

数据演示

String[] arr1 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7"};
String[] arr2 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0"};
String[] arr3 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu"};
String[] arr4 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n"};
String[] arr5 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n", "jaua", "zth9", "maxe"};
String[] arr6 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n", "jaua", "zth9", "maxe", "wymp"};

arr1与arr2数据演示：size=16<=64，单链长度>8导致的扩容

arr1是8个字符串,arr1数据在size=16时，全部落到index=2处

arr2是9个字符串，数据在size=16同样会落在index=2处，此时因为链表长度>8结构转变，因为此时总容量=16小于树状结构最小容量64，因此只扩容1倍=32，重新计算hash定位，部分落到index=2处，部分落到index=18处

for (String key : arr2) {
    System.out.println(String.format("%s\tsize=16,index=%s \t ", key, hash(key) % 16));
}
-------------------------------------------------------
cg80 size=16,index=2
lo8u size=16,index=2
pqdi size=16,index=2
bbam size=16,index=2
hhc5 size=16,index=2
pnem size=16,index=2
u955 size=16,index=2
p4z7 size=16,index=2
phr0 size=16,index=2

Map<String, Integer> map1 = new HashMap<>(16, 1);
for (String key : arr1) {
map1.put(key, 0);
}
Map<String, Integer> map2 = new HashMap<>(16, 1);
for (String key : arr2) {
map2.put(key, 0);
}

内存验证

arr1的落点

arr2的落点

arr4与arr3数据演示：size=32<=64，单链长度>8导致的扩容

前面arr2因为单链长度>8进行了一次扩容，size=16*2=32。arr3是一个单链=8的情况，arr4则是arr3单链长度再次>8触发扩容的情况，此时情况与arr2扩容一样，size调整=32*2=64

for (String key : arr4) {
    System.out.println(String.format("%s\t size=32,index=%s \t", key, hash(key) % 32));
}
-------------------------------------------------------
cg80     size=32,index=18     
lo8u     size=32,index=18     
pqdi     size=32,index=18     
bbam     size=32,index=2     
hhc5     size=32,index=2     
pnem     size=32,index=18     
u955     size=32,index=18     
p4z7     size=32,index=18     
phr0     size=32,index=2     
suv8     size=32,index=18     
u4pu     size=32,index=18     
p63n     size=32,index=18

Map<String, Integer> map3 = new HashMap<>(16, 1);
for (String key : arr3) {
    map3.put(key, 0);
}


Map<String, Integer> map4 = new HashMap<>(16, 1);
for (String key : arr4) {
    map4.put(key, 0);
}

内存验证

arr6与arr5数据演示：size=64，szie>8 红黑树转换

Map<String, Integer> map5 = new HashMap<>(16, 1);
for (String key : arr5) {
    map5.put(key, 0);
}
Map<String, Integer> map6 = new HashMap<>(16, 1);
for (String key : arr6) {
    map6.put(key, 0);
}

arr5是单链长度=8满员情况，arr6则是单链长度>8导致再次扩容的数据（index=50的个数>8）

for (String key : arr6) {
    System.out.println(String.format("%s\t size=64,index=%s", key, hash(key) % 64));
}
-------------------------------------------------------
cg80     size=64,index=50
lo8u     size=64,index=50
pqdi     size=64,index=50
bbam     size=64,index=2
hhc5     size=64,index=2
pnem     size=64,index=18
u955     size=64,index=50
p4z7     size=64,index=50
phr0     size=64,index=2
suv8     size=64,index=18
u4pu     size=64,index=18
p63n     size=64,index=18
jaua     size=64,index=50
zth9     size=64,index=50
maxe     size=64,index=50
wymp     size=64,index=50

内存验证

红黑树结构

常见问题

为什么使用HashMap

HashMap是非synchronized的键值对存储结构，对于查找数据，速度快，效率高
HashMap支持键和值为null存储
HashMap不保证元素的顺序

HashMap中null的使用

key可以为null,但只能有一个，index=0,后续会覆盖前者
value可以为nul，数量不限制

查找效率

在数组中 O(1)
在链表中 O(N)
在树中 O(log N)

为什么采用红黑树而不是AVL树（平衡二叉树）？

区别
- 红黑树特点
  - 每个结点要么是红的要么是黑的。
  - 根结点是黑的。
  - 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
  - 如果一个结点是红的，那么它的两个儿子都是黑的。
  - 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
- 平衡二叉树特点
  - 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
原因
- 二者在查找是都是通过二分法查找，效率差不多
- 插入与删除是红黑树效率较高，因为AVL树要求绝对的平衡，为保证绝对平衡，进行旋转的次数较多

存在问题

在自动调整大小时存在线程安全问题
在ForEach遍历时不能删除元素，正确方式为采用Iterator

为什么使用包装类作为键而不是基本类型

因为包装类重写了hashCode和equals方法，保证了键的不变性，在查询元素时能查找到正确的元素对象

使用对象作为键需要注意什么

注意保证键的不变性，即对象的hashCode和equals方法返回值是确定的

多线程时如何存储

使用HashTable或者ConcurrentHashMap
HashTable是HashMap的synchronized版本，不支持null的键或者值，底层是数组+链表，没有红黑树。ConcurrentHashMap是HashTable的改进版本
ConcurrentHashMap JDK7之前采用锁分离技术，默认将Hash表分为16段，对每段单独加锁，支持16个线程同时访问，支持读取并发，采用fail-fast迭代器，迭代中删除元素抛异常，JDK8之后使用synchronized+cas技术。原因在于分段锁浪费空间且实际中锁竞争情况出现很少。
HashTable是采用锁表技术，对每个操作都加锁保证安全，同一时刻只有一个线程能访问，效率低下，大部分情况可以使用ConcurrentHashMap替代，未采用fail-fast迭代器

扩容为什么是2的整数倍

保证Node的hash尽量的一致性
当n扩容后仍保持2^m时，Node落地点的下标i=(n - 1) & hash会更优化

为什么负载因子0.75，链表转红黑树阈值=8，红黑树转链表=6

作为一般规则，默认的负载因子(0.75)提供了良好的性能权衡时间和空间成本。值越高，空间开销越小，但增加查找成本
阈值=8，是因为Hash下标的落地点遵循泊松分布，在负载因子=0.75前提下，忽略计算方差，λ=0.5时，阈值=8的概率为0.00000006，再高概率小于百万分之一，此时性能已经满足需求
阈值=6，是因为=8时链表转为树，再由树转链表这阈值一定小于8，所以=6