程序员经验分享-hwhale

最通俗易懂的HashMap深度解析

2023-05-16

文章目录

  • 导言
  • Hash表
    • 什么是Hash表
    • 为什么要Hash表
    • Hash表核心原理
      • 核心概念
        • Hash表
        • hash函数
      • 常见冲突解决方法
        • 开放地址法(再散列法)
        • 再哈希法
        • 链地址法（拉链法）
  • java HashMap原理浅析
  • java HashMap核心AIP
    • 查
    • 增
    • 删
    • 其他
      • 快速失败机制 Fail-Fast
  • 总结
  • 参考文章

导言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

常见的逻辑数据结构有: 数组、栈、队列、链表、树、图、散列表、堆。本文的核心就是讲散列表(Hash表)。以下首先介绍Hash相关知识，再以jdk1.8中的HashMap做一个源码解读。

Hash表

什么是Hash表

它最大的特点就是可以快速实现查找、插入和删除。因为它的快速性，常被广大程序员拿来处理大数据问题。

为什么要Hash表

常和Hash放在一起选型考虑的有数组、链表，数组增删困难、队列寻址困难。而Hash就很好的结合两者的优点，使用自定义的下标索引HashCode，加快寻址、插入、删除的操作，本质上就是一个优化的k-v存储。

Hash表核心原理

核心概念

Hash表

散列表。根据关键值(key)访问其value(真正的数据实体)，也就是最常用到的Map。

hash函数

哈希函数是Hahs表的映射函数，它可以把任意长度的输入变换成固定长度的输出，该输出就是哈希值。该哈希值就是该k-v存储的key。设计出一个简单、均匀、存储利用率高的散列函数是散列技术中最关键、最重要的问题。

一句话总结: hash函数是为了快速确定数据所在的"下标"。

常见的hash映射策略有:

  1. 直接定址法：取关键字或关键字的某个线性函数值为散列地址。

  2. 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

  3. 平方取中法：取关键字平方后的中间几位为哈希地址。

    通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

  4. 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

  5. 随机数法

  6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

常见冲突解决方法

理想情况下每个Key都被分配到一个唯一的桶，但大多数的Hash函数都不能支持这一要求，如果要支持则每次分配新的key时需要知道旧的Keys的值，一般来说这并不值的。因此我们需要处理散列冲突。

常见的Hash冲突有如下几种:

开放地址法(再散列法)

开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1) 其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)，称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

总而言之，就是冲突的时候往后顺序挪若干位插入。

再哈希法

当发生冲突时，使用第二个、第三个哈希函数…计算地址，直到无冲突时。缺点：计算时间增加。比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止.这种方法不易产生聚集，但增加了计算时间。

多次Hash，冲突一次Hash一次。

链地址法（拉链法）

将所有关键字为同义词的记录存储在同一线性链表中.基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

jdk 的hashmap就是基于这个的变体，1.7前几乎就是链地址法，1.8及其之后是待红黑树的链地址法。

java HashMap原理浅析

一张图表示(图片来源):

图1

java hashMap就是基于的“链地址法”，链地址法中的“同义词链表”在jdk hashmap中通过java.util.HashMap.Node构成链表表示，Node源码主要内容如下所示(暂不考虑红黑树节点: TreeNode):

static class Node<K,V> implements Map.Entry<K,V> {
    //省略构造函数和get、set方法，以及其他例如Hash、equals的方法
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

所有的桶元素存储在transient Node<K,V>[] table;这里源码396行。jdk1.8中使用(n - 1) & hash来获取桶的下标位置此处的与操作逻辑上等价于%，如果冲突了则在加在其链表尾。

Node的hash值来自于:

static final int hash(Object key) {
    int h;
    // 从此可以看错HashMap支持key为null的对象
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash和key的关系: hash值就是key的hashcode经过一个位运算得到。ps: 对于java.lang.Object#hashCode，该方法是专门用来支持hash数据结构的。

hash值决定该value在哪个桶，key保证在全局上唯一(桶链表上更是唯一)。

java HashMap核心AIP

略过各种便于开发使用的api不谈，java中的HashMap就是个支持增、删、查的散列表。

查

先从最简单的查开始。所有的查都是调用方法getNode实现的:

final HashMap.Node<K, V> getNode(int hash, Object key) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> first, e;
    int n;
    K k;
    // 如果table有元素则使用hash索引到对应的Node
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        // 如果第一个就是则直接返回
        if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果第一个不是: 
        if ((e = first.next) != null) {
            // 红黑树则走红黑树getNode逻辑
            if (first instanceof HashMap.TreeNode)
                return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
            // 非红黑树则走链表逻辑: 遍历链表
            do {
                //遍历找到了，返回
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 如果找不到则返回null
    return null;
}

增

增的核心就是java.util.HashMap#putVal这个方法:

// hash: 用于定位桶的位置，
// evict: 当table处于初始化时为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;
    // 如果对应的hashMap桶不存在则直接新建一个桶
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果对应的桶(也就是p)存在
    else {
        Node<K,V> e; K k;
        // 桶数组上的node.key和要put的key相同=>将这个桶node赋值到e上
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        
		/* 不是桶上的node*/
        // 如果是红黑树结构走红黑树putVal逻辑
        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) // 该链表大于8了
                        treeifyBin(tab, hash); // 可以简单理解成"尝试"转为红黑树，当tab太短时就不转
                    break;
                }
                // 如果在该桶里找到了对应key，退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        //当执行到这里时，e就是key对应的node(不管是查出来的还是new出来的)
        if (e != null) { 
            V oldValue = e.value;
            // 替换旧数据
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // linkHashMap相关,暂时不管
            return oldValue;
        }
    }
    // 无关代码
 /*   ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);*/
    return null;
}

