1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // ignore-lexer-test FIXME #15883
13 //! Unordered containers, implemented as hash-tables (`HashSet` and `HashMap` types)
16 use cmp::{max, Eq, Equiv, PartialEq};
17 use collections::{Collection, Mutable, Set, MutableSet, Map, MutableMap};
21 use hash::{Hash, Hasher, RandomSipHasher};
22 use iter::{Iterator, FilterMap, Chain, Repeat, Zip, Extendable};
23 use iter::{range, range_inclusive, FromIterator};
27 use option::{Some, None, Option};
28 use result::{Ok, Err};
33 use hash::{Hash, Hasher};
34 use iter::range_step_inclusive;
35 use iter::{Iterator, range};
37 use mem::{min_align_of, size_of};
38 use mem::{overwrite, transmute};
39 use num::{CheckedMul, is_power_of_two};
41 use option::{Some, None, Option};
45 use rt::heap::{allocate, deallocate};
47 static EMPTY_BUCKET: u64 = 0u64;
49 /// The raw hashtable, providing safe-ish access to the unzipped and highly
50 /// optimized arrays of hashes, keys, and values.
52 /// This design uses less memory and is a lot faster than the naive
53 /// `Vec<Option<u64, K, V>>`, because we don't pay for the overhead of an
54 /// option on every element, and we get a generally more cache-aware design.
56 /// Key invariants of this structure:
58 /// - if hashes[i] == EMPTY_BUCKET, then keys[i] and vals[i] have
59 /// 'undefined' contents. Don't read from them. This invariant is
60 /// enforced outside this module with the `EmptyIndex`, `FullIndex`,
61 /// and `SafeHash` types.
63 /// - An `EmptyIndex` is only constructed for a bucket at an index with
64 /// a hash of EMPTY_BUCKET.
66 /// - A `FullIndex` is only constructed for a bucket at an index with a
67 /// non-EMPTY_BUCKET hash.
69 /// - A `SafeHash` is only constructed for non-`EMPTY_BUCKET` hash. We get
70 /// around hashes of zero by changing them to 0x8000_0000_0000_0000,
71 /// which will likely map to the same bucket, while not being confused
74 /// - All three "arrays represented by pointers" are the same length:
75 /// `capacity`. This is set at creation and never changes. The arrays
76 /// are unzipped to save space (we don't have to pay for the padding
77 /// between odd sized elements, such as in a map from u64 to u8), and
78 /// be more cache aware (scanning through 8 hashes brings in 2 cache
79 /// lines, since they're all right beside each other).
81 /// You can kind of think of this module/data structure as a safe wrapper
82 /// around just the "table" part of the hashtable. It enforces some
83 /// invariants at the type level and employs some performance trickery,
84 /// but in general is just a tricked out `Vec<Option<u64, K, V>>`.
88 /// Feb 11, 2014: This hashtable was just implemented, and, hard as I tried,
89 /// isn't yet totally safe. There's a "known exploit" that you can create
90 /// multiple FullIndexes for a bucket, `take` one, and then still `take`
91 /// the other causing undefined behavior. Currently, there's no story
92 /// for how to protect against this statically. Therefore, there are asserts
93 /// on `take`, `get`, `get_mut`, and `put` which check the bucket state.
94 /// With time, and when we're confident this works correctly, they should
95 /// be removed. Also, the bounds check in `peek` is especially painful,
96 /// as that's called in the innermost loops of the hashtable and has the
97 /// potential to be a major performance drain. Remove this too.
99 /// Or, better than remove, only enable these checks for debug builds.
100 /// There's currently no "debug-only" asserts in rust, so if you're reading
101 /// this and going "what? of course there are debug-only asserts!", then
102 /// please make this use them!
103 #[unsafe_no_drop_flag]
104 pub struct RawTable<K, V> {
112 /// Represents an index into a `RawTable` with no key or value in it.
113 pub struct EmptyIndex {
115 nocopy: marker::NoCopy,
118 /// Represents an index into a `RawTable` with a key, value, and hash
120 pub struct FullIndex {
123 nocopy: marker::NoCopy,
127 /// Since we get the hash for free whenever we check the bucket state,
128 /// this function is provided for fast access, letting us avoid
129 /// redundant trips back to the hashtable.
131 pub fn hash(&self) -> SafeHash { self.hash }
133 /// Same comment as with `hash`.
135 pub fn raw_index(&self) -> uint { self.idx as uint }
138 /// Represents the state of a bucket: it can either have a key/value
139 /// pair (be full) or not (be empty). You cannot `take` empty buckets,
140 /// and you cannot `put` into full buckets.
141 pub enum BucketState {
146 /// A hash that is not zero, since we use a hash of zero to represent empty
148 #[deriving(PartialEq)]
149 pub struct SafeHash {
154 /// Peek at the hash value, which is guaranteed to be non-zero.
156 pub fn inspect(&self) -> u64 { self.hash }
159 /// We need to remove hashes of 0. That's reserved for empty buckets.
160 /// This function wraps up `hash_keyed` to be the only way outside this
161 /// module to generate a SafeHash.
162 pub fn make_hash<T: Hash<S>, S, H: Hasher<S>>(hasher: &H, t: &T) -> SafeHash {
163 match hasher.hash(t) {
164 // This constant is exceedingly likely to hash to the same
165 // bucket, but it won't be counted as empty!
166 EMPTY_BUCKET => SafeHash { hash: 0x8000_0000_0000_0000 },
167 h => SafeHash { hash: h },
171 fn round_up_to_next(unrounded: uint, target_alignment: uint) -> uint {
172 assert!(is_power_of_two(target_alignment));
173 (unrounded + target_alignment - 1) & !(target_alignment - 1)
178 assert_eq!(round_up_to_next(0, 4), 0);
179 assert_eq!(round_up_to_next(1, 4), 4);
180 assert_eq!(round_up_to_next(2, 4), 4);
181 assert_eq!(round_up_to_next(3, 4), 4);
182 assert_eq!(round_up_to_next(4, 4), 4);
183 assert_eq!(round_up_to_next(5, 4), 8);
186 // Returns a tuple of (minimum required malloc alignment, hash_offset,
187 // key_offset, val_offset, array_size), from the start of a mallocated array.
188 fn calculate_offsets(
189 hash_size: uint, hash_align: uint,
190 keys_size: uint, keys_align: uint,
191 vals_size: uint, vals_align: uint) -> (uint, uint, uint, uint, uint) {
194 let end_of_hashes = hash_offset + hash_size;
196 let keys_offset = round_up_to_next(end_of_hashes, keys_align);
197 let end_of_keys = keys_offset + keys_size;
199 let vals_offset = round_up_to_next(end_of_keys, vals_align);
200 let end_of_vals = vals_offset + vals_size;
202 let min_align = cmp::max(hash_align, cmp::max(keys_align, vals_align));
204 (min_align, hash_offset, keys_offset, vals_offset, end_of_vals)
208 fn test_offset_calculation() {
209 assert_eq!(calculate_offsets(128, 8, 15, 1, 4, 4 ), (8, 0, 128, 144, 148));
210 assert_eq!(calculate_offsets(3, 1, 2, 1, 1, 1 ), (1, 0, 3, 5, 6));
211 assert_eq!(calculate_offsets(6, 2, 12, 4, 24, 8), (8, 0, 8, 24, 48));
214 impl<K, V> RawTable<K, V> {
216 /// Does not initialize the buckets. The caller should ensure they,
217 /// at the very least, set every hash to EMPTY_BUCKET.
218 unsafe fn new_uninitialized(capacity: uint) -> RawTable<K, V> {
219 let hashes_size = capacity.checked_mul(&size_of::<u64>())
220 .expect("capacity overflow");
221 let keys_size = capacity.checked_mul(&size_of::< K >())
222 .expect("capacity overflow");
223 let vals_size = capacity.checked_mul(&size_of::< V >())
224 .expect("capacity overflow");
226 // Allocating hashmaps is a little tricky. We need to allocate three
227 // arrays, but since we know their sizes and alignments up front,
228 // we just allocate a single array, and then have the subarrays
231 // This is great in theory, but in practice getting the alignment
232 // right is a little subtle. Therefore, calculating offsets has been
233 // factored out into a different function.
234 let (malloc_alignment, hash_offset, keys_offset, vals_offset, size) =
236 hashes_size, min_align_of::<u64>(),
237 keys_size, min_align_of::< K >(),
238 vals_size, min_align_of::< V >());
240 let buffer = allocate(size, malloc_alignment);
242 let hashes = buffer.offset(hash_offset as int) as *mut u64;
243 let keys = buffer.offset(keys_offset as int) as *mut K;
244 let vals = buffer.offset(vals_offset as int) as *mut V;
255 /// Creates a new raw table from a given capacity. All buckets are
257 #[allow(experimental)]
258 pub fn new(capacity: uint) -> RawTable<K, V> {
260 let ret = RawTable::new_uninitialized(capacity);
261 set_memory(ret.hashes, 0u8, capacity);
266 /// Reads a bucket at a given index, returning an enum indicating whether
267 /// there's anything there or not. You need to match on this enum to get
268 /// the appropriate types to pass on to most of the other functions in
270 pub fn peek(&self, index: uint) -> BucketState {
271 debug_assert!(index < self.capacity);
273 let idx = index as int;
274 let hash = unsafe { *self.hashes.offset(idx) };
276 let nocopy = marker::NoCopy;
287 hash: SafeHash { hash: full_hash },
293 /// Gets references to the key and value at a given index.
294 pub fn read<'a>(&'a self, index: &FullIndex) -> (&'a K, &'a V) {
298 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
299 (&*self.keys.offset(idx), &*self.vals.offset(idx))
303 /// Gets references to the key and value at a given index, with the
304 /// value's reference being mutable.
305 pub fn read_mut<'a>(&'a mut self, index: &FullIndex) -> (&'a K, &'a mut V) {
309 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
310 (&*self.keys.offset(idx), &mut *self.vals.offset(idx))
314 /// Read everything, mutably.
315 pub fn read_all_mut<'a>(&'a mut self, index: &FullIndex)
316 -> (&'a mut SafeHash, &'a mut K, &'a mut V) {
320 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
321 (transmute(self.hashes.offset(idx)),
322 &mut *self.keys.offset(idx), &mut *self.vals.offset(idx))
326 /// Puts a key and value pair, along with the key's hash, into a given
327 /// index in the hashtable. Note how the `EmptyIndex` is 'moved' into this
328 /// function, because that slot will no longer be empty when we return!
329 /// A FullIndex is returned for later use, pointing to the newly-filled
330 /// slot in the hashtable.
332 /// Use `make_hash` to construct a `SafeHash` to pass to this function.
333 pub fn put(&mut self, index: EmptyIndex, hash: SafeHash, k: K, v: V) -> FullIndex {
337 debug_assert_eq!(*self.hashes.offset(idx), EMPTY_BUCKET);
338 *self.hashes.offset(idx) = hash.inspect();
339 overwrite(&mut *self.keys.offset(idx), k);
340 overwrite(&mut *self.vals.offset(idx), v);
345 FullIndex { idx: idx, hash: hash, nocopy: marker::NoCopy }
348 /// Removes a key and value from the hashtable.
350 /// This works similarly to `put`, building an `EmptyIndex` out of the
352 pub fn take(&mut self, index: FullIndex) -> (EmptyIndex, K, V) {
356 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
358 *self.hashes.offset(idx) = EMPTY_BUCKET;
360 // Drop the mutable constraint.
361 let keys = self.keys as *const K;
362 let vals = self.vals as *const V;
364 let k = ptr::read(keys.offset(idx));
365 let v = ptr::read(vals.offset(idx));
369 (EmptyIndex { idx: idx, nocopy: marker::NoCopy }, k, v)
373 /// The hashtable's capacity, similar to a vector's.
374 pub fn capacity(&self) -> uint {
378 /// The number of elements ever `put` in the hashtable, minus the number
379 /// of elements ever `take`n.
380 pub fn size(&self) -> uint {
384 pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
385 Entries { table: self, idx: 0, elems_seen: 0 }
388 pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> {
389 MutEntries { table: self, idx: 0, elems_seen: 0 }
392 pub fn move_iter(self) -> MoveEntries<K, V> {
393 MoveEntries { table: self, idx: 0 }
397 // `read_all_mut` casts a `*u64` to a `*SafeHash`. Since we statically
398 // ensure that a `FullIndex` points to an index with a non-zero hash,
399 // and a `SafeHash` is just a `u64` with a different name, this is
402 // This test ensures that a `SafeHash` really IS the same size as a
403 // `u64`. If you need to change the size of `SafeHash` (and
404 // consequently made this test fail), `read_all_mut` needs to be
405 // modified to no longer assume this.
407 fn can_alias_safehash_as_u64() {
408 assert_eq!(size_of::<SafeHash>(), size_of::<u64>())
411 /// Iterator over shared references to entries in a table.
412 pub struct Entries<'a, K, V> {
413 table: &'a RawTable<K, V>,
418 /// Iterator over mutable references to entries in a table.
419 pub struct MutEntries<'a, K, V> {
420 table: &'a mut RawTable<K, V>,
425 /// Iterator over the entries in a table, consuming the table.
426 pub struct MoveEntries<K, V> {
427 table: RawTable<K, V>,
431 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
432 fn next(&mut self) -> Option<(&'a K, &'a V)> {
433 while self.idx < self.table.capacity() {
437 match self.table.peek(i) {
440 self.elems_seen += 1;
441 return Some(self.table.read(&idx));
449 fn size_hint(&self) -> (uint, Option<uint>) {
450 let size = self.table.size() - self.elems_seen;
455 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
456 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
457 while self.idx < self.table.capacity() {
461 match self.table.peek(i) {
463 // the transmute here fixes:
464 // error: lifetime of `self` is too short to guarantee its contents
465 // can be safely reborrowed
466 Full(idx) => unsafe {
467 self.elems_seen += 1;
468 return Some(transmute(self.table.read_mut(&idx)));
476 fn size_hint(&self) -> (uint, Option<uint>) {
477 let size = self.table.size() - self.elems_seen;
482 impl<K, V> Iterator<(SafeHash, K, V)> for MoveEntries<K, V> {
483 fn next(&mut self) -> Option<(SafeHash, K, V)> {
484 while self.idx < self.table.capacity() {
488 match self.table.peek(i) {
492 let (_, k, v) = self.table.take(idx);
493 return Some((h, k, v));
501 fn size_hint(&self) -> (uint, Option<uint>) {
502 let size = self.table.size();
507 impl<K: Clone, V: Clone> Clone for RawTable<K, V> {
508 fn clone(&self) -> RawTable<K, V> {
510 let mut new_ht = RawTable::new_uninitialized(self.capacity());
512 for i in range(0, self.capacity()) {
515 *new_ht.hashes.offset(i as int) = EMPTY_BUCKET;
518 let hash = idx.hash().inspect();
519 let (k, v) = self.read(&idx);
520 *new_ht.hashes.offset(i as int) = hash;
521 overwrite(&mut *new_ht.keys.offset(i as int), (*k).clone());
522 overwrite(&mut *new_ht.vals.offset(i as int), (*v).clone());
527 new_ht.size = self.size();
535 impl<K, V> Drop for RawTable<K, V> {
537 // This is in reverse because we're likely to have partially taken
538 // some elements out with `.move_iter()` from the front.
539 for i in range_step_inclusive(self.capacity as int - 1, 0, -1) {
540 // Check if the size is 0, so we don't do a useless scan when
541 // dropping empty tables such as on resize.
542 if self.size == 0 { break }
544 match self.peek(i as uint) {
546 Full(idx) => { self.take(idx); }
550 assert_eq!(self.size, 0);
552 if self.hashes.is_not_null() {
553 let hashes_size = self.capacity * size_of::<u64>();
554 let keys_size = self.capacity * size_of::<K>();
555 let vals_size = self.capacity * size_of::<V>();
556 let (align, _, _, _, size) = calculate_offsets(hashes_size, min_align_of::<u64>(),
557 keys_size, min_align_of::<K>(),
558 vals_size, min_align_of::<V>());
561 deallocate(self.hashes as *mut u8, size, align);
562 // Remember how everything was allocated out of one buffer
563 // during initialization? We only need one call to free here.
566 self.hashes = RawPtr::null();
572 static INITIAL_LOG2_CAP: uint = 5;
573 static INITIAL_CAPACITY: uint = 1 << INITIAL_LOG2_CAP; // 2^5
575 /// The default behavior of HashMap implements a load factor of 90.9%.
576 /// This behavior is characterized by the following conditions:
578 /// - if `size * 1.1 < cap < size * 4` then shouldn't resize
579 /// - if `cap < minimum_capacity * 2` then shouldn't shrink
581 struct DefaultResizePolicy {
582 /// Doubled minimal capacity. The capacity must never drop below
583 /// the minimum capacity. (The check happens before the capacity
584 /// is potentially halved.)
585 minimum_capacity2: uint
588 impl DefaultResizePolicy {
589 fn new(new_capacity: uint) -> DefaultResizePolicy {
590 DefaultResizePolicy {
591 minimum_capacity2: new_capacity << 1
596 fn capacity_range(&self, new_size: uint) -> (uint, uint) {
597 ((new_size * 11) / 10, max(new_size << 3, self.minimum_capacity2))
601 fn reserve(&mut self, new_capacity: uint) {
602 self.minimum_capacity2 = new_capacity << 1;
606 // The main performance trick in this hashmap is called Robin Hood Hashing.
607 // It gains its excellent performance from one key invariant:
609 // If an insertion collides with an existing element, and that elements
610 // "probe distance" (how far away the element is from its ideal location)
611 // is higher than how far we've already probed, swap the elements.
613 // This massively lowers variance in probe distance, and allows us to get very
614 // high load factors with good performance. The 90% load factor I use is rather
617 // > Why a load factor of approximately 90%?
619 // In general, all the distances to initial buckets will converge on the mean.
620 // At a load factor of α, the odds of finding the target bucket after k
621 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
622 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
623 // this down to make the math easier on the CPU and avoid its FPU.
624 // Since on average we start the probing in the middle of a cache line, this
625 // strategy pulls in two cache lines of hashes on every lookup. I think that's
626 // pretty good, but if you want to trade off some space, it could go down to one
627 // cache line on average with an α of 0.84.
629 // > Wait, what? Where did you get 1-α^k from?
631 // On the first probe, your odds of a collision with an existing element is α.
632 // The odds of doing this twice in a row is approximately α^2. For three times,
633 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
634 // colliding after k tries is 1-α^k.
636 // Future Improvements (FIXME!)
637 // ============================
639 // Allow the load factor to be changed dynamically and/or at initialization.
641 // Also, would it be possible for us to reuse storage when growing the
642 // underlying table? This is exactly the use case for 'realloc', and may
643 // be worth exploring.
645 // Future Optimizations (FIXME!)
646 // =============================
648 // The paper cited below mentions an implementation which keeps track of the
649 // distance-to-initial-bucket histogram. I'm suspicious of this approach because
650 // it requires maintaining an internal map. If this map were replaced with a
651 // hashmap, it would be faster, but now our data structure is self-referential
652 // and blows up. Also, this allows very good first guesses, but array accesses
653 // are no longer linear and in one direction, as we have now. There is also
654 // memory and cache pressure that this map would entail that would be very
655 // difficult to properly see in a microbenchmark.
657 // Another possible design choice that I made without any real reason is
658 // parameterizing the raw table over keys and values. Technically, all we need
659 // is the size and alignment of keys and values, and the code should be just as
660 // efficient (well, we might need one for power-of-two size and one for not...).
661 // This has the potential to reduce code bloat in rust executables, without
662 // really losing anything except 4 words (key size, key alignment, val size,
663 // val alignment) which can be passed in to every call of a `RawTable` function.
664 // This would definitely be an avenue worth exploring if people start complaining
665 // about the size of rust executables.
667 // There's also an "optimization" that has been omitted regarding how the
668 // hashtable allocates. The vector type has set the expectation that a hashtable
669 // which never has an element inserted should not allocate. I'm suspicious of
670 // implementing this for hashtables, because supporting it has no performance
671 // benefit over using an `Option<HashMap<K, V>>`, and is significantly more
674 /// A hash map implementation which uses linear probing with Robin
675 /// Hood bucket stealing.
677 /// The hashes are all keyed by the task-local random number generator
678 /// on creation by default, this means the ordering of the keys is
679 /// randomized, but makes the tables more resistant to
680 /// denial-of-service attacks (Hash DoS). This behaviour can be
681 /// overridden with one of the constructors.
683 /// It is required that the keys implement the `Eq` and `Hash` traits, although
684 /// this can frequently be achieved by using `#[deriving(Eq, Hash)]`.
686 /// Relevant papers/articles:
688 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
689 /// 2. Emmanuel Goossaert. ["Robin Hood
690 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
691 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
692 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
697 /// use std::collections::HashMap;
699 /// // type inference lets us omit an explicit type signature (which
700 /// // would be `HashMap<&str, &str>` in this example).
701 /// let mut book_reviews = HashMap::new();
703 /// // review some books.
704 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
705 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
706 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
707 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
709 /// // check for a specific one.
710 /// if !book_reviews.contains_key(&("Les Misérables")) {
711 /// println!("We've got {} reviews, but Les Misérables ain't one.",
712 /// book_reviews.len());
715 /// // oops, this review has a lot of spelling mistakes, let's delete it.
716 /// book_reviews.remove(&("The Adventures of Sherlock Holmes"));
718 /// // look up the values associated with some keys.
719 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
720 /// for book in to_find.iter() {
721 /// match book_reviews.find(book) {
722 /// Some(review) => println!("{}: {}", *book, *review),
723 /// None => println!("{} is unreviewed.", *book)
727 /// // iterate over everything.
728 /// for (book, review) in book_reviews.iter() {
729 /// println!("{}: \"{}\"", *book, *review);
733 /// The easiest way to use `HashMap` with a custom type is to derive `Eq` and `Hash`.
734 /// We must also derive `PartialEq`.
737 /// use std::collections::HashMap;
739 /// #[deriving(Hash, Eq, PartialEq, Show)]
740 /// struct Viking<'a> {
745 /// let mut vikings = HashMap::new();
747 /// vikings.insert("Norway", Viking { name: "Einar", power: 9u });
748 /// vikings.insert("Denmark", Viking { name: "Olaf", power: 4u });
749 /// vikings.insert("Iceland", Viking { name: "Harald", power: 8u });
751 /// // Use derived implementation to print the vikings.
752 /// for (land, viking) in vikings.iter() {
753 /// println!("{} at {}", viking, land);
757 pub struct HashMap<K, V, H = RandomSipHasher> {
758 // All hashes are keyed on these values, to prevent hash collision attacks.
761 table: table::RawTable<K, V>,
763 // We keep this at the end since it might as well have tail padding.
764 resize_policy: DefaultResizePolicy,
767 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
768 // Probe the `idx`th bucket for a given hash, returning the index of the
771 // This exploits the power-of-two size of the hashtable. As long as this
772 // is always true, we can use a bitmask of cap-1 to do modular arithmetic.
774 // Prefer using this with increasing values of `idx` rather than repeatedly
775 // calling `probe_next`. This reduces data-dependencies between loops, which
776 // can help the optimizer, and certainly won't hurt it. `probe_next` is
777 // simply for convenience, and is no more efficient than `probe`.
778 fn probe(&self, hash: &table::SafeHash, idx: uint) -> uint {
779 let hash_mask = self.table.capacity() - 1;
781 // So I heard a rumor that unsigned overflow is safe in rust..
782 ((hash.inspect() as uint) + idx) & hash_mask
785 // Generate the next probe in a sequence. Prefer using 'probe' by itself,
786 // but this can sometimes be useful.
787 fn probe_next(&self, probe: uint) -> uint {
788 let hash_mask = self.table.capacity() - 1;
789 (probe + 1) & hash_mask
792 fn make_hash<X: Hash<S>>(&self, x: &X) -> table::SafeHash {
793 table::make_hash(&self.hasher, x)
796 /// Get the distance of the bucket at the given index that it lies
797 /// from its 'ideal' location.
799 /// In the cited blog posts above, this is called the "distance to
800 /// initial bucket", or DIB.
801 fn bucket_distance(&self, index_of_elem: &table::FullIndex) -> uint {
802 // where the hash of the element that happens to reside at
803 // `index_of_elem` tried to place itself first.
804 let first_probe_index = self.probe(&index_of_elem.hash(), 0);
806 let raw_index = index_of_elem.raw_index();
808 if first_probe_index <= raw_index {
809 // probe just went forward
810 raw_index - first_probe_index
812 // probe wrapped around the hashtable
813 raw_index + (self.table.capacity() - first_probe_index)
817 /// Search for a pre-hashed key.
818 fn search_hashed_generic(&self, hash: &table::SafeHash, is_match: |&K| -> bool)
819 -> Option<table::FullIndex> {
820 for num_probes in range(0u, self.table.size()) {
821 let probe = self.probe(hash, num_probes);
823 let idx = match self.table.peek(probe) {
824 table::Empty(_) => return None, // hit an empty bucket
825 table::Full(idx) => idx
828 // We can finish the search early if we hit any bucket
829 // with a lower distance to initial bucket than we've probed.
830 if self.bucket_distance(&idx) < num_probes { return None }
832 // If the hash doesn't match, it can't be this one..
833 if *hash != idx.hash() { continue }
835 let (k, _) = self.table.read(&idx);
837 // If the key doesn't match, it can't be this one..
838 if !is_match(k) { continue }
846 fn search_hashed(&self, hash: &table::SafeHash, k: &K) -> Option<table::FullIndex> {
847 self.search_hashed_generic(hash, |k_| *k == *k_)
850 fn search_equiv<Q: Hash<S> + Equiv<K>>(&self, q: &Q) -> Option<table::FullIndex> {
851 self.search_hashed_generic(&self.make_hash(q), |k| q.equiv(k))
854 /// Search for a key, yielding the index if it's found in the hashtable.
855 /// If you already have the hash for the key lying around, use
857 fn search(&self, k: &K) -> Option<table::FullIndex> {
858 self.search_hashed(&self.make_hash(k), k)
861 fn pop_internal(&mut self, starting_index: table::FullIndex) -> Option<V> {
862 let starting_probe = starting_index.raw_index();
865 let mut probe = self.probe_next(starting_probe);
866 for _ in range(0u, self.table.size()) {
867 match self.table.peek(probe) {
868 table::Empty(_) => {}, // empty bucket. this is the end of our shifting.
869 table::Full(idx) => {
870 // Bucket that isn't us, which has a non-zero probe distance.
871 // This isn't the ending index, so keep searching.
872 if self.bucket_distance(&idx) != 0 {
873 probe = self.probe_next(probe);
877 // if we do have a bucket_distance of zero, we're at the end
878 // of what we need to shift.
887 let (_, _, retval) = self.table.take(starting_index);
889 let mut probe = starting_probe;
890 let mut next_probe = self.probe_next(probe);
892 // backwards-shift all the elements after our newly-deleted one.
893 while next_probe != ending_probe {
894 match self.table.peek(next_probe) {
896 // nothing to shift in. just empty it out.
897 match self.table.peek(probe) {
898 table::Empty(_) => {},
899 table::Full(idx) => { self.table.take(idx); }
902 table::Full(next_idx) => {
903 // something to shift. move it over!
904 let next_hash = next_idx.hash();
905 let (_, next_key, next_val) = self.table.take(next_idx);
906 match self.table.peek(probe) {
907 table::Empty(idx) => {
908 self.table.put(idx, next_hash, next_key, next_val);
910 table::Full(idx) => {
911 let (emptyidx, _, _) = self.table.take(idx);
912 self.table.put(emptyidx, next_hash, next_key, next_val);
919 next_probe = self.probe_next(next_probe);
922 // Done the backwards shift, but there's still an element left!
924 match self.table.peek(probe) {
925 table::Empty(_) => {},
926 table::Full(idx) => { self.table.take(idx); }
929 // Now we're done all our shifting. Return the value we grabbed
935 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Collection for HashMap<K, V, H> {
936 /// Return the number of elements in the map.
937 fn len(&self) -> uint { self.table.size() }
940 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H> {
941 /// Clear the map, removing all key-value pairs. Keeps the allocated memory
943 fn clear(&mut self) {
944 // Prevent reallocations from happening from now on. Makes it possible
945 // for the map to be reused but has a downside: reserves permanently.
946 self.resize_policy.reserve(self.table.size());
948 for i in range(0, self.table.capacity()) {
949 match self.table.peek(i) {
950 table::Empty(_) => {},
951 table::Full(idx) => { self.table.take(idx); }
957 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Map<K, V> for HashMap<K, V, H> {
958 fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
959 self.search(k).map(|idx| {
960 let (_, v) = self.table.read(&idx);
965 fn contains_key(&self, k: &K) -> bool {
966 self.search(k).is_some()
970 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V, H> {
971 fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
972 match self.search(k) {
975 let (_, v) = self.table.read_mut(&idx);
981 fn swap(&mut self, k: K, v: V) -> Option<V> {
982 let hash = self.make_hash(&k);
983 let potential_new_size = self.table.size() + 1;
984 self.make_some_room(potential_new_size);
986 for dib in range_inclusive(0u, self.table.size()) {
987 let probe = self.probe(&hash, dib);
989 let idx = match self.table.peek(probe) {
990 table::Empty(idx) => {
992 self.table.put(idx, hash, k, v);
995 table::Full(idx) => idx
998 if idx.hash() == hash {
999 let (bucket_k, bucket_v) = self.table.read_mut(&idx);
1001 // Found an existing value.
1002 return Some(replace(bucket_v, v));
1006 let probe_dib = self.bucket_distance(&idx);
1008 if probe_dib < dib {
1009 // Found a luckier bucket. This implies that the key does not
1010 // already exist in the hashtable. Just do a robin hood
1012 self.robin_hood(idx, probe_dib, hash, k, v);
1017 // We really shouldn't be here.
1018 fail!("Internal HashMap error: Out of space.");
1021 fn pop(&mut self, k: &K) -> Option<V> {
1022 if self.table.size() == 0 {
1026 let potential_new_size = self.table.size() - 1;
1027 self.make_some_room(potential_new_size);
1029 let starting_index = match self.search(k) {
1031 None => return None,
1034 self.pop_internal(starting_index)
1039 impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
1040 /// Create an empty HashMap.
1045 /// use std::collections::HashMap;
1046 /// let mut map: HashMap<&str, int> = HashMap::new();
1049 pub fn new() -> HashMap<K, V, RandomSipHasher> {
1050 HashMap::with_capacity(INITIAL_CAPACITY)
1053 /// Creates an empty hash map with the given initial capacity.
1058 /// use std::collections::HashMap;
1059 /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
1062 pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
1063 let hasher = RandomSipHasher::new();
1064 HashMap::with_capacity_and_hasher(capacity, hasher)
1068 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
1069 /// Creates an empty hashmap which will use the given hasher to hash keys.
1071 /// The creates map has the default initial capacity.
1076 /// use std::collections::HashMap;
1077 /// use std::hash::sip::SipHasher;
1079 /// let h = SipHasher::new();
1080 /// let mut map = HashMap::with_hasher(h);
1081 /// map.insert(1i, 2u);
1084 pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
1085 HashMap::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
1088 /// Create an empty HashMap with space for at least `capacity`
1089 /// elements, using `hasher` to hash the keys.
1091 /// Warning: `hasher` is normally randomly generated, and
1092 /// is designed to allow HashMaps to be resistant to attacks that
1093 /// cause many collisions and very poor performance. Setting it
1094 /// manually using this function can expose a DoS attack vector.
1099 /// use std::collections::HashMap;
1100 /// use std::hash::sip::SipHasher;
1102 /// let h = SipHasher::new();
1103 /// let mut map = HashMap::with_capacity_and_hasher(10, h);
1104 /// map.insert(1i, 2u);
1107 pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
1108 let cap = num::next_power_of_two(max(INITIAL_CAPACITY, capacity));
1111 resize_policy: DefaultResizePolicy::new(cap),
1112 table: table::RawTable::new(cap),
1116 /// The hashtable will never try to shrink below this size. You can use
1117 /// this function to reduce reallocations if your hashtable frequently
1118 /// grows and shrinks by large amounts.
1120 /// This function has no effect on the operational semantics of the
1121 /// hashtable, only on performance.
1124 /// use std::collections::HashMap;
1125 /// let mut map: HashMap<&str, int> = HashMap::new();
1126 /// map.reserve(10);
1128 pub fn reserve(&mut self, new_minimum_capacity: uint) {
1129 let cap = num::next_power_of_two(
1130 max(INITIAL_CAPACITY, new_minimum_capacity));
1132 self.resize_policy.reserve(cap);
1134 if self.table.capacity() < cap {
1139 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
1140 /// 1) Make sure the new capacity is enough for all the elements, accounting
1141 /// for the load factor.
1142 /// 2) Ensure new_capacity is a power of two.
1143 fn resize(&mut self, new_capacity: uint) {
1144 assert!(self.table.size() <= new_capacity);
1145 assert!(num::is_power_of_two(new_capacity));
1147 let old_table = replace(&mut self.table, table::RawTable::new(new_capacity));
1148 let old_size = old_table.size();
1150 for (h, k, v) in old_table.move_iter() {
1151 self.insert_hashed_nocheck(h, k, v);
1154 assert_eq!(self.table.size(), old_size);
1157 /// Performs any necessary resize operations, such that there's space for
1158 /// new_size elements.
1159 fn make_some_room(&mut self, new_size: uint) {
1160 let (grow_at, shrink_at) = self.resize_policy.capacity_range(new_size);
1161 let cap = self.table.capacity();
1163 // An invalid value shouldn't make us run out of space.
1164 debug_assert!(grow_at >= new_size);
1167 let new_capacity = cap << 1;
1168 self.resize(new_capacity);
1169 } else if shrink_at <= cap {
1170 let new_capacity = cap >> 1;
1171 self.resize(new_capacity);
1175 /// Perform robin hood bucket stealing at the given 'index'. You must
1176 /// also pass that probe's "distance to initial bucket" so we don't have
1177 /// to recalculate it, as well as the total number of probes already done
1178 /// so we have some sort of upper bound on the number of probes to do.
1180 /// 'hash', 'k', and 'v' are the elements to robin hood into the hashtable.
1181 fn robin_hood(&mut self, mut index: table::FullIndex, mut dib_param: uint,
1182 mut hash: table::SafeHash, mut k: K, mut v: V) {
1184 let (old_hash, old_key, old_val) = {
1185 let (old_hash_ref, old_key_ref, old_val_ref) =
1186 self.table.read_all_mut(&index);
1188 let old_hash = replace(old_hash_ref, hash);
1189 let old_key = replace(old_key_ref, k);
1190 let old_val = replace(old_val_ref, v);
1192 (old_hash, old_key, old_val)
1195 let mut probe = self.probe_next(index.raw_index());
1197 for dib in range(dib_param + 1, self.table.size()) {
1198 let full_index = match self.table.peek(probe) {
1199 table::Empty(idx) => {
1201 self.table.put(idx, old_hash, old_key, old_val);
1204 table::Full(idx) => idx
1207 let probe_dib = self.bucket_distance(&full_index);
1209 // Robin hood! Steal the spot.
1210 if probe_dib < dib {
1212 dib_param = probe_dib;
1219 probe = self.probe_next(probe);
1222 fail!("HashMap fatal error: 100% load factor?");
1226 /// Insert a pre-hashed key-value pair, without first checking
1227 /// that there's enough room in the buckets. Returns a reference to the
1228 /// newly insert value.
1230 /// If the key already exists, the hashtable will be returned untouched
1231 /// and a reference to the existing element will be returned.
1232 fn insert_hashed_nocheck<'a>(
1233 &'a mut self, hash: table::SafeHash, k: K, v: V) -> &'a mut V {
1235 for dib in range_inclusive(0u, self.table.size()) {
1236 let probe = self.probe(&hash, dib);
1238 let idx = match self.table.peek(probe) {
1239 table::Empty(idx) => {
1241 let fullidx = self.table.put(idx, hash, k, v);
1242 let (_, val) = self.table.read_mut(&fullidx);
1245 table::Full(idx) => idx
1248 if idx.hash() == hash {
1249 let (bucket_k, bucket_v) = self.table.read_mut(&idx);
1250 // FIXME #12147 the conditional return confuses
1251 // borrowck if we return bucket_v directly
1252 let bv: *mut V = bucket_v;
1254 // Key already exists. Get its reference.
1255 return unsafe {&mut *bv};
1259 let probe_dib = self.bucket_distance(&idx);
1261 if probe_dib < dib {
1262 // Found a luckier bucket than me. Better steal his spot.
1263 self.robin_hood(idx, probe_dib, hash, k, v);
1265 // Now that it's stolen, just read the value's pointer
1266 // right out of the table!
1267 match self.table.peek(probe) {
1268 table::Empty(_) => fail!("Just stole a spot, but now that spot's empty."),
1269 table::Full(idx) => {
1270 let (_, v) = self.table.read_mut(&idx);
1277 // We really shouldn't be here.
1278 fail!("Internal HashMap error: Out of space.");
1281 /// Inserts an element which has already been hashed, returning a reference
1282 /// to that element inside the hashtable. This is more efficient that using
1283 /// `insert`, since the key will not be rehashed.
1284 fn insert_hashed<'a>(&'a mut self, hash: table::SafeHash, k: K, v: V) -> &'a mut V {
1285 let potential_new_size = self.table.size() + 1;
1286 self.make_some_room(potential_new_size);
1287 self.insert_hashed_nocheck(hash, k, v)
1290 /// Return the value corresponding to the key in the map, or insert
1291 /// and return the value if it doesn't exist.
1296 /// use std::collections::HashMap;
1297 /// let mut map = HashMap::new();
1299 /// // Insert 1i with key "a"
1300 /// assert_eq!(*map.find_or_insert("a", 1i), 1);
1302 /// // Find the existing key
1303 /// assert_eq!(*map.find_or_insert("a", -2), 1);
1305 pub fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a mut V {
1306 self.find_with_or_insert_with(k, v, |_k, _v, _a| (), |_k, a| a)
1309 /// Return the value corresponding to the key in the map, or create,
1310 /// insert, and return a new value if it doesn't exist.
1315 /// use std::collections::HashMap;
1316 /// let mut map = HashMap::new();
1318 /// // Insert 10 with key 2
1319 /// assert_eq!(*map.find_or_insert_with(2i, |&key| 5 * key as uint), 10u);
1321 /// // Find the existing key
1322 /// assert_eq!(*map.find_or_insert_with(2, |&key| key as uint), 10);
1324 pub fn find_or_insert_with<'a>(&'a mut self, k: K, f: |&K| -> V)
1326 self.find_with_or_insert_with(k, (), |_k, _v, _a| (), |k, _a| f(k))
1329 /// Insert a key-value pair into the map if the key is not already present.
1330 /// Otherwise, modify the existing value for the key.
1331 /// Returns the new or modified value for the key.
1336 /// use std::collections::HashMap;
1337 /// let mut map = HashMap::new();
1339 /// // Insert 2 with key "a"
1340 /// assert_eq!(*map.insert_or_update_with("a", 2u, |_key, val| *val = 3), 2);
1342 /// // Update and return the existing value
1343 /// assert_eq!(*map.insert_or_update_with("a", 9, |_key, val| *val = 7), 7);
1344 /// assert_eq!(map.get(&"a"), &7);
1346 pub fn insert_or_update_with<'a>(
1352 self.find_with_or_insert_with(k, v, |k, v, _a| f(k, v), |_k, a| a)
1355 /// Modify and return the value corresponding to the key in the map, or
1356 /// insert and return a new value if it doesn't exist.
1358 /// This method allows for all insertion behaviours of a hashmap;
1359 /// see methods like
1360 /// [`insert`](../trait.MutableMap.html#tymethod.insert),
1361 /// [`find_or_insert`](#method.find_or_insert) and
1362 /// [`insert_or_update_with`](#method.insert_or_update_with)
1363 /// for less general and more friendly variations of this.
1368 /// use std::collections::HashMap;
1370 /// // map some strings to vectors of strings
1371 /// let mut map = HashMap::new();
1372 /// map.insert("a key", vec!["value"]);
1373 /// map.insert("z key", vec!["value"]);
1375 /// let new = vec!["a key", "b key", "z key"];
1377 /// for k in new.move_iter() {
1378 /// map.find_with_or_insert_with(
1380 /// // if the key does exist either prepend or append this
1381 /// // new value based on the first letter of the key.
1382 /// |key, already, new| {
1383 /// if key.as_slice().starts_with("z") {
1384 /// already.insert(0, new);
1386 /// already.push(new);
1389 /// // if the key doesn't exist in the map yet, add it in
1390 /// // the obvious way.
1391 /// |_k, v| vec![v]);
1394 /// assert_eq!(map.len(), 3);
1395 /// assert_eq!(map.get(&"a key"), &vec!["value", "new value"]);
1396 /// assert_eq!(map.get(&"b key"), &vec!["new value"]);
1397 /// assert_eq!(map.get(&"z key"), &vec!["new value", "value"]);
1399 pub fn find_with_or_insert_with<'a, A>(&'a mut self,
1402 found: |&K, &mut V, A|,
1403 not_found: |&K, A| -> V)
1405 let hash = self.make_hash(&k);
1406 match self.search_hashed(&hash, &k) {
1408 let v = not_found(&k, a);
1409 self.insert_hashed(hash, k, v)
1412 let (_, v_ref) = self.table.read_mut(&idx);
1413 found(&k, v_ref, a);
1419 /// Retrieves a value for the given key.
1420 /// See [`find`](../trait.Map.html#tymethod.find) for a non-failing alternative.
1424 /// Fails if the key is not present.
1429 /// use std::collections::HashMap;
1431 /// let mut map = HashMap::new();
1432 /// map.insert("a", 1i);
1433 /// assert_eq!(map.get(&"a"), &1);
1435 pub fn get<'a>(&'a self, k: &K) -> &'a V {
1436 match self.find(k) {
1438 None => fail!("no entry found for key")
1442 /// Retrieves a mutable value for the given key.
1443 /// See [`find_mut`](../trait.MutableMap.html#tymethod.find_mut) for a non-failing alternative.
1447 /// Fails if the key is not present.
1452 /// use std::collections::HashMap;
1454 /// let mut map = HashMap::new();
1455 /// map.insert("a", 1i);
1457 /// // val will freeze map to prevent usage during its lifetime
1458 /// let val = map.get_mut(&"a");
1461 /// assert_eq!(map.get(&"a"), &40);
1463 /// // A more direct way could be:
1464 /// *map.get_mut(&"a") = -2;
1465 /// assert_eq!(map.get(&"a"), &-2);
1467 pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V {
1468 match self.find_mut(k) {
1470 None => fail!("no entry found for key")
1474 /// Return true if the map contains a value for the specified key,
1475 /// using equivalence.
1477 /// See [pop_equiv](#method.pop_equiv) for an extended example.
1478 pub fn contains_key_equiv<Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
1479 self.search_equiv(key).is_some()
1482 /// Return the value corresponding to the key in the map, using
1485 /// See [pop_equiv](#method.pop_equiv) for an extended example.
1486 pub fn find_equiv<'a, Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
1487 match self.search_equiv(k) {
1490 let (_, v_ref) = self.table.read(&idx);
1496 /// Remove an equivalent key from the map, returning the value at the
1497 /// key if the key was previously in the map.
1501 /// This is a slightly silly example where we define the number's parity as
1502 /// the equivalence class. It is important that the values hash the same,
1503 /// which is why we override `Hash`.
1506 /// use std::collections::HashMap;
1507 /// use std::hash::Hash;
1508 /// use std::hash::sip::SipState;
1510 /// #[deriving(Eq, PartialEq)]
1511 /// struct EvenOrOdd {
1515 /// impl Hash for EvenOrOdd {
1516 /// fn hash(&self, state: &mut SipState) {
1517 /// let parity = self.num % 2;
1518 /// parity.hash(state);
1522 /// impl Equiv<EvenOrOdd> for EvenOrOdd {
1523 /// fn equiv(&self, other: &EvenOrOdd) -> bool {
1524 /// self.num % 2 == other.num % 2
1528 /// let mut map = HashMap::new();
1529 /// map.insert(EvenOrOdd { num: 3 }, "foo");
1531 /// assert!(map.contains_key_equiv(&EvenOrOdd { num: 1 }));
1532 /// assert!(!map.contains_key_equiv(&EvenOrOdd { num: 4 }));
1534 /// assert_eq!(map.find_equiv(&EvenOrOdd { num: 5 }), Some(&"foo"));
1535 /// assert_eq!(map.find_equiv(&EvenOrOdd { num: 2 }), None);
1537 /// assert_eq!(map.pop_equiv(&EvenOrOdd { num: 1 }), Some("foo"));
1538 /// assert_eq!(map.pop_equiv(&EvenOrOdd { num: 2 }), None);
1542 pub fn pop_equiv<Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
1543 if self.table.size() == 0 {
1547 let potential_new_size = self.table.size() - 1;
1548 self.make_some_room(potential_new_size);
1550 let starting_index = match self.search_equiv(k) {
1552 None => return None,
1555 self.pop_internal(starting_index)
1558 /// An iterator visiting all keys in arbitrary order.
1559 /// Iterator element type is `&'a K`.
1564 /// use std::collections::HashMap;
1566 /// let mut map = HashMap::new();
1567 /// map.insert("a", 1i);
1568 /// map.insert("b", 2);
1569 /// map.insert("c", 3);
1571 /// for key in map.keys() {
1572 /// println!("{}", key);
1575 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1576 self.iter().map(|(k, _v)| k)
1579 /// An iterator visiting all values in arbitrary order.
1580 /// Iterator element type is `&'a V`.
1585 /// use std::collections::HashMap;
1587 /// let mut map = HashMap::new();
1588 /// map.insert("a", 1i);
1589 /// map.insert("b", 2);
1590 /// map.insert("c", 3);
1592 /// for key in map.values() {
1593 /// println!("{}", key);
1596 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1597 self.iter().map(|(_k, v)| v)
1600 /// An iterator visiting all key-value pairs in arbitrary order.
1601 /// Iterator element type is `(&'a K, &'a V)`.
1606 /// use std::collections::HashMap;
1608 /// let mut map = HashMap::new();
1609 /// map.insert("a", 1i);
1610 /// map.insert("b", 2);
1611 /// map.insert("c", 3);
1613 /// for (key, val) in map.iter() {
1614 /// println!("key: {} val: {}", key, val);
1617 pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
1621 /// An iterator visiting all key-value pairs in arbitrary order,
1622 /// with mutable references to the values.
1623 /// Iterator element type is `(&'a K, &'a mut V)`.
1628 /// use std::collections::HashMap;
1630 /// let mut map = HashMap::new();
1631 /// map.insert("a", 1i);
1632 /// map.insert("b", 2);
1633 /// map.insert("c", 3);
1635 /// // Update all values
1636 /// for (_, val) in map.mut_iter() {
1640 /// for (key, val) in map.iter() {
1641 /// println!("key: {} val: {}", key, val);
1644 pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> {
1645 self.table.mut_iter()
1648 /// Creates a consuming iterator, that is, one that moves each key-value
1649 /// pair out of the map in arbitrary order. The map cannot be used after
1655 /// use std::collections::HashMap;
1657 /// let mut map = HashMap::new();
1658 /// map.insert("a", 1i);
1659 /// map.insert("b", 2);
1660 /// map.insert("c", 3);
1662 /// // Not possible with .iter()
1663 /// let vec: Vec<(&str, int)> = map.move_iter().collect();
1665 pub fn move_iter(self) -> MoveEntries<K, V> {
1666 self.table.move_iter().map(|(_, k, v)| (k, v))
1670 impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
1671 /// Return a copy of the value corresponding to the key.
1676 /// use std::collections::HashMap;
1678 /// let mut map: HashMap<uint, String> = HashMap::new();
1679 /// map.insert(1u, "foo".to_string());
1680 /// let s: String = map.find_copy(&1).unwrap();
1682 pub fn find_copy(&self, k: &K) -> Option<V> {
1683 self.find(k).map(|v| (*v).clone())
1686 /// Return a copy of the value corresponding to the key.
1690 /// Fails if the key is not present.
1695 /// use std::collections::HashMap;
1697 /// let mut map: HashMap<uint, String> = HashMap::new();
1698 /// map.insert(1u, "foo".to_string());
1699 /// let s: String = map.get_copy(&1);
1701 pub fn get_copy(&self, k: &K) -> V {
1702 (*self.get(k)).clone()
1706 impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
1707 fn eq(&self, other: &HashMap<K, V, H>) -> bool {
1708 if self.len() != other.len() { return false; }
1711 .all(|(key, value)| {
1712 match other.find(key) {
1714 Some(v) => *value == *v
1720 impl<K: Eq + Hash<S>, V: Eq, S, H: Hasher<S>> Eq for HashMap<K, V, H> {}
1722 impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
1723 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1724 try!(write!(f, "{{"));
1726 for (i, (k, v)) in self.iter().enumerate() {
1727 if i != 0 { try!(write!(f, ", ")); }
1728 try!(write!(f, "{}: {}", *k, *v));
1735 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
1736 fn default() -> HashMap<K, V, H> {
1737 HashMap::with_hasher(Default::default())
1741 /// HashMap iterator
1742 pub type Entries<'a, K, V> = table::Entries<'a, K, V>;
1744 /// HashMap mutable values iterator
1745 pub type MutEntries<'a, K, V> = table::MutEntries<'a, K, V>;
1747 /// HashMap move iterator
1748 pub type MoveEntries<K, V> =
1749 iter::Map<'static, (table::SafeHash, K, V), (K, V), table::MoveEntries<K, V>>;
1751 /// HashMap keys iterator
1752 pub type Keys<'a, K, V> =
1753 iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
1755 /// HashMap values iterator
1756 pub type Values<'a, K, V> =
1757 iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
1759 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
1760 fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
1761 let (lower, _) = iter.size_hint();
1762 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1768 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Extendable<(K, V)> for HashMap<K, V, H> {
1769 fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
1770 for (k, v) in iter {
1776 /// HashSet iterator
1777 pub type SetItems<'a, K> =
1778 iter::Map<'static, (&'a K, &'a ()), &'a K, Entries<'a, K, ()>>;
1780 /// HashSet move iterator
1781 pub type SetMoveItems<K> =
1782 iter::Map<'static, (K, ()), K, MoveEntries<K, ()>>;
1784 /// An implementation of a hash set using the underlying representation of a
1785 /// HashMap where the value is (). As with the `HashMap` type, a `HashSet`
1786 /// requires that the elements implement the `Eq` and `Hash` traits.
1791 /// use std::collections::HashSet;
1793 /// // Type inference lets us omit an explicit type signature (which
1794 /// // would be `HashSet<&str>` in this example).
1795 /// let mut books = HashSet::new();
1797 /// // Add some books.
1798 /// books.insert("A Dance With Dragons");
1799 /// books.insert("To Kill a Mockingbird");
1800 /// books.insert("The Odyssey");
1801 /// books.insert("The Great Gatsby");
1803 /// // Check for a specific one.
1804 /// if !books.contains(&("The Winds of Winter")) {
1805 /// println!("We have {} books, but The Winds of Winter ain't one.",
1809 /// // Remove a book.
1810 /// books.remove(&"The Odyssey");
1812 /// // Iterate over everything.
1813 /// for book in books.iter() {
1814 /// println!("{}", *book);
1818 /// The easiest way to use `HashSet` with a custom type is to derive
1819 /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the
1820 /// future be implied by `Eq`.
1823 /// use std::collections::HashSet;
1825 /// #[deriving(Hash, Eq, PartialEq, Show)]
1826 /// struct Viking<'a> {
1831 /// let mut vikings = HashSet::new();
1833 /// vikings.insert(Viking { name: "Einar", power: 9u });
1834 /// vikings.insert(Viking { name: "Einar", power: 9u });
1835 /// vikings.insert(Viking { name: "Olaf", power: 4u });
1836 /// vikings.insert(Viking { name: "Harald", power: 8u });
1838 /// // Use derived implementation to print the vikings.
1839 /// for x in vikings.iter() {
1840 /// println!("{}", x);
1844 pub struct HashSet<T, H = RandomSipHasher> {
1845 map: HashMap<T, (), H>
1848 impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
1849 /// Create an empty HashSet.
1853 /// use std::collections::HashSet;
1854 /// let mut set: HashSet<int> = HashSet::new();
1857 pub fn new() -> HashSet<T, RandomSipHasher> {
1858 HashSet::with_capacity(INITIAL_CAPACITY)
1861 /// Create an empty HashSet with space for at least `n` elements in
1866 /// use std::collections::HashSet;
1867 /// let mut set: HashSet<int> = HashSet::with_capacity(10);
1870 pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
1871 HashSet { map: HashMap::with_capacity(capacity) }
1875 impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
1876 /// Creates a new empty hash set which will use the given hasher to hash
1879 /// The hash set is also created with the default initial capacity.
1884 /// use std::collections::HashSet;
1885 /// use std::hash::sip::SipHasher;
1887 /// let h = SipHasher::new();
1888 /// let mut set = HashSet::with_hasher(h);
1892 pub fn with_hasher(hasher: H) -> HashSet<T, H> {
1893 HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
1896 /// Create an empty HashSet with space for at least `capacity`
1897 /// elements in the hash table, using `hasher` to hash the keys.
1899 /// Warning: `hasher` is normally randomly generated, and
1900 /// is designed to allow `HashSet`s to be resistant to attacks that
1901 /// cause many collisions and very poor performance. Setting it
1902 /// manually using this function can expose a DoS attack vector.
1907 /// use std::collections::HashSet;
1908 /// use std::hash::sip::SipHasher;
1910 /// let h = SipHasher::new();
1911 /// let mut set = HashSet::with_capacity_and_hasher(10u, h);
1915 pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashSet<T, H> {
1916 HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
1919 /// Reserve space for at least `n` elements in the hash table.
1923 /// use std::collections::HashSet;
1924 /// let mut set: HashSet<int> = HashSet::new();
1925 /// set.reserve(10);
1927 pub fn reserve(&mut self, n: uint) {
1931 /// Returns true if the hash set contains a value equivalent to the
1932 /// given query value.
1936 /// This is a slightly silly example where we define the number's
1937 /// parity as the equivilance class. It is important that the
1938 /// values hash the same, which is why we implement `Hash`.
1941 /// use std::collections::HashSet;
1942 /// use std::hash::Hash;
1943 /// use std::hash::sip::SipState;
1945 /// #[deriving(Eq, PartialEq)]
1946 /// struct EvenOrOdd {
1950 /// impl Hash for EvenOrOdd {
1951 /// fn hash(&self, state: &mut SipState) {
1952 /// let parity = self.num % 2;
1953 /// parity.hash(state);
1957 /// impl Equiv<EvenOrOdd> for EvenOrOdd {
1958 /// fn equiv(&self, other: &EvenOrOdd) -> bool {
1959 /// self.num % 2 == other.num % 2
1963 /// let mut set = HashSet::new();
1964 /// set.insert(EvenOrOdd { num: 3u });
1966 /// assert!(set.contains_equiv(&EvenOrOdd { num: 3u }));
1967 /// assert!(set.contains_equiv(&EvenOrOdd { num: 5u }));
1968 /// assert!(!set.contains_equiv(&EvenOrOdd { num: 4u }));
1969 /// assert!(!set.contains_equiv(&EvenOrOdd { num: 2u }));
1972 pub fn contains_equiv<Q: Hash<S> + Equiv<T>>(&self, value: &Q) -> bool {
1973 self.map.contains_key_equiv(value)
1976 /// An iterator visiting all elements in arbitrary order.
1977 /// Iterator element type is &'a T.
1982 /// use std::collections::HashSet;
1983 /// let mut set = HashSet::new();
1984 /// set.insert("a");
1985 /// set.insert("b");
1987 /// // Will print in an arbitrary order.
1988 /// for x in set.iter() {
1989 /// println!("{}", x);
1992 pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
1996 /// Creates a consuming iterator, that is, one that moves each value out
1997 /// of the set in arbitrary order. The set cannot be used after calling
2003 /// use std::collections::HashSet;
2004 /// let mut set = HashSet::new();
2005 /// set.insert("a".to_string());
2006 /// set.insert("b".to_string());
2008 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
2009 /// let v: Vec<String> = set.move_iter().collect();
2011 /// // Will print in an arbitrary order.
2012 /// for x in v.iter() {
2013 /// println!("{}", x);
2016 pub fn move_iter(self) -> SetMoveItems<T> {
2017 self.map.move_iter().map(|(k, _)| k)
2020 /// Visit the values representing the difference.
2025 /// use std::collections::HashSet;
2026 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
2027 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
2029 /// // Can be seen as `a - b`.
2030 /// for x in a.difference(&b) {
2031 /// println!("{}", x); // Print 1
2034 /// let diff: HashSet<int> = a.difference(&b).map(|&x| x).collect();
2035 /// assert_eq!(diff, [1i].iter().map(|&x| x).collect());
2037 /// // Note that difference is not symmetric,
2038 /// // and `b - a` means something else:
2039 /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect();
2040 /// assert_eq!(diff, [4i].iter().map(|&x| x).collect());
2042 pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> SetAlgebraItems<'a, T, H> {
2043 Repeat::new(other).zip(self.iter())
2044 .filter_map(|(other, elt)| {
2045 if !other.contains(elt) { Some(elt) } else { None }
2049 /// Visit the values representing the symmetric difference.
2054 /// use std::collections::HashSet;
2055 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
2056 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
2058 /// // Print 1, 4 in arbitrary order.
2059 /// for x in a.symmetric_difference(&b) {
2060 /// println!("{}", x);
2063 /// let diff1: HashSet<int> = a.symmetric_difference(&b).map(|&x| x).collect();
2064 /// let diff2: HashSet<int> = b.symmetric_difference(&a).map(|&x| x).collect();
2066 /// assert_eq!(diff1, diff2);
2067 /// assert_eq!(diff1, [1i, 4].iter().map(|&x| x).collect());
2069 pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
2070 -> Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>> {
2071 self.difference(other).chain(other.difference(self))
2074 /// Visit the values representing the intersection.
2079 /// use std::collections::HashSet;
2080 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
2081 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
2083 /// // Print 2, 3 in arbitrary order.
2084 /// for x in a.intersection(&b) {
2085 /// println!("{}", x);
2088 /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect();
2089 /// assert_eq!(diff, [2i, 3].iter().map(|&x| x).collect());
2091 pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>)
2092 -> SetAlgebraItems<'a, T, H> {
2093 Repeat::new(other).zip(self.iter())
2094 .filter_map(|(other, elt)| {
2095 if other.contains(elt) { Some(elt) } else { None }
2099 /// Visit the values representing the union.
2104 /// use std::collections::HashSet;
2105 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
2106 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
2108 /// // Print 1, 2, 3, 4 in arbitrary order.
2109 /// for x in a.union(&b) {
2110 /// println!("{}", x);
2113 /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect();
2114 /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
2116 pub fn union<'a>(&'a self, other: &'a HashSet<T, H>)
2117 -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> {
2118 self.iter().chain(other.difference(self))
2122 impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
2123 fn eq(&self, other: &HashSet<T, H>) -> bool {
2124 if self.len() != other.len() { return false; }
2126 self.iter().all(|key| other.contains(key))
2130 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
2132 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Collection for HashSet<T, H> {
2133 fn len(&self) -> uint { self.map.len() }
2136 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> {
2137 fn clear(&mut self) { self.map.clear() }
2140 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> {
2141 fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
2143 fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
2144 self.iter().all(|v| !other.contains(v))
2147 fn is_subset(&self, other: &HashSet<T, H>) -> bool {
2148 self.iter().all(|v| other.contains(v))
2152 impl<T: Eq + Hash<S>, S, H: Hasher<S>> MutableSet<T> for HashSet<T, H> {
2153 fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
2155 fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
2159 impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
2160 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2161 try!(write!(f, "{{"));
2163 for (i, x) in self.iter().enumerate() {
2164 if i != 0 { try!(write!(f, ", ")); }
2165 try!(write!(f, "{}", *x));
2172 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
2173 fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
2174 let (lower, _) = iter.size_hint();
2175 let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
2181 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extendable<T> for HashSet<T, H> {
2182 fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
2189 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
2190 fn default() -> HashSet<T, H> {
2191 HashSet::with_hasher(Default::default())
2195 // `Repeat` is used to feed the filter closure an explicit capture
2196 // of a reference to the other set
2197 /// Set operations iterator
2198 pub type SetAlgebraItems<'a, T, H> =
2199 FilterMap<'static, (&'a HashSet<T, H>, &'a T), &'a T,
2200 Zip<Repeat<&'a HashSet<T, H>>, SetItems<'a, T>>>;
2209 use iter::{Iterator,range_inclusive,range_step_inclusive};
2212 struct KindaIntLike(int);
2214 impl Equiv<int> for KindaIntLike {
2215 fn equiv(&self, other: &int) -> bool {
2216 let KindaIntLike(this) = *self;
2220 impl<S: hash::Writer> hash::Hash<S> for KindaIntLike {
2221 fn hash(&self, state: &mut S) {
2222 let KindaIntLike(this) = *self;
2228 fn test_create_capacity_zero() {
2229 let mut m = HashMap::with_capacity(0);
2231 assert!(m.insert(1i, 1i));
2233 assert!(m.contains_key(&1));
2234 assert!(!m.contains_key(&0));
2239 let mut m = HashMap::new();
2240 assert_eq!(m.len(), 0);
2241 assert!(m.insert(1i, 2i));
2242 assert_eq!(m.len(), 1);
2243 assert!(m.insert(2i, 4i));
2244 assert_eq!(m.len(), 2);
2245 assert_eq!(*m.find(&1).unwrap(), 2);
2246 assert_eq!(*m.find(&2).unwrap(), 4);
2249 local_data_key!(drop_vector: RefCell<Vec<int>>)
2251 #[deriving(Hash, PartialEq, Eq)]
2258 fn new(k: uint) -> Dropable {
2259 let v = drop_vector.get().unwrap();
2260 v.borrow_mut().as_mut_slice()[k] += 1;
2266 impl Drop for Dropable {
2267 fn drop(&mut self) {
2268 let v = drop_vector.get().unwrap();
2269 v.borrow_mut().as_mut_slice()[self.k] -= 1;
2275 drop_vector.replace(Some(RefCell::new(Vec::from_elem(200, 0i))));
2278 let mut m = HashMap::new();
2280 let v = drop_vector.get().unwrap();
2281 for i in range(0u, 200) {
2282 assert_eq!(v.borrow().as_slice()[i], 0);
2286 for i in range(0u, 100) {
2287 let d1 = Dropable::new(i);
2288 let d2 = Dropable::new(i+100);
2292 let v = drop_vector.get().unwrap();
2293 for i in range(0u, 200) {
2294 assert_eq!(v.borrow().as_slice()[i], 1);
2298 for i in range(0u, 50) {
2299 let k = Dropable::new(i);
2302 assert!(v.is_some());
2304 let v = drop_vector.get().unwrap();
2305 assert_eq!(v.borrow().as_slice()[i], 1);
2306 assert_eq!(v.borrow().as_slice()[i+100], 1);
2309 let v = drop_vector.get().unwrap();
2310 for i in range(0u, 50) {
2311 assert_eq!(v.borrow().as_slice()[i], 0);
2312 assert_eq!(v.borrow().as_slice()[i+100], 0);
2315 for i in range(50u, 100) {
2316 assert_eq!(v.borrow().as_slice()[i], 1);
2317 assert_eq!(v.borrow().as_slice()[i+100], 1);
2321 let v = drop_vector.get().unwrap();
2322 for i in range(0u, 200) {
2323 assert_eq!(v.borrow().as_slice()[i], 0);
2328 fn test_empty_pop() {
2329 let mut m: HashMap<int, bool> = HashMap::new();
2330 assert_eq!(m.pop(&0), None);
2334 fn test_lots_of_insertions() {
2335 let mut m = HashMap::new();
2337 // Try this a few times to make sure we never screw up the hashmap's
2339 for _ in range(0i, 10) {
2340 assert!(m.is_empty());
2342 for i in range_inclusive(1i, 1000) {
2343 assert!(m.insert(i, i));
2345 for j in range_inclusive(1, i) {
2347 assert_eq!(r, Some(&j));
2350 for j in range_inclusive(i+1, 1000) {
2352 assert_eq!(r, None);
2356 for i in range_inclusive(1001i, 2000) {
2357 assert!(!m.contains_key(&i));
2361 for i in range_inclusive(1i, 1000) {
2362 assert!(m.remove(&i));
2364 for j in range_inclusive(1, i) {
2365 assert!(!m.contains_key(&j));
2368 for j in range_inclusive(i+1, 1000) {
2369 assert!(m.contains_key(&j));
2373 for i in range_inclusive(1i, 1000) {
2374 assert!(!m.contains_key(&i));
2377 for i in range_inclusive(1i, 1000) {
2378 assert!(m.insert(i, i));
2382 for i in range_step_inclusive(1000i, 1, -1) {
2383 assert!(m.remove(&i));
2385 for j in range_inclusive(i, 1000) {
2386 assert!(!m.contains_key(&j));
2389 for j in range_inclusive(1, i-1) {
2390 assert!(m.contains_key(&j));
2397 fn test_find_mut() {
2398 let mut m = HashMap::new();
2399 assert!(m.insert(1i, 12i));
2400 assert!(m.insert(2i, 8i));
2401 assert!(m.insert(5i, 14i));
2403 match m.find_mut(&5) {
2404 None => fail!(), Some(x) => *x = new
2406 assert_eq!(m.find(&5), Some(&new));
2410 fn test_insert_overwrite() {
2411 let mut m = HashMap::new();
2412 assert!(m.insert(1i, 2i));
2413 assert_eq!(*m.find(&1).unwrap(), 2);
2414 assert!(!m.insert(1i, 3i));
2415 assert_eq!(*m.find(&1).unwrap(), 3);
2419 fn test_insert_conflicts() {
2420 let mut m = HashMap::with_capacity(4);
2421 assert!(m.insert(1i, 2i));
2422 assert!(m.insert(5i, 3i));
2423 assert!(m.insert(9i, 4i));
2424 assert_eq!(*m.find(&9).unwrap(), 4);
2425 assert_eq!(*m.find(&5).unwrap(), 3);
2426 assert_eq!(*m.find(&1).unwrap(), 2);
2430 fn test_conflict_remove() {
2431 let mut m = HashMap::with_capacity(4);
2432 assert!(m.insert(1i, 2i));
2433 assert_eq!(*m.find(&1).unwrap(), 2);
2434 assert!(m.insert(5, 3));
2435 assert_eq!(*m.find(&1).unwrap(), 2);
2436 assert_eq!(*m.find(&5).unwrap(), 3);
2437 assert!(m.insert(9, 4));
2438 assert_eq!(*m.find(&1).unwrap(), 2);
2439 assert_eq!(*m.find(&5).unwrap(), 3);
2440 assert_eq!(*m.find(&9).unwrap(), 4);
2441 assert!(m.remove(&1));
2442 assert_eq!(*m.find(&9).unwrap(), 4);
2443 assert_eq!(*m.find(&5).unwrap(), 3);
2447 fn test_is_empty() {
2448 let mut m = HashMap::with_capacity(4);
2449 assert!(m.insert(1i, 2i));
2450 assert!(!m.is_empty());
2451 assert!(m.remove(&1));
2452 assert!(m.is_empty());
2457 let mut m = HashMap::new();
2459 assert_eq!(m.pop(&1), Some(2));
2460 assert_eq!(m.pop(&1), None);
2464 #[allow(experimental)]
2465 fn test_pop_equiv() {
2466 let mut m = HashMap::new();
2468 assert_eq!(m.pop_equiv(&KindaIntLike(1)), Some(2));
2469 assert_eq!(m.pop_equiv(&KindaIntLike(1)), None);
2474 let mut m = HashMap::new();
2475 assert_eq!(m.swap(1i, 2i), None);
2476 assert_eq!(m.swap(1i, 3i), Some(2));
2477 assert_eq!(m.swap(1i, 4i), Some(3));
2481 fn test_move_iter() {
2483 let mut hm = HashMap::new();
2491 let v = hm.move_iter().collect::<Vec<(char, int)>>();
2492 assert!([('a', 1), ('b', 2)] == v.as_slice() || [('b', 2), ('a', 1)] == v.as_slice());
2497 let mut m = HashMap::with_capacity(4);
2498 for i in range(0u, 32) {
2499 assert!(m.insert(i, i*2));
2501 assert_eq!(m.len(), 32);
2503 let mut observed: u32 = 0;
2505 for (k, v) in m.iter() {
2506 assert_eq!(*v, *k * 2);
2507 observed |= 1 << *k;
2509 assert_eq!(observed, 0xFFFF_FFFF);
2514 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
2515 let map = vec.move_iter().collect::<HashMap<int, char>>();
2516 let keys = map.keys().map(|&k| k).collect::<Vec<int>>();
2517 assert_eq!(keys.len(), 3);
2518 assert!(keys.contains(&1));
2519 assert!(keys.contains(&2));
2520 assert!(keys.contains(&3));
2525 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
2526 let map = vec.move_iter().collect::<HashMap<int, char>>();
2527 let values = map.values().map(|&v| v).collect::<Vec<char>>();
2528 assert_eq!(values.len(), 3);
2529 assert!(values.contains(&'a'));
2530 assert!(values.contains(&'b'));
2531 assert!(values.contains(&'c'));
2536 let mut m = HashMap::new();
2537 assert!(m.find(&1i).is_none());
2541 Some(v) => assert_eq!(*v, 2)
2547 let mut m1 = HashMap::new();
2552 let mut m2 = HashMap::new();
2565 let mut map: HashMap<int, int> = HashMap::new();
2566 let empty: HashMap<int, int> = HashMap::new();
2571 let map_str = format!("{}", map);
2573 assert!(map_str == "{1: 2, 3: 4}".to_string() || map_str == "{3: 4, 1: 2}".to_string());
2574 assert_eq!(format!("{}", empty), "{}".to_string());
2579 let mut m = HashMap::new();
2581 assert_eq!(m.len(), 0);
2582 assert!(m.is_empty());
2585 let old_cap = m.table.capacity();
2586 while old_cap == m.table.capacity() {
2591 assert_eq!(m.len(), i);
2592 assert!(!m.is_empty());
2596 fn test_resize_policy() {
2597 let mut m = HashMap::new();
2599 assert_eq!(m.len(), 0);
2600 assert!(m.is_empty());
2602 let initial_cap = m.table.capacity();
2603 m.reserve(initial_cap * 2);
2604 let cap = m.table.capacity();
2606 assert_eq!(cap, initial_cap * 2);
2609 for _ in range(0, cap * 3 / 4) {
2614 assert_eq!(m.len(), i);
2615 assert_eq!(m.table.capacity(), cap);
2617 for _ in range(0, cap / 4) {
2622 let new_cap = m.table.capacity();
2623 assert_eq!(new_cap, cap * 2);
2625 for _ in range(0, cap / 2) {
2628 assert_eq!(m.table.capacity(), new_cap);
2631 for _ in range(0, cap / 2 - 1) {
2636 assert_eq!(m.table.capacity(), cap);
2637 assert_eq!(m.len(), i);
2638 assert!(!m.is_empty());
2642 fn test_find_equiv() {
2643 let mut m = HashMap::new();
2645 let (foo, bar, baz) = (1i,2i,3i);
2646 m.insert("foo".to_string(), foo);
2647 m.insert("bar".to_string(), bar);
2648 m.insert("baz".to_string(), baz);
2651 assert_eq!(m.find_equiv(&("foo")), Some(&foo));
2652 assert_eq!(m.find_equiv(&("bar")), Some(&bar));
2653 assert_eq!(m.find_equiv(&("baz")), Some(&baz));
2655 assert_eq!(m.find_equiv(&("qux")), None);
2659 fn test_from_iter() {
2660 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2662 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2664 for &(k, v) in xs.iter() {
2665 assert_eq!(map.find(&k), Some(&v));
2670 fn test_size_hint() {
2671 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2673 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2675 let mut iter = map.iter();
2677 for _ in iter.by_ref().take(3) {}
2679 assert_eq!(iter.size_hint(), (3, Some(3)));
2683 fn test_mut_size_hint() {
2684 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2686 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2688 let mut iter = map.mut_iter();
2690 for _ in iter.by_ref().take(3) {}
2692 assert_eq!(iter.size_hint(), (3, Some(3)));
2701 use slice::ImmutableEqVector;
2702 use collections::Collection;
2705 fn test_disjoint() {
2706 let mut xs = HashSet::new();
2707 let mut ys = HashSet::new();
2708 assert!(xs.is_disjoint(&ys));
2709 assert!(ys.is_disjoint(&xs));
2710 assert!(xs.insert(5i));
2711 assert!(ys.insert(11i));
2712 assert!(xs.is_disjoint(&ys));
2713 assert!(ys.is_disjoint(&xs));
2714 assert!(xs.insert(7));
2715 assert!(xs.insert(19));
2716 assert!(xs.insert(4));
2717 assert!(ys.insert(2));
2718 assert!(ys.insert(-11));
2719 assert!(xs.is_disjoint(&ys));
2720 assert!(ys.is_disjoint(&xs));
2721 assert!(ys.insert(7));
2722 assert!(!xs.is_disjoint(&ys));
2723 assert!(!ys.is_disjoint(&xs));
2727 fn test_subset_and_superset() {
2728 let mut a = HashSet::new();
2729 assert!(a.insert(0i));
2730 assert!(a.insert(5));
2731 assert!(a.insert(11));
2732 assert!(a.insert(7));
2734 let mut b = HashSet::new();
2735 assert!(b.insert(0i));
2736 assert!(b.insert(7));
2737 assert!(b.insert(19));
2738 assert!(b.insert(250));
2739 assert!(b.insert(11));
2740 assert!(b.insert(200));
2742 assert!(!a.is_subset(&b));
2743 assert!(!a.is_superset(&b));
2744 assert!(!b.is_subset(&a));
2745 assert!(!b.is_superset(&a));
2747 assert!(b.insert(5));
2749 assert!(a.is_subset(&b));
2750 assert!(!a.is_superset(&b));
2751 assert!(!b.is_subset(&a));
2752 assert!(b.is_superset(&a));
2757 let mut a = HashSet::new();
2758 for i in range(0u, 32) {
2759 assert!(a.insert(i));
2761 let mut observed: u32 = 0;
2763 observed |= 1 << *k;
2765 assert_eq!(observed, 0xFFFF_FFFF);
2769 fn test_intersection() {
2770 let mut a = HashSet::new();
2771 let mut b = HashSet::new();
2773 assert!(a.insert(11i));
2774 assert!(a.insert(1));
2775 assert!(a.insert(3));
2776 assert!(a.insert(77));
2777 assert!(a.insert(103));
2778 assert!(a.insert(5));
2779 assert!(a.insert(-5));
2781 assert!(b.insert(2i));
2782 assert!(b.insert(11));
2783 assert!(b.insert(77));
2784 assert!(b.insert(-9));
2785 assert!(b.insert(-42));
2786 assert!(b.insert(5));
2787 assert!(b.insert(3));
2790 let expected = [3, 5, 11, 77];
2791 for x in a.intersection(&b) {
2792 assert!(expected.contains(x));
2795 assert_eq!(i, expected.len());
2799 fn test_difference() {
2800 let mut a = HashSet::new();
2801 let mut b = HashSet::new();
2803 assert!(a.insert(1i));
2804 assert!(a.insert(3));
2805 assert!(a.insert(5));
2806 assert!(a.insert(9));
2807 assert!(a.insert(11));
2809 assert!(b.insert(3i));
2810 assert!(b.insert(9));
2813 let expected = [1, 5, 11];
2814 for x in a.difference(&b) {
2815 assert!(expected.contains(x));
2818 assert_eq!(i, expected.len());
2822 fn test_symmetric_difference() {
2823 let mut a = HashSet::new();
2824 let mut b = HashSet::new();
2826 assert!(a.insert(1i));
2827 assert!(a.insert(3));
2828 assert!(a.insert(5));
2829 assert!(a.insert(9));
2830 assert!(a.insert(11));
2832 assert!(b.insert(-2i));
2833 assert!(b.insert(3));
2834 assert!(b.insert(9));
2835 assert!(b.insert(14));
2836 assert!(b.insert(22));
2839 let expected = [-2, 1, 5, 11, 14, 22];
2840 for x in a.symmetric_difference(&b) {
2841 assert!(expected.contains(x));
2844 assert_eq!(i, expected.len());
2849 let mut a = HashSet::new();
2850 let mut b = HashSet::new();
2852 assert!(a.insert(1i));
2853 assert!(a.insert(3));
2854 assert!(a.insert(5));
2855 assert!(a.insert(9));
2856 assert!(a.insert(11));
2857 assert!(a.insert(16));
2858 assert!(a.insert(19));
2859 assert!(a.insert(24));
2861 assert!(b.insert(-2i));
2862 assert!(b.insert(1));
2863 assert!(b.insert(5));
2864 assert!(b.insert(9));
2865 assert!(b.insert(13));
2866 assert!(b.insert(19));
2869 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
2870 for x in a.union(&b) {
2871 assert!(expected.contains(x));
2874 assert_eq!(i, expected.len());
2878 fn test_from_iter() {
2879 let xs = [1i, 2, 3, 4, 5, 6, 7, 8, 9];
2881 let set: HashSet<int> = xs.iter().map(|&x| x).collect();
2883 for x in xs.iter() {
2884 assert!(set.contains(x));
2889 fn test_move_iter() {
2891 let mut hs = HashSet::new();
2899 let v = hs.move_iter().collect::<Vec<char>>();
2900 assert!(['a', 'b'] == v.as_slice() || ['b', 'a'] == v.as_slice());
2905 // These constants once happened to expose a bug in insert().
2906 // I'm keeping them around to prevent a regression.
2907 let mut s1 = HashSet::new();
2913 let mut s2 = HashSet::new();
2927 let mut set: HashSet<int> = HashSet::new();
2928 let empty: HashSet<int> = HashSet::new();
2933 let set_str = format!("{}", set);
2935 assert!(set_str == "{1, 2}".to_string() || set_str == "{2, 1}".to_string());
2936 assert_eq!(format!("{}", empty), "{}".to_string());
2945 use self::test::Bencher;
2946 use iter::{range_inclusive};
2949 fn new_drop(b : &mut Bencher) {
2953 let m : HashMap<int, int> = HashMap::new();
2954 assert_eq!(m.len(), 0);
2959 fn new_insert_drop(b : &mut Bencher) {
2963 let mut m = HashMap::new();
2965 assert_eq!(m.len(), 1);
2970 fn insert(b: &mut Bencher) {
2973 let mut m = HashMap::new();
2975 for i in range_inclusive(1i, 1000) {
2988 fn find_existing(b: &mut Bencher) {
2991 let mut m = HashMap::new();
2993 for i in range_inclusive(1i, 1000) {
2998 for i in range_inclusive(1i, 1000) {
3005 fn find_nonexisting(b: &mut Bencher) {
3008 let mut m = HashMap::new();
3010 for i in range_inclusive(1i, 1000) {
3015 for i in range_inclusive(1001i, 2000) {
3022 fn hashmap_as_queue(b: &mut Bencher) {
3025 let mut m = HashMap::new();
3027 for i in range_inclusive(1i, 1000) {
3035 m.insert(k + 1000, k + 1000);
3041 fn find_pop_insert(b: &mut Bencher) {
3044 let mut m = HashMap::new();
3046 for i in range_inclusive(1i, 1000) {
3054 m.find(&(k + 2000));
3056 m.insert(k + 1000, k + 1000);