std: Stabilize the std::hash module

This commit aims to prepare the `std::hash` module for alpha by formalizing its
current interface whileholding off on adding `#[stable]` to the new APIs.  The
current usage with the `HashMap` and `HashSet` types is also reconciled by
separating out composable parts of the design. The primary goal of this slight
redesign is to separate the concepts of a hasher's state from a hashing
algorithm itself.

The primary change of this commit is to separate the `Hasher` trait into a
`Hasher` and a `HashState` trait. Conceptually the old `Hasher` trait was
actually just a factory for various states, but hashing had very little control
over how these states were used. Additionally the old `Hasher` trait was
actually fairly unrelated to hashing.

This commit redesigns the existing `Hasher` trait to match what the notion of a
`Hasher` normally implies with the following definition:

    trait Hasher {
        type Output;
        fn reset(&mut self);
        fn finish(&self) -> Output;
    }

This `Hasher` trait emphasizes that hashing algorithms may produce outputs other
than a `u64`, so the output type is made generic. Other than that, however, very
little is assumed about a particular hasher. It is left up to implementors to
provide specific methods or trait implementations to feed data into a hasher.

The corresponding `Hash` trait becomes:

    trait Hash<H: Hasher> {
        fn hash(&self, &mut H);
    }

The old default of `SipState` was removed from this trait as it's not something
that we're willing to stabilize until the end of time, but the type parameter is
always required to implement `Hasher`. Note that the type parameter `H` remains
on the trait to enable multidispatch for specialization of hashing for
particular hashers.

Note that `Writer` is not mentioned in either of `Hash` or `Hasher`, it is
simply used as part `derive` and the implementations for all primitive types.

With these definitions, the old `Hasher` trait is realized as a new `HashState`
trait in the `collections::hash_state` module as an unstable addition for
now. The current definition looks like:

    trait HashState {
        type Hasher: Hasher;
        fn hasher(&self) -> Hasher;
    }

The purpose of this trait is to emphasize that the one piece of functionality
for implementors is that new instances of `Hasher` can be created.  This
conceptually represents the two keys from which more instances of a
`SipHasher` can be created, and a `HashState` is what's stored in a
`HashMap`, not a `Hasher`.

Implementors of custom hash algorithms should implement the `Hasher` trait, and
only hash algorithms intended for use in hash maps need to implement or worry
about the `HashState` trait.

The entire module and `HashState` infrastructure remains `#[unstable]` due to it
being recently redesigned, but some other stability decision made for the
`std::hash` module are:

* The `Writer` trait remains `#[experimental]` as it's intended to be replaced
  with an `io::Writer` (more details soon).
* The top-level `hash` function is `#[unstable]` as it is intended to be generic
  over the hashing algorithm instead of hardwired to `SipHasher`
* The inner `sip` module is now private as its one export, `SipHasher` is
  reexported in the `hash` module.

And finally, a few changes were made to the default parameters on `HashMap`.

* The `RandomSipHasher` default type parameter was renamed to `RandomState`.
  This renaming emphasizes that it is not a hasher, but rather just state to
  generate hashers. It also moves away from the name "sip" as it may not always
  be implemented as `SipHasher`. This type lives in the
  `std::collections::hash_map` module as `#[unstable]`

* The associated `Hasher` type of `RandomState` is creatively called...
  `Hasher`! This concrete structure lives next to `RandomState` as an
  implemenation of the "default hashing algorithm" used for a `HashMap`. Under
  the hood this is currently implemented as `SipHasher`, but it draws an
  explicit interface for now and allows us to modify the implementation over
  time if necessary.

There are many breaking changes outlined above, and as a result this commit is
a:

[breaking-change]

14 files changed, 363 insertions, 276 deletions

