HashMap & HashSet 的key“自动排序”问题

小半 • 2023年1月15日下午2:01 • 技术随笔 • 阅读 227

在使用 HashSet 或 HashMap 时，有时候会发现：无序加入若干键值对，遍历 keySet 发现，似乎按照一定的顺序返回了，并不是按照我们存储的顺序。具体原因分析如下。

key 为 Integer

HashMap 先计算出 key 的 hash 值，再通过 hash & (length – 1) = index 得到具体插入位置的。

如果 key 是 Integer，其 hash 值计算方式为：

public int hashCode() {
    return value; //value即为Integer本身
}

可以看到是直接返回 Integer 本身的，如果 key 数值小于等于 15，则 hash 值为 key，计算的 index 同样也为 key，最后遍历 keySet 看上去就像是排过序的。

如果 key 数值大于 15，且 HashMap 没有扩容，容量依旧为 16，大于 15 的数字的 hash 值计算得到的 index 也在 0~15 内，此时看上去就是乱序的。

key 为 String

如果 key 是 String，其 hash 值计算方式为：

public int hashCode() {
    int h = hash;     //默认为0
    if (h == 0 && value.length > 0) {
        char val[] = value;    //String对象的字符数组

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];    //使用字符的ASCII码计算
        }
        hash = h;
    }
    return h;
}

若加入一组键值对，键为 “ccc”,“aaa”,“h”,“ddd”，遍历 keySet 会发现是按照 “aaa”,“ccc”,“ddd”,“h” 输出的，看上去像是字典序排序的，其实这些 key 对应的 index 为 3,1,8,4，遍历索引 index 输出，看上去就像是排序了。

综上，key “自动排序”其实是 hash 值的锅。

如何按照输入的顺序输出 key

使用 LinkedHashMap.

如何根据 key 自定义排序

使用 TreeMap

//默认为升序排序
Map<String, String> map = new TreeMap<String, String>(
new Comparator() {
public int compare(String obj1, String obj2) {
//降序
return obj2.compareTo(obj1);
}
});

如何根据 value 自定义排序

Map<String, String> map = new TreeMap<String, String>(); //不一定非得使用TreeMap
map.add... //插入数据

//后处理
//1.转换为list
List<Map.Entry<String,String>> list = new ArrayList<Map.Entry<String,String>>(map.entrySet());
//2.Collections进行排序
Collections.sort(list,new Comparator<Map.Entry<String,String>>() {
    
    public int compare(Entry<String, String> o1,
                       Entry<String, String> o2) {
        //升序
        return o1.getValue().compareTo(o2.getValue());
    }

});