auto merge of #5696 : thestinger/rust/hashmap, r=sanxiyn

This naming is free now that `oldmap` has finally been removed, so this is a search-and-replace to take advantage of that. It might as well be called `HashMap` instead of being named after the specific implementation, since there's only one.

SipHash distributes keys so well that I don't think there will ever be much need to use anything but a simple hash table with open addressing. If there *is* a better way to do it, it will probably be better in all cases and can just be the default implementation. 

A cuckoo-hashing implementation combining a weaker hash with SipHash could be useful, but that won't be as general purpose - you would need to write a separate fast hash function specialized for the type to really take advantage of it (like taking a page from libstdc++/libc++ and just using the integer value as the "hash"). I think a more specific naming for a truly alternative implementation like that would be fine, with the nice naming reserved for the general purpose container.

74 files changed, 1301 insertions, 1305 deletions

diff --git a/src/libcore/gc.rs b/src/libcore/gc.rs
index 2f35c1e0bb1..9fd9ac3a8c8 100644
--- a/src/libcore/gc.rs
+++ b/src/libcore/gc.rs
@@ -43,7 +43,7 @@ use io;
 use libc::{size_t, uintptr_t};
 use option::{None, Option, Some};
 use ptr;
-use hashmap::linear::LinearSet;
+use hashmap::HashSet;
 use stackwalk;
 use sys;
 
@@ -344,7 +344,7 @@ pub fn cleanup_stack_for_failure() {
             ptr::null()
         };
 
