{
"$type": "site.standard.document",
"bskyPostRef": {
"cid": "bafyreiafuczb64mhnpxekz2ttnqmlghefsi3oroy2q6uwvhhtkfazj67k4",
"uri": "at://did:plc:ivbknywyskln22er3nkssdhl/app.bsky.feed.post/3mo5mmjoowht2"
},
"path": "/t/the-hashtable-problem-a-litmus-test-for-external-impl-proposals/24396#post_1",
"publishedAt": "2026-06-13T05:21:12.000Z",
"site": "https://internals.rust-lang.org",
"tags": [
"The \"Hashtable Problem\" from nikomatsakis at 2011-12",
"@nikomatsakis 2017-2",
"My Named impl draft",
"Named impl with Implementation Selection Variant",
"[Pre-RFC] Selectable Trait Implementations",
"[Pre-RFC] Scoped `impl Trait for Type`"
],
"textContent": "# The Hashtable Problem: A Litmus Test for External Impl Proposals\n\nAny proposal aiming to relax the orphan rule or enable external trait implementations must address the hashtable problem.\n\n## Explain\n\nThe earliest article is The \"Hashtable Problem\" from nikomatsakis at 2011-12:\n\n> There is a danger with typeclasses only on functions because they permit a lack of coherence. This danger is particularly acute with collections, where the definition of a particular interface---such as hashable or ord---may be used in structuring the data structure. This renders the data structure corrupt when used with a different implementation.\n\nAlso there is a comment from @nikomatsakis 2017-2:\n\n> We called it the hashtable problem because – imagine you had a hashtable with keys to type K that is built up using one impl of Hash, but then you pass that hashtable to another module, where a distinct Hash impl is in scope. It’s going to be pandemonium. What that e-mail proposed was to solve this by making the impl “part of the type”, in a sense. At the end of the day it seemed like a lot of complexity and we opted against it – but there are real costs. I’m not sure of the best fix here.\n\nThe problem affects:\n\n * struct `HashMap` with trait `Hash`\n * struct `BTreeMap` with trait `Ord`\n\n\n\n## Sample codes\n\n 1. example in typical scoped impl\n\n\n\n\n let mut map = HashMap::<i32, &'static str>::new();\n map.insert(42, \"the answer to the universe\"); // default hash of i32\n {\n use AnotherHashForI32 as impl Hash for i32;\n let found = map.get(&42); // a different hash of i32, can we find the answer?\n }\n\n\n 2. example in typical named impl\n\n\n\n\n let mut map = HashMap::<i32, &'static str>::new();\n map.insert(42, \"the answer to the universe\"); // default hash of i32\n\n let altmap = &map as &HashMap<i32 + Hash use AnotherHashForI32, &'static str>;\n let found = altmap.get(&(42 as (i32 + Hash use AnotherHashForI32))); // a different hash of i32, can we find the answer?\n\n\n## Where is the problem from?\n\n\n let key = 42;\n let mut map = HashMap::<i32, &'static str>::new();\n map.insert(key, \"the answer to the universe\"); // default hash of i32\n let found = map.get(&key); // ok\n\n let altkey = key as (i32 + Hash use AnotherHashForI32);\n let mut altmap = HashMap::<i32 + Hash use AnotherHashForI32, &'static str>::new();\n altmap.insert(altkey, \"the answer to the universe\"); // a different hash of i32\n let found = altmap.get(&altkey); // ok\n\n\nThe code above works fine.\n\nThe problem is from the type casting of the container:\n\n\n let altmap = &map as &HashMap<i32 + Hash use AnotherHashForI32, &'static str>;\n\n\nWith scoped impl, there are also implicitly type casting:\n\n\n let mut map = HashMap::<i32, &'static str>::new();\n map.insert(42, \"the answer to the universe\");\n {\n use AnotherHashForI32 as impl Hash for i32;\n let found = map.get(&42); // `map` is casted, and `&42` is casted\n }\n\n\n## Solutions\n\n 1. the strictest way\nOnly allow casting of `T <-> T + Impl`, `&T <-> &(T + Impl)`, and `&mut T <-> &mut(T + Impl)`\nThis is just a better newtype pattern.\n\n 2. the most detailed way\nDisable implementation casting from `HashMap<K + Hash use HashImpl1, _>` to `HashMap<K + Hash use HashImpl2, _>`\n\n pub struct HashMap<#[disable_impl_casting(Hash)]K: Hash, V> {}\n\n\nUnsolved problems:\n\n * inner different implementation `HashMap<(i32 + Hash use HashImpl1, i32), _>`\n * indirect implements\n 3. disable implementation casting on `HashMap`\n\n #[disable_impl_casting]\n pub struct HashMap<K, V> {}\n\n\n 4. disable implementation casting on `HashMap` with `K`\n\n pub struct HashMap<#[disable_impl_casting(all)]K: Hash, V> {}\n\n\n 5. disable external impl of `Hash` In My Named impl draft, this is selected:\n\n #[disable_named_impl(exist_default)]\n pub trait Hash {}\n\n\nUnsolved problems:\n\n * indirect implementation\n\n\n\n## Progressive Hashtable Violations via External Impls\n\n 1. different implementation the Key with a different `Hash` implementation\n\n impl Hash for i32 use AlterHash {\n fn hash<H: Hasher>(&self, state: &mut H) {\n self.hash(state);\n 8.hash(state);\n }\n }\n\n let map = HashMap::<i32, i32>::new();\n map.insert(42, 42);\n\n type AltKey = i32 + Hash use AlterHash;\n let altmap = &map as &HashMap<AltKey, i32>;\n let altkey = 42 as AltKey;\n let found = altmap.get(&altkey);\n\n\n 2. inner different implementation the inner type of Key with a different `Hash` implementation\n\n impl Hash for i32 use AlterHash {\n fn hash<H: Hasher>(&self, state: &mut H) {\n self.hash(state);\n 8.hash(state);\n }\n }\n\n let map = HashMap::<(i32,), i32>::new();\n map.insert((42,), 42);\n\n type AltKey = (i32 + Hash use AlterHash,);\n let altmap = &map as &HashMap<AltKey, i32>;\n let altkey = (42,) as AltKey;\n let found = altmap.get(&altkey);\n\n\n 3. indirect implementation the inner type of Key with a different `Display` implementation but affects `Hash` of Key\n\n struct Key<T: Display>(T);\n impl<T: Display> Hash for Key<T> {\n fn hash<H: Hasher>(&self, state: &mut H) {\n format!(\"{}\", self.0).hash(state);\n }\n }\n\n impl Display for i32 use AlterDisplay {\n fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {\n write!(f, \"I32AlterDisplay\")\n }\n }\n\n let map = HashMap::<Key<i32>, i32>::new();\n map.insert(Key(42), 42);\n\n type AltKey = Key<i32 + Display use AlterDisplay>;\n let altmap = &map as &HashMap<AltKey, i32>;\n let altkey = Key(42) as AltKey;\n let found = altmap.get(&altkey);\n\n\n\n\n\n## Analyzing Whether Existing Forum Proposals Can Solve the Three Issues Above\n\n * Named impl with Implementation Selection Variant TODO\n * [Pre-RFC] Selectable Trait Implementations TODO\n * [Pre-RFC] Scoped `impl Trait for Type` TODO\n\n",
"title": "The Hashtable Problem: A Litmus Test for External Impl Proposals"
}