删

final HashMap.Node<K, V> removeNode(int hash, Object key, Object value,
                                    boolean matchValue, boolean movable) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> p;
    int n, index;
    // 存在对应的桶
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        HashMap.Node<K, V> node = null, e;
        K k;
        V v;
        // key相同了=>找出要删除的Node=>赋值给node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // key不同则遍历查找(树查找或链表查找)
        else if ((e = p.next) != null) {
            // 树查找
            if (p instanceof HashMap.TreeNode)
                node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
            // 链表查找
            else {
                // 如果走链表查找分支，则p就不是桶里的Node了，并且p!=node
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e; 
                } while ((e = e.next) != null);
            }
        }
        // node不为null表示之前的操作找到了对应的key
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 树的删除
            if (node instanceof HashMap.TreeNode)
                ((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            //node就是桶中的那个node
            else if (node == p)
                tab[index] = node.next;
            // 链表中的节点的删除
            else
                p.next = node.next;
            /* 无关代码先忽略
                ++modCount;
                --size;
                afterNodeRemoval(node);*/
            return node;
        }
    }
    // 不存在对应的桶或桶里没有数据
    return null;
}

其他

快速失败机制 Fail-Fast

这个机制是用来应对并发情况的(HashMap不支持访问)。如果要并发访问请使用:java.util.concurrent.ConcurrentHashMap

上文中的modCount字段就与此有关，当用户通过迭代器访问HashMap时，会对比这个值，如果不符合预期就会抛出异常ConcurrentModificationException;

//java.util.HashMap.EntrySet#forEach
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

总结

无论是增、删、查，HashMap的查询过程都是先判断hash，在判断key。如果key相同则hash一定相同(因为hash就是key的hashCode)。但是，当hash相同时，key不一定相同，因为hash相同知识表示他们在一个桶链表上，但不一定是同一个key。

所以那个常见的问题: 重写hashCode()和重写equals()的关系可以这样理解(结论是一起重写):

  1. 重写hashCode确定桶下标，重写equals确定全局唯一
  2. 重写了equals一定要重写hashCode方法，因为要保证两个equals的对象hashCode也一样(保证全局唯一)，否则的话可能插入两个一样(equals)的对象
  3. 重写了hashCode一定要重写equals，因为不在同一个的桶链表上(hash不同)的一定不equals。

参考文章

  1. 数据结构与算法: hashMap
  2. HashMap实现原理
  3. 为什么重写equals同时要重写hashCode？
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

HashMap

最通俗易懂

深度解析

