为何HashMap的keySet遍历Integer键总是有序？复杂度与稳定性疑问

问题背景 #

以下是运行在LeetCode的Java代码：

class Solution {
    private int[] nums;
    private HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();
    private HashMap<Integer, Integer> occurances = new HashMap<Integer, Integer>();
    private int dp(int current) {
        //System.out.println(current);
        return 0;
    }
    
    public int deleteAndEarn(int[] nums) {
        for(var i = 0; i < nums.length; i++) {
            var n = nums[i];
            var o = occurances.getOrDefault(n, 0);
            o++;
            occurances.put(n, o);
        }
        
        int max = 0;
        for(Integer i: occurances.keySet()) {
            System.out.println(i);
            max = Math.max(dp(i), max);
        }
        
        return max;
    }
}

输入nums = [3,4,2,9,2,4,3,2,4,5]时，标准输出为：

2
3
4
5
9

测试多种nums组合后发现，HashMap的keySet()遍历出的Integer键始终有序，但已知HashMap的put和keySet操作时间复杂度为O(1)而非O(nlogn)，因此产生以下疑问：

• 底层是什么原因导致键总是有序？
• 打印这些键的算法时间复杂度是否仍为O(n)？
• 是否会出现键无序的情况？

解答 #

1. 为什么测试的Integer键看起来总是有序？ #

Java中HashMap的底层实现是数组+链表/红黑树，Integer类型的hashCode()返回值就是它本身的数值。而HashMap会通过hash值 & (容量-1)计算键对应的数组索引。
LeetCode环境中HashMap的初始容量通常为16，当你使用的Integer键是小范围连续（或近似连续）数值时，它们的索引会和数值大小正相关（比如2对应索引2，3对应索引3，9对应索引9）。而HashMap遍历keySet()时，是按底层数组的索引顺序依次遍历，遇到非空桶就取出键，所以最终输出的顺序看起来是按数值升序排列的。

2. 打印键的时间复杂度仍为O(n)吗？ #

是的。HashMap遍历keySet()的过程是遍历所有桶，每个键只被访问一次。虽然底层数组可能存在大量空桶，但空桶的遍历是常数时间开销，整体时间复杂度仍为O(n)（n为键的实际数量），和键是否有序无关。

3. 会出现键无序的情况吗？ #

当然会，以下几种场景都会导致遍历顺序无序：

• 当Integer键的数值超过HashMap的初始容量时，比如键为17：17的hash值是17，初始容量16时，17 & 15 = 1，所以17会被放到索引1的桶中，遍历会先输出17再输出2，顺序被打乱。
• 发生哈希碰撞时：如果两个不同的Integer键哈希到同一个桶，它们会以链表或红黑树的形式存储，遍历顺序是插入顺序而非数值大小顺序。
• 使用非Integer类型的键：比如String类型，其hashCode和字符串内容的关联并非线性，必然会出现无序的遍历结果。

内容的提问来源于stack exchange，提问作者Gregory Ray