Collections

HashMap: 衝突は処理できるがequalsとhashCodeの不整合は検索を壊す

同じhashCodeのキーは共存できますが、equalsがtrueなのにhashCodeが違うキーでは登録済みの値を検索できません。

Java 8+

pitfallmaphashcodeequalscollections

01 / 01 proof

SourceHashMapContracts.java

Java 21

package examples.map;

import java.util.HashMap;
import java.util.Map;

public final class HashMapContracts {
  private HashMapContracts() {}

  public static Map<CollisionKey, String> valuesWithCollidingHashes() {
    Map<CollisionKey, String> values = new HashMap<>();
    values.put(new CollisionKey("alpha"), "A");
    values.put(new CollisionKey("beta"), "B");
    return values;
  }

  public static Map<InconsistentKey, String> valuesWithInconsistentKey(InconsistentKey key) {
    Map<InconsistentKey, String> values = new HashMap<>();
    values.put(key, "stored");
    return values;
  }

  public record CollisionKey(String id) {
    @Override
    public int hashCode() {
      return 7;
    }
  }

  public record InconsistentKey(String id, int hash) {
    @Override
    public boolean equals(Object other) {
      return other instanceof InconsistentKey key && id.equals(key.id);
    }

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

Source✓Test

TestHashMapContractsTest.java

Java 21

package examples.map;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;

import org.junit.jupiter.api.Test;

class HashMapContractsTest {
  @Test
  void 同じhashCodeでもequalsが異なるキーは別の値として保存できる() {
    var values = HashMapContracts.valuesWithCollidingHashes();

    assertEquals(2, values.size());
    assertEquals("A", values.get(new HashMapContracts.CollisionKey("alpha")));
    assertEquals("B", values.get(new HashMapContracts.CollisionKey("beta")));
  }

  @Test
  void equalsがtrueでもhashCodeが違うキーでは登録済みの値を検索できない() {
    var values =
        HashMapContracts.valuesWithInconsistentKey(new HashMapContracts.InconsistentKey("same", 1));

    assertFalse(values.containsKey(new HashMapContracts.InconsistentKey("same", 2)));
  }
}

01Assertion

このテストで確認できること

同じhashCodeでもequalsが異なるキーは別の値として保存できる
equalsがtrueでもhashCodeが違うキーではcontainsKeyがfalseになる

HashMapの衝突は通常の動作です。一方でequalsがtrueなら同じhashCodeを返す契約を破ると、Mapは同じ値として検索できません。

OBSERVED RESULT

expected: colliding keys size → 2
actual:   2
expected: inconsistent key contains → false
actual:   false

View source on GitHub ↗View source on GitHub ↗