最通俗易懂的HashMap深度解析 的相关文章

  • 如何断言两个具有 Javabean 值的 HashMap 相等？

    我有两个HashMap

  • Java：具有重复键的 Json 可以使用 Jackson 进行映射

    我有一个具有相同键但不同值的 json 文件 如下所示 domains A name a type a1 B name r type g1 A name b type b1 这是来自外部系统 如何转换json 到 java 映射对象并访问不

  • HashMap 分组依据 (Java)

    有没有一种方法可以在Java中按Key分组并将值添加到HashMap中 HashMap

  • 如何在 Java 中创建哈希表？

    在 Java 中创建哈希表 或关联数组 最直接的方法是什么 我的 google fu 已经出现了几个例子 但是有一个标准的方法来做到这一点吗 有没有一种方法可以用键 gt 值对列表填充表 而无需为每对对象单独调用 add 方法 Map ma

  • 2d(3d) 坐标的哈希图（即双精度向量）？

    我想知道是否有一个通用的全能解决方案hash map对于坐标 2d 或 3d 即双精度向量 一个例子here https stackoverflow com questions 7222143 unordered map hash func

  • Guava 地图中的驱逐惰性

    当前的地图驱逐算法相当懒惰 看起来过期的对象只有在访问数据结构时才会被驱逐 例如 从地址到索引器的映射定义为 ConcurrentMap

  • unordered_map线程安全

    我正在使用 boost thread 库将单线程程序更改为多线程程序 该程序使用 unordered map 作为 hasp map 进行查找 我的问题是 某一时刻 许多线程将进行写入 而另一时刻 许多线程将进行读取 但不会同时进行读取和写

  • 迭代 Hashmap 时如何得到 ConcurrentModificationException？

    我正在尝试将键值对添加到迭代器方法内的哈希映射中 但这并没有给我ConcurrentModificationException Why 由于 Hashmap 是快速失败的 Map

  • clojure 中的反转哈希映射

    我在 clojure 中有哈希映射 key1 value1 key2 value2 key3 value1 我需要将其转换为哈希映射 value1 key1 key3 value2 key2 有 Clojure 方法可以做到这一点吗 clo

  • c++ pthread - 如何使地图访问线程安全？

    我有一个映射作为成员变量和多个访问该映射的线程 读写访问 现在我必须确保只有一个线程可以访问该地图 但我该如何点呢 最好的解决方案是什么 Boost 包含一些用于共享访问的很好的锁实现 看看文档 http www boost org doc

  • 按顺序范围循环映射

    我正在寻找一种确定的方法来范围Go map为了 Go 规范 https golang org ref spec For statements陈述如下 映射的迭代顺序未指定 并且不保证从一次迭代到下一次迭代的顺序相同 如果在迭代过程中删除尚未

  • Java HashMap - 深拷贝

    我只是想找出如何进行深层复制的最佳解决方案HashMap 该映射中没有对象实现Cloneable 我想找到比序列化和反序列化更好的解决方案 看一眼深度克隆 在 Google Code 上您可以找到一个库 你可以阅读它https github

  • Java - 线程“主”中的异常 java.util.ConcurrentModificationException

    有什么办法可以修改HashMap迭代特定键时的值 下面给出一个示例程序 public static void main String args HashMap

  • 使用 get/post 的免费云数据存储？ [关闭]

    Closed 此问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我知道还有其他类似的键 值存储http openkeyval org http openkeyval o

  • 哈希表的空间复杂度是多少？

    具有 32 位键和指向单独存储的值的 32 位指针的哈希表的大小是多少 是 2 32 个槽 4 字节 键 4 字节 指向值的指针 4 10 9 4 4 32GB 我想了解哈希表的空间复杂度 我认为你问错了问题 数据结构的空间复杂度表示它占用

  • JQuery $.ajax() 在 java servlet 中发布数据

    我想将数据发送到 java servlet 进行处理 数据将具有可变长度并采用键 值对 A1984 1 A9873 5 A1674 2 A8724 1 A3574 3 A1165 5 数据不需要这样格式化 这就是我现在的方式 var sav

  • 使用 HashMap 映射 String 和 int

    我有一个显示国家 地区名称的列表视图 我已将名称作为字符串数组存储在 strings xml 中 称为国家 地区名称 在填充 ListView 时 我使用从 strings xml 读取的 ArrayAdapter String count

  • 为什么 Hashtable 不允许空键或空值？

    正如 JDK 文档中所指定的 Hashtable 不允许空键或空值 HashMap 允许一个空键和任意数量的空值 为什么是这样 Hashtable 是较旧的类 通常不鼓励使用它 也许他们看到了对 null 键的需要 更重要的是 null 值

  • 使用 TreeMap 和 Comparator 按值对 HashMap 进行排序

    我使用以下代码创建哈希图 然后使用树形图和比较器对哈希图中的值进行排序 然而 输出结果却出乎意料 所以任何关于我做错了什么的想法都会有帮助 Code public static void main String args System ou

  • 如果计算的哈希码超过整数最大限制，会发生什么？

    这是 Java HashTable 类的 hashCode 实现 如果哈希表中的元素数量很大并且哈希码超过 INTEGER MAX LIMIT 2 147 483 648 到 2 147 483 647 该怎么办 我假设 hashCodes

随机推荐

热门标签