Java中如何快速移除Map中指定id的自定义类Key对应的元素？

核心思路 #

要实现最快删除，必须避免全表遍历的*O(n)复杂度，利用HashMapremove()方法的O(1)*时间复杂度特性，核心前提是保证HashMap可以正确匹配到id相同的Example对象作为key。

最优方案（时间复杂度O(1)，最快实现） #

题目明确说明id是Example类的唯一值，我们只需要让Example类的equals()和hashCode()方法仅基于id字段计算即可，只要两个Example对象的id相同，HashMap就会判定为同一个key。

步骤1：调整Example类的equals和hashCode生成规则 #

示例中用了Lombok的@Data注解，默认会基于所有字段生成equals和hashCode，我们可以通过注解配置仅用id生成：

@Data
@EqualsAndHashCode(onlyExplicitlyIncluded = true)
public static class Example {
    // 唯一键
    @EqualsAndHashCode.Include
    int    id;
    Object filed;
}

如果不使用Lombok，手动重写两个方法即可：

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Example example = (Example) o;
    return id == example.id;
}

@Override
public int hashCode() {
    return Objects.hash(id);
}

步骤2：直接构造临时key调用remove删除 #

// 构造仅id为1的临时key对象，不需要匹配其他字段值
Example keyToRemove = new Example();
keyToRemove.setId(1);
// 直接删除，时间复杂度O(1)
map.remove(keyToRemove);

次优方案（无法修改Example类时使用，时间复杂度O(n)） #

如果因为业务限制不能修改Example类的equals和hashCode实现，只能遍历entrySet匹配id后删除，因为id唯一，找到后可直接终止遍历减少损耗：

Iterator<Map.Entry<Example, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Example, Object> entry = iterator.next();
    if (entry.getKey().getId() == 1) {
        iterator.remove();
        break; // 匹配到唯一id后直接退出，减少不必要遍历
    }
}

内容的提问来源于stack exchange，提问作者anan.kun