Improve `make_hash` function

The `make_hash` function is used to prevent hashes of non-empty
buckets to collide with `EMPTY_HASH = 0u64`. Ideally this function
also preserve the uniform distribution of hashes and is cheap to
compute.

The new implementation reduces the input hash size by one bit, simply
by setting the most significant bit. This obviously prevent output
hashes to collide with `EMPTY_HASH` and guarantees that the uniform
distribution is preserved. Moreover, the new function is simpler (no
comparisons, just an OR) and (under the same assumptions as the old
function, i.e. only the least significant bit will contribute to the
bucket index) no additional collisions are caused.

1 files changed, 6 insertions, 8 deletions

diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index a687ba3da8d..85298665021 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -1,4 +1,4 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2014-2015 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -139,13 +139,11 @@ impl SafeHash {
 /// This function wraps up `hash_keyed` to be the only way outside this
 /// module to generate a SafeHash.
 pub fn make_hash<Sized? T: Hash<S>, S, H: Hasher<S>>(hasher: &H, t: &T) -> SafeHash {
-    match hasher.hash(t) {
-        // This constant is exceedingly likely to hash to the same
-        // bucket, but it won't be counted as empty! Just so we can maintain
-        // our precious uniform distribution of initial indexes.
-        EMPTY_BUCKET => SafeHash { hash: 0x8000_0000_0000_0000 },
-        h            => SafeHash { hash: h },
-    }
+    // We need to avoid 0u64 in order to prevent collisions with
+    // EMPTY_HASH. We can maintain our precious uniform distribution
+    // of initial indexes by unconditionally setting the MSB,
+    // effectively reducing 64-bits hashes to 63 bits.
+    SafeHash { hash: 0x8000_0000_0000_0000 | hasher.hash(t) }
 }
 
 // `replace` casts a `*u64` to a `*SafeHash`. Since we statically