为什么有时HashSet（HashMap）“感觉”是有序的

桃扇骨 2022-12-08 01:54 51阅读 0赞

# 场景 #

在学习时，所有博客都说HashSet是无序的。但是实际测试的时候，发现有时看起来好像是有序的。比如下面这段代码，使用Jdk1.8编译：

HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            set.add(i);
        }
        System.out.println(set);

输出结果为：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

此时你可能会认为，是样本量太小了，于是把数据扩张到1W，发现还是有序的。然后又把数据扩展到10W，发现前面是有序的，但是到后面就会无序。感觉很奇怪。

这里抛出结论，以“JDK1.7，存储的是Integer数据类型”为例，如果存储的数据大于65535，就后面的就不保证有序了。

要理解这个问题，需要知道Hash表的基本原理，这里就不再说了。主要针对JDK源码进行分析。

# JDK1.8中的Hash函数 #

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

在1.8中的hash函数为：取对象的hashcode，然后除以 2^16（65536），然后再进行异或运算。

举个例子

十进制： 100
    二进制： 0110 0100
    对其进行右移16位，得： 0000 0000
    然后与其自身进行异或操作：
    0110 0100
    0000 0000
    得:0110 0100

有上述例子可知，当hashcode值小于65536时，那么它的hash值就是它本身。

再看Integer的hashcode实现：

@Override
    public int hashCode() {
        return Integer.hashCode(value);
    }
    
    static int hashCode(int value) {
        return value;
    }

综上，Integer小于65536时，hash函数计算出来的值就是它本身，所以他也会放在对应的表中的位置。

当大于等于65535时，计算出来的hash值就不是它自身，所以位置就会发生偏移。就不能保证有序了。举个例子：

十进制：70000
    二进制：0001 0001 0001 0111 0000
    右移16位，得：0000 0000 0000 0000 0001
    两者异或：
    0001 0001 0001 0111 0000
    0000 0000 0000 0000 0001
    得：0001 0001 0001 0111 0001
    转化为十进制就是：70001

由上述例子可以看出，70000计算出的hash地址为70001。这样它存放的位置就出现了偏差，hash表也就无序了。