diff --git a/src/libstd/bitflags.rs b/src/libstd/bitflags.rs
index 5764962b51b..8dc41368e7f 100644
--- a/src/libstd/bitflags.rs
+++ b/src/libstd/bitflags.rs
@@ -273,7 +273,7 @@ macro_rules! bitflags {
 #[cfg(test)]
 #[allow(non_upper_case_globals)]
 mod tests {
-    use hash;
+    use hash::{self, SipHasher};
     use option::Option::{Some, None};
 
     bitflags! {
@@ -467,9 +467,9 @@ mod tests {
     fn test_hash() {
       let mut x = Flags::empty();
       let mut y = Flags::empty();
-      assert!(hash::hash(&x) == hash::hash(&y));
+      assert!(hash::hash::<Flags, SipHasher>(&x) == hash::hash::<Flags, SipHasher>(&y));
       x = Flags::all();
       y = FlagABC;
-      assert!(hash::hash(&x) == hash::hash(&y));
+      assert!(hash::hash::<Flags, SipHasher>(&x) == hash::hash::<Flags, SipHasher>(&y));
     }
 }
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 2011c03c773..bf3b4864515 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -19,16 +19,15 @@ use clone::Clone;
 use cmp::{max, Eq, PartialEq};
 use default::Default;
 use fmt::{self, Show};
-use hash::{Hash, Hasher, RandomSipHasher};
+use hash::{self, Hash, SipHasher};
 use iter::{self, Iterator, IteratorExt, FromIterator, Extend, Map};
 use marker::Sized;
 use mem::{self, replace};
 use num::{Int, UnsignedInt};
 use ops::{Deref, FnMut, Index, IndexMut};
-use option::Option;
-use option::Option::{Some, None};
-use result::Result;
-use result::Result::{Ok, Err};
+use option::Option::{self, Some, None};
+use rand::{self, Rng};
+use result::Result::{self, Ok, Err};
 
 use super::table::{
     self,
@@ -44,6 +43,7 @@ use super::table::BucketState::{
     Empty,
     Full,
 };
+use super::state::HashState;
 
 const INITIAL_LOG2_CAP: uint = 5;
 pub const INITIAL_CAPACITY: uint = 1 << INITIAL_LOG2_CAP; // 2^5
@@ -297,9 +297,9 @@ fn test_resize_policy() {
 /// ```
 #[derive(Clone)]
 #[stable]
-pub struct HashMap<K, V, H = RandomSipHasher> {
+pub struct HashMap<K, V, S = RandomState> {
     // All hashes are keyed on these values, to prevent hash collision attacks.
-    hasher: H,
+    hash_state: S,
 
     table: RawTable<K, V>,
 
@@ -439,17 +439,20 @@ impl<K, V, M> SearchResult<K, V, M> {
     }
 }
 
-#[old_impl_check]
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
-    fn make_hash<X: ?Sized + Hash<S>>(&self, x: &X) -> SafeHash {
-        table::make_hash(&self.hasher, x)
+impl<K, V, S, H> HashMap<K, V, S>
+    where K: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
+    fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash<H> {
+        table::make_hash(&self.hash_state, x)
     }
 
     /// Search for a key, yielding the index if it's found in the hashtable.
     /// If you already have the hash for the key lying around, use
     /// search_hashed.
     fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
-        where Q: BorrowFrom<K> + Eq + Hash<S>
+        where Q: BorrowFrom<K> + Eq + Hash<H>
     {
         let hash = self.make_hash(q);
         search_hashed(&self.table, hash, |k| q.eq(BorrowFrom::borrow_from(k)))
@@ -457,7 +460,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 
     fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
-        where Q: BorrowFrom<K> + Eq + Hash<S>
+        where Q: BorrowFrom<K> + Eq + Hash<H>
     {
         let hash = self.make_hash(q);
         search_hashed(&mut self.table, hash, |k| q.eq(BorrowFrom::borrow_from(k)))
@@ -486,7 +489,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 }
 
-impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
+impl<K: Hash<Hasher> + Eq, V> HashMap<K, V, RandomState> {
     /// Create an empty HashMap.
     ///
     /// # Example
@@ -497,9 +500,8 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     /// ```
     #[inline]
     #[stable]
-    pub fn new() -> HashMap<K, V, RandomSipHasher> {
-        let hasher = RandomSipHasher::new();
-        HashMap::with_hasher(hasher)
+    pub fn new() -> HashMap<K, V, RandomState> {
+        Default::default()
     }
 
     /// Creates an empty hash map with the given initial capacity.
@@ -512,14 +514,16 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     /// ```
     #[inline]
     #[stable]
-    pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
-        let hasher = RandomSipHasher::new();
-        HashMap::with_capacity_and_hasher(capacity, hasher)
+    pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomState> {
+        HashMap::with_capacity_and_hash_state(capacity, Default::default())
     }
 }
 
-#[old_impl_check]
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
+impl<K, V, S, H> HashMap<K, V, S>
+    where K: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
     /// Creates an empty hashmap which will use the given hasher to hash keys.
     ///
     /// The creates map has the default initial capacity.
@@ -528,17 +532,17 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// ```
     /// use std::collections::HashMap;
-    /// use std::hash::sip::SipHasher;
+    /// use std::collections::hash_map::RandomState;
     ///
-    /// let h = SipHasher::new();
-    /// let mut map = HashMap::with_hasher(h);
+    /// let s = RandomState::new();
+    /// let mut map = HashMap::with_hash_state(s);
     /// map.insert(1i, 2u);
     /// ```
     #[inline]
     #[unstable = "hasher stuff is unclear"]
-    pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
+    pub fn with_hash_state(hash_state: S) -> HashMap<K, V, S> {
         HashMap {
-            hasher:        hasher,
+            hash_state:    hash_state,
             resize_policy: DefaultResizePolicy::new(),
             table:         RawTable::new(0),
         }
@@ -556,21 +560,22 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     ///
     /// ```
     /// use std::collections::HashMap;
-    /// use std::hash::sip::SipHasher;
+    /// use std::collections::hash_map::RandomState;
     ///
-    /// let h = SipHasher::new();
-    /// let mut map = HashMap::with_capacity_and_hasher(10, h);
+    /// let s = RandomState::new();
+    /// let mut map = HashMap::with_capacity_and_hash_state(10, s);
     /// map.insert(1i, 2u);
     /// ```
     #[inline]
     #[unstable = "hasher stuff is unclear"]
-    pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
+    pub fn with_capacity_and_hash_state(capacity: uint, hash_state: S)
+                                        -> HashMap<K, V, S> {
         let resize_policy = DefaultResizePolicy::new();
         let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
         let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
         assert!(internal_cap >= capacity, "capacity overflow");
         HashMap {
-            hasher:        hasher,
+            hash_state:    hash_state,
             resize_policy: resize_policy,
             table:         RawTable::new(internal_cap),
         }
@@ -1031,7 +1036,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// ```
     #[stable]
     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
-        where Q: Hash<S> + Eq + BorrowFrom<K>
+        where Q: Hash<H> + Eq + BorrowFrom<K>
     {
         self.search(k).map(|bucket| bucket.into_refs().1)
     }
@@ -1054,7 +1059,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// ```
     #[stable]
     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
-        where Q: Hash<S> + Eq + BorrowFrom<K>
+        where Q: Hash<H> + Eq + BorrowFrom<K>
     {
         self.search(k).is_some()
     }
@@ -1080,7 +1085,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// ```
     #[stable]
     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
-        where Q: Hash<S> + Eq + BorrowFrom<K>
+        where Q: Hash<H> + Eq + BorrowFrom<K>
     {
         self.search_mut(k).map(|bucket| bucket.into_mut_refs().1)
     }
@@ -1132,7 +1137,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// ```
     #[stable]
     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
-        where Q: Hash<S> + Eq + BorrowFrom<K>
+        where Q: Hash<H> + Eq + BorrowFrom<K>
     {
         if self.table.size() == 0 {
             return None
@@ -1189,10 +1194,12 @@ fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHas
     }
 }
 
-#[stable]
-#[old_impl_check]
-impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
-    fn eq(&self, other: &HashMap<K, V, H>) -> bool {
+impl<K, V, S, H> PartialEq for HashMap<K, V, S>
+    where K: Eq + Hash<H>, V: PartialEq,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
+    fn eq(&self, other: &HashMap<K, V, S>) -> bool {
         if self.len() != other.len() { return false; }
 
         self.iter().all(|(key, value)|
@@ -1202,12 +1209,18 @@ impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V,
 }
 
 #[stable]
-#[old_impl_check]
-impl<K: Eq + Hash<S>, V: Eq, S, H: Hasher<S>> Eq for HashMap<K, V, H> {}
+impl<K, V, S, H> Eq for HashMap<K, V, S>
+    where K: Eq + Hash<H>, V: Eq,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{}
 
 #[stable]
-#[old_impl_check]
-impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
+impl<K, V, S, H> Show for HashMap<K, V, S>
+    where K: Eq + Hash<H> + Show, V: Show,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "HashMap {{"));
 
@@ -1221,18 +1234,22 @@ impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H>
 }
 
 #[stable]
-#[old_impl_check]
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
-    #[stable]
-    fn default() -> HashMap<K, V, H> {
-        HashMap::with_hasher(Default::default())
+impl<K, V, S, H> Default for HashMap<K, V, S>
+    where K: Eq + Hash<H>,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
+    fn default() -> HashMap<K, V, S> {
+        HashMap::with_hash_state(Default::default())
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<K: Hash<S> + Eq, Q: ?Sized, V, S, H: Hasher<S>> Index<Q> for HashMap<K, V, H>
-    where Q: BorrowFrom<K> + Hash<S> + Eq
+impl<K, Q: ?Sized, V, S, H> Index<Q> for HashMap<K, V, S>
+    where K: Eq + Hash<H>,
+          Q: Eq + Hash<H> + BorrowFrom<K>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
 {
     type Output = V;
 
@@ -1243,9 +1260,11 @@ impl<K: Hash<S> + Eq, Q: ?Sized, V, S, H: Hasher<S>> Index<Q> for HashMap<K, V,
 }
 
 #[stable]
-#[old_impl_check]
-impl<K: Hash<S> + Eq, Q: ?Sized, V, S, H: Hasher<S>> IndexMut<Q> for HashMap<K, V, H>
-    where Q: BorrowFrom<K> + Hash<S> + Eq
+impl<K, V, S, H, Q: ?Sized> IndexMut<Q> for HashMap<K, V, S>
+    where K: Eq + Hash<H>,
+          Q: Eq + Hash<H> + BorrowFrom<K>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
 {
     type Output = V;
 
@@ -1473,19 +1492,26 @@ impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
 }
 
 #[stable]
-#[old_impl_check]
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
-    fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> HashMap<K, V, H> {
+impl<K, V, S, H> FromIterator<(K, V)> for HashMap<K, V, S>
+    where K: Eq + Hash<H>,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
+    fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> HashMap<K, V, S> {
         let lower = iter.size_hint().0;
-        let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
+        let mut map = HashMap::with_capacity_and_hash_state(lower,
+                                                            Default::default());
         map.extend(iter);
         map
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Extend<(K, V)> for HashMap<K, V, H> {
+impl<K, V, S, H> Extend<(K, V)> for HashMap<K, V, S>
+    where K: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
     fn extend<T: Iterator<Item=(K, V)>>(&mut self, mut iter: T) {
         for (k, v) in iter {
             self.insert(k, v);
@@ -1493,6 +1519,64 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Extend<(K, V)> for HashMap<K, V, H> {
     }
 }
 
+
+/// `RandomState` is the default state for `HashMap` types.
+///
+/// A particular instance `RandomState` will create the same instances of
+/// `Hasher`, but the hashers created by two different `RandomState`
+/// instances are unlikely to produce the same result for the same values.
+#[derive(Clone)]
+#[allow(missing_copy_implementations)]
+#[unstable = "hashing an hash maps may be altered"]
+pub struct RandomState {
+    k0: u64,
+    k1: u64,
+}
+
+#[unstable = "hashing an hash maps may be altered"]
+impl RandomState {
+    /// Construct a new `RandomState` that is initialized with random keys.
+    #[inline]
+    pub fn new() -> RandomState {
+        let mut r = rand::thread_rng();
+        RandomState { k0: r.gen(), k1: r.gen() }
+    }
+}
+
+#[unstable = "hashing an hash maps may be altered"]
+impl HashState for RandomState {
+    type Hasher = Hasher;
+    fn hasher(&self) -> Hasher {
+        Hasher { inner: SipHasher::new_with_keys(self.k0, self.k1) }
+    }
+}
+
+#[unstable = "hashing an hash maps may be altered"]
+impl Default for RandomState {
+    #[inline]
+    fn default() -> RandomState {
+        RandomState::new()
+    }
+}
+
+/// A hasher implementation which is generated from `RandomState` instances.
+///
+/// This is the default hasher used in a `HashMap` to hash keys. Types do not
+/// typically declare an ability to explicitly hash into this particular type,
+/// but rather in a `H: hash::Writer` type parameter.
+#[allow(missing_copy_implementations)]
+pub struct Hasher { inner: SipHasher }
+
+impl hash::Writer for Hasher {
+    fn write(&mut self, data: &[u8]) { self.inner.write(data) }
+}
+
+impl hash::Hasher for Hasher {
+    type Output = u64;
+    fn reset(&mut self) { self.inner.reset() }
+    fn finish(&self) -> u64 { self.inner.finish() }
+}
+
 #[cfg(test)]
 mod test_map {
     use prelude::v1::*;
diff --git a/src/libstd/collections/hash/mod.rs b/src/libstd/collections/hash/mod.rs
index ee3fc1e6ac3..47e300af269 100644
--- a/src/libstd/collections/hash/mod.rs
+++ b/src/libstd/collections/hash/mod.rs
@@ -11,6 +11,7 @@
 //! Unordered containers, implemented as hash-tables
 
 mod bench;
+mod table;
 pub mod map;
 pub mod set;
-mod table;
+pub mod state;
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index f66e5384942..4003d3addf1 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -17,12 +17,13 @@ use core::marker::Sized;
 use default::Default;
 use fmt::Show;
 use fmt;
-use hash::{Hash, Hasher, RandomSipHasher};
+use hash::{self, Hash};
 use iter::{Iterator, IteratorExt, FromIterator, Map, Chain, Extend};
 use ops::{BitOr, BitAnd, BitXor, Sub};
 use option::Option::{Some, None, self};
 
-use super::map::{self, HashMap, Keys, INITIAL_CAPACITY};
+use super::map::{self, HashMap, Keys, INITIAL_CAPACITY, RandomState, Hasher};
+use super::state::HashState;
 
 // Future Optimization (FIXME!)
 // =============================
@@ -90,11 +91,11 @@ use super::map::{self, HashMap, Keys, INITIAL_CAPACITY};
 /// ```
 #[derive(Clone)]
 #[stable]
-pub struct HashSet<T, H = RandomSipHasher> {
-    map: HashMap<T, (), H>
+pub struct HashSet<T, S = RandomState> {
+    map: HashMap<T, (), S>
 }
 
-impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
+impl<T: Hash<Hasher> + Eq> HashSet<T, RandomState> {
     /// Create an empty HashSet.
     ///
     /// # Example
@@ -105,7 +106,7 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
     /// ```
     #[inline]
     #[stable]
-    pub fn new() -> HashSet<T, RandomSipHasher> {
+    pub fn new() -> HashSet<T, RandomState> {
         HashSet::with_capacity(INITIAL_CAPACITY)
     }
 
@@ -120,13 +121,16 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
     /// ```
     #[inline]
     #[stable]
-    pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
+    pub fn with_capacity(capacity: uint) -> HashSet<T, RandomState> {
         HashSet { map: HashMap::with_capacity(capacity) }
     }
 }
 
-#[old_impl_check]
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
+impl<T, S, H> HashSet<T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
     /// Creates a new empty hash set which will use the given hasher to hash
     /// keys.
     ///
@@ -136,16 +140,16 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     ///
     /// ```
     /// use std::collections::HashSet;
-    /// use std::hash::sip::SipHasher;
+    /// use std::collections::hash_map::RandomState;
     ///
-    /// let h = SipHasher::new();
-    /// let mut set = HashSet::with_hasher(h);
+    /// let s = RandomState::new();
+    /// let mut set = HashSet::with_hash_state(s);
     /// set.insert(2u);
     /// ```
     #[inline]
     #[unstable = "hasher stuff is unclear"]
-    pub fn with_hasher(hasher: H) -> HashSet<T, H> {
-        HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
+    pub fn with_hash_state(hash_state: S) -> HashSet<T, S> {
+        HashSet::with_capacity_and_hash_state(INITIAL_CAPACITY, hash_state)
     }
 
     /// Create an empty HashSet with space for at least `capacity`
@@ -160,16 +164,19 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     ///
     /// ```
     /// use std::collections::HashSet;
-    /// use std::hash::sip::SipHasher;
+    /// use std::collections::hash_map::RandomState;
     ///
-    /// let h = SipHasher::new();
-    /// let mut set = HashSet::with_capacity_and_hasher(10u, h);
+    /// let s = RandomState::new();
+    /// let mut set = HashSet::with_capacity_and_hash_state(10u, s);
     /// set.insert(1i);
     /// ```
     #[inline]
     #[unstable = "hasher stuff is unclear"]
-    pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashSet<T, H> {
-        HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
+    pub fn with_capacity_and_hash_state(capacity: uint, hash_state: S)
+                                        -> HashSet<T, S> {
+        HashSet {
+            map: HashMap::with_capacity_and_hash_state(capacity, hash_state),
+        }
     }
 
     /// Returns the number of elements the set can hold without reallocating.
@@ -300,7 +307,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff, [4i].iter().map(|&x| x).collect());
     /// ```
     #[stable]
-    pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> Difference<'a, T, H> {
+    pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
         Difference {
             iter: self.iter(),
             other: other,
@@ -328,8 +335,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff1, [1i, 4].iter().map(|&x| x).collect());
     /// ```
     #[stable]
-    pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
-        -> SymmetricDifference<'a, T, H> {
+    pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>)
+        -> SymmetricDifference<'a, T, S> {
         SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
     }
 
@@ -351,7 +358,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff, [2i, 3].iter().map(|&x| x).collect());
     /// ```
     #[stable]
-    pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>) -> Intersection<'a, T, H> {
+    pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
         Intersection {
             iter: self.iter(),
             other: other,
@@ -376,7 +383,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
     /// ```
     #[stable]
-    pub fn union<'a>(&'a self, other: &'a HashSet<T, H>) -> Union<'a, T, H> {
+    pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
         Union { iter: self.iter().chain(other.difference(self)) }
     }
 
@@ -452,7 +459,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// ```
     #[stable]
     pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
-        where Q: BorrowFrom<T> + Hash<S> + Eq
+        where Q: BorrowFrom<T> + Hash<H> + Eq
     {
         self.map.contains_key(value)
     }
@@ -475,7 +482,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(a.is_disjoint(&b), false);
     /// ```
     #[stable]
-    pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
+    pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
         self.iter().all(|v| !other.contains(v))
     }
 
@@ -496,7 +503,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(set.is_subset(&sup), false);
     /// ```
     #[stable]
-    pub fn is_subset(&self, other: &HashSet<T, H>) -> bool {
+    pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
         self.iter().all(|v| other.contains(v))
     }
 
@@ -521,7 +528,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// ```
     #[inline]
     #[stable]
-    pub fn is_superset(&self, other: &HashSet<T, H>) -> bool {
+    pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
         other.is_subset(self)
     }
 
@@ -562,16 +569,19 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// ```
     #[stable]
     pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
-        where Q: BorrowFrom<T> + Hash<S> + Eq
+        where Q: BorrowFrom<T> + Hash<H> + Eq
     {
         self.map.remove(value).is_some()
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
-    fn eq(&self, other: &HashSet<T, H>) -> bool {
+impl<T, S, H> PartialEq for HashSet<T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
+    fn eq(&self, other: &HashSet<T, S>) -> bool {
         if self.len() != other.len() { return false; }
 
         self.iter().all(|key| other.contains(key))
@@ -579,12 +589,18 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
 }
 
 #[stable]
-#[old_impl_check]
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
+impl<T, S, H> Eq for HashSet<T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{}
 
 #[stable]
-#[old_impl_check]
-impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
+impl<T, S, H> fmt::Show for HashSet<T, S>
+    where T: Eq + Hash<H> + fmt::Show,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "HashSet {{"));
 
@@ -598,19 +614,25 @@ impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
 }
 
 #[stable]
-#[old_impl_check]
-impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
-    fn from_iter<I: Iterator<Item=T>>(iter: I) -> HashSet<T, H> {
+impl<T, S, H> FromIterator<T> for HashSet<T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
+    fn from_iter<I: Iterator<Item=T>>(iter: I) -> HashSet<T, S> {
         let lower = iter.size_hint().0;
-        let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
+        let mut set = HashSet::with_capacity_and_hash_state(lower, Default::default());
         set.extend(iter);
         set
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Extend<T> for HashSet<T, H> {
+impl<T, S, H> Extend<T> for HashSet<T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
+{
     fn extend<I: Iterator<Item=T>>(&mut self, mut iter: I) {
         for k in iter {
             self.insert(k);
@@ -619,21 +641,26 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> Extend<T> for HashSet<T, H> {
 }
 
 #[stable]
-#[old_impl_check]
-impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
+impl<T, S, H> Default for HashSet<T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
     #[stable]
-    fn default() -> HashSet<T, H> {
-        HashSet::with_hasher(Default::default())
+    fn default() -> HashSet<T, S> {
+        HashSet::with_hash_state(Default::default())
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
-BitOr<&'b HashSet<T, H>> for &'a HashSet<T, H> {
-    type Output = HashSet<T, H>;
+impl<'a, 'b, T, S, H> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S>
+    where T: Eq + Hash<H> + Clone,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
+    type Output = HashSet<T, S>;
 
-    /// Returns the union of `self` and `rhs` as a new `HashSet<T, H>`.
+    /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
     ///
     /// # Examples
     ///
@@ -653,18 +680,20 @@ BitOr<&'b HashSet<T, H>> for &'a HashSet<T, H> {
     /// }
     /// assert_eq!(i, expected.len());
     /// ```
-    fn bitor(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
+    fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
         self.union(rhs).cloned().collect()
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
-BitAnd<&'b HashSet<T, H>> for &'a HashSet<T, H> {
-    type Output = HashSet<T, H>;
+impl<'a, 'b, T, S, H> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S>
+    where T: Eq + Hash<H> + Clone,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
+    type Output = HashSet<T, S>;
 
-    /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, H>`.
+    /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
     ///
     /// # Examples
     ///
@@ -684,18 +713,20 @@ BitAnd<&'b HashSet<T, H>> for &'a HashSet<T, H> {
     /// }
     /// assert_eq!(i, expected.len());
     /// ```
-    fn bitand(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
+    fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
         self.intersection(rhs).cloned().collect()
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
-BitXor<&'b HashSet<T, H>> for &'a HashSet<T, H> {
-    type Output = HashSet<T, H>;
+impl<'a, 'b, T, S, H> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S>
+    where T: Eq + Hash<H> + Clone,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
+    type Output = HashSet<T, S>;
 
-    /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, H>`.
+    /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
     ///
     /// # Examples
     ///
@@ -715,18 +746,20 @@ BitXor<&'b HashSet<T, H>> for &'a HashSet<T, H> {
     /// }
     /// assert_eq!(i, expected.len());
     /// ```
-    fn bitxor(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
+    fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
         self.symmetric_difference(rhs).cloned().collect()
     }
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, 'b, T: Eq + Hash<S> + Clone, S, H: Hasher<S> + Default>
-Sub<&'b HashSet<T, H>> for &'a HashSet<T, H> {
-    type Output = HashSet<T, H>;
+impl<'a, 'b, T, S, H> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S>
+    where T: Eq + Hash<H> + Clone,
+          S: HashState<Hasher=H> + Default,
+          H: hash::Hasher<Output=u64>
+{
+    type Output = HashSet<T, S>;
 
-    /// Returns the difference of `self` and `rhs` as a new `HashSet<T, H>`.
+    /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
     ///
     /// # Examples
     ///
@@ -746,7 +779,7 @@ Sub<&'b HashSet<T, H>> for &'a HashSet<T, H> {
     /// }
     /// assert_eq!(i, expected.len());
     /// ```
-    fn sub(self, rhs: &HashSet<T, H>) -> HashSet<T, H> {
+    fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
         self.difference(rhs).cloned().collect()
     }
 }
@@ -771,32 +804,32 @@ pub struct Drain<'a, K: 'a> {
 
 /// Intersection iterator
 #[stable]
-pub struct Intersection<'a, T: 'a, H: 'a> {
+pub struct Intersection<'a, T: 'a, S: 'a> {
     // iterator of the first set
     iter: Iter<'a, T>,
     // the second set
-    other: &'a HashSet<T, H>,
+    other: &'a HashSet<T, S>,
 }
 
 /// Difference iterator
 #[stable]
-pub struct Difference<'a, T: 'a, H: 'a> {
+pub struct Difference<'a, T: 'a, S: 'a> {
     // iterator of the first set
     iter: Iter<'a, T>,
     // the second set
-    other: &'a HashSet<T, H>,
+    other: &'a HashSet<T, S>,
 }
 
 /// Symmetric difference iterator.
 #[stable]
-pub struct SymmetricDifference<'a, T: 'a, H: 'a> {
-    iter: Chain<Difference<'a, T, H>, Difference<'a, T, H>>
+pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
+    iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>
 }
 
 /// Set union iterator.
 #[stable]
-pub struct Union<'a, T: 'a, H: 'a> {
-    iter: Chain<Iter<'a, T>, Difference<'a, T, H>>
+pub struct Union<'a, T: 'a, S: 'a> {
+    iter: Chain<Iter<'a, T>, Difference<'a, T, S>>
 }
 
 #[stable]
@@ -824,9 +857,10 @@ impl<'a, K: 'a> Iterator for Drain<'a, K> {
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, T, S, H> Iterator for Intersection<'a, T, H>
-    where T: Eq + Hash<S>, H: Hasher<S>
+impl<'a, T, S, H> Iterator for Intersection<'a, T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
 {
     type Item = &'a T;
 
@@ -848,9 +882,10 @@ impl<'a, T, S, H> Iterator for Intersection<'a, T, H>
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, T, S, H> Iterator for Difference<'a, T, H>
-    where T: Eq + Hash<S>, H: Hasher<S>
+impl<'a, T, S, H> Iterator for Difference<'a, T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
 {
     type Item = &'a T;
 
@@ -872,9 +907,10 @@ impl<'a, T, S, H> Iterator for Difference<'a, T, H>
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, T, S, H> Iterator for SymmetricDifference<'a, T, H>
-    where T: Eq + Hash<S>, H: Hasher<S>
+impl<'a, T, S, H> Iterator for SymmetricDifference<'a, T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
 {
     type Item = &'a T;
 
@@ -883,9 +919,10 @@ impl<'a, T, S, H> Iterator for SymmetricDifference<'a, T, H>
 }
 
 #[stable]
-#[old_impl_check]
-impl<'a, T, S, H> Iterator for Union<'a, T, H>
-    where T: Eq + Hash<S>, H: Hasher<S>
+impl<'a, T, S, H> Iterator for Union<'a, T, S>
+    where T: Eq + Hash<H>,
+          S: HashState<Hasher=H>,
+          H: hash::Hasher<Output=u64>
 {
     type Item = &'a T;
 
diff --git a/src/libstd/collections/hash/state.rs b/src/libstd/collections/hash/state.rs
new file mode 100644
index 00000000000..ffbc958f179
--- /dev/null
+++ b/src/libstd/collections/hash/state.rs
@@ -0,0 +1,51 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use clone::Clone;
+use default::Default;
+use hash;
+
+/// A trait representing stateful hashes which can be used to hash keys in a
+/// `HashMap`.
+///
+/// A HashState is used as a factory for instances of `Hasher` which a `HashMap`
+/// can then use to hash keys independently. A `HashMap` by default uses a state
+/// which will create instances of a `SipHasher`, but a custom state factory can
+/// be provided to the `with_hash_state` function.
+///
+/// If a hashing algorithm has no initial state, then the `Hasher` type for that
+/// algorithm can implement the `Default` trait and create hash maps with the
+/// `DefaultState` structure. This state is 0-sized and will simply delegate
+/// to `Default` when asked to create a hasher.
+pub trait HashState {
+    type Hasher: hash::Hasher;
+
+    /// Creates a new hasher based on the given state of this object.
+    fn hasher(&self) -> Self::Hasher;
+}
+
+/// A structure which is a factory for instances of `Hasher` which implement the
+/// default trait.
+///
+/// This struct has is 0-sized and does not need construction.
+pub struct DefaultState<H>;
+
+impl<H: Default + hash::Hasher> HashState for DefaultState<H> {
+    type Hasher = H;
+    fn hasher(&self) -> H { Default::default() }
+}
+
+impl<H> Clone for DefaultState<H> {
+    fn clone(&self) -> DefaultState<H> { DefaultState }
+}
+
+impl<H> Default for DefaultState<H> {
+    fn default() -> DefaultState<H> { DefaultState }
+}
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 6eb98da4da4..e43cc053ba0 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -26,6 +26,7 @@ use option::Option::{Some, None};
 use ptr::{Unique, PtrExt, copy_nonoverlapping_memory, zero_memory};
 use ptr;
 use rt::heap::{allocate, deallocate};
+use collections::hash_state::HashState;
 
 const EMPTY_BUCKET: u64 = 0u64;
 
@@ -138,12 +139,18 @@ impl SafeHash {
 /// We need to remove hashes of 0. That's reserved for empty buckets.
 /// This function wraps up `hash_keyed` to be the only way outside this
 /// module to generate a SafeHash.
-pub fn make_hash<T: ?Sized + Hash<S>, S, H: Hasher<S>>(hasher: &H, t: &T) -> SafeHash {
+pub fn make_hash<T: ?Sized, S, H>(hash_state: &S, t: &T) -> SafeHash
+    where T: Hash<H>,
+          S: HashState<Hasher=H>,
+          H: Hasher<Output=u64>
+{
+    let mut state = hash_state.hasher();
+    t.hash(&mut state);
     // 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) }
+    SafeHash { hash: 0x8000_0000_0000_0000 | state.finish() }
 }
 
 // `replace` casts a `*u64` to a `*SafeHash`. Since we statically
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index 9b2a4926bcb..71ab89027ff 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -333,3 +333,10 @@ pub mod hash_set {
     //! A hashset
     pub use super::hash::set::*;
 }
+
+/// Experimental support for providing custom hash algorithms to a HashMap and
+/// HashSet.
+#[unstable = "module was recently added"]
+pub mod hash_state {
+    pub use super::hash::state::*;
+}
diff --git a/src/libstd/hash.rs b/src/libstd/hash.rs
deleted file mode 100644
index 69e7e429d07..00000000000
--- a/src/libstd/hash.rs
+++ /dev/null
@@ -1,105 +0,0 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! Generic hashing support.
-//!
-//! This module provides a generic way to compute the hash of a value. The
-//! simplest way to make a type hashable is to use `#[derive(Hash)]`:
-//!
-//! # Example
-//!
-//! ```rust
-//! use std::hash;
-//! use std::hash::Hash;
-//!
-//! #[derive(Hash)]
-//! struct Person {
-//!     id: uint,
-//!     name: String,
-//!     phone: u64,
-//! }
-//!
-//! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
-//! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
-//!
-//! assert!(hash::hash(&person1) != hash::hash(&person2));
-//! ```
-//!
-//! If you need more control over how a value is hashed, you need to implement
-//! the trait `Hash`:
-//!
-//! ```rust
-//! use std::hash;
-//! use std::hash::Hash;
-//! use std::hash::sip::SipState;
-//!
-//! struct Person {
-//!     id: uint,
-//!     name: String,
-//!     phone: u64,
-//! }
-//!
-//! impl Hash for Person {
-//!     fn hash(&self, state: &mut SipState) {
-//!         self.id.hash(state);
-//!         self.phone.hash(state);
-//!     }
-//! }
-//!
-//! let person1 = Person { id: 5, name: "Janet".to_string(), phone: 555_666_7777 };
-//! let person2 = Person { id: 5, name: "Bob".to_string(), phone: 555_666_7777 };
-//!
-//! assert!(hash::hash(&person1) == hash::hash(&person2));
-//! ```
-
-#![experimental]
-
-pub use core::hash::{Hash, Hasher, Writer, hash, sip};
-
-use core::marker::Sized;
-use default::Default;
-use rand::Rng;
-use rand;
-
-/// `RandomSipHasher` computes the SipHash algorithm from a stream of bytes
-/// initialized with random keys.
-#[derive(Clone)]
-pub struct RandomSipHasher {
-    hasher: sip::SipHasher,
-}
-
-impl RandomSipHasher {
-    /// Construct a new `RandomSipHasher` that is initialized with random keys.
-    #[inline]
-    pub fn new() -> RandomSipHasher {
-        let mut r = rand::thread_rng();
-        let r0 = r.gen();
-        let r1 = r.gen();
-        RandomSipHasher {
-            hasher: sip::SipHasher::new_with_keys(r0, r1),
-        }
-    }
-}
-
-impl Hasher<sip::SipState> for RandomSipHasher {
-    #[inline]
-    fn hash<T: ?Sized + Hash<sip::SipState>>(&self, value: &T) -> u64 {
-        self.hasher.hash(value)
-    }
-}
-
-#[stable]
-impl Default for RandomSipHasher {
-    #[stable]
-    #[inline]
-    fn default() -> RandomSipHasher {
-        RandomSipHasher::new()
-    }
-}
diff --git a/src/libstd/io/process.rs b/src/libstd/io/process.rs
index 55df6330dd3..ed29d3b2c7f 100644
--- a/src/libstd/io/process.rs
+++ b/src/libstd/io/process.rs
@@ -34,7 +34,7 @@ use sys::process::Process as ProcessImp;
 use sys;
 use thread::Thread;
 
-#[cfg(windows)] use std::hash::sip::SipState;
+#[cfg(windows)] use hash;
 #[cfg(windows)] use str;
 
 /// Signal a process to exit, without forcibly killing it. Corresponds to
@@ -98,7 +98,7 @@ pub struct Process {
 /// A representation of environment variable name
 /// It compares case-insensitive on Windows and case-sensitive everywhere else.
 #[cfg(not(windows))]
-#[derive(PartialEq, Eq, Hash, Clone, Show)]
+#[derive(Hash, PartialEq, Eq, Clone, Show)]
 struct EnvKey(CString);
 
 #[doc(hidden)]
@@ -107,8 +107,8 @@ struct EnvKey(CString);
 struct EnvKey(CString);
 
 #[cfg(windows)]
-impl Hash for EnvKey {
-    fn hash(&self, state: &mut SipState) {
+impl<H: hash::Writer + hash::Hasher> hash::Hash<H> for EnvKey {
+    fn hash(&self, state: &mut H) {
         let &EnvKey(ref x) = self;
         match str::from_utf8(x.as_bytes()) {
             Ok(s) => for ch in s.chars() {
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index eef5bdb60ee..6950a6cf8d0 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -150,6 +150,7 @@ pub use core::clone;
 #[cfg(not(test))] pub use core::cmp;
 pub use core::default;
 pub use core::finally;
+pub use core::hash;
 pub use core::intrinsics;
 pub use core::iter;
 #[cfg(stage0)] #[cfg(not(test))] pub use core::marker as kinds;
@@ -242,7 +243,6 @@ pub mod time;
 /* Common data structures */
 
 pub mod collections;
-pub mod hash;
 
 /* Threads and communication */
 
@@ -274,6 +274,7 @@ mod std {
     pub use clone;
     pub use cmp;
     pub use hash;
+    pub use default;
 
     pub use sync; // used for select!()
     pub use error; // used for try!()
diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs
index 0b7dc19fcab..b13278205b4 100644
--- a/src/libstd/path/posix.rs
+++ b/src/libstd/path/posix.rs
@@ -91,7 +91,7 @@ impl FromStr for Path {
     }
 }
 
-impl<S: hash::Writer> hash::Hash<S> for Path {
+impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Path {
     #[inline]
     fn hash(&self, state: &mut S) {
         self.repr.hash(state)
diff --git a/src/libstd/path/windows.rs b/src/libstd/path/windows.rs
index 5c4e7aa9ac2..0a43c7b5140 100644
--- a/src/libstd/path/windows.rs
+++ b/src/libstd/path/windows.rs
@@ -118,7 +118,7 @@ impl FromStr for Path {
     }
 }
 
-impl<S: hash::Writer> hash::Hash<S> for Path {
+impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Path {
     #[cfg(not(test))]
     #[inline]
     fn hash(&self, state: &mut S) {
diff --git a/src/libstd/sys/unix/process.rs b/src/libstd/sys/unix/process.rs
index 1357bbdd5a3..36bf696dba5 100644
--- a/src/libstd/sys/unix/process.rs
+++ b/src/libstd/sys/unix/process.rs
@@ -11,7 +11,8 @@
 use prelude::v1::*;
 use self::Req::*;
 
-use collections;
+use collections::HashMap;
+use collections::hash_map::Hasher;
 use ffi::CString;
 use hash::Hash;
 use io::process::{ProcessExit, ExitStatus, ExitSignal};
@@ -60,7 +61,7 @@ impl Process {
                               out_fd: Option<P>, err_fd: Option<P>)
                               -> IoResult<Process>
         where C: ProcessConfig<K, V>, P: AsInner<FileDesc>,
-              K: BytesContainer + Eq + Hash, V: BytesContainer
+              K: BytesContainer + Eq + Hash<Hasher>, V: BytesContainer
     {
         use libc::funcs::posix88::unistd::{fork, dup2, close, chdir, execvp};
         use libc::funcs::bsd44::getdtablesize;
@@ -553,11 +554,11 @@ fn with_argv<T,F>(prog: &CString, args: &[CString],
     cb(ptrs.as_ptr())
 }
 
-fn with_envp<K,V,T,F>(env: Option<&collections::HashMap<K, V>>,
+fn with_envp<K,V,T,F>(env: Option<&HashMap<K, V>>,
                       cb: F)
                       -> T
     where F : FnOnce(*const c_void) -> T,
-          K : BytesContainer + Eq + Hash,
+          K : BytesContainer + Eq + Hash<Hasher>,
           V : BytesContainer
 {
     // On posixy systems we can pass a char** for envp, which is a
diff --git a/src/libstd/sys/windows/process.rs b/src/libstd/sys/windows/process.rs
index 8e1f169b5cd..1b837385d1e 100644
--- a/src/libstd/sys/windows/process.rs
+++ b/src/libstd/sys/windows/process.rs
@@ -13,6 +13,7 @@ use prelude::v1::*;
 use collections;
 use ffi::CString;
 use hash::Hash;
+use collections::hash_map::Hasher;
 use io::fs::PathExtensions;
 use io::process::{ProcessExit, ExitStatus, ExitSignal};
 use io::{IoResult, IoError};
@@ -109,7 +110,7 @@ impl Process {
                               out_fd: Option<P>, err_fd: Option<P>)
                               -> IoResult<Process>
         where C: ProcessConfig<K, V>, P: AsInner<FileDesc>,
-              K: BytesContainer + Eq + Hash, V: BytesContainer
+              K: BytesContainer + Eq + Hash<Hasher>, V: BytesContainer
     {
         use libc::types::os::arch::extra::{DWORD, HANDLE, STARTUPINFO};
         use libc::consts::os::extra::{
@@ -424,8 +425,10 @@ fn make_command_line(prog: &CString, args: &[CString]) -> String {
     }
 }
 
-fn with_envp<K, V, T, F>(env: Option<&collections::HashMap<K, V>>, cb: F) -> T where
-    K: BytesContainer + Eq + Hash, V: BytesContainer, F: FnOnce(*mut c_void) -> T,
+fn with_envp<K, V, T, F>(env: Option<&collections::HashMap<K, V>>, cb: F) -> T
+    where K: BytesContainer + Eq + Hash<Hasher>,
+          V: BytesContainer,
+          F: FnOnce(*mut c_void) -> T,
 {
     // On Windows we pass an "environment block" which is not a char**, but
     // rather a concatenation of null-terminated k=v\0 sequences, with a final