[Rust] HashMap が `trait Hash` を実装しない理由

たとえば、Rustの`HashMap`を使って、整数の部分集合から整数に対する写像を定義することを考えます。この時、

```rs
let mut m: HashMap<HashSet<i32>, i32> = HashMap::new();
m.insert(vec![1, 2, 3].into_iter().collect(), 123);
m.insert(vec![4, 5, 6].into_iter().collect(), 456);
```

とやりたくなりますが、じつはこのコードは動きません。なぜなら

- `HashMap`のKeyは`trait Hash`を実装している必要がある
- `HashMap`及び`HashSet`自体は`trait Hash`を実装していない

ため、この例のように`HashMap<>`のKeyとして`HashSet`を用いることは出来ないのです。[^1]

[^1]: この例のように、部分集合の要素が`trait Ord`を実装している場合は、`HashSet`ではなく`BTreeMap`を使用すればよぃです。しかしながら、`trait Ord`を実装しているという制約は強すぎる仮定であると感じます。

ここでは、その理由を考えます。

# `HashMap`, `HashSet` には順番という概念がない

ここで、`HashMap`に`trait Hash`を実装することを考えます。例えば`&[T]`の場合、`trait Hash`の実装は以下のようになります。

```rust
fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
where
	Self: Sized,
{
	for piece in data {
		piece.hash(state);
	}
}
impl<T: Hash> Hash for [T] {
	fn hash<H: Hasher>(&self, state: &mut H) {
		self.len().hash(state);
		Hash::hash_slice(self, state)
	}
}
```

すなわち、`hash()`という関数の内部で、スライスの各要素`piece`に対して`piece.hash(&mut state)`が実行されています。

同じことを`HashMap`でもやればいいと思うわけですが、ここで問題となるのが`HashMap`には順序が存在しないということです。すなわち、部分集合の要素A, B, Cがそれぞれ一般に違うハッシュ値を与えるという前提で、部分集合(A, B, C)と(A, C, B)が同じハッシュ値をとらなければならないのです。

これを解決するためには、`HashMap`のエントリ(`(Key, Value)`の組合せ)を、Keyのハッシュ値(`u64`)の順番でソートする必要があります。そうすれば、部分集合における要素の順番は気にしなくてもよくなるはずです。
具体的には以下のような実装になります。[^2]

[^2]: 以下では標準ライブラリにおいて定義された`trait Hash`を`HashMap`に実装していますが、実際は標準ライブラリ内に書かなければなりません。

```rust
impl<K, V, S> Hash for HashMap<K, V, S>
where
	K: Hash,
	V: Hash,	// <- HashMapにHashを実装するため、新たに課した型制約
{
	fn hash<H: Hasher>(&self, state: &mut H) {
		let mut v = self
			.iter()
			.map(|(key, val)| {
				let mut st = self.hasher.build_hasher();
				key.hash(&mut st);
				(st.finish(), key, val)
			})
			.collect::<Vec<_>>();
		v.sort_by_key(|(h, _, _)| h);
		for (h, key, val) in v.iter() {
			key.hash(state);
			val.hash(state);
		}
	}
}
```

しかしながら、この実装には以下の問題があります。

1. `hash()`の中でソートを実行している。`Rust`のソートはマージソートなので`O(n log n)`掛かります。
2. `k1 == k2 => hash(k1) == hash(k2)`は成り立ちますが、逆は成り立ちません。

1については、`hash()`は本来軽量な処理であるべきなので、`O(n)`で終わるようにすべきです。
2については、上のプログラムにおいて暗黙のうちに`hash(k1) == hash(k2) => k1 == k2`を仮定してしまっています。

例えば、`{k1 => v1, k2 => v2}`と`{k2 => v2, k1 => v1}`について考えます。ここで、`self.hasher.build_hasher()`によって生成される`Hasher`を`h1()`、引数`state`によって与えられる`Hasher`を`h2()`とします。また、`h1(k1) == h1(k2)`かつ`k1 != k2`が成り立っているとします。この場合、`hash()`内のソートでは`h1(k1) == h1(k2)`のため並び替えは発生しません。(ここでのソートは安定ソートである)よって、1つ目の`HashMap`では`h2(k1), h2(v1), h2(k2), h2(v2)`の順、2つ目の`HashMap`では`h2(k2), h2(v2), h2(k1), h2(v1)`の順にハッシュが記録されます。ハッシュ値の記録される順番が異なるのでこれら2つの`HashMap`では異なるハッシュが生成されることになります。

このように、本来イコールであるはずの2つの`HashMap`が異なるハッシュ値を持ってしまいました。

# `HashSet`の場合

`HashMap`の場合、Keyが`trait Ord`を実装していない限りこの問題を解決するのは本質的に不可能です。一方、`HashSet`の場合は、`h2(key)`を用いるのではなく`h2(h1(key))`を用いることで解決できると考えられます。

```rust
impl<T, S> Hash for HashSet<T, S>
where
	T: Hash,
{
	fn hash<H: Hasher>(&self, state: &mut H) {
		let mut v = self
			.iter()
			.map(|val| {
				let mut st = self.hasher.build_hasher();
				val.hash(&mut st);
				st.finish()
			})
			.collect::<Vec<_>>();
		v.sort();
		for h in v.iter() {
			h.hash(state);
		}
	}
}
```

しかしこれでは依然として`sort()`を実行しているため`O(n log n)`掛かります。これを解決するためには、要素を`insert`するときに値のhashをとって、これを

```rs
struct MyHashSet(HashSet, u64);
```

のように定義した`u64`の方にxorすればよいのではないでしょうか(多少hashが弱くなるかもしれませんが)。
そうすれば`HashSet`のハッシュを得るときはその`u64`の値を出してやればいいでしょう。
(もちろんremoveするときもxorする)