• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

TreeMap和HashMap的元素比较

开发技术 开发技术 2周前 (04-07) 10次浏览

写在前面的话

2021.04,准备面试和CCF CSP认证的我准备做一套CCF模拟题,然后就有了此篇博客(x
题目:201912-2 回收站报数
题目截图:

TreeMap和HashMap的元素比较

第一个想法:读取每个垃圾的位置,存入TreeSet中,然后依次取出判断是否可以建立回收站和评分(不可以建立回收站,评分为-1)。
这时候就有读者要问了:啊这你为什么要使用TreeSet呢?不使用HashSet呢?
我回答:因为输出需要顺序啊,HashSet输出是(没有顺序的)不保证有序的,即有可能出现有序但是程序设计不能依赖于此。
读者:噢,原来如此。
做完题目的我:一看你就是一大段文字不喜欢看(x,题目都没看清(别骂了,我也是🤡),题目最后的输出是需要统计每种得分的个数,不需要有序,用HashSet完全是足够了。
读者:WTF,一种植物。

但是在我看错题目的解题过程中(hhh),出现了错误,准确的说是TreeSet的使用错误,这篇博客记录一下错误和过程。

TreeSet compare和contains

错误现象

在上述题目中,笔者使用的是TreeSet进行排序,然后每一个依次判断输出,但是最后输出的结果全部都是4,所有的垃圾点都是回收站并且评分都是4,即对于任意一个垃圾,周围8个边界都存在垃圾。

错误代码

这是我进行判断并且计算评分的代码:

public static int score(int x, int y, Set<Point1912> set) {
        if (set.contains(new Point1912(x + 1, y)) && set.contains(new Point1912(x - 1, y)) && set.contains(new Point1912(x, y + 1)) && set.contains(new Point1912(x, y - 1))) {
            int sum = 0;
            sum += (set.contains(new Point1912(x + 1, y + 1)) ? 1 : 0);
            sum += (set.contains(new Point1912(x - 1, y + 1)) ? 1 : 0);
            sum += (set.contains(new Point1912(x + 1, y - 1)) ? 1 : 0);
            sum += (set.contains(new Point1912(x - 1, y - 1)) ? 1 : 0);
            return sum;
        } else {
            return -1;
        }
    }

坐标类

class Point1912 {
    int x = 0;
    int y = 0;
    int seq = 0;
    
    public Point1912(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public Point1912(int x, int y, int seq) {
        this.x = x;
        this.y = y;
        this.seq = seq;
    }

    @Override
    public boolean equals(Object obj) {
        Point1912 p = (Point1912) obj;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

TreeSet代码

TreeSet<Point1912> set1 = new TreeSet<>(((o1, o2) -> o1.seq - o2.seq));

很明显,在判断的代码中任意的set.contains()都返回了true,但是在坐标类中我明确设计了equals和hashCode方法,保证只有坐标相等的时候才能返回true。

调试

查看源码

最终的比较源码,位置在TreeMap.java

final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

问题就出现在这里了,TreeSet.contains()方法最终在这里进行比较,重点在于该函数使用的是comparator,这个比较器便是TreeMap用于排序的比较器。因为进行判断的元素seq都是默认值,所以判断是否存在的函数要么全部返回false,要么全部返回true,因为我设置seq默认为0,TreeSet中一定存在所以contains全为true。

解决方案

使用HashSet存储坐标,同时使用另一个ArrayList或者数组存储坐标保证顺序。
下面是HashSet.contains()方法的内容,位置HashMap.java

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;
    }

可以这里便是采用key.equals的方法进行比较,重写equals起了作用。
同时这个first instance of TreeNode 可以看到HashMap中如果同一个桶的元素超过了7个,在Java1.8中就就将链表转换为了红黑树,Node变成了TreeNode。

总结

TreeMap中元素的比较采用的是Comparator,或者是元素实现的Comparable接口;
HashMap中元素的比较便是元素的equals方法。
如果没看错题目,估计也没这茬子事(嘤嘤嘤x.x)

人生此处,绝对乐观


程序员灯塔
转载请注明原文链接:TreeMap和HashMap的元素比较
喜欢 (0)