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

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

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を用いることは出来ないのです。¹

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

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

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

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)の順番でソートする必要があります。そうすれば、部分集合における要素の順番は気にしなくてもよくなるはずです。
具体的には以下のような実装になります。²

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))を用いることで解決できると考えられます。

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をとって、これを

struct MyHashSet(HashSet, u64);

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

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

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