为何LinkedHashSet计算容器哈希码时不考虑元素顺序？

我尝试将LinkedHashSet作为HashMap的键使用，但发现不同元素顺序的集合被Map视为相同的键，最终导致后续put操作覆盖了之前的值。

问题代码 #

Map<LinkedHashSet<String>, Integer> ballotsAsSets = new HashMap<>();
for (Map.Entry<List<String>, Integer> e : ballots.entrySet()) {
    LinkedHashSet<String> newKey = new LinkedHashSet<>(e.getKey());
    System.out.println("key = " + newKey + ", hash = " + newKey.hashCode());
    ballotsAsSets.put(newKey, e.getValue());
}

运行输出 #

ballots = {[A, B, C]=1, [B, A, C]=3, [A, C, B]=1}
key = [A, B, C], hash = 198
key = [B, A, C], hash = 198
key = [A, C, B], hash = 198

原因分析 #

LinkedHashSet继承自HashSet，而HashSet的hashCode()实现逻辑是累加所有元素的hashCode值，完全不考虑元素的存储顺序；同时LinkedHashSet的equals()方法继承自AbstractSet，仅判断两个集合的元素是否完全一致（不校验顺序）。

HashMap判断键是否相等的逻辑是：先比较hashCode是否一致，若一致再调用equals()方法。因此元素相同但顺序不同的LinkedHashSet，会被HashMap判定为同一个键，后续put操作会覆盖之前存入的值。

解决方案：自定义有序Set类重写hashCode和equals #

创建一个继承LinkedHashSet的子类，重写hashCode()和equals()方法，让它们考虑元素的顺序：

import java.util.LinkedHashSet;
import java.util.Iterator;

public class OrderedLinkedHashSet<E> extends LinkedHashSet<E> {

    @Override
    public int hashCode() {
        int hashCode = 1;
        for (E element : this) {
            hashCode = 31 * hashCode + (element == null ? 0 : element.hashCode());
        }
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof OrderedLinkedHashSet)) {
            return false;
        }
        OrderedLinkedHashSet<?> otherSet = (OrderedLinkedHashSet<?>) obj;
        if (this.size() != otherSet.size()) {
            return false;
        }

        Iterator<E> thisIterator = this.iterator();
        Iterator<?> otherIterator = otherSet.iterator();
        while (thisIterator.hasNext() && otherIterator.hasNext()) {
            E thisElement = thisIterator.next();
            Object otherElement = otherIterator.next();
            if (!(thisElement == null ? otherElement == null : thisElement.equals(otherElement))) {
                return false;
            }
        }
        return !thisIterator.hasNext() && !otherIterator.hasNext();
    }
}

修改原代码中的LinkedHashSet为这个自定义类即可：

Map<OrderedLinkedHashSet<String>, Integer> ballotsAsSets = new HashMap<>();
for (Map.Entry<List<String>, Integer> e : ballots.entrySet()) {
    OrderedLinkedHashSet<String> newKey = new OrderedLinkedHashSet<>(e.getKey());
    System.out.println("key = " + newKey + ", hash = " + newKey.hashCode());
    ballotsAsSets.put(newKey, e.getValue());
}

此时不同顺序的集合会生成不同的hashCode，且equals方法会校验元素顺序，不会再被HashMap视为同一个键，put操作也不会覆盖原有值。

内容的提问来源于stack exchange，提问作者Ihor M.