-        let mut roots = LinearSet::new();
+        let mut roots = HashSet::new();
         for walk_gc_roots(need_cleanup, sentinel) |root, tydesc| {
             // Track roots to avoid double frees.
             if roots.contains(&*root) {
diff --git a/src/libcore/hashmap.rs b/src/libcore/hashmap.rs
index 9387ec4f432..5dbf085f097 100644
--- a/src/libcore/hashmap.rs
+++ b/src/libcore/hashmap.rs
@@ -13,1013 +13,1009 @@
 //! The tables use a keyed hash with new random keys generated for each container, so the ordering
 //! of a set of keys in a hash table is randomized.
 
-/// Open addressing with linear probing.
-pub mod linear {
-    use container::{Container, Mutable, Map, Set};
-    use cmp::{Eq, Equiv};
-    use hash::Hash;
-    use to_bytes::IterBytes;
-    use iter::BaseIter;
-    use hash::Hash;
-    use iter;
-    use option::{None, Option, Some};
-    use rand::RngUtil;
-    use rand;
-    use uint;
-    use vec;
-    use util::unreachable;
+use container::{Container, Mutable, Map, Set};
+use cmp::{Eq, Equiv};
+use hash::Hash;
+use to_bytes::IterBytes;
+use iter::BaseIter;
+use hash::Hash;
+use iter;
+use option::{None, Option, Some};
+use rand::RngUtil;
+use rand;
+use uint;
+use vec;
+use util::unreachable;
+
+static INITIAL_CAPACITY: uint = 32u; // 2^5
+
+struct Bucket<K,V> {
+    hash: uint,
+    key: K,
+    value: V,
+}
 
-    static INITIAL_CAPACITY: uint = 32u; // 2^5
+pub struct HashMap<K,V> {
+    priv k0: u64,
+    priv k1: u64,
+    priv resize_at: uint,
+    priv size: uint,
+    priv buckets: ~[Option<Bucket<K, V>>],
+}
 
-    struct Bucket<K,V> {
-        hash: uint,
-        key: K,
-        value: V,
-    }
+// We could rewrite FoundEntry to have type Option<&Bucket<K, V>>
+// which would be nifty
+enum SearchResult {
+    FoundEntry(uint), FoundHole(uint), TableFull
+}
 
-    pub struct LinearMap<K,V> {
-        priv k0: u64,
-        priv k1: u64,
-        priv resize_at: uint,
-        priv size: uint,
-        priv buckets: ~[Option<Bucket<K, V>>],
-    }
+#[inline(always)]
+fn resize_at(capacity: uint) -> uint {
+    ((capacity as float) * 3. / 4.) as uint
+}
 
-    // We could rewrite FoundEntry to have type Option<&Bucket<K, V>>
-    // which would be nifty
-    enum SearchResult {
-        FoundEntry(uint), FoundHole(uint), TableFull
+pub fn linear_map_with_capacity<K:Eq + Hash,V>(
+    initial_capacity: uint) -> HashMap<K, V> {
+    let r = rand::task_rng();
+    linear_map_with_capacity_and_keys(r.gen_u64(), r.gen_u64(),
+                                      initial_capacity)
+}
+
+fn linear_map_with_capacity_and_keys<K:Eq + Hash,V>(
+    k0: u64, k1: u64,
+    initial_capacity: uint) -> HashMap<K, V> {
+    HashMap {
+        k0: k0, k1: k1,
+        resize_at: resize_at(initial_capacity),
+        size: 0,
+        buckets: vec::from_fn(initial_capacity, |_| None)
     }
+}
 
+priv impl<K:Hash + IterBytes + Eq,V> HashMap<K, V> {
     #[inline(always)]
-    fn resize_at(capacity: uint) -> uint {
-        ((capacity as float) * 3. / 4.) as uint
+    fn to_bucket(&self, h: uint) -> uint {
+        // A good hash function with entropy spread over all of the
+        // bits is assumed. SipHash is more than good enough.
+        h % self.buckets.len()
     }
 
-    pub fn linear_map_with_capacity<K:Eq + Hash,V>(
-        initial_capacity: uint) -> LinearMap<K, V> {
-        let r = rand::task_rng();
-        linear_map_with_capacity_and_keys(r.gen_u64(), r.gen_u64(),
-                                          initial_capacity)
+    #[inline(always)]
+    fn next_bucket(&self, idx: uint, len_buckets: uint) -> uint {
+        let n = (idx + 1) % len_buckets;
+        debug!("next_bucket(%?, %?) = %?", idx, len_buckets, n);
+        n
     }
 
-    fn linear_map_with_capacity_and_keys<K:Eq + Hash,V>(
-        k0: u64, k1: u64,
-        initial_capacity: uint) -> LinearMap<K, V> {
-        LinearMap {
-            k0: k0, k1: k1,
-            resize_at: resize_at(initial_capacity),
-            size: 0,
-            buckets: vec::from_fn(initial_capacity, |_| None)
+    #[inline(always)]
+    fn bucket_sequence(&self, hash: uint,
+                            op: &fn(uint) -> bool) -> uint {
+        let start_idx = self.to_bucket(hash);
+        let len_buckets = self.buckets.len();
+        let mut idx = start_idx;
+        loop {
+            if !op(idx) {
+                return idx;
+            }
+            idx = self.next_bucket(idx, len_buckets);
+            if idx == start_idx {
+                return start_idx;
+            }
         }
     }
 
-    priv impl<K:Hash + IterBytes + Eq,V> LinearMap<K, V> {
-        #[inline(always)]
-        fn to_bucket(&self, h: uint) -> uint {
-            // A good hash function with entropy spread over all of the
-            // bits is assumed. SipHash is more than good enough.
-            h % self.buckets.len()
-        }
+    #[inline(always)]
+    fn bucket_for_key(&self, k: &K) -> SearchResult {
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        self.bucket_for_key_with_hash(hash, k)
+    }
 
-        #[inline(always)]
-        fn next_bucket(&self, idx: uint, len_buckets: uint) -> uint {
-            let n = (idx + 1) % len_buckets;
-            debug!("next_bucket(%?, %?) = %?", idx, len_buckets, n);
-            n
-        }
+    #[inline(always)]
+    fn bucket_for_key_equiv<Q:Hash + IterBytes + Equiv<K>>(&self,
+                                                           k: &Q)
+                                                        -> SearchResult {
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        self.bucket_for_key_with_hash_equiv(hash, k)
+    }
 
-        #[inline(always)]
-        fn bucket_sequence(&self, hash: uint,
-                                op: &fn(uint) -> bool) -> uint {
-            let start_idx = self.to_bucket(hash);
-            let len_buckets = self.buckets.len();
-            let mut idx = start_idx;
-            loop {
-                if !op(idx) {
-                    return idx;
-                }
-                idx = self.next_bucket(idx, len_buckets);
-                if idx == start_idx {
-                    return start_idx;
-                }
+    #[inline(always)]
+    fn bucket_for_key_with_hash(&self,
+                                hash: uint,
+                                k: &K)
+                             -> SearchResult {
+        let _ = for self.bucket_sequence(hash) |i| {
+            match self.buckets[i] {
+                Some(ref bkt) => if bkt.hash == hash && *k == bkt.key {
+                    return FoundEntry(i);
+                },
+                None => return FoundHole(i)
             }
-        }
-
-        #[inline(always)]
-        fn bucket_for_key(&self, k: &K) -> SearchResult {
-            let hash = k.hash_keyed(self.k0, self.k1) as uint;
-            self.bucket_for_key_with_hash(hash, k)
-        }
-
-        #[inline(always)]
-        fn bucket_for_key_equiv<Q:Hash + IterBytes + Equiv<K>>(&self,
-                                                               k: &Q)
-                                                            -> SearchResult {
-            let hash = k.hash_keyed(self.k0, self.k1) as uint;
-            self.bucket_for_key_with_hash_equiv(hash, k)
-        }
+        };
+        TableFull
+    }
 
-        #[inline(always)]
-        fn bucket_for_key_with_hash(&self,
-                                    hash: uint,
-                                    k: &K)
-                                 -> SearchResult {
-            let _ = for self.bucket_sequence(hash) |i| {
-                match self.buckets[i] {
-                    Some(ref bkt) => if bkt.hash == hash && *k == bkt.key {
+    #[inline(always)]
+    fn bucket_for_key_with_hash_equiv<Q:Equiv<K>>(&self,
+                                                  hash: uint,
+                                                  k: &Q)
+                                               -> SearchResult {
+        let _ = for self.bucket_sequence(hash) |i| {
+            match self.buckets[i] {
+                Some(ref bkt) => {
+                    if bkt.hash == hash && k.equiv(&bkt.key) {
                         return FoundEntry(i);
-                    },
-                    None => return FoundHole(i)
-                }
-            };
-            TableFull
-        }
-
-        #[inline(always)]
-        fn bucket_for_key_with_hash_equiv<Q:Equiv<K>>(&self,
-                                                      hash: uint,
-                                                      k: &Q)
-                                                   -> SearchResult {
-            let _ = for self.bucket_sequence(hash) |i| {
-                match self.buckets[i] {
-                    Some(ref bkt) => {
-                        if bkt.hash == hash && k.equiv(&bkt.key) {
-                            return FoundEntry(i);
-                        }
-                    },
-                    None => return FoundHole(i)
-                }
-            };
-            TableFull
-        }
+                    }
+                },
+                None => return FoundHole(i)
+            }
+        };
+        TableFull
+    }
 
-        /// Expand the capacity of the array to the next power of two
-        /// and re-insert each of the existing buckets.
-        #[inline(always)]
-        fn expand(&mut self) {
-            let new_capacity = self.buckets.len() * 2;
-            self.resize(new_capacity);
-        }
+    /// Expand the capacity of the array to the next power of two
+    /// and re-insert each of the existing buckets.
+    #[inline(always)]
+    fn expand(&mut self) {
+        let new_capacity = self.buckets.len() * 2;
+        self.resize(new_capacity);
+    }
 
-        /// Expands the capacity of the array and re-insert each of the
-        /// existing buckets.
-        fn resize(&mut self, new_capacity: uint) {
-            let old_capacity = self.buckets.len();
-            self.resize_at = resize_at(new_capacity);
+    /// Expands the capacity of the array and re-insert each of the
+    /// existing buckets.
+    fn resize(&mut self, new_capacity: uint) {
+        let old_capacity = self.buckets.len();
+        self.resize_at = resize_at(new_capacity);
 
-            let mut old_buckets = vec::from_fn(new_capacity, |_| None);
-            self.buckets <-> old_buckets;
+        let mut old_buckets = vec::from_fn(new_capacity, |_| None);
+        self.buckets <-> old_buckets;
 
-            self.size = 0;
-            for uint::range(0, old_capacity) |i| {
-                let mut bucket = None;
-                bucket <-> old_buckets[i];
-                self.insert_opt_bucket(bucket);
-            }
+        self.size = 0;
+        for uint::range(0, old_capacity) |i| {
+            let mut bucket = None;
+            bucket <-> old_buckets[i];
+            self.insert_opt_bucket(bucket);
         }
+    }
 
-        fn insert_opt_bucket(&mut self, bucket: Option<Bucket<K, V>>) {
-            match bucket {
-                Some(Bucket{hash: hash, key: key, value: value}) => {
-                    self.insert_internal(hash, key, value);
-                }
-                None => {}
+    fn insert_opt_bucket(&mut self, bucket: Option<Bucket<K, V>>) {
+        match bucket {
+            Some(Bucket{hash: hash, key: key, value: value}) => {
+                self.insert_internal(hash, key, value);
             }
+            None => {}
         }
+    }
 
-        #[inline(always)]
-        fn value_for_bucket(&self, idx: uint) -> &'self V {
-            match self.buckets[idx] {
-                Some(ref bkt) => &bkt.value,
-                None => fail!(~"LinearMap::find: internal logic error"),
-            }
+    #[inline(always)]
+    fn value_for_bucket(&self, idx: uint) -> &'self V {
+        match self.buckets[idx] {
+            Some(ref bkt) => &bkt.value,
+            None => fail!(~"HashMap::find: internal logic error"),
         }
+    }
 
-        #[inline(always)]
-        fn mut_value_for_bucket(&mut self, idx: uint) -> &'self mut V {
-            match self.buckets[idx] {
-                Some(ref mut bkt) => &mut bkt.value,
-                None => unreachable()
-            }
+    #[inline(always)]
+    fn mut_value_for_bucket(&mut self, idx: uint) -> &'self mut V {
+        match self.buckets[idx] {
+            Some(ref mut bkt) => &mut bkt.value,
+            None => unreachable()
         }
+    }
 
-        /// Inserts the key value pair into the buckets.
-        /// Assumes that there will be a bucket.
-        /// True if there was no previous entry with that key
-        fn insert_internal(&mut self, hash: uint, k: K, v: V) -> bool {
-            match self.bucket_for_key_with_hash(hash, &k) {
-                TableFull => { fail!(~"Internal logic error"); }
-                FoundHole(idx) => {
-                    debug!("insert fresh (%?->%?) at idx %?, hash %?",
-                           k, v, idx, hash);
-                    self.buckets[idx] = Some(Bucket{hash: hash, key: k,
-                                                    value: v});
-                    self.size += 1;
-                    true
-                }
-                FoundEntry(idx) => {
-                    debug!("insert overwrite (%?->%?) at idx %?, hash %?",
-                           k, v, idx, hash);
-                    self.buckets[idx] = Some(Bucket{hash: hash, key: k,
-                                                    value: v});
-                    false
-                }
+    /// Inserts the key value pair into the buckets.
+    /// Assumes that there will be a bucket.
+    /// True if there was no previous entry with that key
+    fn insert_internal(&mut self, hash: uint, k: K, v: V) -> bool {
+        match self.bucket_for_key_with_hash(hash, &k) {
+            TableFull => { fail!(~"Internal logic error"); }
+            FoundHole(idx) => {
+                debug!("insert fresh (%?->%?) at idx %?, hash %?",
+                       k, v, idx, hash);
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                                value: v});
+                self.size += 1;
+                true
+            }
+            FoundEntry(idx) => {
+                debug!("insert overwrite (%?->%?) at idx %?, hash %?",
+                       k, v, idx, hash);
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                                value: v});
+                false
             }
         }
+    }
 
-        fn pop_internal(&mut self, hash: uint, k: &K) -> Option<V> {
-            // Removing from an open-addressed hashtable
-            // is, well, painful.  The problem is that
-            // the entry may lie on the probe path for other
-            // entries, so removing it would make you think that
-            // those probe paths are empty.
-            //
-            // To address this we basically have to keep walking,
-            // re-inserting entries we find until we reach an empty
-            // bucket.  We know we will eventually reach one because
-            // we insert one ourselves at the beginning (the removed
-            // entry).
-            //
-            // I found this explanation elucidating:
-            // http://www.maths.lse.ac.uk/Courses/MA407/del-hash.pdf
-            let mut idx = match self.bucket_for_key_with_hash(hash, k) {
-                TableFull | FoundHole(_) => return None,
-                FoundEntry(idx) => idx
-            };
-
-            let len_buckets = self.buckets.len();
+    fn pop_internal(&mut self, hash: uint, k: &K) -> Option<V> {
+        // Removing from an open-addressed hashtable
+        // is, well, painful.  The problem is that
+        // the entry may lie on the probe path for other
+        // entries, so removing it would make you think that
+        // those probe paths are empty.
+        //
+        // To address this we basically have to keep walking,
+        // re-inserting entries we find until we reach an empty
+        // bucket.  We know we will eventually reach one because
+        // we insert one ourselves at the beginning (the removed
+        // entry).
+        //
+        // I found this explanation elucidating:
+        // http://www.maths.lse.ac.uk/Courses/MA407/del-hash.pdf
+        let mut idx = match self.bucket_for_key_with_hash(hash, k) {
+            TableFull | FoundHole(_) => return None,
+            FoundEntry(idx) => idx
+        };
+
+        let len_buckets = self.buckets.len();
+        let mut bucket = None;
+        self.buckets[idx] <-> bucket;
+
+        let value = match bucket {
+            None => None,
+            Some(bucket) => {
+                let Bucket{value: value, _} = bucket;
+                Some(value)
+            },
+        };
+
+        /* re-inserting buckets may cause changes in size, so remember
+        what our new size is ahead of time before we start insertions */
+        let size = self.size - 1;
+        idx = self.next_bucket(idx, len_buckets);
+        while self.buckets[idx].is_some() {
             let mut bucket = None;
-            self.buckets[idx] <-> bucket;
-
-            let value = match bucket {
-                None => None,
-                Some(bucket) => {
-                    let Bucket{value: value, _} = bucket;
-                    Some(value)
-                },
-            };
-
-            /* re-inserting buckets may cause changes in size, so remember
-            what our new size is ahead of time before we start insertions */
-            let size = self.size - 1;
+            bucket <-> self.buckets[idx];
+            self.insert_opt_bucket(bucket);
             idx = self.next_bucket(idx, len_buckets);
-            while self.buckets[idx].is_some() {
-                let mut bucket = None;
-                bucket <-> self.buckets[idx];
-                self.insert_opt_bucket(bucket);
-                idx = self.next_bucket(idx, len_buckets);
-            }
-            self.size = size;
-
-            value
         }
+        self.size = size;
 
-        fn search(&self, hash: uint,
-                  op: &fn(x: &Option<Bucket<K, V>>) -> bool) {
-            let _ = self.bucket_sequence(hash, |i| op(&self.buckets[i]));
-        }
+        value
     }
 
-    impl<'self,K:Hash + IterBytes + Eq,V>
-            BaseIter<(&'self K, &'self V)> for LinearMap<K, V> {
-        /// Visit all key-value pairs
-        fn each(&self, blk: &fn(&(&'self K, &'self V)) -> bool) {
-            for uint::range(0, self.buckets.len()) |i| {
-                let mut broke = false;
-                do self.buckets[i].map |bucket| {
-                    if !blk(&(&bucket.key, &bucket.value)) {
-                        broke = true; // FIXME(#3064) just write "break;"
-                    }
-                };
-                if broke { break; }
-            }
+    fn search(&self, hash: uint,
+              op: &fn(x: &Option<Bucket<K, V>>) -> bool) {
+        let _ = self.bucket_sequence(hash, |i| op(&self.buckets[i]));
+    }
+}
+
+impl<'self,K:Hash + IterBytes + Eq,V>
+        BaseIter<(&'self K, &'self V)> for HashMap<K, V> {
+    /// Visit all key-value pairs
+    fn each(&self, blk: &fn(&(&'self K, &'self V)) -> bool) {
+        for uint::range(0, self.buckets.len()) |i| {
+            let mut broke = false;
+            do self.buckets[i].map |bucket| {
+                if !blk(&(&bucket.key, &bucket.value)) {
+                    broke = true; // FIXME(#3064) just write "break;"
+                }
+            };
+            if broke { break; }
         }
-        fn size_hint(&self) -> Option<uint> { Some(self.len()) }
     }
+    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
+}
 
 
-    impl<K:Hash + IterBytes + Eq,V> Container for LinearMap<K, V> {
-        /// Return the number of elements in the map
-        fn len(&const self) -> uint { self.size }
+impl<K:Hash + IterBytes + Eq,V> Container for HashMap<K, V> {
+    /// Return the number of elements in the map
+    fn len(&const self) -> uint { self.size }
 
-        /// Return true if the map contains no elements
-        fn is_empty(&const self) -> bool { self.len() == 0 }
-    }
+    /// Return true if the map contains no elements
+    fn is_empty(&const self) -> bool { self.len() == 0 }
+}
 
-    impl<K:Hash + IterBytes + Eq,V> Mutable for LinearMap<K, V> {
-        /// Clear the map, removing all key-value pairs.
-        fn clear(&mut self) {
-            for uint::range(0, self.buckets.len()) |idx| {
-                self.buckets[idx] = None;
-            }
-            self.size = 0;
+impl<K:Hash + IterBytes + Eq,V> Mutable for HashMap<K, V> {
+    /// Clear the map, removing all key-value pairs.
+    fn clear(&mut self) {
+        for uint::range(0, self.buckets.len()) |idx| {
+            self.buckets[idx] = None;
         }
+        self.size = 0;
     }
+}
 
-    impl<'self,K:Hash + IterBytes + Eq,V> Map<K, V> for LinearMap<K, V> {
-        /// Return true if the map contains a value for the specified key
-        fn contains_key(&self, k: &K) -> bool {
-            match self.bucket_for_key(k) {
-                FoundEntry(_) => {true}
-                TableFull | FoundHole(_) => {false}
-            }
-        }
-
-        /// Visit all keys
-        fn each_key(&self, blk: &fn(k: &K) -> bool) {
-            self.each(|&(k, _)| blk(k))
+impl<'self,K:Hash + IterBytes + Eq,V> Map<K, V> for HashMap<K, V> {
+    /// Return true if the map contains a value for the specified key
+    fn contains_key(&self, k: &K) -> bool {
+        match self.bucket_for_key(k) {
+            FoundEntry(_) => {true}
+            TableFull | FoundHole(_) => {false}
         }
+    }
 
-        /// Visit all values
-        fn each_value(&self, blk: &fn(v: &V) -> bool) {
-            self.each(|&(_, v)| blk(v))
-        }
+    /// Visit all keys
+    fn each_key(&self, blk: &fn(k: &K) -> bool) {
+        self.each(|&(k, _)| blk(k))
+    }
 
-        /// Iterate over the map and mutate the contained values
-        fn mutate_values(&mut self, blk: &fn(&'self K,
-                              &'self mut V) -> bool) {
-            for uint::range(0, self.buckets.len()) |i| {
-                match self.buckets[i] {
-                  Some(Bucket{key: ref key, value: ref mut value, _}) => {
-                    if !blk(key, value) { return }
-                  }
-                  None => ()
-                }
-            }
-        }
+    /// Visit all values
+    fn each_value(&self, blk: &fn(v: &V) -> bool) {
+        self.each(|&(_, v)| blk(v))
+    }
 
-        /// Return a reference to the value corresponding to the key
-        fn find(&self, k: &K) -> Option<&'self V> {
-            match self.bucket_for_key(k) {
-                FoundEntry(idx) => Some(self.value_for_bucket(idx)),
-                TableFull | FoundHole(_) => None,
+    /// Iterate over the map and mutate the contained values
+    fn mutate_values(&mut self, blk: &fn(&'self K,
+                          &'self mut V) -> bool) {
+        for uint::range(0, self.buckets.len()) |i| {
+            match self.buckets[i] {
+              Some(Bucket{key: ref key, value: ref mut value, _}) => {
+                if !blk(key, value) { return }
+              }
+              None => ()
             }
         }
+    }
 
-        /// Return a mutable reference to the value corresponding to the key
-        fn find_mut(&mut self, k: &K) -> Option<&'self mut V> {
-            let idx = match self.bucket_for_key(k) {
-                FoundEntry(idx) => idx,
-                TableFull | FoundHole(_) => return None
-            };
-            unsafe {  // FIXME(#4903)---requires flow-sensitive borrow checker
-                Some(::cast::transmute_mut_region(self.mut_value_for_bucket(idx)))
-            }
+    /// Return a reference to the value corresponding to the key
+    fn find(&self, k: &K) -> Option<&'self V> {
+        match self.bucket_for_key(k) {
+            FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+            TableFull | FoundHole(_) => None,
         }
+    }
 
-        /// Insert a key-value pair into the map. An existing value for a
-        /// key is replaced by the new value. Return true if the key did
-        /// not already exist in the map.
-        fn insert(&mut self, k: K, v: V) -> bool {
-            if self.size >= self.resize_at {
-                // n.b.: We could also do this after searching, so
-                // that we do not resize if this call to insert is
-                // simply going to update a key in place.  My sense
-                // though is that it's worse to have to search through
-                // buckets to find the right spot twice than to just
-                // resize in this corner case.
-                self.expand();
-            }
-
-            let hash = k.hash_keyed(self.k0, self.k1) as uint;
-            self.insert_internal(hash, k, v)
+    /// Return a mutable reference to the value corresponding to the key
+    fn find_mut(&mut self, k: &K) -> Option<&'self mut V> {
+        let idx = match self.bucket_for_key(k) {
+            FoundEntry(idx) => idx,
+            TableFull | FoundHole(_) => return None
+        };
+        unsafe {  // FIXME(#4903)---requires flow-sensitive borrow checker
+            Some(::cast::transmute_mut_region(self.mut_value_for_bucket(idx)))
         }
+    }
 
-        /// Remove a key-value pair from the map. Return true if the key
-        /// was present in the map, otherwise false.
-        fn remove(&mut self, k: &K) -> bool {
-            self.pop(k).is_some()
-        }
+    /// Insert a key-value pair into the map. An existing value for a
+    /// key is replaced by the new value. Return true if the key did
+    /// not already exist in the map.
+    fn insert(&mut self, k: K, v: V) -> bool {
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
+        }
+
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        self.insert_internal(hash, k, v)
     }
 
-    pub impl<K: Hash + IterBytes + Eq, V> LinearMap<K, V> {
-        /// Create an empty LinearMap
-        fn new() -> LinearMap<K, V> {
-            LinearMap::with_capacity(INITIAL_CAPACITY)
-        }
+    /// Remove a key-value pair from the map. Return true if the key
+    /// was present in the map, otherwise false.
+    fn remove(&mut self, k: &K) -> bool {
+        self.pop(k).is_some()
+    }
+}
 
-        /// Create an empty LinearMap with space for at least `n` elements in
-        /// the hash table.
-        fn with_capacity(capacity: uint) -> LinearMap<K, V> {
-            linear_map_with_capacity(capacity)
-        }
+pub impl<K: Hash + IterBytes + Eq, V> HashMap<K, V> {
+    /// Create an empty HashMap
+    fn new() -> HashMap<K, V> {
+        HashMap::with_capacity(INITIAL_CAPACITY)
+    }
 
-        /// Reserve space for at least `n` elements in the hash table.
-        fn reserve_at_least(&mut self, n: uint) {
-            if n > self.buckets.len() {
-                let buckets = n * 4 / 3 + 1;
-                self.resize(uint::next_power_of_two(buckets));
-            }
-        }
+    /// Create an empty HashMap with space for at least `n` elements in
+    /// the hash table.
+    fn with_capacity(capacity: uint) -> HashMap<K, V> {
+        linear_map_with_capacity(capacity)
+    }
 
-        fn pop(&mut self, k: &K) -> Option<V> {
-            let hash = k.hash_keyed(self.k0, self.k1) as uint;
-            self.pop_internal(hash, k)
+    /// Reserve space for at least `n` elements in the hash table.
+    fn reserve_at_least(&mut self, n: uint) {
+        if n > self.buckets.len() {
+            let buckets = n * 4 / 3 + 1;
+            self.resize(uint::next_power_of_two(buckets));
         }
+    }
 
-        fn swap(&mut self, k: K, v: V) -> Option<V> {
-            // this could be faster.
-            let hash = k.hash_keyed(self.k0, self.k1) as uint;
-            let old_value = self.pop_internal(hash, &k);
-
-            if self.size >= self.resize_at {
-                // n.b.: We could also do this after searching, so
-                // that we do not resize if this call to insert is
-                // simply going to update a key in place.  My sense
-                // though is that it's worse to have to search through
-                // buckets to find the right spot twice than to just
-                // resize in this corner case.
-                self.expand();
-            }
+    fn pop(&mut self, k: &K) -> Option<V> {
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        self.pop_internal(hash, k)
+    }
 
-            self.insert_internal(hash, k, v);
+    fn swap(&mut self, k: K, v: V) -> Option<V> {
+        // this could be faster.
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        let old_value = self.pop_internal(hash, &k);
 
-            old_value
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
         }
 
-        /// Return the value corresponding to the key in the map, or insert
-        /// and return the value if it doesn't exist.
-        fn find_or_insert(&mut self, k: K, v: V) -> &'self V {
-            if self.size >= self.resize_at {
-                // n.b.: We could also do this after searching, so
-                // that we do not resize if this call to insert is
-                // simply going to update a key in place.  My sense
-                // though is that it's worse to have to search through
-                // buckets to find the right spot twice than to just
-                // resize in this corner case.
-                self.expand();
-            }
+        self.insert_internal(hash, k, v);
 
-            let hash = k.hash_keyed(self.k0, self.k1) as uint;
-            let idx = match self.bucket_for_key_with_hash(hash, &k) {
-                TableFull => fail!(~"Internal logic error"),
-                FoundEntry(idx) => idx,
-                FoundHole(idx) => {
-                    self.buckets[idx] = Some(Bucket{hash: hash, key: k,
-                                         value: v});
-                    self.size += 1;
-                    idx
-                },
-            };
+        old_value
+    }
 
-            unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
-                ::cast::transmute_region(self.value_for_bucket(idx))
-            }
+    /// Return the value corresponding to the key in the map, or insert
+    /// and return the value if it doesn't exist.
+    fn find_or_insert(&mut self, k: K, v: V) -> &'self V {
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
+        }
+
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        let idx = match self.bucket_for_key_with_hash(hash, &k) {
+            TableFull => fail!(~"Internal logic error"),
+            FoundEntry(idx) => idx,
+            FoundHole(idx) => {
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                     value: v});
+                self.size += 1;
+                idx
+            },
+        };
+
+        unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
+            ::cast::transmute_region(self.value_for_bucket(idx))
         }
+    }
 
-        /// Return the value corresponding to the key in the map, or create,
-        /// insert, and return a new value if it doesn't exist.
-        fn find_or_insert_with(&mut self, k: K, f: &fn(&K) -> V) -> &'self V {
-            if self.size >= self.resize_at {
-                // n.b.: We could also do this after searching, so
-                // that we do not resize if this call to insert is
-                // simply going to update a key in place.  My sense
-                // though is that it's worse to have to search through
-                // buckets to find the right spot twice than to just
-                // resize in this corner case.
-                self.expand();
-            }
-
-            let hash = k.hash_keyed(self.k0, self.k1) as uint;
-            let idx = match self.bucket_for_key_with_hash(hash, &k) {
-                TableFull => fail!(~"Internal logic error"),
-                FoundEntry(idx) => idx,
-                FoundHole(idx) => {
-                    let v = f(&k);
-                    self.buckets[idx] = Some(Bucket{hash: hash, key: k,
-                                         value: v});
-                    self.size += 1;
-                    idx
-                },
-            };
-
-            unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
-                ::cast::transmute_region(self.value_for_bucket(idx))
-            }
+    /// Return the value corresponding to the key in the map, or create,
+    /// insert, and return a new value if it doesn't exist.
+    fn find_or_insert_with(&mut self, k: K, f: &fn(&K) -> V) -> &'self V {
+        if self.size >= self.resize_at {
+            // n.b.: We could also do this after searching, so
+            // that we do not resize if this call to insert is
+            // simply going to update a key in place.  My sense
+            // though is that it's worse to have to search through
+            // buckets to find the right spot twice than to just
+            // resize in this corner case.
+            self.expand();
+        }
+
+        let hash = k.hash_keyed(self.k0, self.k1) as uint;
+        let idx = match self.bucket_for_key_with_hash(hash, &k) {
+            TableFull => fail!(~"Internal logic error"),
+            FoundEntry(idx) => idx,
+            FoundHole(idx) => {
+                let v = f(&k);
+                self.buckets[idx] = Some(Bucket{hash: hash, key: k,
+                                     value: v});
+                self.size += 1;
+                idx
+            },
+        };
+
+        unsafe { // FIXME(#4903)---requires flow-sensitive borrow checker
+            ::cast::transmute_region(self.value_for_bucket(idx))
         }
+    }
 
-        fn consume(&mut self, f: &fn(K, V)) {
-            let mut buckets = ~[];
-            self.buckets <-> buckets;
-            self.size = 0;
-
-            do vec::consume(buckets) |_, bucket| {
-                match bucket {
-                    None => {},
-                    Some(bucket) => {
-                        let Bucket{key: key, value: value, _} = bucket;
-                        f(key, value)
-                    }
+    fn consume(&mut self, f: &fn(K, V)) {
+        let mut buckets = ~[];
+        self.buckets <-> buckets;
+        self.size = 0;
+
+        do vec::consume(buckets) |_, bucket| {
+            match bucket {
+                None => {},
+                Some(bucket) => {
+                    let Bucket{key: key, value: value, _} = bucket;
+                    f(key, value)
                 }
             }
         }
+    }
 
-        fn get(&self, k: &K) -> &'self V {
-            match self.find(k) {
-                Some(v) => v,
-                None => fail!(fmt!("No entry found for key: %?", k)),
-            }
+    fn get(&self, k: &K) -> &'self V {
+        match self.find(k) {
+            Some(v) => v,
+            None => fail!(fmt!("No entry found for key: %?", k)),
         }
+    }
 
-        /// Return true if the map contains a value for the specified key,
-        /// using equivalence
-        fn contains_key_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, key: &Q)
-                                                          -> bool {
-            match self.bucket_for_key_equiv(key) {
-                FoundEntry(_) => {true}
-                TableFull | FoundHole(_) => {false}
-            }
+    /// Return true if the map contains a value for the specified key,
+    /// using equivalence
+    fn contains_key_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, key: &Q)
+                                                      -> bool {
+        match self.bucket_for_key_equiv(key) {
+            FoundEntry(_) => {true}
+            TableFull | FoundHole(_) => {false}
         }
+    }
 
-        /// Return the value corresponding to the key in the map, using
-        /// equivalence
-        fn find_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, k: &Q)
-                                                  -> Option<&'self V> {
-            match self.bucket_for_key_equiv(k) {
-                FoundEntry(idx) => Some(self.value_for_bucket(idx)),
-                TableFull | FoundHole(_) => None,
-            }
+    /// Return the value corresponding to the key in the map, using
+    /// equivalence
+    fn find_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, k: &Q)
+                                              -> Option<&'self V> {
+        match self.bucket_for_key_equiv(k) {
+            FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+            TableFull | FoundHole(_) => None,
         }
     }
+}
 
-    impl<K:Hash + IterBytes + Eq,V:Eq> Eq for LinearMap<K, V> {
-        fn eq(&self, other: &LinearMap<K, V>) -> bool {
-            if self.len() != other.len() { return false; }
+impl<K:Hash + IterBytes + Eq,V:Eq> Eq for HashMap<K, V> {
+    fn eq(&self, other: &HashMap<K, V>) -> bool {
+        if self.len() != other.len() { return false; }
 
-            for self.each |&(key, value)| {
-                match other.find(key) {
-                    None => return false,
-                    Some(v) => if value != v { return false },
-                }
+        for self.each |&(key, value)| {
+            match other.find(key) {
+                None => return false,
+                Some(v) => if value != v { return false },
             }
-
-            true
         }
 
-        fn ne(&self, other: &LinearMap<K, V>) -> bool { !self.eq(other) }
+        true
     }
 
-    pub struct LinearSet<T> {
-        priv map: LinearMap<T, ()>
-    }
+    fn ne(&self, other: &HashMap<K, V>) -> bool { !self.eq(other) }
+}
 
-    impl<T:Hash + IterBytes + Eq> BaseIter<T> for LinearSet<T> {
-        /// Visit all values in order
-        fn each(&self, f: &fn(&T) -> bool) { self.map.each_key(f) }
-        fn size_hint(&self) -> Option<uint> { Some(self.len()) }
-    }
+pub struct HashSet<T> {
+    priv map: HashMap<T, ()>
+}
 
-    impl<T:Hash + IterBytes + Eq> Eq for LinearSet<T> {
-        fn eq(&self, other: &LinearSet<T>) -> bool { self.map == other.map }
-        fn ne(&self, other: &LinearSet<T>) -> bool { self.map != other.map }
-    }
+impl<T:Hash + IterBytes + Eq> BaseIter<T> for HashSet<T> {
+    /// Visit all values in order
+    fn each(&self, f: &fn(&T) -> bool) { self.map.each_key(f) }
+    fn size_hint(&self) -> Option<uint> { Some(self.len()) }
+}
 
-    impl<T:Hash + IterBytes + Eq> Container for LinearSet<T> {
-        /// Return the number of elements in the set
-        fn len(&const self) -> uint { self.map.len() }
+impl<T:Hash + IterBytes + Eq> Eq for HashSet<T> {
+    fn eq(&self, other: &HashSet<T>) -> bool { self.map == other.map }
+    fn ne(&self, other: &HashSet<T>) -> bool { self.map != other.map }
+}
 
-        /// Return true if the set contains no elements
-        fn is_empty(&const self) -> bool { self.map.is_empty() }
-    }
+impl<T:Hash + IterBytes + Eq> Container for HashSet<T> {
+    /// Return the number of elements in the set
+    fn len(&const self) -> uint { self.map.len() }
 
-    impl<T:Hash + IterBytes + Eq> Mutable for LinearSet<T> {
-        /// Clear the set, removing all values.
-        fn clear(&mut self) { self.map.clear() }
-    }
+    /// Return true if the set contains no elements
+    fn is_empty(&const self) -> bool { self.map.is_empty() }
+}
 
-    impl<T:Hash + IterBytes + Eq> Set<T> for LinearSet<T> {
-        /// Return true if the set contains a value
-        fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
+impl<T:Hash + IterBytes + Eq> Mutable for HashSet<T> {
+    /// Clear the set, removing all values.
+    fn clear(&mut self) { self.map.clear() }
+}
 
-        /// Add a value to the set. Return true if the value was not already
-        /// present in the set.
-        fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+impl<T:Hash + IterBytes + Eq> Set<T> for HashSet<T> {
+    /// Return true if the set contains a value
+    fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
 
-        /// Remove a value from the set. Return true if the value was
-        /// present in the set.
-        fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+    /// Add a value to the set. Return true if the value was not already
+    /// present in the set.
+    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
 
-        /// Return true if the set has no elements in common with `other`.
-        /// This is equivalent to checking for an empty intersection.
-        fn is_disjoint(&self, other: &LinearSet<T>) -> bool {
-            iter::all(self, |v| !other.contains(v))
-        }
+    /// Remove a value from the set. Return true if the value was
+    /// present in the set.
+    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
 
-        /// Return true if the set is a subset of another
-        fn is_subset(&self, other: &LinearSet<T>) -> bool {
-            iter::all(self, |v| other.contains(v))
-        }
+    /// Return true if the set has no elements in common with `other`.
+    /// This is equivalent to checking for an empty intersection.
+    fn is_disjoint(&self, other: &HashSet<T>) -> bool {
+        iter::all(self, |v| !other.contains(v))
+    }
 
-        /// Return true if the set is a superset of another
-        fn is_superset(&self, other: &LinearSet<T>) -> bool {
-            other.is_subset(self)
-        }
+    /// Return true if the set is a subset of another
+    fn is_subset(&self, other: &HashSet<T>) -> bool {
+        iter::all(self, |v| other.contains(v))
+    }
 
-        /// Visit the values representing the difference
-        fn difference(&self, other: &LinearSet<T>, f: &fn(&T) -> bool) {
-            for self.each |v| {
-                if !other.contains(v) {
-                    if !f(v) { return }
-                }
+    /// Return true if the set is a superset of another
+    fn is_superset(&self, other: &HashSet<T>) -> bool {
+        other.is_subset(self)
+    }
+
+    /// Visit the values representing the difference
+    fn difference(&self, other: &HashSet<T>, f: &fn(&T) -> bool) {
+        for self.each |v| {
+            if !other.contains(v) {
+                if !f(v) { return }
             }
         }
+    }
 
-        /// Visit the values representing the symmetric difference
-        fn symmetric_difference(&self,
-                                other: &LinearSet<T>,
-                                f: &fn(&T) -> bool) {
-            self.difference(other, f);
-            other.difference(self, f);
-        }
+    /// Visit the values representing the symmetric difference
+    fn symmetric_difference(&self,
+                            other: &HashSet<T>,
+                            f: &fn(&T) -> bool) {
+        self.difference(other, f);
+        other.difference(self, f);
+    }
 
-        /// Visit the values representing the intersection
-        fn intersection(&self, other: &LinearSet<T>, f: &fn(&T) -> bool) {
-            for self.each |v| {
-                if other.contains(v) {
-                    if !f(v) { return }
-                }
+    /// Visit the values representing the intersection
+    fn intersection(&self, other: &HashSet<T>, f: &fn(&T) -> bool) {
+        for self.each |v| {
+            if other.contains(v) {
+                if !f(v) { return }
             }
         }
+    }
 
-        /// Visit the values representing the union
-        fn union(&self, other: &LinearSet<T>, f: &fn(&T) -> bool) {
-            for self.each |v| {
-                if !f(v) { return }
-            }
+    /// Visit the values representing the union
+    fn union(&self, other: &HashSet<T>, f: &fn(&T) -> bool) {
+        for self.each |v| {
+            if !f(v) { return }
+        }
 
-            for other.each |v| {
-                if !self.contains(v) {
-                    if !f(v) { return }
-                }
+        for other.each |v| {
+            if !self.contains(v) {
+                if !f(v) { return }
             }
         }
     }
+}
 
-    pub impl <T:Hash + IterBytes + Eq> LinearSet<T> {
-        /// Create an empty LinearSet
-        fn new() -> LinearSet<T> {
-            LinearSet::with_capacity(INITIAL_CAPACITY)
-        }
+pub impl <T:Hash + IterBytes + Eq> HashSet<T> {
+    /// Create an empty HashSet
+    fn new() -> HashSet<T> {
+        HashSet::with_capacity(INITIAL_CAPACITY)
+    }
 
-        /// Create an empty LinearSet with space for at least `n` elements in
-        /// the hash table.
-        fn with_capacity(capacity: uint) -> LinearSet<T> {
-            LinearSet { map: LinearMap::with_capacity(capacity) }
-        }
+    /// Create an empty HashSet with space for at least `n` elements in
+    /// the hash table.
+    fn with_capacity(capacity: uint) -> HashSet<T> {
+        HashSet { map: HashMap::with_capacity(capacity) }
+    }
 
-        /// Reserve space for at least `n` elements in the hash table.
-        fn reserve_at_least(&mut self, n: uint) {
-            self.map.reserve_at_least(n)
-        }
+    /// Reserve space for at least `n` elements in the hash table.
+    fn reserve_at_least(&mut self, n: uint) {
+        self.map.reserve_at_least(n)
+    }
 
-        /// Consumes all of the elements in the set, emptying it out
-        fn consume(&mut self, f: &fn(T)) {
-            self.map.consume(|k, _| f(k))
-        }
+    /// Consumes all of the elements in the set, emptying it out
+    fn consume(&mut self, f: &fn(T)) {
+        self.map.consume(|k, _| f(k))
     }
+}
+
+#[test]
+mod test_map {
+    use container::{Container, Map, Set};
+    use option::{None, Some};
+    use super::*;
+    use uint;
 
     #[test]
-    mod test_map {
-        use container::{Container, Map, Set};
-        use option::{None, Some};
-        use hashmap::linear::LinearMap;
-        use hashmap::linear;
-        use uint;
-
-        #[test]
-        pub fn test_insert() {
-            let mut m = LinearMap::new();
-            assert!(m.insert(1, 2));
-            assert!(m.insert(2, 4));
-            assert!(*m.get(&1) == 2);
-            assert!(*m.get(&2) == 4);
-        }
+    pub fn test_insert() {
+        let mut m = HashMap::new();
+        assert!(m.insert(1, 2));
+        assert!(m.insert(2, 4));
+        assert!(*m.get(&1) == 2);
+        assert!(*m.get(&2) == 4);
+    }
 
-        #[test]
-        fn test_find_mut() {
-            let mut m = LinearMap::new();
-            assert!(m.insert(1, 12));
-            assert!(m.insert(2, 8));
-            assert!(m.insert(5, 14));
-            let new = 100;
-            match m.find_mut(&5) {
-                None => fail!(), Some(x) => *x = new
-            }
-            assert_eq!(m.find(&5), Some(&new));
-        }
+    #[test]
+    fn test_find_mut() {
+        let mut m = HashMap::new();
+        assert!(m.insert(1, 12));
+        assert!(m.insert(2, 8));
+        assert!(m.insert(5, 14));
+        let new = 100;
+        match m.find_mut(&5) {
+            None => fail!(), Some(x) => *x = new
+        }
+        assert_eq!(m.find(&5), Some(&new));
+    }
 
-        #[test]
-        pub fn test_insert_overwrite() {
-            let mut m = LinearMap::new();
-            assert!(m.insert(1, 2));
-            assert!(*m.get(&1) == 2);
-            assert!(!m.insert(1, 3));
-            assert!(*m.get(&1) == 3);
-        }
+    #[test]
+    pub fn test_insert_overwrite() {
+        let mut m = HashMap::new();
+        assert!(m.insert(1, 2));
+        assert!(*m.get(&1) == 2);
+        assert!(!m.insert(1, 3));
+        assert!(*m.get(&1) == 3);
+    }
 
-        #[test]
-        pub fn test_insert_conflicts() {
-            let mut m = linear::linear_map_with_capacity(4);
-            assert!(m.insert(1, 2));
-            assert!(m.insert(5, 3));
-            assert!(m.insert(9, 4));
-            assert!(*m.get(&9) == 4);
-            assert!(*m.get(&5) == 3);
-            assert!(*m.get(&1) == 2);
-        }
+    #[test]
+    pub fn test_insert_conflicts() {
+        let mut m = linear_map_with_capacity(4);
+        assert!(m.insert(1, 2));
+        assert!(m.insert(5, 3));
+        assert!(m.insert(9, 4));
+        assert!(*m.get(&9) == 4);
+        assert!(*m.get(&5) == 3);
+        assert!(*m.get(&1) == 2);
+    }
 
-        #[test]
-        pub fn test_conflict_remove() {
-            let mut m = linear::linear_map_with_capacity(4);
-            assert!(m.insert(1, 2));
-            assert!(m.insert(5, 3));
-            assert!(m.insert(9, 4));
-            assert!(m.remove(&1));
-            assert!(*m.get(&9) == 4);
-            assert!(*m.get(&5) == 3);
-        }
+    #[test]
+    pub fn test_conflict_remove() {
+        let mut m = linear_map_with_capacity(4);
+        assert!(m.insert(1, 2));
+        assert!(m.insert(5, 3));
+        assert!(m.insert(9, 4));
+        assert!(m.remove(&1));
+        assert!(*m.get(&9) == 4);
+        assert!(*m.get(&5) == 3);
+    }
 
-        #[test]
-        pub fn test_is_empty() {
-            let mut m = linear::linear_map_with_capacity(4);
-            assert!(m.insert(1, 2));
-            assert!(!m.is_empty());
-            assert!(m.remove(&1));
-            assert!(m.is_empty());
-        }
+    #[test]
+    pub fn test_is_empty() {
+        let mut m = linear_map_with_capacity(4);
+        assert!(m.insert(1, 2));
+        assert!(!m.is_empty());
+        assert!(m.remove(&1));
+        assert!(m.is_empty());
+    }
 
-        #[test]
-        pub fn test_pop() {
-            let mut m = LinearMap::new();
-            m.insert(1, 2);
-            assert!(m.pop(&1) == Some(2));
-            assert!(m.pop(&1) == None);
-        }
+    #[test]
+    pub fn test_pop() {
+        let mut m = HashMap::new();
+        m.insert(1, 2);
+        assert!(m.pop(&1) == Some(2));
+        assert!(m.pop(&1) == None);
+    }
 
-        #[test]
-        pub fn test_swap() {
-            let mut m = LinearMap::new();
-            assert!(m.swap(1, 2) == None);
-            assert!(m.swap(1, 3) == Some(2));
-            assert!(m.swap(1, 4) == Some(3));
-        }
+    #[test]
+    pub fn test_swap() {
+        let mut m = HashMap::new();
+        assert!(m.swap(1, 2) == None);
+        assert!(m.swap(1, 3) == Some(2));
+        assert!(m.swap(1, 4) == Some(3));
+    }
 
-        #[test]
-        pub fn test_find_or_insert() {
-            let mut m = LinearMap::new::<int, int>();
-            assert!(m.find_or_insert(1, 2) == &2);
-            assert!(m.find_or_insert(1, 3) == &2);
-        }
+    #[test]
+    pub fn test_find_or_insert() {
+        let mut m = HashMap::new::<int, int>();
+        assert!(m.find_or_insert(1, 2) == &2);
+        assert!(m.find_or_insert(1, 3) == &2);
+    }
 
-        #[test]
-        pub fn test_find_or_insert_with() {
-            let mut m = LinearMap::new::<int, int>();
-            assert!(m.find_or_insert_with(1, |_| 2) == &2);
-            assert!(m.find_or_insert_with(1, |_| 3) == &2);
-        }
+    #[test]
+    pub fn test_find_or_insert_with() {
+        let mut m = HashMap::new::<int, int>();
+        assert!(m.find_or_insert_with(1, |_| 2) == &2);
+        assert!(m.find_or_insert_with(1, |_| 3) == &2);
+    }
 
-        #[test]
-        pub fn test_consume() {
-            let mut m = LinearMap::new();
-            assert!(m.insert(1, 2));
-            assert!(m.insert(2, 3));
-            let mut m2 = LinearMap::new();
-            do m.consume |k, v| {
-                m2.insert(k, v);
-            }
-            assert!(m.len() == 0);
-            assert!(m2.len() == 2);
-            assert!(m2.get(&1) == &2);
-            assert!(m2.get(&2) == &3);
-        }
+    #[test]
+    pub fn test_consume() {
+        let mut m = HashMap::new();
+        assert!(m.insert(1, 2));
+        assert!(m.insert(2, 3));
+        let mut m2 = HashMap::new();
+        do m.consume |k, v| {
+            m2.insert(k, v);
+        }
+        assert!(m.len() == 0);
+        assert!(m2.len() == 2);
+        assert!(m2.get(&1) == &2);
+        assert!(m2.get(&2) == &3);
+    }
 
-        #[test]
-        pub fn test_iterate() {
-            let mut m = linear::linear_map_with_capacity(4);
-            for uint::range(0, 32) |i| {
-                assert!(m.insert(i, i*2));
-            }
-            let mut observed = 0;
-            for m.each |&(k, v)| {
-                assert!(*v == *k * 2);
-                observed |= (1 << *k);
-            }
-            assert!(observed == 0xFFFF_FFFF);
+    #[test]
+    pub fn test_iterate() {
+        let mut m = linear_map_with_capacity(4);
+        for uint::range(0, 32) |i| {
+            assert!(m.insert(i, i*2));
         }
-
-        #[test]
-        pub fn test_find() {
-            let mut m = LinearMap::new();
-            assert!(m.find(&1).is_none());
-            m.insert(1, 2);
-            match m.find(&1) {
-                None => fail!(),
-                Some(v) => assert!(*v == 2)
-            }
+        let mut observed = 0;
+        for m.each |&(k, v)| {
+            assert!(*v == *k * 2);
+            observed |= (1 << *k);
         }
+        assert!(observed == 0xFFFF_FFFF);
+    }
 
-        #[test]
-        pub fn test_eq() {
-            let mut m1 = LinearMap::new();
-            m1.insert(1, 2);
-            m1.insert(2, 3);
-            m1.insert(3, 4);
+    #[test]
+    pub fn test_find() {
+        let mut m = HashMap::new();
+        assert!(m.find(&1).is_none());
+        m.insert(1, 2);
+        match m.find(&1) {
+            None => fail!(),
+            Some(v) => assert!(*v == 2)
+        }
+    }
 
-            let mut m2 = LinearMap::new();
-            m2.insert(1, 2);
-            m2.insert(2, 3);
+    #[test]
+    pub fn test_eq() {
+        let mut m1 = HashMap::new();
+        m1.insert(1, 2);
+        m1.insert(2, 3);
+        m1.insert(3, 4);
 
-            assert!(m1 != m2);
+        let mut m2 = HashMap::new();
+        m2.insert(1, 2);
+        m2.insert(2, 3);
 
-            m2.insert(3, 4);
+        assert!(m1 != m2);
 
-            assert!(m1 == m2);
-        }
+        m2.insert(3, 4);
 
-        #[test]
-        pub fn test_expand() {
-            let mut m = LinearMap::new();
+        assert!(m1 == m2);
+    }
 
-            assert!(m.len() == 0);
-            assert!(m.is_empty());
+    #[test]
+    pub fn test_expand() {
+        let mut m = HashMap::new();
 
-            let mut i = 0u;
-            let old_resize_at = m.resize_at;
-            while old_resize_at == m.resize_at {
-                m.insert(i, i);
-                i += 1;
-            }
+        assert!(m.len() == 0);
+        assert!(m.is_empty());
 
-            assert!(m.len() == i);
-            assert!(!m.is_empty());
+        let mut i = 0u;
+        let old_resize_at = m.resize_at;
+        while old_resize_at == m.resize_at {
+            m.insert(i, i);
+            i += 1;
         }
+
+        assert!(m.len() == i);
+        assert!(!m.is_empty());
     }
+}
 
 #[test]
-    mod test_set {
-        use hashmap::linear;
-        use container::{Container, Map, Set};
-        use vec;
-
-        #[test]
-        fn test_disjoint() {
-            let mut xs = linear::LinearSet::new();
-            let mut ys = linear::LinearSet::new();
-            assert!(xs.is_disjoint(&ys));
-            assert!(ys.is_disjoint(&xs));
-            assert!(xs.insert(5));
-            assert!(ys.insert(11));
-            assert!(xs.is_disjoint(&ys));
-            assert!(ys.is_disjoint(&xs));
-            assert!(xs.insert(7));
-            assert!(xs.insert(19));
-            assert!(xs.insert(4));
-            assert!(ys.insert(2));
-            assert!(ys.insert(-11));
-            assert!(xs.is_disjoint(&ys));
-            assert!(ys.is_disjoint(&xs));
-            assert!(ys.insert(7));
-            assert!(!xs.is_disjoint(&ys));
-            assert!(!ys.is_disjoint(&xs));
-        }
+mod test_set {
+    use super::*;
+    use container::{Container, Map, Set};
+    use vec;
 
-        #[test]
-        fn test_subset_and_superset() {
-            let mut a = linear::LinearSet::new();
-            assert!(a.insert(0));
-            assert!(a.insert(5));
-            assert!(a.insert(11));
-            assert!(a.insert(7));
-
-            let mut b = linear::LinearSet::new();
-            assert!(b.insert(0));
-            assert!(b.insert(7));
-            assert!(b.insert(19));
-            assert!(b.insert(250));
-            assert!(b.insert(11));
-            assert!(b.insert(200));
-
-            assert!(!a.is_subset(&b));
-            assert!(!a.is_superset(&b));
-            assert!(!b.is_subset(&a));
-            assert!(!b.is_superset(&a));
-
-            assert!(b.insert(5));
-
-            assert!(a.is_subset(&b));
-            assert!(!a.is_superset(&b));
-            assert!(!b.is_subset(&a));
-            assert!(b.is_superset(&a));
-        }
+    #[test]
+    fn test_disjoint() {
+        let mut xs = HashSet::new();
+        let mut ys = HashSet::new();
+        assert!(xs.is_disjoint(&ys));
+        assert!(ys.is_disjoint(&xs));
+        assert!(xs.insert(5));
+        assert!(ys.insert(11));
+        assert!(xs.is_disjoint(&ys));
+        assert!(ys.is_disjoint(&xs));
+        assert!(xs.insert(7));
+        assert!(xs.insert(19));
+        assert!(xs.insert(4));
+        assert!(ys.insert(2));
+        assert!(ys.insert(-11));
+        assert!(xs.is_disjoint(&ys));
+        assert!(ys.is_disjoint(&xs));
+        assert!(ys.insert(7));
+        assert!(!xs.is_disjoint(&ys));
+        assert!(!ys.is_disjoint(&xs));
+    }
 
-        #[test]
-        fn test_intersection() {
-            let mut a = linear::LinearSet::new();
-            let mut b = linear::LinearSet::new();
-
-            assert!(a.insert(11));
-            assert!(a.insert(1));
-            assert!(a.insert(3));
-            assert!(a.insert(77));
-            assert!(a.insert(103));
-            assert!(a.insert(5));
-            assert!(a.insert(-5));
-
-            assert!(b.insert(2));
-            assert!(b.insert(11));
-            assert!(b.insert(77));
-            assert!(b.insert(-9));
-            assert!(b.insert(-42));
-            assert!(b.insert(5));
-            assert!(b.insert(3));
-
-            let mut i = 0;
-            let expected = [3, 5, 11, 77];
-            for a.intersection(&b) |x| {
-                assert!(vec::contains(expected, x));
-                i += 1
-            }
-            assert!(i == expected.len());
-        }
+    #[test]
+    fn test_subset_and_superset() {
+        let mut a = HashSet::new();
+        assert!(a.insert(0));
+        assert!(a.insert(5));
+        assert!(a.insert(11));
+        assert!(a.insert(7));
+
+        let mut b = HashSet::new();
+        assert!(b.insert(0));
+        assert!(b.insert(7));
+        assert!(b.insert(19));
+        assert!(b.insert(250));
+        assert!(b.insert(11));
+        assert!(b.insert(200));
+
+        assert!(!a.is_subset(&b));
+        assert!(!a.is_superset(&b));
+        assert!(!b.is_subset(&a));
+        assert!(!b.is_superset(&a));
+
+        assert!(b.insert(5));
+
+        assert!(a.is_subset(&b));
+        assert!(!a.is_superset(&b));
+        assert!(!b.is_subset(&a));
+        assert!(b.is_superset(&a));
+    }
 
-        #[test]
-        fn test_difference() {
-            let mut a = linear::LinearSet::new();
-            let mut b = linear::LinearSet::new();
-
-            assert!(a.insert(1));
-            assert!(a.insert(3));
-            assert!(a.insert(5));
-            assert!(a.insert(9));
-            assert!(a.insert(11));
-
-            assert!(b.insert(3));
-            assert!(b.insert(9));
-
-            let mut i = 0;
-            let expected = [1, 5, 11];
-            for a.difference(&b) |x| {
-                assert!(vec::contains(expected, x));
-                i += 1
-            }
-            assert!(i == expected.len());
-        }
+    #[test]
+    fn test_intersection() {
+        let mut a = HashSet::new();
+        let mut b = HashSet::new();
+
+        assert!(a.insert(11));
+        assert!(a.insert(1));
+        assert!(a.insert(3));
+        assert!(a.insert(77));
+        assert!(a.insert(103));
+        assert!(a.insert(5));
+        assert!(a.insert(-5));
+
+        assert!(b.insert(2));
+        assert!(b.insert(11));
+        assert!(b.insert(77));
+        assert!(b.insert(-9));
+        assert!(b.insert(-42));
+        assert!(b.insert(5));
+        assert!(b.insert(3));
+
+        let mut i = 0;
+        let expected = [3, 5, 11, 77];
+        for a.intersection(&b) |x| {
+            assert!(vec::contains(expected, x));
+            i += 1
+        }
+        assert!(i == expected.len());
+    }
 
-        #[test]
-        fn test_symmetric_difference() {
-            let mut a = linear::LinearSet::new();
-            let mut b = linear::LinearSet::new();
-
-            assert!(a.insert(1));
-            assert!(a.insert(3));
-            assert!(a.insert(5));
-            assert!(a.insert(9));
-            assert!(a.insert(11));
-
-            assert!(b.insert(-2));
-            assert!(b.insert(3));
-            assert!(b.insert(9));
-            assert!(b.insert(14));
-            assert!(b.insert(22));
-
-            let mut i = 0;
-            let expected = [-2, 1, 5, 11, 14, 22];
-            for a.symmetric_difference(&b) |x| {
-                assert!(vec::contains(expected, x));
-                i += 1
-            }
-            assert!(i == expected.len());
-        }
+    #[test]
+    fn test_difference() {
+        let mut a = HashSet::new();
+        let mut b = HashSet::new();
+
+        assert!(a.insert(1));
+        assert!(a.insert(3));
+        assert!(a.insert(5));
+        assert!(a.insert(9));
+        assert!(a.insert(11));
+
+        assert!(b.insert(3));
+        assert!(b.insert(9));
+
+        let mut i = 0;
+        let expected = [1, 5, 11];
+        for a.difference(&b) |x| {
+            assert!(vec::contains(expected, x));
+            i += 1
+        }
+        assert!(i == expected.len());
+    }
 
-        #[test]
-        fn test_union() {
-            let mut a = linear::LinearSet::new();
-            let mut b = linear::LinearSet::new();
-
-            assert!(a.insert(1));
-            assert!(a.insert(3));
-            assert!(a.insert(5));
-            assert!(a.insert(9));
-            assert!(a.insert(11));
-            assert!(a.insert(16));
-            assert!(a.insert(19));
-            assert!(a.insert(24));
-
-            assert!(b.insert(-2));
-            assert!(b.insert(1));
-            assert!(b.insert(5));
-            assert!(b.insert(9));
-            assert!(b.insert(13));
-            assert!(b.insert(19));
-
-            let mut i = 0;
-            let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
-            for a.union(&b) |x| {
-                assert!(vec::contains(expected, x));
-                i += 1
-            }
-            assert!(i == expected.len());
-        }
+    #[test]
+    fn test_symmetric_difference() {
+        let mut a = HashSet::new();
+        let mut b = HashSet::new();
+
+        assert!(a.insert(1));
+        assert!(a.insert(3));
+        assert!(a.insert(5));
+        assert!(a.insert(9));
+        assert!(a.insert(11));
+
+        assert!(b.insert(-2));
+        assert!(b.insert(3));
+        assert!(b.insert(9));
+        assert!(b.insert(14));
+        assert!(b.insert(22));
+
+        let mut i = 0;
+        let expected = [-2, 1, 5, 11, 14, 22];
+        for a.symmetric_difference(&b) |x| {
+            assert!(vec::contains(expected, x));
+            i += 1
+        }
+        assert!(i == expected.len());
+    }
+
+    #[test]
+    fn test_union() {
+        let mut a = HashSet::new();
+        let mut b = HashSet::new();
+
+        assert!(a.insert(1));
+        assert!(a.insert(3));
+        assert!(a.insert(5));
+        assert!(a.insert(9));
+        assert!(a.insert(11));
+        assert!(a.insert(16));
+        assert!(a.insert(19));
+        assert!(a.insert(24));
+
+        assert!(b.insert(-2));
+        assert!(b.insert(1));
+        assert!(b.insert(5));
+        assert!(b.insert(9));
+        assert!(b.insert(13));
+        assert!(b.insert(19));
+
+        let mut i = 0;
+        let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
+        for a.union(&b) |x| {
+            assert!(vec::contains(expected, x));
+            i += 1
+        }
+        assert!(i == expected.len());
     }
 }
diff --git a/src/libcore/task/spawn.rs b/src/libcore/task/spawn.rs
index 39e43ba6fc5..e1b645cd562 100644
--- a/src/libcore/task/spawn.rs
+++ b/src/libcore/task/spawn.rs
@@ -79,7 +79,7 @@ use comm::{Chan, GenericChan};
 use prelude::*;
 use unstable;
 use ptr;
-use hashmap::linear::LinearSet;
+use hashmap::HashSet;
 use task::local_data_priv::{local_get, local_set};
 use task::rt::rust_task;
 use task::rt;
@@ -96,10 +96,10 @@ macro_rules! move_it (
     { $x:expr } => ( unsafe { let y = *ptr::addr_of(&($x)); y } )
 )
 
-type TaskSet = LinearSet<*rust_task>;
+type TaskSet = HashSet<*rust_task>;
 
 fn new_taskset() -> TaskSet {
-    LinearSet::new()
+    HashSet::new()
 }
 fn taskset_insert(tasks: &mut TaskSet, task: *rust_task) {
     let didnt_overwrite = tasks.insert(task);
diff --git a/src/libcore/unstable/global.rs b/src/libcore/unstable/global.rs
index ef5970658a1..41d0842002f 100644
--- a/src/libcore/unstable/global.rs
+++ b/src/libcore/unstable/global.rs
@@ -34,7 +34,7 @@ use ops::Drop;
 use unstable::{Exclusive, exclusive};
 use unstable::at_exit::at_exit;
 use unstable::intrinsics::atomic_cxchg;
-use hashmap::linear::LinearMap;
+use hashmap::HashMap;
 use sys::Closure;
 
 #[cfg(test)] use unstable::{SharedMutableState, shared_mutable_state};
@@ -144,7 +144,7 @@ pub unsafe fn global_data_clone<T:Owned + Clone>(
 // destructor. Keys are pointers derived from the type of the
 // global value.  There is a single GlobalState instance per runtime.
 struct GlobalState {
-    map: LinearMap<uint, (*c_void, ~fn())>
+    map: HashMap<uint, (*c_void, ~fn())>
 }
 
 impl Drop for GlobalState {
@@ -171,7 +171,7 @@ fn get_global_state() -> Exclusive<GlobalState> {
 
         // The global state object
         let state = GlobalState {
-            map: LinearMap::new()
+            map: HashMap::new()
         };
 
         // It's under a reference-counted mutex
diff --git a/src/libcore/unstable/weak_task.rs b/src/libcore/unstable/weak_task.rs
index 8b24c2fa6f6..6eabb0629d1 100644
--- a/src/libcore/unstable/weak_task.rs
+++ b/src/libcore/unstable/weak_task.rs
@@ -21,7 +21,7 @@ is trying to shut down.
 use cell::Cell;
 use comm::{GenericSmartChan, stream};
 use comm::{Port, Chan, SharedChan, GenericChan, GenericPort};
-use hashmap::linear::LinearMap;
+use hashmap::HashMap;
 use option::{Some, None};
 use unstable::at_exit::at_exit;
 use unstable::finally::Finally;
@@ -97,7 +97,7 @@ fn create_global_service() -> ~WeakTaskService {
 
 fn run_weak_task_service(port: Port<ServiceMsg>) {
 
-    let mut shutdown_map = LinearMap::new();
+    let mut shutdown_map = HashMap::new();
 
     loop {
         match port.recv() {
diff --git a/src/librustc/back/rpath.rs b/src/librustc/back/rpath.rs
index 6c485df84b4..cc1168bd79d 100644
--- a/src/librustc/back/rpath.rs
+++ b/src/librustc/back/rpath.rs
@@ -18,7 +18,7 @@ use core::os;
 use core::uint;
 use core::util;
 use core::vec;
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 
 fn not_win32(os: session::os) -> bool {
   match os {
@@ -186,7 +186,7 @@ pub fn get_install_prefix_rpath(target_triple: &str) -> Path {
 }
 
 pub fn minimize_rpaths(rpaths: &[Path]) -> ~[Path] {
-    let mut set = LinearSet::new();
+    let mut set = HashSet::new();
     let mut minimized = ~[];
     for rpaths.each |rpath| {
         if set.insert(rpath.to_str()) {
diff --git a/src/librustc/lib/llvm.rs b/src/librustc/lib/llvm.rs
index 34678d1803c..b6d3fce7e75 100644
--- a/src/librustc/lib/llvm.rs
+++ b/src/librustc/lib/llvm.rs
@@ -10,7 +10,7 @@
 
 use core::prelude::*;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::libc::c_uint;
 use core::option;
 use core::ptr;
@@ -1467,8 +1467,8 @@ pub fn SetLinkage(Global: ValueRef, Link: Linkage) {
 /* Memory-managed object interface to type handles. */
 
 pub struct TypeNames {
-    type_names: @mut LinearMap<TypeRef, @str>,
-    named_types: @mut LinearMap<@str, TypeRef>
+    type_names: @mut HashMap<TypeRef, @str>,
+    named_types: @mut HashMap<@str, TypeRef>
 }
 
 pub fn associate_type(tn: @TypeNames, s: @str, t: TypeRef) {
@@ -1486,8 +1486,8 @@ pub fn name_has_type(tn: @TypeNames, s: @str) -> Option<TypeRef> {
 
 pub fn mk_type_names() -> @TypeNames {
     @TypeNames {
-        type_names: @mut LinearMap::new(),
-        named_types: @mut LinearMap::new()
+        type_names: @mut HashMap::new(),
+        named_types: @mut HashMap::new()
     }
 }
 
diff --git a/src/librustc/metadata/creader.rs b/src/librustc/metadata/creader.rs
index 086c6a33b3e..8609434e6df 100644
--- a/src/librustc/metadata/creader.rs
+++ b/src/librustc/metadata/creader.rs
@@ -18,7 +18,7 @@ use metadata::decoder;
 use metadata::filesearch::FileSearch;
 use metadata::loader;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::vec;
 use syntax::attr;
 use syntax::codemap::{span, dummy_sp};
@@ -302,7 +302,7 @@ fn resolve_crate_deps(e: @mut Env, cdata: @~[u8]) -> cstore::cnum_map {
     debug!("resolving deps of external crate");
     // The map from crate numbers in the crate we're resolving to local crate
     // numbers
-    let mut cnum_map = LinearMap::new();
+    let mut cnum_map = HashMap::new();
     for decoder::get_crate_deps(e.intr, cdata).each |dep| {
         let extrn_cnum = dep.cnum;
         let cname = dep.name;
diff --git a/src/librustc/metadata/cstore.rs b/src/librustc/metadata/cstore.rs
index c836538e1e6..65bd37236b7 100644
--- a/src/librustc/metadata/cstore.rs
+++ b/src/librustc/metadata/cstore.rs
@@ -17,7 +17,7 @@ use core::prelude::*;
 use metadata::cstore;
 use metadata::decoder;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::vec;
 use std;
 use syntax::ast;
@@ -27,7 +27,7 @@ use syntax::parse::token::ident_interner;
 // local crate numbers (as generated during this session). Each external
 // crate may refer to types in other external crates, and each has their
 // own crate numbers.
-pub type cnum_map = @mut LinearMap<ast::crate_num, ast::crate_num>;
+pub type cnum_map = @mut HashMap<ast::crate_num, ast::crate_num>;
 
 pub struct crate_metadata {
     name: @~str,
@@ -37,7 +37,7 @@ pub struct crate_metadata {
 }
 
 pub struct CStore {
-    priv metas: LinearMap <ast::crate_num, @crate_metadata>,
+    priv metas: HashMap <ast::crate_num, @crate_metadata>,
     priv extern_mod_crate_map: extern_mod_crate_map,
     priv used_crate_files: ~[Path],
     priv used_libraries: ~[~str],
@@ -46,12 +46,12 @@ pub struct CStore {
 }
 
 // Map from node_id's of local extern mod statements to crate numbers
-type extern_mod_crate_map = LinearMap<ast::node_id, ast::crate_num>;
+type extern_mod_crate_map = HashMap<ast::node_id, ast::crate_num>;
 
 pub fn mk_cstore(intr: @ident_interner) -> CStore {
     return CStore {
-        metas: LinearMap::new(),
-        extern_mod_crate_map: LinearMap::new(),
+        metas: HashMap::new(),
+        extern_mod_crate_map: HashMap::new(),
         used_crate_files: ~[],
         used_libraries: ~[],
         used_link_args: ~[],
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 340ad443b58..6000e559554 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -25,7 +25,7 @@ use util::ppaux::ty_to_str;
 
 use core::flate;
 use core::hash::HashUtil;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::int;
 use core::io::{Writer, WriterUtil};
 use core::io;
@@ -50,7 +50,7 @@ use syntax;
 use writer = std::ebml::writer;
 
 // used by astencode:
-type abbrev_map = @mut LinearMap<ty::t, tyencode::ty_abbrev>;
+type abbrev_map = @mut HashMap<ty::t, tyencode::ty_abbrev>;
 
 pub type encode_inlined_item = @fn(ecx: @EncodeContext,
                                    ebml_w: writer::Encoder,
@@ -62,8 +62,8 @@ pub struct EncodeParams {
     tcx: ty::ctxt,
     reachable: reachable::map,
     reexports2: middle::resolve::ExportMap2,
-    item_symbols: @mut LinearMap<ast::node_id, ~str>,
-    discrim_symbols: @mut LinearMap<ast::node_id, ~str>,
+    item_symbols: @mut HashMap<ast::node_id, ~str>,
+    discrim_symbols: @mut HashMap<ast::node_id, ~str>,
     link_meta: LinkMeta,
     cstore: @mut cstore::CStore,
     encode_inlined_item: encode_inlined_item
@@ -89,8 +89,8 @@ pub struct EncodeContext {
     stats: @mut Stats,
     reachable: reachable::map,
     reexports2: middle::resolve::ExportMap2,
-    item_symbols: @mut LinearMap<ast::node_id, ~str>,
-    discrim_symbols: @mut LinearMap<ast::node_id, ~str>,
+    item_symbols: @mut HashMap<ast::node_id, ~str>,
+    discrim_symbols: @mut HashMap<ast::node_id, ~str>,
     link_meta: LinkMeta,
     cstore: @mut cstore::CStore,
     encode_inlined_item: encode_inlined_item,
@@ -1345,7 +1345,7 @@ pub fn encode_metadata(+parms: EncodeParams, crate: &crate) -> ~[u8] {
         link_meta: link_meta,
         cstore: cstore,
         encode_inlined_item: encode_inlined_item,
-        type_abbrevs: @mut LinearMap::new()
+        type_abbrevs: @mut HashMap::new()
      };
 
     let ebml_w = writer::Encoder(wr as @io::Writer);
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 9b777332c27..251ba9b35cb 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -16,7 +16,7 @@ use core::prelude::*;
 use middle::ty::param_ty;
 use middle::ty;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::io::WriterUtil;
 use core::io;
 use core::uint;
@@ -47,7 +47,7 @@ pub struct ty_abbrev {
 
 pub enum abbrev_ctxt {
     ac_no_abbrevs,
-    ac_use_abbrevs(@mut LinearMap<ty::t, ty_abbrev>),
+    ac_use_abbrevs(@mut HashMap<ty::t, ty_abbrev>),
 }
 
 fn cx_uses_abbrevs(cx: @ctxt) -> bool {
diff --git a/src/librustc/middle/borrowck/check_loans.rs b/src/librustc/middle/borrowck/check_loans.rs
index ac74dc25fd0..16035656742 100644
--- a/src/librustc/middle/borrowck/check_loans.rs
+++ b/src/librustc/middle/borrowck/check_loans.rs
@@ -31,7 +31,7 @@ use middle::mem_categorization::{lp_comp, lp_deref, lp_local};
 use middle::ty;
 use util::ppaux::ty_to_str;
 
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use core::uint;
 use syntax::ast::m_mutbl;
 use syntax::ast;
@@ -44,7 +44,7 @@ struct CheckLoanCtxt {
     bccx: @BorrowckCtxt,
     req_maps: ReqMaps,
 
-    reported: LinearSet<ast::node_id>,
+    reported: HashSet<ast::node_id>,
 
     declared_purity: @mut ast::purity,
     fn_args: @mut @~[ast::node_id]
@@ -68,7 +68,7 @@ pub fn check_loans(bccx: @BorrowckCtxt,
     let clcx = @mut CheckLoanCtxt {
         bccx: bccx,
         req_maps: req_maps,
-        reported: LinearSet::new(),
+        reported: HashSet::new(),
         declared_purity: @mut ast::impure_fn,
         fn_args: @mut @~[]
     };
diff --git a/src/librustc/middle/borrowck/gather_loans.rs b/src/librustc/middle/borrowck/gather_loans.rs
index 925659984d4..122e2c64b21 100644
--- a/src/librustc/middle/borrowck/gather_loans.rs
+++ b/src/librustc/middle/borrowck/gather_loans.rs
@@ -31,7 +31,7 @@ use middle::ty;
 use util::common::indenter;
 use util::ppaux::{expr_repr, region_to_str};
 
-use core::hashmap::linear::{LinearSet, LinearMap};
+use core::hashmap::{HashSet, HashMap};
 use core::vec;
 use syntax::ast::{m_const, m_imm, m_mutbl};
 use syntax::ast;
@@ -72,17 +72,17 @@ struct GatherLoanCtxt {
     req_maps: ReqMaps,
     item_ub: ast::node_id,
     root_ub: ast::node_id,
-    ignore_adjustments: LinearSet<ast::node_id>
+    ignore_adjustments: HashSet<ast::node_id>
 }
 
 pub fn gather_loans(bccx: @BorrowckCtxt, crate: @ast::crate) -> ReqMaps {
     let glcx = @mut GatherLoanCtxt {
         bccx: bccx,
-        req_maps: ReqMaps { req_loan_map: LinearMap::new(),
-                            pure_map: LinearMap::new() },
+        req_maps: ReqMaps { req_loan_map: HashMap::new(),
+                            pure_map: HashMap::new() },
         item_ub: 0,
         root_ub: 0,
-        ignore_adjustments: LinearSet::new()
+        ignore_adjustments: HashSet::new()
     };
     let v = visit::mk_vt(@visit::Visitor {visit_expr: req_loans_in_expr,
                                           visit_fn: req_loans_in_fn,
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index 3f4f7469832..5e7903f6610 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -234,7 +234,7 @@ use middle::moves;
 use util::common::stmt_set;
 use util::ppaux::note_and_explain_region;
 
-use core::hashmap::linear::{LinearSet, LinearMap};
+use core::hashmap::{HashSet, HashMap};
 use core::io;
 use core::result::{Result, Ok, Err};
 use core::to_bytes;
@@ -260,9 +260,9 @@ pub fn check_crate(
         moves_map: moves_map,
         capture_map: capture_map,
         root_map: root_map(),
-        mutbl_map: @mut LinearSet::new(),
-        write_guard_map: @mut LinearSet::new(),
-        stmt_map: @mut LinearSet::new(),
+        mutbl_map: @mut HashSet::new(),
+        write_guard_map: @mut HashSet::new(),
+        stmt_map: @mut HashSet::new(),
         stats: @mut BorrowStats {
             loaned_paths_same: 0,
             loaned_paths_imm: 0,
@@ -333,7 +333,7 @@ pub struct RootInfo {
 // a map mapping id's of expressions of gc'd type (@T, @[], etc) where
 // the box needs to be kept live to the id of the scope for which they
 // must stay live.
-pub type root_map = @mut LinearMap<root_map_key, RootInfo>;
+pub type root_map = @mut HashMap<root_map_key, RootInfo>;
 
 // the keys to the root map combine the `id` of the expression with
 // the number of types that it is autodereferenced.  So, for example,
@@ -348,11 +348,11 @@ pub struct root_map_key {
 
 // set of ids of local vars / formal arguments that are modified / moved.
 // this is used in trans for optimization purposes.
-pub type mutbl_map = @mut LinearSet<ast::node_id>;
+pub type mutbl_map = @mut HashSet<ast::node_id>;
 
 // A set containing IDs of expressions of gc'd type that need to have a write
 // guard.
-pub type write_guard_map = @mut LinearSet<root_map_key>;
+pub type write_guard_map = @mut HashSet<root_map_key>;
 
 // Errors that can occur
 #[deriving(Eq)]
@@ -405,8 +405,8 @@ pub struct Loan {
 /// - `pure_map`: map from block/expr that must be pure to the error message
 ///   that should be reported if they are not pure
 pub struct ReqMaps {
-    req_loan_map: LinearMap<ast::node_id, @mut ~[Loan]>,
-    pure_map: LinearMap<ast::node_id, bckerr>
+    req_loan_map: HashMap<ast::node_id, @mut ~[Loan]>,
+    pure_map: HashMap<ast::node_id, bckerr>
 }
 
 pub fn save_and_restore<T:Copy,U>(save_and_restore_t: &mut T,
@@ -450,7 +450,7 @@ impl to_bytes::IterBytes for root_map_key {
 }
 
 pub fn root_map() -> root_map {
-    return @mut LinearMap::new();
+    return @mut HashMap::new();
 }
 
 // ___________________________________________________________________________
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index d610b007f35..d6434e469b2 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -20,7 +20,7 @@ use core::vec;
 use syntax::{ast, ast_map, ast_util, visit};
 use syntax::ast::*;
 
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 
 //
 // This pass classifies expressions by their constant-ness.
@@ -189,14 +189,14 @@ pub fn lookup_const_by_id(tcx: ty::ctxt,
         }
     } else {
         let maps = astencode::Maps {
-            mutbl_map: @mut LinearSet::new(),
-            root_map: @mut LinearMap::new(),
-            last_use_map: @mut LinearMap::new(),
-            method_map: @mut LinearMap::new(),
-            vtable_map: @mut LinearMap::new(),
-            write_guard_map: @mut LinearSet::new(),
-            moves_map: @mut LinearSet::new(),
-            capture_map: @mut LinearMap::new()
+            mutbl_map: @mut HashSet::new(),
+            root_map: @mut HashMap::new(),
+            last_use_map: @mut HashMap::new(),
+            method_map: @mut HashMap::new(),
+            vtable_map: @mut HashMap::new(),
+            write_guard_map: @mut HashSet::new(),
+            moves_map: @mut HashSet::new(),
+            capture_map: @mut HashMap::new()
         };
         match csearch::maybe_get_item_ast(tcx, def_id,
             |a, b, c, d| astencode::decode_inlined_item(a, b, maps, /*bar*/ copy c, d)) {
diff --git a/src/librustc/middle/freevars.rs b/src/librustc/middle/freevars.rs
index 19d3e1f431d..e6e9f3be85d 100644
--- a/src/librustc/middle/freevars.rs
+++ b/src/librustc/middle/freevars.rs
@@ -17,7 +17,7 @@ use core::prelude::*;
 use middle::resolve;
 use middle::ty;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use syntax::codemap::span;
 use syntax::{ast, ast_util, visit};
 
@@ -30,7 +30,7 @@ pub struct freevar_entry {
     span: span     //< First span where it is accessed (there can be multiple)
 }
 pub type freevar_info = @~[@freevar_entry];
-pub type freevar_map = @mut LinearMap<ast::node_id, freevar_info>;
+pub type freevar_map = @mut HashMap<ast::node_id, freevar_info>;
 
 // Searches through part of the AST for all references to locals or
 // upvars in this frame and returns the list of definition IDs thus found.
@@ -39,7 +39,7 @@ pub type freevar_map = @mut LinearMap<ast::node_id, freevar_info>;
 // in order to start the search.
 fn collect_freevars(def_map: resolve::DefMap, blk: &ast::blk)
     -> freevar_info {
-    let seen = @mut LinearMap::new();
+    let seen = @mut HashMap::new();
     let refs = @mut ~[];
 
     fn ignore_item(_i: @ast::item, &&_depth: int, _v: visit::vt<int>) { }
@@ -92,7 +92,7 @@ fn collect_freevars(def_map: resolve::DefMap, blk: &ast::blk)
 // one pass. This could be improved upon if it turns out to matter.
 pub fn annotate_freevars(def_map: resolve::DefMap, crate: @ast::crate) ->
    freevar_map {
-    let freevars = @mut LinearMap::new();
+    let freevars = @mut HashMap::new();
 
     let walk_fn: @fn(&visit::fn_kind,
                      &ast::fn_decl,
diff --git a/src/librustc/middle/lang_items.rs b/src/librustc/middle/lang_items.rs
index 566a52c3894..ab9b8ca0db6 100644
--- a/src/librustc/middle/lang_items.rs
+++ b/src/librustc/middle/lang_items.rs
@@ -31,7 +31,7 @@ use syntax::ast_util::local_def;
 use syntax::visit::{default_simple_visitor, mk_simple_visitor, SimpleVisitor};
 use syntax::visit::visit_crate;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::ptr;
 
 pub enum LangItem {
@@ -259,7 +259,7 @@ fn LanguageItemCollector<'r>(crate: @crate,
                              session: Session,
                              items: &'r mut LanguageItems)
                           -> LanguageItemCollector<'r> {
-    let mut item_refs = LinearMap::new();
+    let mut item_refs = HashMap::new();
 
     item_refs.insert(@~"const", ConstTraitLangItem as uint);
     item_refs.insert(@~"copy", CopyTraitLangItem as uint);
@@ -317,7 +317,7 @@ struct LanguageItemCollector<'self> {
     crate: @crate,
     session: Session,
 
-    item_refs: LinearMap<@~str, uint>,
+    item_refs: HashMap<@~str, uint>,
 }
 
 pub impl<'self> LanguageItemCollector<'self> {
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index ba232f55f74..a21cc26bd91 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -15,7 +15,7 @@ use driver::session;
 use middle::ty;
 use util::ppaux::{ty_to_str};
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::char;
 use core::cmp;
 use core::i8;
@@ -108,7 +108,7 @@ struct LintSpec {
     default: level
 }
 
-pub type LintDict = @LinearMap<~str, LintSpec>;
+pub type LintDict = @HashMap<~str, LintSpec>;
 
 /*
   Pass names should not contain a '-', as the compiler normalizes
@@ -273,7 +273,7 @@ pub fn get_lint_dict() -> LintDict {
          }),
         */
     ];
-    let mut map = LinearMap::new();
+    let mut map = HashMap::new();
     do vec::consume(v) |_, (k, v)| {
         map.insert(k, v);
     }
@@ -282,7 +282,7 @@ pub fn get_lint_dict() -> LintDict {
 
 // This is a highly not-optimal set of data structure decisions.
 type LintModes = @mut SmallIntMap<level>;
-type LintModeMap = @mut LinearMap<ast::node_id, LintModes>;
+type LintModeMap = @mut HashMap<ast::node_id, LintModes>;
 
 // settings_map maps node ids of items with non-default lint settings
 // to their settings; default_settings contains the settings for everything
@@ -295,7 +295,7 @@ pub struct LintSettings {
 pub fn mk_lint_settings() -> LintSettings {
     LintSettings {
         default_settings: @mut SmallIntMap::new(),
-        settings_map: @mut LinearMap::new()
+        settings_map: @mut HashMap::new()
     }
 }
 
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index e9e226d36d1..01598b11851 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -111,7 +111,7 @@ use middle::typeck;
 use middle::moves;
 use util::ppaux::ty_to_str;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::io::WriterUtil;
 use core::io;
 use core::ptr;
@@ -134,7 +134,7 @@ use syntax::{visit, ast_util};
 //
 // Very subtle (#2633): borrowck will remove entries from this table
 // if it detects an outstanding loan (that is, the addr is taken).
-pub type last_use_map = @mut LinearMap<node_id, @mut ~[node_id]>;
+pub type last_use_map = @mut HashMap<node_id, @mut ~[node_id]>;
 
 #[deriving(Eq)]
 struct Variable(uint);
@@ -172,7 +172,7 @@ pub fn check_crate(tcx: ty::ctxt,
         .. *visit::default_visitor()
     });
 
-    let last_use_map = @mut LinearMap::new();
+    let last_use_map = @mut HashMap::new();
     let initial_maps = @mut IrMaps(tcx,
                                    method_map,
                                    variable_moves_map,
@@ -264,9 +264,9 @@ struct IrMaps {
 
     num_live_nodes: uint,
     num_vars: uint,
-    live_node_map: LinearMap<node_id, LiveNode>,
-    variable_map: LinearMap<node_id, Variable>,
-    capture_info_map: LinearMap<node_id, @~[CaptureInfo]>,
+    live_node_map: HashMap<node_id, LiveNode>,
+    variable_map: HashMap<node_id, Variable>,
+    capture_info_map: HashMap<node_id, @~[CaptureInfo]>,
     var_kinds: ~[VarKind],
     lnks: ~[LiveNodeKind],
 }
@@ -285,9 +285,9 @@ fn IrMaps(tcx: ty::ctxt,
         last_use_map: last_use_map,
         num_live_nodes: 0,
         num_vars: 0,
-        live_node_map: LinearMap::new(),
-        variable_map: LinearMap::new(),
-        capture_info_map: LinearMap::new(),
+        live_node_map: HashMap::new(),
+        variable_map: HashMap::new(),
+        capture_info_map: HashMap::new(),
         var_kinds: ~[],
         lnks: ~[]
     }
@@ -612,7 +612,7 @@ static ACC_READ: uint = 1u;
 static ACC_WRITE: uint = 2u;
 static ACC_USE: uint = 4u;
 
-type LiveNodeMap = @mut LinearMap<node_id, LiveNode>;
+type LiveNodeMap = @mut HashMap<node_id, LiveNode>;
 
 struct Liveness {
     tcx: ty::ctxt,
@@ -639,8 +639,8 @@ fn Liveness(ir: @mut IrMaps, specials: Specials) -> Liveness {
         users: @mut vec::from_elem(ir.num_live_nodes * ir.num_vars,
                                    invalid_users()),
         loop_scope: @mut ~[],
-        break_ln: @mut LinearMap::new(),
-        cont_ln: @mut LinearMap::new()
+        break_ln: @mut HashMap::new(),
+        cont_ln: @mut HashMap::new()
     }
 }
 
diff --git a/src/librustc/middle/moves.rs b/src/librustc/middle/moves.rs
index a93618b6624..2f379ece5d3 100644
--- a/src/librustc/middle/moves.rs
+++ b/src/librustc/middle/moves.rs
@@ -215,7 +215,7 @@ use middle::typeck::method_map;
 use util::ppaux;
 use util::common::indenter;
 
-use core::hashmap::linear::{LinearSet, LinearMap};
+use core::hashmap::{HashSet, HashMap};
 use core::vec;
 use syntax::ast::*;
 use syntax::ast_util;
@@ -240,14 +240,14 @@ pub struct CaptureVar {
     mode: CaptureMode // How variable is being accessed
 }
 
-pub type CaptureMap = @mut LinearMap<node_id, @[CaptureVar]>;
+pub type CaptureMap = @mut HashMap<node_id, @[CaptureVar]>;
 
-pub type MovesMap = @mut LinearSet<node_id>;
+pub type MovesMap = @mut HashSet<node_id>;
 
 /**
  * For each variable which will be moved, links to the
  * expression */
-pub type VariableMovesMap = @mut LinearMap<node_id, @expr>;
+pub type VariableMovesMap = @mut HashMap<node_id, @expr>;
 
 /** See the section Output on the module comment for explanation. */
 pub struct MoveMaps {
@@ -280,9 +280,9 @@ pub fn compute_moves(tcx: ty::ctxt,
         tcx: tcx,
         method_map: method_map,
         move_maps: MoveMaps {
-            moves_map: @mut LinearSet::new(),
-            variable_moves_map: @mut LinearMap::new(),
-            capture_map: @mut LinearMap::new()
+            moves_map: @mut HashSet::new(),
+            variable_moves_map: @mut HashMap::new(),
+            capture_map: @mut HashMap::new()
         }
     };
     visit::visit_crate(*crate, visit_cx, visitor);
diff --git a/src/librustc/middle/pat_util.rs b/src/librustc/middle/pat_util.rs
index 0e47dabcce9..2e2048b7ae4 100644
--- a/src/librustc/middle/pat_util.rs
+++ b/src/librustc/middle/pat_util.rs
@@ -12,17 +12,17 @@ use core::prelude::*;
 
 use middle::resolve;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use syntax::ast::*;
 use syntax::ast_util::{path_to_ident, walk_pat};
 use syntax::codemap::span;
 
-pub type PatIdMap = LinearMap<ident, node_id>;
+pub type PatIdMap = HashMap<ident, node_id>;
 
 // This is used because same-named variables in alternative patterns need to
 // use the node_id of their namesake in the first pattern.
 pub fn pat_id_map(dm: resolve::DefMap, pat: @pat) -> PatIdMap {
-    let mut map = LinearMap::new();
+    let mut map = HashMap::new();
     do pat_bindings(dm, pat) |_bm, p_id, _s, n| {
       map.insert(path_to_ident(n), p_id);
     };
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index f6025548d71..75eb8ef1a85 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -26,7 +26,7 @@ use middle::ty::{region_variance, rv_covariant, rv_invariant};
 use middle::ty::{rv_contravariant};
 use middle::ty;
 
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::vec;
 use syntax::ast_map;
 use syntax::codemap::span;
@@ -46,7 +46,7 @@ Encodes the bounding lifetime for a given AST node:
 - Variables and bindings are mapped to the block in which they are declared.
 
 */
-pub type region_map = @mut LinearMap<ast::node_id, ast::node_id>;
+pub type region_map = @mut HashMap<ast::node_id, ast::node_id>;
 
 pub struct ctxt {
     sess: Session,
@@ -62,7 +62,7 @@ pub struct ctxt {
     // the condition in a while loop is always a parent.  In those
     // cases, we add the node id of such an expression to this set so
     // that when we visit it we can view it as a parent.
-    root_exprs: @mut LinearSet<ast::node_id>,
+    root_exprs: @mut HashSet<ast::node_id>,
 
     // The parent scope is the innermost block, statement, call, or match
     // expression during the execution of which the current expression
@@ -350,8 +350,8 @@ pub fn resolve_crate(sess: Session,
                   -> region_map {
     let cx: ctxt = ctxt {sess: sess,
                          def_map: def_map,
-                         region_map: @mut LinearMap::new(),
-                         root_exprs: @mut LinearSet::new(),
+                         region_map: @mut HashMap::new(),
+                         root_exprs: @mut HashSet::new(),
                          parent: None};
     let visitor = visit::mk_vt(@visit::Visitor {
         visit_block: resolve_block,
@@ -387,7 +387,7 @@ pub fn resolve_crate(sess: Session,
 // a worklist.  We can then process the worklist, propagating indirect
 // dependencies until a fixed point is reached.
 
-pub type region_paramd_items = @mut LinearMap<ast::node_id, region_variance>;
+pub type region_paramd_items = @mut HashMap<ast::node_id, region_variance>;
 
 #[deriving(Eq)]
 pub struct region_dep {
@@ -395,7 +395,7 @@ pub struct region_dep {
     id: ast::node_id
 }
 
-pub type dep_map = @mut LinearMap<ast::node_id, @mut ~[region_dep]>;
+pub type dep_map = @mut HashMap<ast::node_id, @mut ~[region_dep]>;
 
 pub struct DetermineRpCtxt {
     sess: Session,
@@ -790,8 +790,8 @@ pub fn determine_rp_in_crate(sess: Session,
         sess: sess,
         ast_map: ast_map,
         def_map: def_map,
-        region_paramd_items: @mut LinearMap::new(),
-        dep_map: @mut LinearMap::new(),
+        region_paramd_items: @mut HashMap::new(),
+        dep_map: @mut HashMap::new(),
         worklist: ~[],
         item_id: 0,
         anon_implies_rp: false,
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 70d9dfacb69..08542301e23 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -77,10 +77,10 @@ use syntax::opt_vec::OptVec;
 
 use core::option::Some;
 use core::str::each_split_str;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 
 // Definition mapping
-pub type DefMap = @mut LinearMap<node_id,def>;
+pub type DefMap = @mut HashMap<node_id,def>;
 
 pub struct binding_info {
     span: span,
@@ -88,7 +88,7 @@ pub struct binding_info {
 }
 
 // Map from the name in a pattern to its binding mode.
-pub type BindingMap = LinearMap<ident,binding_info>;
+pub type BindingMap = HashMap<ident,binding_info>;
 
 // Implementation resolution
 //
@@ -109,11 +109,11 @@ pub struct Impl {
 }
 
 // Trait method resolution
-pub type TraitMap = LinearMap<node_id,@mut ~[def_id]>;
+pub type TraitMap = HashMap<node_id,@mut ~[def_id]>;
 
 // This is the replacement export map. It maps a module to all of the exports
 // within.
-pub type ExportMap2 = @mut LinearMap<node_id, ~[Export2]>;
+pub type ExportMap2 = @mut HashMap<node_id, ~[Export2]>;
 
 pub struct Export2 {
     name: @~str,        // The name of the target.
@@ -328,13 +328,13 @@ pub fn namespace_for_duplicate_checking_mode(mode: DuplicateCheckingMode)
 
 /// One local scope.
 pub struct Rib {
-    bindings: @mut LinearMap<ident,def_like>,
+    bindings: @mut HashMap<ident,def_like>,
     kind: RibKind,
 }
 
 pub fn Rib(kind: RibKind) -> Rib {
     Rib {
-        bindings: @mut LinearMap::new(),
+        bindings: @mut HashMap::new(),
         kind: kind
     }
 }
@@ -450,12 +450,12 @@ pub struct Module {
     def_id: Option<def_id>,
     kind: ModuleKind,
 
-    children: @mut LinearMap<ident, @mut NameBindings>,
+    children: @mut HashMap<ident, @mut NameBindings>,
     imports: @mut ~[@ImportDirective],
 
     // The external module children of this node that were declared with
     // `extern mod`.
-    external_module_children: @mut LinearMap<ident, @mut Module>,
+    external_module_children: @mut HashMap<ident, @mut Module>,
 
     // The anonymous children of this node. Anonymous children are pseudo-
     // modules that are implicitly created around items contained within
@@ -472,10 +472,10 @@ pub struct Module {
     // There will be an anonymous module created around `g` with the ID of the
     // entry block for `f`.
 
-    anonymous_children: @mut LinearMap<node_id,@mut Module>,
+    anonymous_children: @mut HashMap<node_id,@mut Module>,
 
     // The status of resolving each import in this module.
-    import_resolutions: @mut LinearMap<ident, @mut ImportResolution>,
+    import_resolutions: @mut HashMap<ident, @mut ImportResolution>,
 
     // The number of unresolved globs that this module exports.
     glob_count: uint,
@@ -492,11 +492,11 @@ pub fn Module(parent_link: ParentLink,
         parent_link: parent_link,
         def_id: def_id,
         kind: kind,
-        children: @mut LinearMap::new(),
+        children: @mut HashMap::new(),
         imports: @mut ~[],
-        external_module_children: @mut LinearMap::new(),
-        anonymous_children: @mut LinearMap::new(),
-        import_resolutions: @mut LinearMap::new(),
+        external_module_children: @mut HashMap::new(),
+        anonymous_children: @mut HashMap::new(),
+        import_resolutions: @mut HashMap::new(),
         glob_count: 0,
         resolved_import_count: 0
     }
@@ -707,7 +707,7 @@ pub fn NameBindings() -> NameBindings {
 
 /// Interns the names of the primitive types.
 pub struct PrimitiveTypeTable {
-    primitive_types: LinearMap<ident,prim_ty>,
+    primitive_types: HashMap<ident,prim_ty>,
 }
 
 pub impl PrimitiveTypeTable {
@@ -720,7 +720,7 @@ pub impl PrimitiveTypeTable {
 
 pub fn PrimitiveTypeTable(intr: @ident_interner) -> PrimitiveTypeTable {
     let mut table = PrimitiveTypeTable {
-        primitive_types: LinearMap::new()
+        primitive_types: HashMap::new()
     };
 
     table.intern(intr, @~"bool",    ty_bool);
@@ -775,8 +775,8 @@ pub fn Resolver(session: Session,
 
         graph_root: graph_root,
 
-        trait_info: LinearMap::new(),
-        structs: LinearSet::new(),
+        trait_info: HashMap::new(),
+        structs: HashSet::new(),
 
         unresolved_imports: 0,
 
@@ -799,9 +799,9 @@ pub fn Resolver(session: Session,
         attr_main_fn: None,
         main_fns: ~[],
 
-        def_map: @mut LinearMap::new(),
-        export_map2: @mut LinearMap::new(),
-        trait_map: LinearMap::new(),
+        def_map: @mut HashMap::new(),
+        export_map2: @mut HashMap::new(),
+        trait_map: HashMap::new(),
 
         intr: session.intr()
     };
@@ -819,8 +819,8 @@ pub struct Resolver {
 
     graph_root: @mut NameBindings,
 
-    trait_info: LinearMap<def_id, LinearSet<ident>>,
-    structs: LinearSet<def_id>,
+    trait_info: HashMap<def_id, HashSet<ident>>,
+    structs: HashSet<def_id>,
 
     // The number of imports that are currently unresolved.
     unresolved_imports: uint,
@@ -1309,7 +1309,7 @@ pub impl Resolver {
                 }
 
                 // Add the names of all the methods to the trait info.
-                let mut method_names = LinearSet::new();
+                let mut method_names = HashSet::new();
                 for methods.each |method| {
                     let ty_m = trait_method_to_ty_method(method);
 
@@ -1543,7 +1543,7 @@ pub impl Resolver {
 
     fn handle_external_def(@mut self,
                            def: def,
-                           modules: &mut LinearMap<def_id, @mut Module>,
+                           modules: &mut HashMap<def_id, @mut Module>,
                            child_name_bindings: @mut NameBindings,
                            final_ident: &str,
                            ident: ident,
@@ -1623,7 +1623,7 @@ pub impl Resolver {
                 // Nothing to do.
               }
               Some(method_names) => {
-                let mut interned_method_names = LinearSet::new();
+                let mut interned_method_names = HashSet::new();
                 for method_names.each |method_data| {
                     let (method_name, self_ty) = *method_data;
                     debug!("(building reduced graph for \
@@ -1663,7 +1663,7 @@ pub impl Resolver {
      * crate.
      */
     fn build_reduced_graph_for_external_crate(@mut self, root: @mut Module) {
-        let mut modules = LinearMap::new();
+        let mut modules = HashMap::new();
 
         // Create all the items reachable by paths.
         for each_path(self.session.cstore, root.def_id.get().crate)
@@ -3906,7 +3906,7 @@ pub impl Resolver {
     }
 
     fn binding_mode_map(@mut self, pat: @pat) -> BindingMap {
-        let mut result = LinearMap::new();
+        let mut result = HashMap::new();
         do pat_bindings(self.def_map, pat) |binding_mode, _id, sp, path| {
             let ident = path_to_ident(path);
             result.insert(ident,
@@ -3958,7 +3958,7 @@ pub impl Resolver {
     fn resolve_arm(@mut self, arm: &arm, visitor: ResolveVisitor) {
         self.value_ribs.push(@Rib(NormalRibKind));
 
-        let bindings_list = @mut LinearMap::new();
+        let bindings_list = @mut HashMap::new();
         for arm.pats.each |pattern| {
             self.resolve_pattern(*pattern, RefutableMode, Immutable,
                                  Some(bindings_list), visitor);
@@ -4078,7 +4078,7 @@ pub impl Resolver {
                        mutability: Mutability,
                        // Maps idents to the node ID for the (outermost)
                        // pattern that binds them
-                       bindings_list: Option<@mut LinearMap<ident,node_id>>,
+                       bindings_list: Option<@mut HashMap<ident,node_id>>,
                        visitor: ResolveVisitor) {
         let pat_id = pattern.id;
         do walk_pat(pattern) |pattern| {
@@ -4282,7 +4282,7 @@ pub impl Resolver {
                 }
 
                 pat_struct(path, _, _) => {
-                    let structs: &mut LinearSet<def_id> = &mut self.structs;
+                    let structs: &mut HashSet<def_id> = &mut self.structs;
                     match self.resolve_path(path, TypeNS, false, visitor) {
                         Some(def_ty(class_id))
                                 if structs.contains(&class_id) => {
@@ -4791,7 +4791,7 @@ pub impl Resolver {
 
             expr_struct(path, _, _) => {
                 // Resolve the path to the structure it goes to.
-                let structs: &mut LinearSet<def_id> = &mut self.structs;
+                let structs: &mut HashSet<def_id> = &mut self.structs;
                 match self.resolve_path(path, TypeNS, false, visitor) {
                     Some(def_ty(class_id)) | Some(def_struct(class_id))
                             if structs.contains(&class_id) => {
diff --git a/src/librustc/middle/trans/_match.rs b/src/librustc/middle/trans/_match.rs
index 12eaeb77d11..32c9189ad2d 100644
--- a/src/librustc/middle/trans/_match.rs
+++ b/src/librustc/middle/trans/_match.rs
@@ -167,7 +167,7 @@ use middle::trans::type_of;
 use middle::ty;
 use util::common::indenter;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use syntax::ast;
 use syntax::ast::ident;
 use syntax::ast_util::path_to_ident;
@@ -323,7 +323,7 @@ pub struct BindingInfo {
     ty: ty::t,
 }
 
-pub type BindingsMap = LinearMap<ident, BindingInfo>;
+pub type BindingsMap = HashMap<ident, BindingInfo>;
 
 pub struct ArmData<'self> {
     bodycx: block,
@@ -1620,7 +1620,7 @@ pub fn trans_match_inner(scope_cx: block,
         // to an alloca() that will be the value for that local variable.
         // Note that we use the names because each binding will have many ids
         // from the various alternatives.
-        let mut bindings_map = LinearMap::new();
+        let mut bindings_map = HashMap::new();
         do pat_bindings(tcx.def_map, arm.pats[0]) |bm, p_id, _s, path| {
             let ident = path_to_ident(path);
             let variable_ty = node_id_type(bcx, p_id);
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index 15238f16894..aa97c287b4c 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -67,7 +67,7 @@ use util::ppaux::ty_to_str;
 use util::ppaux;
 
 use core::hash;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::int;
 use core::io;
 use core::libc::{c_uint, c_ulonglong};
@@ -1609,9 +1609,9 @@ pub fn new_fn_ctxt_w_id(ccx: @CrateContext,
           llself: None,
           personality: None,
           loop_ret: None,
-          llargs: @mut LinearMap::new(),
-          lllocals: @mut LinearMap::new(),
-          llupvars: @mut LinearMap::new(),
+          llargs: @mut HashMap::new(),
+          lllocals: @mut HashMap::new(),
+          llupvars: @mut HashMap::new(),
           id: id,
           impl_id: impl_id,
           param_substs: param_substs,
@@ -2610,7 +2610,7 @@ pub fn p2i(ccx: @CrateContext, v: ValueRef) -> ValueRef {
     }
 }
 
-pub fn declare_intrinsics(llmod: ModuleRef) -> LinearMap<~str, ValueRef> {
+pub fn declare_intrinsics(llmod: ModuleRef) -> HashMap<~str, ValueRef> {
     let T_memcpy32_args: ~[TypeRef] =
         ~[T_ptr(T_i8()), T_ptr(T_i8()), T_i32(), T_i32(), T_i1()];
     let T_memcpy64_args: ~[TypeRef] =
@@ -2743,7 +2743,7 @@ pub fn declare_intrinsics(llmod: ModuleRef) -> LinearMap<~str, ValueRef> {
     let bswap64 = decl_cdecl_fn(llmod, ~"llvm.bswap.i64",
                                 T_fn(~[T_i64()], T_i64()));
 
-    let mut intrinsics = LinearMap::new();
+    let mut intrinsics = HashMap::new();
     intrinsics.insert(~"llvm.gcroot", gcroot);
     intrinsics.insert(~"llvm.gcread", gcread);
     intrinsics.insert(~"llvm.memcpy.p0i8.p0i8.i32", memcpy32);
@@ -2804,7 +2804,7 @@ pub fn declare_intrinsics(llmod: ModuleRef) -> LinearMap<~str, ValueRef> {
 }
 
 pub fn declare_dbg_intrinsics(llmod: ModuleRef,
-                              intrinsics: &mut LinearMap<~str, ValueRef>) {
+                              intrinsics: &mut HashMap<~str, ValueRef>) {
     let declare =
         decl_cdecl_fn(llmod, ~"llvm.dbg.declare",
                       T_fn(~[T_metadata(), T_metadata()], T_void()));
@@ -3052,37 +3052,37 @@ pub fn trans_crate(sess: session::Session,
               llmod: llmod,
               td: td,
               tn: tn,
-              externs: @mut LinearMap::new(),
+              externs: @mut HashMap::new(),
               intrinsics: intrinsics,
-              item_vals: @mut LinearMap::new(),
+              item_vals: @mut HashMap::new(),
               exp_map2: emap2,
               reachable: reachable,
-              item_symbols: @mut LinearMap::new(),
+              item_symbols: @mut HashMap::new(),
               link_meta: link_meta,
-              enum_sizes: @mut LinearMap::new(),
-              discrims: @mut LinearMap::new(),
-              discrim_symbols: @mut LinearMap::new(),
-              tydescs: @mut LinearMap::new(),
+              enum_sizes: @mut HashMap::new(),
+              discrims: @mut HashMap::new(),
+              discrim_symbols: @mut HashMap::new(),
+              tydescs: @mut HashMap::new(),
               finished_tydescs: @mut false,
-              external: @mut LinearMap::new(),
-              monomorphized: @mut LinearMap::new(),
-              monomorphizing: @mut LinearMap::new(),
-              type_use_cache: @mut LinearMap::new(),
-              vtables: @mut LinearMap::new(),
-              const_cstr_cache: @mut LinearMap::new(),
-              const_globals: @mut LinearMap::new(),
-              const_values: @mut LinearMap::new(),
-              extern_const_values: @mut LinearMap::new(),
-              module_data: @mut LinearMap::new(),
-              lltypes: @mut LinearMap::new(),
-              llsizingtypes: @mut LinearMap::new(),
-              adt_reprs: @mut LinearMap::new(),
+              external: @mut HashMap::new(),
+              monomorphized: @mut HashMap::new(),
+              monomorphizing: @mut HashMap::new(),
+              type_use_cache: @mut HashMap::new(),
+              vtables: @mut HashMap::new(),
+              const_cstr_cache: @mut HashMap::new(),
+              const_globals: @mut HashMap::new(),
+              const_values: @mut HashMap::new(),
+              extern_const_values: @mut HashMap::new(),
+              module_data: @mut HashMap::new(),
+              lltypes: @mut HashMap::new(),
+              llsizingtypes: @mut HashMap::new(),
+              adt_reprs: @mut HashMap::new(),
               names: new_namegen(sess.parse_sess.interner),
               next_addrspace: new_addrspace_gen(),
               symbol_hasher: symbol_hasher,
-              type_hashcodes: @mut LinearMap::new(),
-              type_short_names: @mut LinearMap::new(),
-              all_llvm_symbols: @mut LinearSet::new(),
+              type_hashcodes: @mut HashMap::new(),
+              type_short_names: @mut HashMap::new(),
+              all_llvm_symbols: @mut HashSet::new(),
               tcx: tcx,
               maps: maps,
               stats: @mut Stats {
@@ -3095,7 +3095,7 @@ pub fn trans_crate(sess: session::Session,
                 n_inlines: 0u,
                 n_closures: 0u,
                 llvm_insn_ctxt: @mut ~[],
-                llvm_insns: @mut LinearMap::new(),
+                llvm_insns: @mut HashMap::new(),
                 fn_times: @mut ~[]
               },
               upcalls: upcall::declare_upcalls(targ_cfg, llmod),
diff --git a/src/librustc/middle/trans/build.rs b/src/librustc/middle/trans/build.rs
index ab0e2f38a0b..fa2be2f415f 100644
--- a/src/librustc/middle/trans/build.rs
+++ b/src/librustc/middle/trans/build.rs
@@ -18,7 +18,7 @@ use syntax::codemap::span;
 
 use core::prelude::*;
 use core::cast;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::libc::{c_uint, c_ulonglong, c_char};
 use core::libc;
 use core::option::Some;
@@ -55,7 +55,7 @@ pub fn count_insn(cx: block, category: &str) {
         // Build version of path with cycles removed.
 
         // Pass 1: scan table mapping str -> rightmost pos.
-        let mut mm = LinearMap::new();
+        let mut mm = HashMap::new();
         let len = vec::len(*v);
         let mut i = 0u;
         while i < len {
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index 6bb30a5d5b5..f0c17a6f80d 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -45,7 +45,7 @@ use util::ppaux::{expr_repr, ty_to_str};
 
 use core::cast;
 use core::hash;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::libc::{c_uint, c_longlong, c_ulonglong};
 use core::ptr;
 use core::str;
@@ -134,7 +134,7 @@ pub struct Stats {
     n_inlines: uint,
     n_closures: uint,
     llvm_insn_ctxt: @mut ~[~str],
-    llvm_insns: @mut LinearMap<~str, uint>,
+    llvm_insns: @mut HashMap<~str, uint>,
     fn_times: @mut ~[(~str, int)] // (ident, time)
 }
 
@@ -156,7 +156,7 @@ pub fn BuilderRef_res(B: BuilderRef) -> BuilderRef_res {
     }
 }
 
-pub type ExternMap = @mut LinearMap<@str, ValueRef>;
+pub type ExternMap = @mut HashMap<@str, ValueRef>;
 
 // Crate context.  Every crate we compile has one of these.
 pub struct CrateContext {
@@ -165,30 +165,30 @@ pub struct CrateContext {
      td: TargetData,
      tn: @TypeNames,
      externs: ExternMap,
-     intrinsics: LinearMap<~str, ValueRef>,
-     item_vals: @mut LinearMap<ast::node_id, ValueRef>,
+     intrinsics: HashMap<~str, ValueRef>,
+     item_vals: @mut HashMap<ast::node_id, ValueRef>,
      exp_map2: resolve::ExportMap2,
      reachable: reachable::map,
-     item_symbols: @mut LinearMap<ast::node_id, ~str>,
+     item_symbols: @mut HashMap<ast::node_id, ~str>,
      link_meta: LinkMeta,
-     enum_sizes: @mut LinearMap<ty::t, uint>,
-     discrims: @mut LinearMap<ast::def_id, ValueRef>,
-     discrim_symbols: @mut LinearMap<ast::node_id, ~str>,
-     tydescs: @mut LinearMap<ty::t, @mut tydesc_info>,
+     enum_sizes: @mut HashMap<ty::t, uint>,
+     discrims: @mut HashMap<ast::def_id, ValueRef>,
+     discrim_symbols: @mut HashMap<ast::node_id, ~str>,
+     tydescs: @mut HashMap<ty::t, @mut tydesc_info>,
      // Set when running emit_tydescs to enforce that no more tydescs are
      // created.
      finished_tydescs: @mut bool,
      // Track mapping of external ids to local items imported for inlining
-     external: @mut LinearMap<ast::def_id, Option<ast::node_id>>,
+     external: @mut HashMap<ast::def_id, Option<ast::node_id>>,
      // Cache instances of monomorphized functions
-     monomorphized: @mut LinearMap<mono_id, ValueRef>,
-     monomorphizing: @mut LinearMap<ast::def_id, uint>,
+     monomorphized: @mut HashMap<mono_id, ValueRef>,
+     monomorphizing: @mut HashMap<ast::def_id, uint>,
      // Cache computed type parameter uses (see type_use.rs)
-     type_use_cache: @mut LinearMap<ast::def_id, ~[type_use::type_uses]>,
+     type_use_cache: @mut HashMap<ast::def_id, ~[type_use::type_uses]>,
      // Cache generated vtables
-     vtables: @mut LinearMap<mono_id, ValueRef>,
+     vtables: @mut HashMap<mono_id, ValueRef>,
      // Cache of constant strings,
-     const_cstr_cache: @mut LinearMap<@~str, ValueRef>,
+     const_cstr_cache: @mut HashMap<@~str, ValueRef>,
 
      // Reverse-direction for const ptrs cast from globals.
      // Key is an int, cast from a ValueRef holding a *T,
@@ -198,24 +198,24 @@ pub struct CrateContext {
      // when we ptrcast, and we have to ptrcast during translation
      // of a [T] const because we form a slice, a [*T,int] pair, not
      // a pointer to an LLVM array type.
-     const_globals: @mut LinearMap<int, ValueRef>,
+     const_globals: @mut HashMap<int, ValueRef>,
 
      // Cache of emitted const values
-     const_values: @mut LinearMap<ast::node_id, ValueRef>,
+     const_values: @mut HashMap<ast::node_id, ValueRef>,
 
      // Cache of external const values
-     extern_const_values: @mut LinearMap<ast::def_id, ValueRef>,
+     extern_const_values: @mut HashMap<ast::def_id, ValueRef>,
 
-     module_data: @mut LinearMap<~str, ValueRef>,
-     lltypes: @mut LinearMap<ty::t, TypeRef>,
-     llsizingtypes: @mut LinearMap<ty::t, TypeRef>,
-     adt_reprs: @mut LinearMap<ty::t, @adt::Repr>,
+     module_data: @mut HashMap<~str, ValueRef>,
+     lltypes: @mut HashMap<ty::t, TypeRef>,
+     llsizingtypes: @mut HashMap<ty::t, TypeRef>,
+     adt_reprs: @mut HashMap<ty::t, @adt::Repr>,
      names: namegen,
      next_addrspace: addrspace_gen,
      symbol_hasher: @hash::State,
-     type_hashcodes: @mut LinearMap<ty::t, @str>,
-     type_short_names: @mut LinearMap<ty::t, ~str>,
-     all_llvm_symbols: @mut LinearSet<~str>,
+     type_hashcodes: @mut HashMap<ty::t, @str>,
+     type_short_names: @mut HashMap<ty::t, ~str>,
+     all_llvm_symbols: @mut HashSet<~str>,
      tcx: ty::ctxt,
      maps: astencode::Maps,
      stats: @mut Stats,
@@ -314,12 +314,12 @@ pub struct fn_ctxt_ {
     loop_ret: Option<(ValueRef, ValueRef)>,
 
     // Maps arguments to allocas created for them in llallocas.
-    llargs: @mut LinearMap<ast::node_id, local_val>,
+    llargs: @mut HashMap<ast::node_id, local_val>,
     // Maps the def_ids for local variables to the allocas created for
     // them in llallocas.
-    lllocals: @mut LinearMap<ast::node_id, local_val>,
+    lllocals: @mut HashMap<ast::node_id, local_val>,
     // Same as above, but for closure upvars
-    llupvars: @mut LinearMap<ast::node_id, ValueRef>,
+    llupvars: @mut HashMap<ast::node_id, ValueRef>,
 
     // The node_id of the function, or -1 if it doesn't correspond to
     // a user-defined function.
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index d290a8ffa5c..277d529c846 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -20,7 +20,7 @@ use middle::trans;
 use middle::ty;
 use util::ppaux::ty_to_str;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::libc;
 use core::option;
 use core::sys;
@@ -106,7 +106,7 @@ pub struct DebugContext {
 
 pub fn mk_ctxt(+crate: ~str, intr: @ident_interner) -> DebugContext {
     DebugContext {
-        llmetadata: @mut LinearMap::new(),
+        llmetadata: @mut HashMap::new(),
         names: new_namegen(intr),
         crate_file: crate
     }
@@ -151,7 +151,7 @@ struct RetvalMetadata {
     id: ast::node_id
 }
 
-type metadata_cache = @mut LinearMap<int, ~[debug_metadata]>;
+type metadata_cache = @mut HashMap<int, ~[debug_metadata]>;
 
 enum debug_metadata {
     file_metadata(@Metadata<FileMetadata>),
diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs
index dc910f9f178..5afdd1b0271 100644
--- a/src/librustc/middle/trans/expr.rs
+++ b/src/librustc/middle/trans/expr.rs
@@ -153,7 +153,7 @@ use util::common::indenter;
 use util::ppaux::ty_to_str;
 
 use core::cast::transmute;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use syntax::print::pprust::{expr_to_str};
 use syntax::ast;
 use syntax::codemap;
@@ -1091,7 +1091,7 @@ pub fn trans_local_var(bcx: block, def: ast::def) -> Datum {
     };
 
     fn take_local(bcx: block,
-                  table: &LinearMap<ast::node_id, local_val>,
+                  table: &HashMap<ast::node_id, local_val>,
                   nid: ast::node_id) -> Datum {
         let (v, mode) = match table.find(&nid) {
             Some(&local_mem(v)) => (v, ByRef),
diff --git a/src/librustc/middle/trans/reachable.rs b/src/librustc/middle/trans/reachable.rs
index 8824e0b7829..9f9323bf9f7 100644
--- a/src/librustc/middle/trans/reachable.rs
+++ b/src/librustc/middle/trans/reachable.rs
@@ -21,7 +21,7 @@ use middle::ty;
 use middle::typeck;
 
 use core::prelude::*;
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use syntax::ast;
 use syntax::ast::*;
 use syntax::ast_util::def_id_of_def;
@@ -30,18 +30,18 @@ use syntax::codemap;
 use syntax::print::pprust::expr_to_str;
 use syntax::{visit, ast_map};
 
-pub type map = @LinearSet<node_id>;
+pub type map = @HashSet<node_id>;
 
 struct ctx<'self> {
     exp_map2: resolve::ExportMap2,
     tcx: ty::ctxt,
     method_map: typeck::method_map,
-    rmap: &'self mut LinearSet<node_id>,
+    rmap: &'self mut HashSet<node_id>,
 }
 
 pub fn find_reachable(crate_mod: &_mod, exp_map2: resolve::ExportMap2,
                       tcx: ty::ctxt, method_map: typeck::method_map) -> map {
-    let mut rmap = LinearSet::new();
+    let mut rmap = HashSet::new();
     {
         let cx = ctx {
             exp_map2: exp_map2,
@@ -96,7 +96,7 @@ fn traverse_public_mod(cx: ctx, mod_id: node_id, m: &_mod) {
 
 fn traverse_public_item(cx: ctx, item: @item) {
     // XXX: it shouldn't be necessary to do this
-    let rmap: &mut LinearSet<node_id> = cx.rmap;
+    let rmap: &mut HashSet<node_id> = cx.rmap;
     if rmap.contains(&item.id) { return; }
     rmap.insert(item.id);
     match item.node {
@@ -154,7 +154,7 @@ fn mk_ty_visitor() -> visit::vt<ctx> {
 
 fn traverse_ty<'a>(ty: @Ty, cx: ctx<'a>, v: visit::vt<ctx<'a>>) {
     // XXX: it shouldn't be necessary to do this
-    let rmap: &mut LinearSet<node_id> = cx.rmap;
+    let rmap: &mut HashSet<node_id> = cx.rmap;
     if rmap.contains(&ty.id) { return; }
     rmap.insert(ty.id);
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index fddcce523f4..30b933061e2 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -36,7 +36,7 @@ use core::result;
 use core::to_bytes;
 use core::uint;
 use core::vec;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use std::smallintmap::SmallIntMap;
 use syntax::ast::*;
 use syntax::ast_util::{is_local, local_def};
@@ -119,7 +119,7 @@ pub struct creader_cache_key {
     len: uint
 }
 
-type creader_cache = @mut LinearMap<creader_cache_key, t>;
+type creader_cache = @mut HashMap<creader_cache_key, t>;
 
 impl to_bytes::IterBytes for creader_cache_key {
     fn iter_bytes(&self, +lsb0: bool, f: to_bytes::Cb) {
@@ -210,7 +210,7 @@ pub enum AutoRefKind {
 // This is a map from ID of each implementation to the method info and trait
 // method ID of each of the default methods belonging to the trait that that
 // implementation implements.
-pub type ProvidedMethodsMap = @mut LinearMap<def_id,@mut ~[@ProvidedMethodInfo]>;
+pub type ProvidedMethodsMap = @mut HashMap<def_id,@mut ~[@ProvidedMethodInfo]>;
 
 // Stores the method info and definition ID of the associated trait method for
 // each instantiation of each provided method.
@@ -233,7 +233,7 @@ pub type ctxt = @ctxt_;
 
 struct ctxt_ {
     diag: @syntax::diagnostic::span_handler,
-    interner: @mut LinearMap<intern_key, t_box>,
+    interner: @mut HashMap<intern_key, t_box>,
     next_id: @mut uint,
     vecs_implicitly_copyable: bool,
     legacy_modes: bool,
@@ -253,43 +253,43 @@ struct ctxt_ {
     // of this node.  This only applies to nodes that refer to entities
     // parameterized by type parameters, such as generic fns, types, or
     // other items.
-    node_type_substs: @mut LinearMap<node_id, ~[t]>,
+    node_type_substs: @mut HashMap<node_id, ~[t]>,
 
     items: ast_map::map,
-    intrinsic_defs: @mut LinearMap<ast::ident, (ast::def_id, t)>,
+    intrinsic_defs: @mut HashMap<ast::ident, (ast::def_id, t)>,
     freevars: freevars::freevar_map,
     tcache: type_cache,
     rcache: creader_cache,
     ccache: constness_cache,
-    short_names_cache: @mut LinearMap<t, @~str>,
-    needs_unwind_cleanup_cache: @mut LinearMap<t, bool>,
-    tc_cache: @mut LinearMap<uint, TypeContents>,
-    ast_ty_to_ty_cache: @mut LinearMap<node_id, ast_ty_to_ty_cache_entry>,
-    enum_var_cache: @mut LinearMap<def_id, @~[VariantInfo]>,
-    trait_method_cache: @mut LinearMap<def_id, @~[method]>,
-    ty_param_bounds: @mut LinearMap<ast::node_id, param_bounds>,
-    inferred_modes: @mut LinearMap<ast::node_id, ast::mode>,
-    adjustments: @mut LinearMap<ast::node_id, @AutoAdjustment>,
-    normalized_cache: @mut LinearMap<t, t>,
+    short_names_cache: @mut HashMap<t, @~str>,
+    needs_unwind_cleanup_cache: @mut HashMap<t, bool>,
+    tc_cache: @mut HashMap<uint, TypeContents>,
+    ast_ty_to_ty_cache: @mut HashMap<node_id, ast_ty_to_ty_cache_entry>,
+    enum_var_cache: @mut HashMap<def_id, @~[VariantInfo]>,
+    trait_method_cache: @mut HashMap<def_id, @~[method]>,
+    ty_param_bounds: @mut HashMap<ast::node_id, param_bounds>,
+    inferred_modes: @mut HashMap<ast::node_id, ast::mode>,
+    adjustments: @mut HashMap<ast::node_id, @AutoAdjustment>,
+    normalized_cache: @mut HashMap<t, t>,
     lang_items: middle::lang_items::LanguageItems,
     // A mapping from an implementation ID to the method info and trait
     // method ID of the provided (a.k.a. default) methods in the traits that
     // that implementation implements.
     provided_methods: ProvidedMethodsMap,
-    provided_method_sources: @mut LinearMap<ast::def_id, ProvidedMethodSource>,
-    supertraits: @mut LinearMap<ast::def_id, @~[InstantiatedTraitRef]>,
+    provided_method_sources: @mut HashMap<ast::def_id, ProvidedMethodSource>,
+    supertraits: @mut HashMap<ast::def_id, @~[InstantiatedTraitRef]>,
 
     // A mapping from the def ID of an enum or struct type to the def ID
     // of the method that implements its destructor. If the type is not
     // present in this map, it does not have a destructor. This map is
     // populated during the coherence phase of typechecking.
-    destructor_for_type: @mut LinearMap<ast::def_id, ast::def_id>,
+    destructor_for_type: @mut HashMap<ast::def_id, ast::def_id>,
 
     // A method will be in this list if and only if it is a destructor.
-    destructors: @mut LinearSet<ast::def_id>,
+    destructors: @mut HashSet<ast::def_id>,
 
     // Maps a trait onto a mapping from self-ty to impl
-    trait_impls: @mut LinearMap<ast::def_id, @mut LinearMap<t, @Impl>>
+    trait_impls: @mut HashMap<ast::def_id, @mut HashMap<t, @Impl>>
 }
 
 enum tbox_flag {
@@ -771,18 +771,18 @@ pub struct ty_param_substs_and_ty {
     ty: ty::t
 }
 
-type type_cache = @mut LinearMap<ast::def_id, ty_param_bounds_and_ty>;
+type type_cache = @mut HashMap<ast::def_id, ty_param_bounds_and_ty>;
 
-type constness_cache = @mut LinearMap<ast::def_id, const_eval::constness>;
+type constness_cache = @mut HashMap<ast::def_id, const_eval::constness>;
 
 pub type node_type_table = @mut SmallIntMap<t>;
 
 fn mk_rcache() -> creader_cache {
-    return @mut LinearMap::new();
+    return @mut HashMap::new();
 }
 
-pub fn new_ty_hash<V:Copy>() -> @mut LinearMap<t, V> {
-    @mut LinearMap::new()
+pub fn new_ty_hash<V:Copy>() -> @mut HashMap<t, V> {
+    @mut HashMap::new()
 }
 
 pub fn mk_ctxt(s: session::Session,
@@ -809,7 +809,7 @@ pub fn mk_ctxt(s: session::Session,
                        lint::vecs_implicitly_copyable) == allow;
     @ctxt_ {
         diag: s.diagnostic(),
-        interner: @mut LinearMap::new(),
+        interner: @mut HashMap::new(),
         next_id: @mut 0,
         vecs_implicitly_copyable: vecs_implicitly_copyable,
         legacy_modes: legacy_modes,
@@ -819,30 +819,30 @@ pub fn mk_ctxt(s: session::Session,
         region_map: region_map,
         region_paramd_items: region_paramd_items,
         node_types: @mut SmallIntMap::new(),
-        node_type_substs: @mut LinearMap::new(),
+        node_type_substs: @mut HashMap::new(),
         items: amap,
-        intrinsic_defs: @mut LinearMap::new(),
+        intrinsic_defs: @mut HashMap::new(),
         freevars: freevars,
-        tcache: @mut LinearMap::new(),
+        tcache: @mut HashMap::new(),
         rcache: mk_rcache(),
-        ccache: @mut LinearMap::new(),
+        ccache: @mut HashMap::new(),
         short_names_cache: new_ty_hash(),
         needs_unwind_cleanup_cache: new_ty_hash(),
-        tc_cache: @mut LinearMap::new(),
-        ast_ty_to_ty_cache: @mut LinearMap::new(),
-        enum_var_cache: @mut LinearMap::new(),
-        trait_method_cache: @mut LinearMap::new(),
-        ty_param_bounds: @mut LinearMap::new(),
-        inferred_modes: @mut LinearMap::new(),
-        adjustments: @mut LinearMap::new(),
+        tc_cache: @mut HashMap::new(),
+        ast_ty_to_ty_cache: @mut HashMap::new(),
+        enum_var_cache: @mut HashMap::new(),
+        trait_method_cache: @mut HashMap::new(),
+        ty_param_bounds: @mut HashMap::new(),
+        inferred_modes: @mut HashMap::new(),
+        adjustments: @mut HashMap::new(),
         normalized_cache: new_ty_hash(),
         lang_items: lang_items,
-        provided_methods: @mut LinearMap::new(),
-        provided_method_sources: @mut LinearMap::new(),
-        supertraits: @mut LinearMap::new(),
-        destructor_for_type: @mut LinearMap::new(),
-        destructors: @mut LinearSet::new(),
-        trait_impls: @mut LinearMap::new()
+        provided_methods: @mut HashMap::new(),
+        provided_method_sources: @mut HashMap::new(),
+        supertraits: @mut HashMap::new(),
+        destructor_for_type: @mut HashMap::new(),
+        destructors: @mut HashSet::new(),
+        trait_impls: @mut HashMap::new()
      }
 }
 
@@ -1620,7 +1620,7 @@ pub fn type_needs_unwind_cleanup(cx: ctxt, ty: t) -> bool {
       None => ()
     }
 
-    let mut tycache = LinearSet::new();
+    let mut tycache = HashSet::new();
     let needs_unwind_cleanup =
         type_needs_unwind_cleanup_(cx, ty, &mut tycache, false);
     cx.needs_unwind_cleanup_cache.insert(ty, needs_unwind_cleanup);
@@ -1628,7 +1628,7 @@ pub fn type_needs_unwind_cleanup(cx: ctxt, ty: t) -> bool {
 }
 
 fn type_needs_unwind_cleanup_(cx: ctxt, ty: t,
-                              tycache: &mut LinearSet<t>,
+                              tycache: &mut HashSet<t>,
                               encountered_box: bool) -> bool {
 
     // Prevent infinite recursion
@@ -1855,14 +1855,14 @@ pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
         None => {}
     }
 
-    let mut cache = LinearMap::new();
+    let mut cache = HashMap::new();
     let result = tc_ty(cx, ty, &mut cache);
     cx.tc_cache.insert(ty_id, result);
     return result;
 
     fn tc_ty(cx: ctxt,
              ty: t,
-             cache: &mut LinearMap<uint, TypeContents>) -> TypeContents
+             cache: &mut HashMap<uint, TypeContents>) -> TypeContents
     {
         // Subtle: Note that we are *not* using cx.tc_cache here but rather a
         // private cache for this walk.  This is needed in the case of cyclic
@@ -2054,7 +2054,7 @@ pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
 
     fn tc_mt(cx: ctxt,
              mt: mt,
-             cache: &mut LinearMap<uint, TypeContents>) -> TypeContents
+             cache: &mut HashMap<uint, TypeContents>) -> TypeContents
     {
         let mc = if mt.mutbl == m_mutbl {TC_MUTABLE} else {TC_NONE};
         mc + tc_ty(cx, mt.ty, cache)
@@ -3258,7 +3258,7 @@ pub fn occurs_check(tcx: ctxt, sp: span, vid: TyVid, rt: t) {
 
 // Maintains a little union-set tree for inferred modes.  `canon()` returns
 // the current head value for `m0`.
-fn canon<T:Copy + cmp::Eq>(tbl: &mut LinearMap<ast::node_id, ast::inferable<T>>,
+fn canon<T:Copy + cmp::Eq>(tbl: &mut HashMap<ast::node_id, ast::inferable<T>>,
                          +m0: ast::inferable<T>) -> ast::inferable<T> {
     match m0 {
         ast::infer(id) => {
@@ -4286,7 +4286,7 @@ pub fn iter_bound_traits_and_supertraits(tcx: ctxt,
             }
         };
 
-        let mut supertrait_map = LinearMap::new();
+        let mut supertrait_map = HashMap::new();
         let mut seen_def_ids = ~[];
         let mut i = 0;
         let trait_ty_id = ty_to_def_id(bound_trait_ty).expect(
diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs
index cc2cf7a23c5..f2d0ef22970 100644
--- a/src/librustc/middle/typeck/check/_match.rs
+++ b/src/librustc/middle/typeck/check/_match.rs
@@ -18,7 +18,7 @@ use middle::typeck::check::{instantiate_path, lookup_def};
 use middle::typeck::check::{structure_of, valid_range_bounds};
 use middle::typeck::require_same_types;
 
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::vec;
 use syntax::ast;
 use syntax::ast_util;
@@ -228,7 +228,7 @@ pub fn check_pat_variant(pcx: pat_ctxt, pat: @ast::pat, path: @ast::path,
 /// `class_fields` describes the type of each field of the struct.
 /// `class_id` is the ID of the struct.
 /// `substitutions` are the type substitutions applied to this struct type
-/// (e.g. K,V in LinearMap<K,V>).
+/// (e.g. K,V in HashMap<K,V>).
 /// `etc` is true if the pattern said '...' and false otherwise.
 pub fn check_struct_pat_fields(pcx: pat_ctxt,
                                span: span,
@@ -241,13 +241,13 @@ pub fn check_struct_pat_fields(pcx: pat_ctxt,
     let tcx = pcx.fcx.ccx.tcx;
 
     // Index the class fields.
-    let mut field_map = LinearMap::new();
+    let mut field_map = HashMap::new();
     for class_fields.eachi |i, class_field| {
         field_map.insert(class_field.ident, i);
     }
 
     // Typecheck each field.
-    let mut found_fields = LinearSet::new();
+    let mut found_fields = HashSet::new();
     for fields.each |field| {
         match field_map.find(&field.ident) {
             Some(&index) => {
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 320f0206fb8..3b01f0e839a 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -95,7 +95,7 @@ use middle::typeck::{method_self, method_static, method_trait, method_super};
 use util::common::indenter;
 use util::ppaux::expr_repr;
 
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use core::result;
 use core::uint;
 use core::vec;
@@ -131,7 +131,7 @@ pub fn lookup(
         check_traits: CheckTraitsFlag,      // Whether we check traits only.
         autoderef_receiver: AutoderefReceiverFlag)
      -> Option<method_map_entry> {
-    let mut impl_dups = LinearSet::new();
+    let mut impl_dups = HashSet::new();
     let lcx = LookupContext {
         fcx: fcx,
         expr: expr,
@@ -159,7 +159,7 @@ pub struct LookupContext<'self> {
     callee_id: node_id,
     m_name: ast::ident,
     supplied_tps: &'self [ty::t],
-    impl_dups: &'self mut LinearSet<def_id>,
+    impl_dups: &'self mut HashSet<def_id>,
     inherent_candidates: @mut ~[Candidate],
     extension_candidates: @mut ~[Candidate],
     deref_args: check::DerefArgs,
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 056ccf18599..eba207f978b 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -110,7 +110,7 @@ use util::common::{block_query, indenter, loop_query};
 use util::ppaux::{bound_region_to_str, expr_repr, pat_repr};
 use util::ppaux;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::ptr;
 use core::result::{Result, Ok, Err};
 use core::result;
@@ -158,12 +158,12 @@ pub struct SelfInfo {
 /// share the inherited fields.
 pub struct inherited {
     infcx: @mut infer::InferCtxt,
-    locals: @mut LinearMap<ast::node_id, ty::t>,
+    locals: @mut HashMap<ast::node_id, ty::t>,
 
     // Temporary tables:
-    node_types: @mut LinearMap<ast::node_id, ty::t>,
-    node_type_substs: @mut LinearMap<ast::node_id, ty::substs>,
-    adjustments: @mut LinearMap<ast::node_id, @ty::AutoAdjustment>,
+    node_types: @mut HashMap<ast::node_id, ty::t>,
+    node_type_substs: @mut HashMap<ast::node_id, ty::substs>,
+    adjustments: @mut HashMap<ast::node_id, @ty::AutoAdjustment>,
     method_map: method_map,
     vtable_map: vtable_map,
 }
@@ -220,12 +220,12 @@ pub struct FnCtxt {
 pub fn blank_inherited(ccx: @mut CrateCtxt) -> @inherited {
     @inherited {
         infcx: infer::new_infer_ctxt(ccx.tcx),
-        locals: @mut LinearMap::new(),
-        node_types: @mut LinearMap::new(),
-        node_type_substs: @mut LinearMap::new(),
-        adjustments: @mut LinearMap::new(),
-        method_map: @mut LinearMap::new(),
-        vtable_map: @mut LinearMap::new(),
+        locals: @mut HashMap::new(),
+        node_types: @mut HashMap::new(),
+        node_type_substs: @mut HashMap::new(),
+        adjustments: @mut HashMap::new(),
+        method_map: @mut HashMap::new(),
+        vtable_map: @mut HashMap::new(),
     }
 }
 
@@ -504,7 +504,7 @@ pub fn check_method(ccx: @mut CrateCtxt,
 
 pub fn check_no_duplicate_fields(tcx: ty::ctxt,
                                  fields: ~[(ast::ident, span)]) {
-    let mut field_names = LinearMap::new();
+    let mut field_names = HashMap::new();
 
     for fields.each |p| {
         let (id, sp) = *p;
@@ -1761,7 +1761,7 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
                                       check_completeness: bool)  {
         let tcx = fcx.ccx.tcx;
 
-        let mut class_field_map = LinearMap::new();
+        let mut class_field_map = HashMap::new();
         let mut fields_found = 0;
         for field_types.each |field| {
             // XXX: Check visibility here.
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index a1eaa1f6a33..51f54d21ec4 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -28,7 +28,7 @@ use core::result::{Ok, Err};
 use core::result;
 use core::uint;
 use core::vec;
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use syntax::ast;
 use syntax::ast_util;
 use syntax::codemap::span;
@@ -234,7 +234,7 @@ pub fn lookup_vtable(vcx: &VtableContext,
         _ => {
             let mut found = ~[];
 
-            let mut impls_seen = LinearSet::new();
+            let mut impls_seen = HashSet::new();
 
             match vcx.ccx.coherence_info.extension_methods.find(&trait_id) {
                 None => {
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index 4fc9e8d19ae..466cb8ed54f 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -53,7 +53,7 @@ use syntax::visit::{visit_mod};
 use util::ppaux::ty_to_str;
 
 use core::result::Ok;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::uint;
 
 pub struct UniversalQuantificationResult {
@@ -164,17 +164,17 @@ pub fn method_to_MethodInfo(ast_method: @method) -> @MethodInfo {
 pub struct CoherenceInfo {
     // Contains implementations of methods that are inherent to a type.
     // Methods in these implementations don't need to be exported.
-    inherent_methods: @mut LinearMap<def_id, @mut ~[@Impl]>,
+    inherent_methods: @mut HashMap<def_id, @mut ~[@Impl]>,
 
     // Contains implementations of methods associated with a trait. For these,
     // the associated trait must be imported at the call site.
-    extension_methods: @mut LinearMap<def_id, @mut ~[@Impl]>,
+    extension_methods: @mut HashMap<def_id, @mut ~[@Impl]>,
 }
 
 pub fn CoherenceInfo() -> CoherenceInfo {
     CoherenceInfo {
-        inherent_methods: @mut LinearMap::new(),
-        extension_methods: @mut LinearMap::new(),
+        inherent_methods: @mut HashMap::new(),
+        extension_methods: @mut HashMap::new(),
     }
 }
 
@@ -183,7 +183,7 @@ pub fn CoherenceChecker(crate_context: @mut CrateCtxt) -> CoherenceChecker {
         crate_context: crate_context,
         inference_context: new_infer_ctxt(crate_context.tcx),
 
-        base_type_def_ids: @mut LinearMap::new(),
+        base_type_def_ids: @mut HashMap::new(),
     }
 }
 
@@ -194,7 +194,7 @@ pub struct CoherenceChecker {
     // A mapping from implementations to the corresponding base type
     // definition ID.
 
-    base_type_def_ids: @mut LinearMap<def_id,def_id>,
+    base_type_def_ids: @mut HashMap<def_id,def_id>,
 }
 
 pub impl CoherenceChecker {
@@ -471,7 +471,7 @@ pub impl CoherenceChecker {
                ty_to_str(self.crate_context.tcx, self_t));
         match self.crate_context.tcx.trait_impls.find(&trait_t) {
             None => {
-                let m = @mut LinearMap::new();
+                let m = @mut HashMap::new();
                 m.insert(self_t, the_impl);
                 self.crate_context.tcx.trait_impls.insert(trait_t, m);
             }
@@ -501,7 +501,7 @@ pub impl CoherenceChecker {
             f: &fn(x: &ty::method) -> bool) {
         // Make a list of all the names of the provided methods.
         // XXX: This is horrible.
-        let mut provided_method_idents = LinearSet::new();
+        let mut provided_method_idents = HashSet::new();
         let tcx = self.crate_context.tcx;
         for ty::provided_trait_methods(tcx, trait_did).each |ident| {
             provided_method_idents.insert(*ident);
@@ -705,7 +705,7 @@ pub impl CoherenceChecker {
 
         let tcx = self.crate_context.tcx;
 
-        let mut provided_names = LinearSet::new();
+        let mut provided_names = HashSet::new();
         // Implemented methods
         for uint::range(0, all_methods.len()) |i| {
             provided_names.insert(all_methods[i].ident);
@@ -812,7 +812,7 @@ pub impl CoherenceChecker {
 
     // External crate handling
 
-    fn add_impls_for_module(&self, impls_seen: &mut LinearSet<def_id>,
+    fn add_impls_for_module(&self, impls_seen: &mut HashSet<def_id>,
                             crate_store: @mut CStore,
                             module_def_id: def_id) {
         let implementations = get_impls_for_mod(crate_store,
@@ -931,7 +931,7 @@ pub impl CoherenceChecker {
     // Adds implementations and traits from external crates to the coherence
     // info.
     fn add_external_crates(&self) {
-        let mut impls_seen = LinearSet::new();
+        let mut impls_seen = HashSet::new();
 
         let crate_store = self.crate_context.tcx.sess.cstore;
         do iter_crate_data(crate_store) |crate_number, _crate_metadata| {
diff --git a/src/librustc/middle/typeck/infer/region_inference.rs b/src/librustc/middle/typeck/infer/region_inference.rs
index d9f00451dd5..98d12bea6a4 100644
--- a/src/librustc/middle/typeck/infer/region_inference.rs
+++ b/src/librustc/middle/typeck/infer/region_inference.rs
@@ -548,7 +548,7 @@ use util::common::indenter;
 use util::ppaux::note_and_explain_region;
 
 use core::cell::{Cell, empty_cell};
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::result::{Err, Ok};
 use core::to_bytes;
 use core::uint;
@@ -600,12 +600,12 @@ enum CombineMapType {
     Lub, Glb
 }
 
-type CombineMap = LinearMap<TwoRegions, RegionVid>;
+type CombineMap = HashMap<TwoRegions, RegionVid>;
 
 pub struct RegionVarBindings {
     tcx: ty::ctxt,
     var_spans: ~[span],
-    constraints: LinearMap<Constraint, span>,
+    constraints: HashMap<Constraint, span>,
     lubs: CombineMap,
     glbs: CombineMap,
     skolemization_count: uint,
@@ -632,9 +632,9 @@ pub fn RegionVarBindings(tcx: ty::ctxt) -> RegionVarBindings {
         tcx: tcx,
         var_spans: ~[],
         values: empty_cell(),
-        constraints: LinearMap::new(),
-        lubs: LinearMap::new(),
-        glbs: LinearMap::new(),
+        constraints: HashMap::new(),
+        lubs: HashMap::new(),
+        glbs: HashMap::new(),
         skolemization_count: 0,
         bound_count: 0,
         undo_log: ~[]
@@ -1194,7 +1194,7 @@ struct SpannedRegion {
     span: span,
 }
 
-type TwoRegionsMap = LinearSet<TwoRegions>;
+type TwoRegionsMap = HashSet<TwoRegions>;
 
 pub impl RegionVarBindings {
     fn infer_variable_values(&mut self) -> ~[GraphNodeValue] {
@@ -1423,7 +1423,7 @@ pub impl RegionVarBindings {
         &mut self,
         graph: &Graph) -> ~[GraphNodeValue]
     {
-        let mut dup_map = LinearSet::new();
+        let mut dup_map = HashSet::new();
         graph.nodes.mapi(|idx, node| {
             match node.value {
                 Value(_) => {
@@ -1598,7 +1598,7 @@ pub impl RegionVarBindings {
                                 orig_node_idx: RegionVid,
                                 dir: Direction)
                              -> ~[SpannedRegion] {
-        let mut set = LinearSet::new();
+        let mut set = HashSet::new();
         let mut stack = ~[orig_node_idx];
         set.insert(orig_node_idx.to_uint());
         let mut result = ~[];
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index 2b5a47c18c6..d829b0d2a0d 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -55,7 +55,7 @@ use middle::ty;
 use util::common::time;
 use util::ppaux;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::result;
 use core::vec;
 use std::list::List;
@@ -129,7 +129,7 @@ pub struct method_map_entry {
 
 // maps from an expression id that corresponds to a method call to the details
 // of the method to be invoked
-pub type method_map = @mut LinearMap<ast::node_id, method_map_entry>;
+pub type method_map = @mut HashMap<ast::node_id, method_map_entry>;
 
 // Resolutions for bounds of all parameters, left to right, for a given path.
 pub type vtable_res = @~[vtable_origin];
@@ -170,7 +170,7 @@ pub impl vtable_origin {
     }
 }
 
-pub type vtable_map = @mut LinearMap<ast::node_id, vtable_res>;
+pub type vtable_map = @mut HashMap<ast::node_id, vtable_res>;
 
 pub struct CrateCtxt {
     // A mapping from method call sites to traits that have that method.
@@ -342,8 +342,8 @@ pub fn check_crate(tcx: ty::ctxt,
     let time_passes = tcx.sess.time_passes();
     let ccx = @mut CrateCtxt {
         trait_map: trait_map,
-        method_map: @mut LinearMap::new(),
-        vtable_map: @mut LinearMap::new(),
+        method_map: @mut HashMap::new(),
+        vtable_map: @mut HashMap::new(),
         coherence_info: @coherence::CoherenceInfo(),
         tcx: tcx
     };
diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index 2a2d921ba86..30152c22845 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -14,7 +14,7 @@ use syntax::ast;
 use syntax::codemap::{span};
 use syntax::visit;
 
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use core::str;
 use std;
 
@@ -114,7 +114,7 @@ pub fn pluralize(n: uint, +s: ~str) -> ~str {
 }
 
 // A set of node IDs (used to keep track of which node IDs are for statements)
-pub type stmt_set = @mut LinearSet<ast::node_id>;
+pub type stmt_set = @mut HashSet<ast::node_id>;
 
 //
 // Local Variables:
diff --git a/src/librustpkg/rustpkg.rc b/src/librustpkg/rustpkg.rc
index ff549ad2c22..bf1301868af 100644
--- a/src/librustpkg/rustpkg.rc
+++ b/src/librustpkg/rustpkg.rc
@@ -28,7 +28,7 @@ extern mod syntax(vers = "0.6");
 
 use core::*;
 use core::container::Map;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::io::WriterUtil;
 use rustc::driver::{driver, session};
 use rustc::metadata::filesearch;
@@ -253,7 +253,7 @@ impl PackageScript {
 struct Ctx {
     cfgs: ~[~str],
     json: bool,
-    dep_cache: @mut LinearMap<~str, bool>
+    dep_cache: @mut HashMap<~str, bool>
 }
 
 impl Ctx {
@@ -483,14 +483,14 @@ impl Ctx {
         if self.json {
             match PackageScript::parse(&os::getcwd()) {
                 result::Ok(script) => {
-                    let mut map = ~LinearMap::new();
+                    let mut map = ~HashMap::new();
 
                     map.insert(~"id", json::String(script.id));
                     map.insert(~"name", json::String(script.name));
                     map.insert(~"vers", json::String(script.vers.to_str()));
                     map.insert(~"deps", json::List(do script.deps.map |&dep| {
                         let (url, target) = dep;
-                        let mut inner = ~LinearMap::new();
+                        let mut inner = ~HashMap::new();
 
                         inner.insert(~"url", json::String(url));
 
@@ -921,7 +921,7 @@ pub fn main() {
     Ctx {
         cfgs: cfgs,
         json: json,
-        dep_cache: @mut LinearMap::new()
+        dep_cache: @mut HashMap::new()
     }.run(cmd, args);
 }
 
diff --git a/src/librustpkg/util.rs b/src/librustpkg/util.rs
index cd64061af03..9d3751c3de2 100644
--- a/src/librustpkg/util.rs
+++ b/src/librustpkg/util.rs
@@ -10,7 +10,7 @@
 
 use core::*;
 use core::hash::Streaming;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use rustc::driver::{driver, session};
 use rustc::metadata::filesearch;
 use std::getopts::groups::getopts;
@@ -337,7 +337,7 @@ fn _add_pkg(packages: ~[json::Json], pkg: &Package) -> ~[json::Json] {
         }
     }
 
-    let mut map = ~LinearMap::new();
+    let mut map = ~HashMap::new();
 
     map.insert(~"id", json::String(pkg.id));
     map.insert(~"vers", json::String(pkg.vers.to_str()));
diff --git a/src/libstd/json.rs b/src/libstd/json.rs
index e090d6bc036..f426b74736a 100644
--- a/src/libstd/json.rs
+++ b/src/libstd/json.rs
@@ -16,7 +16,7 @@
 
 use core::prelude::*;
 use core::io::{WriterUtil, ReaderUtil};
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 use serialize::Encodable;
 use serialize;
@@ -33,7 +33,7 @@ pub enum Json {
 }
 
 pub type List = ~[Json];
-pub type Object = LinearMap<~str, Json>;
+pub type Object = HashMap<~str, Json>;
 
 #[deriving(Eq)]
 pub struct Error {
@@ -677,7 +677,7 @@ priv impl Parser {
         self.bump();
         self.parse_whitespace();
 
-        let mut values = ~LinearMap::new();
+        let mut values = ~HashMap::new();
 
         if self.ch == '}' {
           self.bump();
@@ -1127,9 +1127,9 @@ impl<A:ToJson> ToJson for ~[A] {
     fn to_json(&self) -> Json { List(self.map(|elt| elt.to_json())) }
 }
 
-impl<A:ToJson + Copy> ToJson for LinearMap<~str, A> {
+impl<A:ToJson + Copy> ToJson for HashMap<~str, A> {
     fn to_json(&self) -> Json {
-        let mut d = LinearMap::new();
+        let mut d = HashMap::new();
         for self.each |&(key, value)| {
             d.insert(copy *key, value.to_json());
         }
@@ -1161,7 +1161,7 @@ mod tests {
     use super::*;
 
     use core::prelude::*;
-    use core::hashmap::linear::LinearMap;
+    use core::hashmap::HashMap;
 
     use std::serialize::Decodable;
 
@@ -1190,7 +1190,7 @@ mod tests {
     }
 
     fn mk_object(items: &[(~str, Json)]) -> Json {
-        let mut d = ~LinearMap::new();
+        let mut d = ~HashMap::new();
 
         for items.each |item| {
             match *item {
@@ -1755,7 +1755,7 @@ mod tests {
     fn test_decode_map() {
         let s = ~"{\"a\": \"Dog\", \"b\": [\"Frog\", \"Henry\", 349]}";
         let decoder = Decoder(from_str(s).unwrap());
-        let mut map: LinearMap<~str, Animal> = Decodable::decode(&decoder);
+        let mut map: HashMap<~str, Animal> = Decodable::decode(&decoder);
 
         assert_eq!(map.pop(&~"a"), Some(Dog));
         assert_eq!(map.pop(&~"b"), Some(Frog(~"Henry", 349)));
diff --git a/src/libstd/net_url.rs b/src/libstd/net_url.rs
index d23784953ef..81598f17aed 100644
--- a/src/libstd/net_url.rs
+++ b/src/libstd/net_url.rs
@@ -17,7 +17,7 @@ use core::from_str::FromStr;
 use core::io::{Reader, ReaderUtil};
 use core::io;
 use core::prelude::*;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::str;
 use core::to_bytes::IterBytes;
 use core::to_bytes;
@@ -212,7 +212,7 @@ fn encode_plus(s: &str) -> ~str {
 /**
  * Encode a hashmap to the 'application/x-www-form-urlencoded' media type.
  */
-pub fn encode_form_urlencoded(m: &LinearMap<~str, ~[~str]>) -> ~str {
+pub fn encode_form_urlencoded(m: &HashMap<~str, ~[~str]>) -> ~str {
     let mut out = ~"";
     let mut first = true;
 
@@ -238,9 +238,9 @@ pub fn encode_form_urlencoded(m: &LinearMap<~str, ~[~str]>) -> ~str {
  * Decode a string encoded with the 'application/x-www-form-urlencoded' media
  * type into a hashmap.
  */
-pub fn decode_form_urlencoded(s: &[u8]) -> LinearMap<~str, ~[~str]> {
+pub fn decode_form_urlencoded(s: &[u8]) -> HashMap<~str, ~[~str]> {
     do io::with_bytes_reader(s) |rdr| {
-        let mut m = LinearMap::new();
+        let mut m = HashMap::new();
         let mut key = ~"";
         let mut value = ~"";
         let mut parsing_key = true;
@@ -818,7 +818,7 @@ mod tests {
 
     use net_url::*;
 
-    use core::hashmap::linear::LinearMap;
+    use core::hashmap::HashMap;
 
     #[test]
     pub fn test_url_parse() {
@@ -1053,18 +1053,18 @@ mod tests {
 
     #[test]
     pub fn test_encode_form_urlencoded() {
-        let mut m = LinearMap::new();
+        let mut m = HashMap::new();
         assert!(encode_form_urlencoded(&m) == ~"");
 
         m.insert(~"", ~[]);
         m.insert(~"foo", ~[]);
         assert!(encode_form_urlencoded(&m) == ~"");
 
-        let mut m = LinearMap::new();
+        let mut m = HashMap::new();
         m.insert(~"foo", ~[~"bar", ~"123"]);
         assert!(encode_form_urlencoded(&m) == ~"foo=bar&foo=123");
 
-        let mut m = LinearMap::new();
+        let mut m = HashMap::new();
         m.insert(~"foo bar", ~[~"abc", ~"12 = 34"]);
         assert!(encode_form_urlencoded(&m) ==
             ~"foo+bar=abc&foo+bar=12+%3D+34");
diff --git a/src/libstd/serialize.rs b/src/libstd/serialize.rs
index ddc84e07a35..e1ab59fb2b3 100644
--- a/src/libstd/serialize.rs
+++ b/src/libstd/serialize.rs
@@ -17,7 +17,7 @@ Core encoding and decoding interfaces.
 #[forbid(non_camel_case_types)];
 
 use core::prelude::*;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::trie::{TrieMap, TrieSet};
 use deque::Deque;
 use dlist::DList;
@@ -591,7 +591,7 @@ impl<
     E: Encoder,
     K: Encodable<E> + Hash + IterBytes + Eq,
     V: Encodable<E>
-> Encodable<E> for LinearMap<K, V> {
+> Encodable<E> for HashMap<K, V> {
     fn encode(&self, e: &E) {
         do e.emit_map(self.len()) {
             let mut i = 0;
@@ -608,10 +608,10 @@ impl<
     D: Decoder,
     K: Decodable<D> + Hash + IterBytes + Eq,
     V: Decodable<D>
-> Decodable<D> for LinearMap<K, V> {
-    fn decode(d: &D) -> LinearMap<K, V> {
+> Decodable<D> for HashMap<K, V> {
+    fn decode(d: &D) -> HashMap<K, V> {
         do d.read_map |len| {
-            let mut map = LinearMap::with_capacity(len);
+            let mut map = HashMap::with_capacity(len);
             for uint::range(0, len) |i| {
                 let key = d.read_map_elt_key(i, || Decodable::decode(d));
                 let val = d.read_map_elt_val(i, || Decodable::decode(d));
@@ -625,7 +625,7 @@ impl<
 impl<
     S: Encoder,
     T: Encodable<S> + Hash + IterBytes + Eq
-> Encodable<S> for LinearSet<T> {
+> Encodable<S> for HashSet<T> {
     fn encode(&self, s: &S) {
         do s.emit_seq(self.len()) {
             let mut i = 0;
@@ -640,10 +640,10 @@ impl<
 impl<
     D: Decoder,
     T: Decodable<D> + Hash + IterBytes + Eq
-> Decodable<D> for LinearSet<T> {
-    fn decode(d: &D) -> LinearSet<T> {
+> Decodable<D> for HashSet<T> {
+    fn decode(d: &D) -> HashSet<T> {
         do d.read_seq |len| {
-            let mut set = LinearSet::with_capacity(len);
+            let mut set = HashSet::with_capacity(len);
             for uint::range(0, len) |i| {
                 set.insert(d.read_seq_elt(i, || Decodable::decode(d)));
             }
diff --git a/src/libstd/workcache.rs b/src/libstd/workcache.rs
index 6ed1364d7fc..3e494d0236e 100644
--- a/src/libstd/workcache.rs
+++ b/src/libstd/workcache.rs
@@ -24,7 +24,7 @@ use core::pipes::recv;
 use core::prelude::*;
 use core::result;
 use core::run;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::task;
 use core::to_bytes;
 
@@ -136,10 +136,10 @@ pub impl WorkKey {
     }
 }
 
-struct WorkMap(LinearMap<WorkKey, ~str>);
+struct WorkMap(HashMap<WorkKey, ~str>);
 
 impl WorkMap {
-    fn new() -> WorkMap { WorkMap(LinearMap::new()) }
+    fn new() -> WorkMap { WorkMap(HashMap::new()) }
 }
 
 impl<S:Encoder> Encodable<S> for WorkMap {
@@ -166,7 +166,7 @@ impl<D:Decoder> Decodable<D> for WorkMap {
 
 struct Database {
     db_filename: Path,
-    db_cache: LinearMap<~str, ~str>,
+    db_cache: HashMap<~str, ~str>,
     db_dirty: bool
 }
 
@@ -212,7 +212,7 @@ struct Context {
     db: @mut Database,
     logger: @mut Logger,
     cfg: @json::Object,
-    freshness: LinearMap<~str,@fn(&str,&str)->bool>
+    freshness: HashMap<~str,@fn(&str,&str)->bool>
 }
 
 struct Prep {
@@ -267,7 +267,7 @@ pub impl Context {
             db: db,
             logger: lg,
             cfg: cfg,
-            freshness: LinearMap::new()
+            freshness: HashMap::new()
         }
     }
 
@@ -411,10 +411,10 @@ fn test() {
     use core::io::WriterUtil;
 
     let db = @mut Database { db_filename: Path("db.json"),
-                             db_cache: LinearMap::new(),
+                             db_cache: HashMap::new(),
                              db_dirty: false };
     let lg = @mut Logger { a: () };
-    let cfg = @LinearMap::new();
+    let cfg = @HashMap::new();
     let cx = @Context::new(db, lg, cfg);
     let w:Work<~str> = do cx.prep("test1") |prep| {
         let pth = Path("foo.c");
diff --git a/src/libsyntax/ast_map.rs b/src/libsyntax/ast_map.rs
index f22b466efeb..147d8227b81 100644
--- a/src/libsyntax/ast_map.rs
+++ b/src/libsyntax/ast_map.rs
@@ -23,7 +23,7 @@ use print::pprust;
 use visit;
 
 use core::cmp;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::str;
 use core::vec;
 
@@ -104,7 +104,7 @@ pub enum ast_node {
     node_struct_ctor(@struct_def, @item, @path),
 }
 
-pub type map = @mut LinearMap<node_id, ast_node>;
+pub type map = @mut HashMap<node_id, ast_node>;
 
 pub struct Ctx {
     map: map,
@@ -134,7 +134,7 @@ pub fn mk_ast_map_visitor() -> vt {
 
 pub fn map_crate(diag: @span_handler, c: crate) -> map {
     let cx = @mut Ctx {
-        map: @mut LinearMap::new(),
+        map: @mut HashMap::new(),
         path: ~[],
         local_id: 0u,
         diag: diag,
diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index 9f8dbef9b96..5063a0381e7 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -20,7 +20,7 @@ use diagnostic::span_handler;
 use parse::comments::{doc_comment_style, strip_doc_comment_decoration};
 
 use core::vec;
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use std;
 
 /* Constructors */
@@ -333,7 +333,7 @@ pub fn find_inline_attr(attrs: &[ast::attribute]) -> inline_attr {
 
 pub fn require_unique_names(diagnostic: @span_handler,
                             metas: &[@ast::meta_item]) {
-    let mut set = LinearSet::new();
+    let mut set = HashSet::new();
     for metas.each |meta| {
         let name = get_meta_item_name(*meta);
 
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 93e2ad64c8c..92f0c7c7679 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -20,7 +20,7 @@ use parse;
 use parse::token;
 
 use core::vec;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 // new-style macro! tt code:
 //
@@ -125,7 +125,7 @@ pub fn syntax_expander_table() -> SyntaxEnv {
     fn builtin_item_tt(f: SyntaxExpanderTTItemFun) -> @Transformer {
         @SE(IdentTT(SyntaxExpanderTTItem{expander: f, span: None}))
     }
-    let mut syntax_expanders = LinearMap::new();
+    let mut syntax_expanders = HashMap::new();
     // NB identifier starts with space, and can't conflict with legal idents
     syntax_expanders.insert(@~" block",
                             @ScopeMacros(true));
@@ -430,8 +430,8 @@ pub fn get_exprs_from_tts(cx: @ext_ctxt, tts: &[ast::token_tree])
 // a transformer env is either a base map or a map on top
 // of another chain.
 pub enum MapChain<K,V> {
-    BaseMapChain(~LinearMap<K,@V>),
-    ConsMapChain(~LinearMap<K,@V>,@mut MapChain<K,V>)
+    BaseMapChain(~HashMap<K,@V>),
+    ConsMapChain(~HashMap<K,@V>,@mut MapChain<K,V>)
 }
 
 
@@ -439,13 +439,13 @@ pub enum MapChain<K,V> {
 impl <K: Eq + Hash + IterBytes ,V: Copy> MapChain<K,V>{
 
     // Constructor. I don't think we need a zero-arg one.
-    fn new(+init: ~LinearMap<K,@V>) -> @mut MapChain<K,V> {
+    fn new(+init: ~HashMap<K,@V>) -> @mut MapChain<K,V> {
         @mut BaseMapChain(init)
     }
 
     // add a new frame to the environment (functionally)
     fn push_frame (@mut self) -> @mut MapChain<K,V> {
-        @mut ConsMapChain(~LinearMap::new() ,self)
+        @mut ConsMapChain(~HashMap::new() ,self)
     }
 
 // no need for pop, it'll just be functional.
@@ -454,7 +454,7 @@ impl <K: Eq + Hash + IterBytes ,V: Copy> MapChain<K,V>{
 
     // ugh: can't get this to compile with mut because of the
     // lack of flow sensitivity.
-    fn get_map(&self) -> &'self LinearMap<K,@V> {
+    fn get_map(&self) -> &'self HashMap<K,@V> {
         match *self {
             BaseMapChain (~ref map) => map,
             ConsMapChain (~ref map,_) => map
@@ -509,10 +509,10 @@ impl <K: Eq + Hash + IterBytes ,V: Copy> MapChain<K,V>{
 #[cfg(test)]
 mod test {
     use super::MapChain;
-    use core::hashmap::linear::LinearMap;
+    use core::hashmap::HashMap;
 
     #[test] fn testenv () {
-        let mut a = LinearMap::new();
+        let mut a = HashMap::new();
         a.insert (@~"abc",@15);
         let m = MapChain::new(~a);
         m.insert (@~"def",@16);
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index f74fbbc3c03..afb7e04a532 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -20,7 +20,7 @@ use parse::token::{Token, EOF, to_str, nonterminal};
 use parse::token;
 
 use core::prelude::*;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 /* This is an Earley-like parser, without support for in-grammar nonterminals,
 only by calling out to the main rust parser for named nonterminals (which it
@@ -186,9 +186,9 @@ pub enum named_match {
 pub type earley_item = ~MatcherPos;
 
 pub fn nameize(p_s: @mut ParseSess, ms: ~[matcher], res: ~[@named_match])
-            -> LinearMap<ident,@named_match> {
+            -> HashMap<ident,@named_match> {
     fn n_rec(p_s: @mut ParseSess, m: matcher, res: ~[@named_match],
-             ret_val: &mut LinearMap<ident, @named_match>) {
+             ret_val: &mut HashMap<ident, @named_match>) {
         match m {
           codemap::spanned {node: match_tok(_), _} => (),
           codemap::spanned {node: match_seq(ref more_ms, _, _, _, _), _} => {
@@ -207,13 +207,13 @@ pub fn nameize(p_s: @mut ParseSess, ms: ~[matcher], res: ~[@named_match])
           }
         }
     }
-    let mut ret_val = LinearMap::new();
+    let mut ret_val = HashMap::new();
     for ms.each() |m| { n_rec(p_s, *m, res, &mut ret_val) }
     return ret_val;
 }
 
 pub enum parse_result {
-    success(LinearMap<ident, @named_match>),
+    success(HashMap<ident, @named_match>),
     failure(codemap::span, ~str),
     error(codemap::span, ~str)
 }
@@ -223,7 +223,7 @@ pub fn parse_or_else(
     +cfg: ast::crate_cfg,
     rdr: @reader,
     ms: ~[matcher]
-) -> LinearMap<ident, @named_match> {
+) -> HashMap<ident, @named_match> {
     match parse(sess, cfg, rdr, ms) {
       success(m) => m,
       failure(sp, str) => sess.span_diagnostic.span_fatal(sp, str),
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index f0e1273534a..f39f3a01328 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -18,7 +18,7 @@ use ext::tt::macro_parser::{named_match, matched_seq, matched_nonterminal};
 use parse::token::{EOF, INTERPOLATED, IDENT, Token, nt_ident, ident_interner};
 use parse::lexer::TokenAndSpan;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::option;
 use core::vec;
 
@@ -39,7 +39,7 @@ pub struct TtReader {
     // the unzipped tree:
     stack: @mut TtFrame,
     /* for MBE-style macro transcription */
-    interpolations: LinearMap<ident, @named_match>,
+    interpolations: HashMap<ident, @named_match>,
     repeat_idx: ~[uint],
     repeat_len: ~[uint],
     /* cached: */
@@ -52,7 +52,7 @@ pub struct TtReader {
  *  should) be none. */
 pub fn new_tt_reader(sp_diag: @span_handler,
                      itr: @ident_interner,
-                     interp: Option<LinearMap<ident,@named_match>>,
+                     interp: Option<HashMap<ident,@named_match>>,
                      +src: ~[ast::token_tree])
                   -> @mut TtReader {
     let r = @mut TtReader {
@@ -66,7 +66,7 @@ pub fn new_tt_reader(sp_diag: @span_handler,
             up: option::None
         },
         interpolations: match interp { /* just a convienience */
-            None => LinearMap::new(),
+            None => HashMap::new(),
             Some(x) => x
         },
         repeat_idx: ~[],
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index d068c887abd..1d780c9b806 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -94,7 +94,7 @@ use opt_vec::OptVec;
 
 use core::either::Either;
 use core::either;
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use core::vec;
 
 #[deriving(Eq)]
@@ -243,7 +243,7 @@ pub fn Parser(sess: @mut ParseSess,
         keywords: token::keyword_table(),
         strict_keywords: token::strict_keyword_table(),
         reserved_keywords: token::reserved_keyword_table(),
-        obsolete_set: @mut LinearSet::new(),
+        obsolete_set: @mut HashSet::new(),
         mod_path_stack: @mut ~[],
     }
 }
@@ -263,12 +263,12 @@ pub struct Parser {
     quote_depth: @mut uint, // not (yet) related to the quasiquoter
     reader: @reader,
     interner: @token::ident_interner,
-    keywords: LinearSet<~str>,
-    strict_keywords: LinearSet<~str>,
-    reserved_keywords: LinearSet<~str>,
+    keywords: HashSet<~str>,
+    strict_keywords: HashSet<~str>,
+    reserved_keywords: HashSet<~str>,
     /// The set of seen errors about obsolete syntax. Used to suppress
     /// extra detail when the same error is seen twice
-    obsolete_set: @mut LinearSet<ObsoleteSyntax>,
+    obsolete_set: @mut HashSet<ObsoleteSyntax>,
     /// Used to determine the path to externally loaded source files
     mod_path_stack: @mut ~[~str],
 
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index 5fdf6f7620c..713a6e89475 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -18,7 +18,7 @@ use util::interner;
 
 use core::cast;
 use core::char;
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use core::str;
 use core::task;
 
@@ -458,8 +458,8 @@ pub fn mk_fake_ident_interner() -> @ident_interner {
  * appear as identifiers at all. Reserved keywords are not used anywhere in
  * the language and may not appear as identifiers.
  */
-pub fn keyword_table() -> LinearSet<~str> {
-    let mut keywords = LinearSet::new();
+pub fn keyword_table() -> HashSet<~str> {
+    let mut keywords = HashSet::new();
     let mut tmp = temporary_keyword_table();
     let mut strict = strict_keyword_table();
     let mut reserved = reserved_keyword_table();
@@ -471,8 +471,8 @@ pub fn keyword_table() -> LinearSet<~str> {
 }
 
 /// Keywords that may be used as identifiers
-pub fn temporary_keyword_table() -> LinearSet<~str> {
-    let mut words = LinearSet::new();
+pub fn temporary_keyword_table() -> HashSet<~str> {
+    let mut words = HashSet::new();
     let keys = ~[
         ~"self", ~"static",
     ];
@@ -483,8 +483,8 @@ pub fn temporary_keyword_table() -> LinearSet<~str> {
 }
 
 /// Full keywords. May not appear anywhere else.
-pub fn strict_keyword_table() -> LinearSet<~str> {
-    let mut words = LinearSet::new();
+pub fn strict_keyword_table() -> HashSet<~str> {
+    let mut words = HashSet::new();
     let keys = ~[
         ~"as",
         ~"break",
@@ -509,8 +509,8 @@ pub fn strict_keyword_table() -> LinearSet<~str> {
     return words;
 }
 
-pub fn reserved_keyword_table() -> LinearSet<~str> {
-    let mut words = LinearSet::new();
+pub fn reserved_keyword_table() -> HashSet<~str> {
+    let mut words = HashSet::new();
     let keys = ~[
         ~"be"
     ];
diff --git a/src/libsyntax/util/interner.rs b/src/libsyntax/util/interner.rs
index 159a205637b..4108871d008 100644
--- a/src/libsyntax/util/interner.rs
+++ b/src/libsyntax/util/interner.rs
@@ -13,10 +13,10 @@
 // type, and vice versa.
 
 use core::prelude::*;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 pub struct Interner<T> {
-    priv map: @mut LinearMap<T, uint>,
+    priv map: @mut HashMap<T, uint>,
     priv vect: @mut ~[T],
 }
 
@@ -24,7 +24,7 @@ pub struct Interner<T> {
 pub impl<T:Eq + IterBytes + Hash + Const + Copy> Interner<T> {
     fn new() -> Interner<T> {
         Interner {
-            map: @mut LinearMap::new(),
+            map: @mut HashMap::new(),
             vect: @mut ~[],
         }
     }
diff --git a/src/test/auxiliary/issue-2631-a.rs b/src/test/auxiliary/issue-2631-a.rs
index fad72ee4eb3..bee754f5bd4 100644
--- a/src/test/auxiliary/issue-2631-a.rs
+++ b/src/test/auxiliary/issue-2631-a.rs
@@ -13,9 +13,9 @@
 
 extern mod std;
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
-pub type header_map = LinearMap<~str, @mut ~[@~str]>;
+pub type header_map = HashMap<~str, @mut ~[@~str]>;
 
 // the unused ty param is necessary so this gets monomorphized
 pub fn request<T:Copy>(req: &header_map) {
diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs
index d6ebf4d346b..8a8962fb9d6 100644
--- a/src/test/bench/core-map.rs
+++ b/src/test/bench/core-map.rs
@@ -13,7 +13,7 @@ extern mod std;
 use core::io;
 use std::time;
 use std::treemap::TreeMap;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::trie::TrieMap;
 
 fn timed(label: &str, f: &fn()) {
@@ -102,7 +102,7 @@ fn main() {
 
     {
         let rng = core::rand::seeded_rng([1, 1, 1, 1, 1, 1, 1]);
-        let mut set = LinearSet::new();
+        let mut set = HashSet::new();
         while set.len() != n_keys {
             let next = rng.next() as uint;
             if set.insert(next) {
@@ -131,21 +131,21 @@ fn main() {
         vector(&mut map, n_keys, rand);
     }
 
-    io::println("\nLinearMap:");
+    io::println("\nHashMap:");
 
     {
-        let mut map = LinearMap::new::<uint, uint>();
+        let mut map = HashMap::new::<uint, uint>();
         ascending(&mut map, n_keys);
     }
 
     {
-        let mut map = LinearMap::new::<uint, uint>();
+        let mut map = HashMap::new::<uint, uint>();
         descending(&mut map, n_keys);
     }
 
     {
         io::println(" Random integers:");
-        let mut map = LinearMap::new::<uint, uint>();
+        let mut map = HashMap::new::<uint, uint>();
         vector(&mut map, n_keys, rand);
     }
 
diff --git a/src/test/bench/core-set.rs b/src/test/bench/core-set.rs
index a3210108dcc..5f8f13896fb 100644
--- a/src/test/bench/core-set.rs
+++ b/src/test/bench/core-set.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 extern mod std;
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 use std::bitv::BitvSet;
 use std::treemap::TreeSet;
 use core::io::WriterUtil;
@@ -158,9 +158,9 @@ fn main() {
     {
         let rng = rand::seeded_rng(seed);
         let mut results = empty_results();
-        results.bench_int(rng, num_keys, max, || LinearSet::new::<uint>());
-        results.bench_str(rng, num_keys, || LinearSet::new::<~str>());
-        write_results("core::hashmap::LinearSet", &results);
+        results.bench_int(rng, num_keys, max, || HashSet::new::<uint>());
+        results.bench_str(rng, num_keys, || HashSet::new::<~str>());
+        write_results("core::hashmap::HashSet", &results);
     }
 
     {
diff --git a/src/test/bench/graph500-bfs.rs b/src/test/bench/graph500-bfs.rs
index a156f915fac..396ea081362 100644
--- a/src/test/bench/graph500-bfs.rs
+++ b/src/test/bench/graph500-bfs.rs
@@ -24,7 +24,7 @@ use std::arc;
 use std::time;
 use std::deque::Deque;
 use std::par;
-use core::hashmap::linear::{LinearMap, LinearSet};
+use core::hashmap::{HashMap, HashSet};
 use core::io::WriterUtil;
 use core::int::abs;
 use core::rand::RngUtil;
@@ -81,7 +81,7 @@ fn make_edges(scale: uint, edgefactor: uint) -> ~[(node_id, node_id)] {
 
 fn make_graph(N: uint, edges: ~[(node_id, node_id)]) -> graph {
     let mut graph = do vec::from_fn(N) |_i| {
-        LinearSet::new()
+        HashSet::new()
     };
 
     do vec::each(edges) |e| {
@@ -104,7 +104,7 @@ fn make_graph(N: uint, edges: ~[(node_id, node_id)]) -> graph {
 }
 
 fn gen_search_keys(graph: &[~[node_id]], n: uint) -> ~[node_id] {
-    let mut keys = LinearSet::new();
+    let mut keys = HashSet::new();
     let r = rand::Rng();
 
     while keys.len() < n {
diff --git a/src/test/bench/shootout-k-nucleotide-pipes.rs b/src/test/bench/shootout-k-nucleotide-pipes.rs
index 3bc40a46cfb..6ba1caa0d1e 100644
--- a/src/test/bench/shootout-k-nucleotide-pipes.rs
+++ b/src/test/bench/shootout-k-nucleotide-pipes.rs
@@ -15,13 +15,13 @@
 
 extern mod std;
 use std::sort;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use core::io::ReaderUtil;
 use core::comm::{stream, Port, Chan};
 use core::cmp::Ord;
 
 // given a map, print a sorted version of it
-fn sort_and_fmt(mm: &LinearMap<~[u8], uint>, total: uint) -> ~str {
+fn sort_and_fmt(mm: &HashMap<~[u8], uint>, total: uint) -> ~str {
    fn pct(xx: uint, yy: uint) -> float {
       return (xx as float) * 100f / (yy as float);
    }
@@ -67,7 +67,7 @@ fn sort_and_fmt(mm: &LinearMap<~[u8], uint>, total: uint) -> ~str {
 }
 
 // given a map, search for the frequency of a pattern
-fn find(mm: &LinearMap<~[u8], uint>, key: ~str) -> uint {
+fn find(mm: &HashMap<~[u8], uint>, key: ~str) -> uint {
    match mm.find(&str::to_bytes(str::to_lower(key))) {
       option::None      => { return 0u; }
       option::Some(&num) => { return num; }
@@ -75,7 +75,7 @@ fn find(mm: &LinearMap<~[u8], uint>, key: ~str) -> uint {
 }
 
 // given a map, increment the counter for a key
-fn update_freq(mm: &mut LinearMap<~[u8], uint>, key: &[u8]) {
+fn update_freq(mm: &mut HashMap<~[u8], uint>, key: &[u8]) {
     let key = vec::slice(key, 0, key.len()).to_vec();
     let newval = match mm.pop(&key) {
         Some(v) => v + 1,
@@ -103,7 +103,7 @@ fn windows_with_carry(bb: &[u8], nn: uint,
 fn make_sequence_processor(sz: uint, from_parent: comm::Port<~[u8]>,
                            to_parent: comm::Chan<~str>) {
 
-   let mut freqs: LinearMap<~[u8], uint> = LinearMap::new();
+   let mut freqs: HashMap<~[u8], uint> = HashMap::new();
    let mut carry: ~[u8] = ~[];
    let mut total: uint = 0u;
 
diff --git a/src/test/bench/shootout-mandelbrot.rs b/src/test/bench/shootout-mandelbrot.rs
index 1764ef48412..f5d1661fa52 100644
--- a/src/test/bench/shootout-mandelbrot.rs
+++ b/src/test/bench/shootout-mandelbrot.rs
@@ -25,7 +25,7 @@
 //  writes pbm image to output path
 
 use core::io::WriterUtil;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 struct cmplx {
     re: f64,
@@ -125,7 +125,7 @@ fn writer(path: ~str, pport: comm::Port<Line>, size: uint)
     };
     cout.write_line("P4");
     cout.write_line(fmt!("%u %u", size, size));
-    let mut lines: LinearMap<uint, Line> = LinearMap::new();
+    let mut lines: HashMap<uint, Line> = HashMap::new();
     let mut done = 0_u;
     let mut i = 0_u;
     while i < size {
diff --git a/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs b/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs
index 6dbfa5dd538..bda659aa7b9 100644
--- a/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs
+++ b/src/test/compile-fail/borrowck-borrowed-uniq-rvalue.rs
@@ -10,11 +10,11 @@
 
 //buggy.rs
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 fn main() {
-    let mut buggy_map :LinearMap<uint, &uint> =
-      LinearMap::new::<uint, &uint>();
+    let mut buggy_map :HashMap<uint, &uint> =
+      HashMap::new::<uint, &uint>();
     buggy_map.insert(42, &*~1); //~ ERROR illegal borrow
 
     // but it is ok if we use a temporary
diff --git a/src/test/compile-fail/borrowck-insert-during-each.rs b/src/test/compile-fail/borrowck-insert-during-each.rs
index 788c5397e35..17c0efe225e 100644
--- a/src/test/compile-fail/borrowck-insert-during-each.rs
+++ b/src/test/compile-fail/borrowck-insert-during-each.rs
@@ -8,10 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use core::hashmap::linear::LinearSet;
+use core::hashmap::HashSet;
 
 struct Foo {
-  n: LinearSet<int>,
+  n: HashSet<int>,
 }
 
 pub impl Foo {
@@ -29,6 +29,6 @@ fn bar(f: &mut Foo) {
 }
 
 fn main() {
-  let mut f = Foo { n: LinearSet::new() };
+  let mut f = Foo { n: HashSet::new() };
   bar(&mut f);
 }
diff --git a/src/test/compile-fail/for-loop-decl.rs b/src/test/compile-fail/for-loop-decl.rs
index 918d8f00d78..de28d726777 100644
--- a/src/test/compile-fail/for-loop-decl.rs
+++ b/src/test/compile-fail/for-loop-decl.rs
@@ -11,10 +11,10 @@
 // error-pattern: mismatched types
 extern mod std;
 use std::bitv;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 struct FnInfo {
-    vars: LinearMap<uint, VarInfo>
+    vars: HashMap<uint, VarInfo>
 }
 
 struct VarInfo {
diff --git a/src/test/compile-fail/map-types.rs b/src/test/compile-fail/map-types.rs
index 6f71bd40aff..ebc5b015d27 100644
--- a/src/test/compile-fail/map-types.rs
+++ b/src/test/compile-fail/map-types.rs
@@ -9,12 +9,12 @@
 // except according to those terms.
 
 use core::container::Map;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 // Test that trait types printed in error msgs include the type arguments.
 
 fn main() {
-    let x: @Map<~str, ~str> = @LinearMap::new::<~str, ~str>() as
+    let x: @Map<~str, ~str> = @HashMap::new::<~str, ~str>() as
         @Map<~str, ~str>;
     let y: @Map<uint, ~str> = @x;
     //~^ ERROR mismatched types: expected `@core::container::Map<uint,~str>`
diff --git a/src/test/run-fail/unwind-misc-1.rs b/src/test/run-fail/unwind-misc-1.rs
index 06a3f0113b0..7e3318f8652 100644
--- a/src/test/run-fail/unwind-misc-1.rs
+++ b/src/test/run-fail/unwind-misc-1.rs
@@ -14,7 +14,7 @@
 
 fn main() {
     let count = @mut 0u;
-    let mut map = core::hashmap::linear::LinearMap::new();
+    let mut map = core::hashmap::HashMap::new();
     let mut arr = ~[];
     for uint::range(0u, 10u) |i| {
         arr += ~[@~"key stuff"];
diff --git a/src/test/run-pass/explicit-self-generic.rs b/src/test/run-pass/explicit-self-generic.rs
index fdf733d0314..1a2a8cab303 100644
--- a/src/test/run-pass/explicit-self-generic.rs
+++ b/src/test/run-pass/explicit-self-generic.rs
@@ -20,17 +20,17 @@ type EqFn<K> = ~fn(K, K) -> bool;
 
 struct LM { resize_at: uint, size: uint }
 
-enum LinearMap<K,V> {
-    LinearMap_(LM)
+enum HashMap<K,V> {
+    HashMap_(LM)
 }
 
-fn linear_map<K,V>() -> LinearMap<K,V> {
-    LinearMap_(LM{
+fn linear_map<K,V>() -> HashMap<K,V> {
+    HashMap_(LM{
         resize_at: 32,
         size: 0})
 }
 
-pub impl<K,V> LinearMap<K,V> {
+pub impl<K,V> HashMap<K,V> {
     fn len(&mut self) -> uint {
         self.size
     }
diff --git a/src/test/run-pass/hashmap-memory.rs b/src/test/run-pass/hashmap-memory.rs
index 4234c064e8d..910708b7106 100644
--- a/src/test/run-pass/hashmap-memory.rs
+++ b/src/test/run-pass/hashmap-memory.rs
@@ -19,7 +19,7 @@
 pub fn map(filename: ~str, emit: map_reduce::putter) { emit(filename, ~"1"); }
 
 mod map_reduce {
-    use core::hashmap::linear::LinearMap;
+    use core::hashmap::HashMap;
     use core::comm::*;
 
     pub type putter = @fn(~str, ~str);
@@ -37,9 +37,9 @@ mod map_reduce {
     }
 
     fn map_task(ctrl: SharedChan<ctrl_proto>, input: ~str) {
-        let intermediates = @mut LinearMap::new();
+        let intermediates = @mut HashMap::new();
 
-        fn emit(im: &mut LinearMap<~str, int>, ctrl: SharedChan<ctrl_proto>, key: ~str,
+        fn emit(im: &mut HashMap<~str, int>, ctrl: SharedChan<ctrl_proto>, key: ~str,
                 _val: ~str) {
             if im.contains_key(&key) {
                 return;
@@ -65,9 +65,9 @@ mod map_reduce {
         // This task becomes the master control task. It spawns others
         // to do the rest.
 
-        let mut reducers: LinearMap<~str, int>;
+        let mut reducers: HashMap<~str, int>;
 
-        reducers = LinearMap::new();
+        reducers = HashMap::new();
 
         start_mappers(ctrl_chan, inputs.clone());
 
diff --git a/src/test/run-pass/issue-1696.rs b/src/test/run-pass/issue-1696.rs
index 5f8b8d29830..5b40d0abff8 100644
--- a/src/test/run-pass/issue-1696.rs
+++ b/src/test/run-pass/issue-1696.rs
@@ -10,10 +10,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 pub fn main() {
-    let mut m = LinearMap::new();
+    let mut m = HashMap::new();
     m.insert(str::to_bytes(~"foo"), str::to_bytes(~"bar"));
     error!(m);
 }
diff --git a/src/test/run-pass/issue-2631-b.rs b/src/test/run-pass/issue-2631-b.rs
index b22c423ed04..f6e40fa247d 100644
--- a/src/test/run-pass/issue-2631-b.rs
+++ b/src/test/run-pass/issue-2631-b.rs
@@ -14,11 +14,11 @@
 extern mod req;
 
 use req::*;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 pub fn main() {
   let v = ~[@~"hi"];
-  let mut m: req::header_map = LinearMap::new();
+  let mut m: req::header_map = HashMap::new();
   m.insert(~"METHOD", @mut v);
   request::<int>(&m);
 }
diff --git a/src/test/run-pass/issue-2804-2.rs b/src/test/run-pass/issue-2804-2.rs
index 8934c3935c0..b25e4095b18 100644
--- a/src/test/run-pass/issue-2804-2.rs
+++ b/src/test/run-pass/issue-2804-2.rs
@@ -13,9 +13,9 @@
 // Minimized version of issue-2804.rs. Both check that callee IDs don't
 // clobber the previous node ID in a macro expr
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
-fn add_interfaces(managed_ip: ~str, device: LinearMap<~str, int>)  {
+fn add_interfaces(managed_ip: ~str, device: HashMap<~str, int>)  {
      error!("%s, %?", managed_ip, device.get(&~"interfaces"));
 }
 
diff --git a/src/test/run-pass/issue-2804.rs b/src/test/run-pass/issue-2804.rs
index 3d1a2c3df5d..4614c26fa5f 100644
--- a/src/test/run-pass/issue-2804.rs
+++ b/src/test/run-pass/issue-2804.rs
@@ -11,7 +11,7 @@
 // except according to those terms.
 
 extern mod std;
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 use std::json;
 
 enum object {
@@ -58,7 +58,7 @@ fn add_interface(store: int, managed_ip: ~str, data: std::json::Json) -> (~str,
     }
 }
 
-fn add_interfaces(store: int, managed_ip: ~str, device: LinearMap<~str, std::json::Json>) -> ~[(~str, object)]
+fn add_interfaces(store: int, managed_ip: ~str, device: HashMap<~str, std::json::Json>) -> ~[(~str, object)]
 {
     match device.get(&~"interfaces")
     {
diff --git a/src/test/run-pass/issue-3026.rs b/src/test/run-pass/issue-3026.rs
index 022d3f6fceb..16e9b4753f8 100644
--- a/src/test/run-pass/issue-3026.rs
+++ b/src/test/run-pass/issue-3026.rs
@@ -10,10 +10,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 pub fn main() {
-    let mut buggy_map: LinearMap<uint, &uint> = LinearMap::new::<uint, &uint>();
+    let mut buggy_map: HashMap<uint, &uint> = HashMap::new::<uint, &uint>();
     let x = ~1;
     buggy_map.insert(42, &*x);
 }
diff --git a/src/test/run-pass/issue-3559.rs b/src/test/run-pass/issue-3559.rs
index f7b7605523c..334831fea4d 100644
--- a/src/test/run-pass/issue-3559.rs
+++ b/src/test/run-pass/issue-3559.rs
@@ -29,7 +29,7 @@ fn check_strs(actual: &str, expected: &str) -> bool
 #[test]
 fn tester()
 {
-    let mut table = core::hashmap::linear::LinearMap();
+    let mut table = core::hashmap::HashMap();
     table.insert(@~"one", 1);
     table.insert(@~"two", 2);
     assert!(check_strs(table.to_str(), ~"xxx"));   // not sure what expected should be
diff --git a/src/test/run-pass/issue-4016.rs b/src/test/run-pass/issue-4016.rs
index 69cd1a2a19d..2384b0e8593 100644
--- a/src/test/run-pass/issue-4016.rs
+++ b/src/test/run-pass/issue-4016.rs
@@ -11,7 +11,7 @@
 // xfail-test
 extern mod std;
 
-use hashmap::linear;
+use hashmap;
 use std::json;
 use std::serialization::{Deserializable, deserialize};
 
diff --git a/src/test/run-pass/issue-4092.rs b/src/test/run-pass/issue-4092.rs
index 85cb3e3207e..e129e0a8868 100644
--- a/src/test/run-pass/issue-4092.rs
+++ b/src/test/run-pass/issue-4092.rs
@@ -8,9 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use core::hashmap::linear::LinearMap;
+use core::hashmap::HashMap;
 
 pub fn main() {
-    let mut x = LinearMap::new();
+    let mut x = HashMap::new();
     x.insert((@"abc", 0), 0);
 }