HashMap踩坑实录——谁动了我的奶酪

软件发布|下载排行|最新软件

当前位置:首页IT学院IT技术

HashMap踩坑实录——谁动了我的奶酪

Nauyus   2019-12-14 我要评论

说到HashMaphashCodeequals ,想必绝大多数人都不会陌生,然而你真的了解这它们的机制么?本文将通过一个简单的Demo还原我自己前不久在 HashMap 上导致的线上问题,看看我是如何跳进这个坑里去的。

起因

在重构一段旧代码的时候发现有个 HashMap 的key对象没有重写 hashCodeequals 方法,使用IDEA自动重构工具生成后引发线上问题,因为实际重构的旧代码复杂,所以我抽出了一个关于奶酪(Cheese)的Demo还原踩坑场景,看看究竟谁动了我的奶酪

一个奶酪的例子

  • 首先,我们有一个奶酪(Cheese)类
/**
 * @author nauyus
 */
public class Cheese {
    /**
     * 大小
     */
    private Integer size;
    /**
     * 价格
     */
    private BigDecimal price;
    /**
     * 制造者
     */
    private String creator;
    
    //节约篇幅省略get/set/构造方法
}    
  • 然后,我们制造一个奶酪并且把它放到 HashMap 中去
Cheese cheese = new Cheese(7, new BigDecimal(20), "nauyus");
Map<Cheese, String> map = new HashMap<>();
map.put(cheese, "something not important");

好了,这时候我收到了阿里代码扫描插件的严正警告:如果自定义对象做为Map的键,那么必须重写hashCode和equals。

看到此警告,加上自己从前的经验,那当然就是改啊,打开Cheese类 Command+N 迅速生成代码然后add,commit,push一气呵成,然后,发布后线上出现了一个大BUG……

HashMap原理浅析

抛开BUG原因,我们先想一想为什么编程规约中强制要求了关于 hashCodeequals 的如下规则?

这要简单说下 HashMap 原理, HashMap 底层数据结构为在 jdk1.7 中为数组+链表, jdk1.8 中为数组+链表+红黑树,大概就长这个样子:

然后我们看看 HashMap 如何将数据存入又如何取出的。

首先看下 put 方法

   /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    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;
        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;
    }

具体细节可以仔细阅读源码,简单说来,就是首先对 key 进行 hash 计算,hash是一个 int 类型的本地方法,也就将 key 的 hashCode 无符号右移16位然后与 hashCode 异或从而得到 hash 值,在 putVal 方法中 (n - 1)& hash 计算得到数组的索引位置,如果位置无冲突,则直接将 value 放入数组中对应位置,如果存在冲突,则使用 equals 方法判断 key 是否为同一对象,同一对象则覆盖,不同对象则将 value 挂到链表或红黑树上。

然后再看看 get 方法

    /**
     * Implements Map.get and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((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);
            }
        }
        return null;
    }

同样的,get 也是通过 first = tab[(n - 1) & hash] 计算出位置然后再决定是否从链表或红黑树中进行查找,过程中同样用到了 equals 方法。

总结一下,put 方法使用基于 hashCodehash 方法得到下标位置,但是不同对象 hash 可能相同,即存在 hash碰撞 的可能,所以需要 equals 方法进一步判断是否为同一对象,get 方法同样使用 hash 方法得到下标位置,再根据 equals 方法确定是否取出该对象。

谁动了我的奶酪

如果我们的自定义对象没有覆写 hashCodeequals ,则会使用父类Object的方法,源码如下:

public native int hashCode;

public boolean equals(Object obj) {
        return (this == obj);
}

hashCode 是个本地方法,和内存地址有关系,而默认的 equals 内部实现就是 "==" 运算符,这就会导致一个结果,值相同对象的 hashCode 并不同,并且 equals 方法返回 false 。所以编程规约强制要求如果自定义对象做为Map的键,那么必须重写hashCode和equals。(敲黑板,这段话第二次出现),没毛病!

如果没有覆写父类方法,下面的程序 cheese 值虽相同,但 put 奶酪后无法 get 到,奶酪被动了

Cheese cheese= new Cheese(7, new BigDecimal(20), "nauyus");
Map<Cheese, String> map = new HashMap<>();
map.put(cheese, "something not important");
cheese = new Cheese(7, new BigDecimal(20), "nauyus");
//没有覆写hashCode和equals时虽然cheese值相同,但输出为null
System.out.println(map.get(cheese));

谁又动了我的奶酪

好了,现在我们知道了如果自定义对象做为Map的键,那么必须重写hashCode和equals。(重要的事情说三遍!),那有人问我重写后的产生的BUG后是怎么回事? 还原了下场景应该是这样的,我重写了 hashCodeequals ,但是千不该万不该忽略了原有代码很多行后还有一行代码,做成Demo后大概是这样的:

Cheese cheese= new Cheese(7, new BigDecimal(20), "nauyus");
Map<Cheese, String> map = new HashMap<>();
map.put(cheese, "something not important");
//一段被我忽略的代码
cheese.setCreator("tom");
System.out.println(map.get(cheese));

putHashMap 后,作为 key 的 cheese 对象再次被 set 了值,导致 hashCode 返回结果有了变更,put 奶酪后无法 get 到,奶酪再一次被动了

总结

总结一下踩坑经历,可以得出以下结论:

  1. 如果自定义对象做为Map的键,那么必须重写hashCode和equals。
  2. 尽量使用不可变对象作为map的键,如String。
  3. 即使万分自信的代码,还是跑一下单元测试为好。(血的教训)

还有啊,

没事还是少瞎改别人代码吧!

感谢阅读,原创不易,如有启发,点个赞吧!这将是我写作的最强动力!本文不同步发布于不止于技术的技术公众号 Nauyus ,主要分享一些编程语言,架构设计,思维认知类文章, 2019年12月起开启周更模式,欢迎关注,共同学习成长!

Copyright 2022 版权所有 软件发布 访问手机版

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们