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 //! Unordered containers, implemented as hash-tables (`HashSet` and `HashMap` types)
14 use cmp::{max, Eq, Equiv, PartialEq};
15 use collections::{Collection, Mutable, Set, MutableSet, Map, MutableMap};
19 use hash::{Hash, Hasher, RandomSipHasher};
20 use iter::{Iterator, FilterMap, Chain, Repeat, Zip, Extendable};
21 use iter::{range, range_inclusive, FromIterator};
25 use option::{Some, None, Option};
26 use result::{Ok, Err};
31 use hash::{Hash, Hasher};
32 use iter::range_step_inclusive;
33 use iter::{Iterator, range};
35 use mem::{min_align_of, size_of};
36 use mem::{overwrite, transmute};
37 use num::{CheckedMul, is_power_of_two};
39 use option::{Some, None, Option};
43 use rt::heap::{allocate, deallocate};
45 static EMPTY_BUCKET: u64 = 0u64;
47 /// The raw hashtable, providing safe-ish access to the unzipped and highly
48 /// optimized arrays of hashes, keys, and values.
50 /// This design uses less memory and is a lot faster than the naive
51 /// `Vec<Option<u64, K, V>>`, because we don't pay for the overhead of an
52 /// option on every element, and we get a generally more cache-aware design.
54 /// Key invariants of this structure:
56 /// - if hashes[i] == EMPTY_BUCKET, then keys[i] and vals[i] have
57 /// 'undefined' contents. Don't read from them. This invariant is
58 /// enforced outside this module with the `EmptyIndex`, `FullIndex`,
59 /// and `SafeHash` types.
61 /// - An `EmptyIndex` is only constructed for a bucket at an index with
62 /// a hash of EMPTY_BUCKET.
64 /// - A `FullIndex` is only constructed for a bucket at an index with a
65 /// non-EMPTY_BUCKET hash.
67 /// - A `SafeHash` is only constructed for non-`EMPTY_BUCKET` hash. We get
68 /// around hashes of zero by changing them to 0x8000_0000_0000_0000,
69 /// which will likely map to the same bucket, while not being confused
72 /// - All three "arrays represented by pointers" are the same length:
73 /// `capacity`. This is set at creation and never changes. The arrays
74 /// are unzipped to save space (we don't have to pay for the padding
75 /// between odd sized elements, such as in a map from u64 to u8), and
76 /// be more cache aware (scanning through 8 hashes brings in 2 cache
77 /// lines, since they're all right beside each other).
79 /// You can kind of think of this module/data structure as a safe wrapper
80 /// around just the "table" part of the hashtable. It enforces some
81 /// invariants at the type level and employs some performance trickery,
82 /// but in general is just a tricked out `Vec<Option<u64, K, V>>`.
86 /// Feb 11, 2014: This hashtable was just implemented, and, hard as I tried,
87 /// isn't yet totally safe. There's a "known exploit" that you can create
88 /// multiple FullIndexes for a bucket, `take` one, and then still `take`
89 /// the other causing undefined behavior. Currently, there's no story
90 /// for how to protect against this statically. Therefore, there are asserts
91 /// on `take`, `get`, `get_mut`, and `put` which check the bucket state.
92 /// With time, and when we're confident this works correctly, they should
93 /// be removed. Also, the bounds check in `peek` is especially painful,
94 /// as that's called in the innermost loops of the hashtable and has the
95 /// potential to be a major performance drain. Remove this too.
97 /// Or, better than remove, only enable these checks for debug builds.
98 /// There's currently no "debug-only" asserts in rust, so if you're reading
99 /// this and going "what? of course there are debug-only asserts!", then
100 /// please make this use them!
101 #[unsafe_no_drop_flag]
102 pub struct RawTable<K, V> {
110 /// Represents an index into a `RawTable` with no key or value in it.
111 pub struct EmptyIndex {
113 nocopy: marker::NoCopy,
116 /// Represents an index into a `RawTable` with a key, value, and hash
118 pub struct FullIndex {
121 nocopy: marker::NoCopy,
125 /// Since we get the hash for free whenever we check the bucket state,
126 /// this function is provided for fast access, letting us avoid
127 /// redundant trips back to the hashtable.
129 pub fn hash(&self) -> SafeHash { self.hash }
131 /// Same comment as with `hash`.
133 pub fn raw_index(&self) -> uint { self.idx as uint }
136 /// Represents the state of a bucket: it can either have a key/value
137 /// pair (be full) or not (be empty). You cannot `take` empty buckets,
138 /// and you cannot `put` into full buckets.
139 pub enum BucketState {
144 /// A hash that is not zero, since we use a hash of zero to represent empty
146 #[deriving(PartialEq)]
147 pub struct SafeHash {
152 /// Peek at the hash value, which is guaranteed to be non-zero.
154 pub fn inspect(&self) -> u64 { self.hash }
157 /// We need to remove hashes of 0. That's reserved for empty buckets.
158 /// This function wraps up `hash_keyed` to be the only way outside this
159 /// module to generate a SafeHash.
160 pub fn make_hash<T: Hash<S>, S, H: Hasher<S>>(hasher: &H, t: &T) -> SafeHash {
161 match hasher.hash(t) {
162 // This constant is exceedingly likely to hash to the same
163 // bucket, but it won't be counted as empty!
164 EMPTY_BUCKET => SafeHash { hash: 0x8000_0000_0000_0000 },
165 h => SafeHash { hash: h },
169 fn round_up_to_next(unrounded: uint, target_alignment: uint) -> uint {
170 assert!(is_power_of_two(target_alignment));
171 (unrounded + target_alignment - 1) & !(target_alignment - 1)
176 assert_eq!(round_up_to_next(0, 4), 0);
177 assert_eq!(round_up_to_next(1, 4), 4);
178 assert_eq!(round_up_to_next(2, 4), 4);
179 assert_eq!(round_up_to_next(3, 4), 4);
180 assert_eq!(round_up_to_next(4, 4), 4);
181 assert_eq!(round_up_to_next(5, 4), 8);
184 // Returns a tuple of (minimum required malloc alignment, hash_offset,
185 // key_offset, val_offset, array_size), from the start of a mallocated array.
186 fn calculate_offsets(
187 hash_size: uint, hash_align: uint,
188 keys_size: uint, keys_align: uint,
189 vals_size: uint, vals_align: uint) -> (uint, uint, uint, uint, uint) {
192 let end_of_hashes = hash_offset + hash_size;
194 let keys_offset = round_up_to_next(end_of_hashes, keys_align);
195 let end_of_keys = keys_offset + keys_size;
197 let vals_offset = round_up_to_next(end_of_keys, vals_align);
198 let end_of_vals = vals_offset + vals_size;
200 let min_align = cmp::max(hash_align, cmp::max(keys_align, vals_align));
202 (min_align, hash_offset, keys_offset, vals_offset, end_of_vals)
206 fn test_offset_calculation() {
207 assert_eq!(calculate_offsets(128, 8, 15, 1, 4, 4 ), (8, 0, 128, 144, 148));
208 assert_eq!(calculate_offsets(3, 1, 2, 1, 1, 1 ), (1, 0, 3, 5, 6));
209 assert_eq!(calculate_offsets(6, 2, 12, 4, 24, 8), (8, 0, 8, 24, 48));
212 impl<K, V> RawTable<K, V> {
214 /// Does not initialize the buckets. The caller should ensure they,
215 /// at the very least, set every hash to EMPTY_BUCKET.
216 unsafe fn new_uninitialized(capacity: uint) -> RawTable<K, V> {
217 let hashes_size = capacity.checked_mul(&size_of::<u64>())
218 .expect("capacity overflow");
219 let keys_size = capacity.checked_mul(&size_of::< K >())
220 .expect("capacity overflow");
221 let vals_size = capacity.checked_mul(&size_of::< V >())
222 .expect("capacity overflow");
224 // Allocating hashmaps is a little tricky. We need to allocate three
225 // arrays, but since we know their sizes and alignments up front,
226 // we just allocate a single array, and then have the subarrays
229 // This is great in theory, but in practice getting the alignment
230 // right is a little subtle. Therefore, calculating offsets has been
231 // factored out into a different function.
232 let (malloc_alignment, hash_offset, keys_offset, vals_offset, size) =
234 hashes_size, min_align_of::<u64>(),
235 keys_size, min_align_of::< K >(),
236 vals_size, min_align_of::< V >());
238 let buffer = allocate(size, malloc_alignment);
240 let hashes = buffer.offset(hash_offset as int) as *mut u64;
241 let keys = buffer.offset(keys_offset as int) as *mut K;
242 let vals = buffer.offset(vals_offset as int) as *mut V;
253 /// Creates a new raw table from a given capacity. All buckets are
255 #[allow(experimental)]
256 pub fn new(capacity: uint) -> RawTable<K, V> {
258 let ret = RawTable::new_uninitialized(capacity);
259 set_memory(ret.hashes, 0u8, capacity);
264 /// Reads a bucket at a given index, returning an enum indicating whether
265 /// there's anything there or not. You need to match on this enum to get
266 /// the appropriate types to pass on to most of the other functions in
268 pub fn peek(&self, index: uint) -> BucketState {
269 debug_assert!(index < self.capacity);
271 let idx = index as int;
272 let hash = unsafe { *self.hashes.offset(idx) };
274 let nocopy = marker::NoCopy;
285 hash: SafeHash { hash: full_hash },
291 /// Gets references to the key and value at a given index.
292 pub fn read<'a>(&'a self, index: &FullIndex) -> (&'a K, &'a V) {
296 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
297 (&*self.keys.offset(idx), &*self.vals.offset(idx))
301 /// Gets references to the key and value at a given index, with the
302 /// value's reference being mutable.
303 pub fn read_mut<'a>(&'a mut self, index: &FullIndex) -> (&'a K, &'a mut V) {
307 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
308 (&*self.keys.offset(idx), &mut *self.vals.offset(idx))
312 /// Read everything, mutably.
313 pub fn read_all_mut<'a>(&'a mut self, index: &FullIndex)
314 -> (&'a mut SafeHash, &'a mut K, &'a mut V) {
318 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
319 (transmute(self.hashes.offset(idx)),
320 &mut *self.keys.offset(idx), &mut *self.vals.offset(idx))
324 /// Puts a key and value pair, along with the key's hash, into a given
325 /// index in the hashtable. Note how the `EmptyIndex` is 'moved' into this
326 /// function, because that slot will no longer be empty when we return!
327 /// A FullIndex is returned for later use, pointing to the newly-filled
328 /// slot in the hashtable.
330 /// Use `make_hash` to construct a `SafeHash` to pass to this function.
331 pub fn put(&mut self, index: EmptyIndex, hash: SafeHash, k: K, v: V) -> FullIndex {
335 debug_assert_eq!(*self.hashes.offset(idx), EMPTY_BUCKET);
336 *self.hashes.offset(idx) = hash.inspect();
337 overwrite(&mut *self.keys.offset(idx), k);
338 overwrite(&mut *self.vals.offset(idx), v);
343 FullIndex { idx: idx, hash: hash, nocopy: marker::NoCopy }
346 /// Removes a key and value from the hashtable.
348 /// This works similarly to `put`, building an `EmptyIndex` out of the
350 pub fn take(&mut self, index: FullIndex) -> (EmptyIndex, K, V) {
354 debug_assert!(*self.hashes.offset(idx) != EMPTY_BUCKET);
356 *self.hashes.offset(idx) = EMPTY_BUCKET;
358 // Drop the mutable constraint.
359 let keys = self.keys as *const K;
360 let vals = self.vals as *const V;
362 let k = ptr::read(keys.offset(idx));
363 let v = ptr::read(vals.offset(idx));
367 (EmptyIndex { idx: idx, nocopy: marker::NoCopy }, k, v)
371 /// The hashtable's capacity, similar to a vector's.
372 pub fn capacity(&self) -> uint {
376 /// The number of elements ever `put` in the hashtable, minus the number
377 /// of elements ever `take`n.
378 pub fn size(&self) -> uint {
382 pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
383 Entries { table: self, idx: 0, elems_seen: 0 }
386 pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> {
387 MutEntries { table: self, idx: 0, elems_seen: 0 }
390 pub fn move_iter(self) -> MoveEntries<K, V> {
391 MoveEntries { table: self, idx: 0 }
395 // `read_all_mut` casts a `*u64` to a `*SafeHash`. Since we statically
396 // ensure that a `FullIndex` points to an index with a non-zero hash,
397 // and a `SafeHash` is just a `u64` with a different name, this is
400 // This test ensures that a `SafeHash` really IS the same size as a
401 // `u64`. If you need to change the size of `SafeHash` (and
402 // consequently made this test fail), `read_all_mut` needs to be
403 // modified to no longer assume this.
405 fn can_alias_safehash_as_u64() {
406 assert_eq!(size_of::<SafeHash>(), size_of::<u64>())
409 /// Iterator over shared references to entries in a table.
410 pub struct Entries<'a, K, V> {
411 table: &'a RawTable<K, V>,
416 /// Iterator over mutable references to entries in a table.
417 pub struct MutEntries<'a, K, V> {
418 table: &'a mut RawTable<K, V>,
423 /// Iterator over the entries in a table, consuming the table.
424 pub struct MoveEntries<K, V> {
425 table: RawTable<K, V>,
429 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
430 fn next(&mut self) -> Option<(&'a K, &'a V)> {
431 while self.idx < self.table.capacity() {
435 match self.table.peek(i) {
438 self.elems_seen += 1;
439 return Some(self.table.read(&idx));
447 fn size_hint(&self) -> (uint, Option<uint>) {
448 let size = self.table.size() - self.elems_seen;
453 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
454 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
455 while self.idx < self.table.capacity() {
459 match self.table.peek(i) {
461 // the transmute here fixes:
462 // error: lifetime of `self` is too short to guarantee its contents
463 // can be safely reborrowed
464 Full(idx) => unsafe {
465 self.elems_seen += 1;
466 return Some(transmute(self.table.read_mut(&idx)));
474 fn size_hint(&self) -> (uint, Option<uint>) {
475 let size = self.table.size() - self.elems_seen;
480 impl<K, V> Iterator<(SafeHash, K, V)> for MoveEntries<K, V> {
481 fn next(&mut self) -> Option<(SafeHash, K, V)> {
482 while self.idx < self.table.capacity() {
486 match self.table.peek(i) {
490 let (_, k, v) = self.table.take(idx);
491 return Some((h, k, v));
499 fn size_hint(&self) -> (uint, Option<uint>) {
500 let size = self.table.size();
505 impl<K: Clone, V: Clone> Clone for RawTable<K, V> {
506 fn clone(&self) -> RawTable<K, V> {
508 let mut new_ht = RawTable::new_uninitialized(self.capacity());
510 for i in range(0, self.capacity()) {
513 *new_ht.hashes.offset(i as int) = EMPTY_BUCKET;
516 let hash = idx.hash().inspect();
517 let (k, v) = self.read(&idx);
518 *new_ht.hashes.offset(i as int) = hash;
519 overwrite(&mut *new_ht.keys.offset(i as int), (*k).clone());
520 overwrite(&mut *new_ht.vals.offset(i as int), (*v).clone());
525 new_ht.size = self.size();
533 impl<K, V> Drop for RawTable<K, V> {
535 // This is in reverse because we're likely to have partially taken
536 // some elements out with `.move_iter()` from the front.
537 for i in range_step_inclusive(self.capacity as int - 1, 0, -1) {
538 // Check if the size is 0, so we don't do a useless scan when
539 // dropping empty tables such as on resize.
540 if self.size == 0 { break }
542 match self.peek(i as uint) {
544 Full(idx) => { self.take(idx); }
548 assert_eq!(self.size, 0);
550 if self.hashes.is_not_null() {
551 let hashes_size = self.capacity * size_of::<u64>();
552 let keys_size = self.capacity * size_of::<K>();
553 let vals_size = self.capacity * size_of::<V>();
554 let (align, _, _, _, size) = calculate_offsets(hashes_size, min_align_of::<u64>(),
555 keys_size, min_align_of::<K>(),
556 vals_size, min_align_of::<V>());
559 deallocate(self.hashes as *mut u8, size, align);
560 // Remember how everything was allocated out of one buffer
561 // during initialization? We only need one call to free here.
564 self.hashes = RawPtr::null();
570 static INITIAL_LOG2_CAP: uint = 5;
571 static INITIAL_CAPACITY: uint = 1 << INITIAL_LOG2_CAP; // 2^5
573 /// The default behavior of HashMap implements a load factor of 90.9%.
574 /// This behavior is characterized by the following conditions:
576 /// - if `size * 1.1 < cap < size * 4` then shouldn't resize
577 /// - if `cap < minimum_capacity * 2` then shouldn't shrink
579 struct DefaultResizePolicy {
580 /// Doubled minimal capacity. The capacity must never drop below
581 /// the minimum capacity. (The check happens before the capacity
582 /// is potentially halved.)
583 minimum_capacity2: uint
586 impl DefaultResizePolicy {
587 fn new(new_capacity: uint) -> DefaultResizePolicy {
588 DefaultResizePolicy {
589 minimum_capacity2: new_capacity << 1
594 fn capacity_range(&self, new_size: uint) -> (uint, uint) {
595 ((new_size * 11) / 10, max(new_size << 3, self.minimum_capacity2))
599 fn reserve(&mut self, new_capacity: uint) {
600 self.minimum_capacity2 = new_capacity << 1;
604 // The main performance trick in this hashmap is called Robin Hood Hashing.
605 // It gains its excellent performance from one key invariant:
607 // If an insertion collides with an existing element, and that elements
608 // "probe distance" (how far away the element is from its ideal location)
609 // is higher than how far we've already probed, swap the elements.
611 // This massively lowers variance in probe distance, and allows us to get very
612 // high load factors with good performance. The 90% load factor I use is rather
615 // > Why a load factor of approximately 90%?
617 // In general, all the distances to initial buckets will converge on the mean.
618 // At a load factor of α, the odds of finding the target bucket after k
619 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
620 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
621 // this down to make the math easier on the CPU and avoid its FPU.
622 // Since on average we start the probing in the middle of a cache line, this
623 // strategy pulls in two cache lines of hashes on every lookup. I think that's
624 // pretty good, but if you want to trade off some space, it could go down to one
625 // cache line on average with an α of 0.84.
627 // > Wait, what? Where did you get 1-α^k from?
629 // On the first probe, your odds of a collision with an existing element is α.
630 // The odds of doing this twice in a row is approximately α^2. For three times,
631 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
632 // colliding after k tries is 1-α^k.
634 // Future Improvements (FIXME!)
635 // ============================
637 // Allow the load factor to be changed dynamically and/or at initialization.
639 // Also, would it be possible for us to reuse storage when growing the
640 // underlying table? This is exactly the use case for 'realloc', and may
641 // be worth exploring.
643 // Future Optimizations (FIXME!)
644 // =============================
646 // The paper cited below mentions an implementation which keeps track of the
647 // distance-to-initial-bucket histogram. I'm suspicious of this approach because
648 // it requires maintaining an internal map. If this map were replaced with a
649 // hashmap, it would be faster, but now our data structure is self-referential
650 // and blows up. Also, this allows very good first guesses, but array accesses
651 // are no longer linear and in one direction, as we have now. There is also
652 // memory and cache pressure that this map would entail that would be very
653 // difficult to properly see in a microbenchmark.
655 // Another possible design choice that I made without any real reason is
656 // parameterizing the raw table over keys and values. Technically, all we need
657 // is the size and alignment of keys and values, and the code should be just as
658 // efficient (well, we might need one for power-of-two size and one for not...).
659 // This has the potential to reduce code bloat in rust executables, without
660 // really losing anything except 4 words (key size, key alignment, val size,
661 // val alignment) which can be passed in to every call of a `RawTable` function.
662 // This would definitely be an avenue worth exploring if people start complaining
663 // about the size of rust executables.
665 // There's also an "optimization" that has been omitted regarding how the
666 // hashtable allocates. The vector type has set the expectation that a hashtable
667 // which never has an element inserted should not allocate. I'm suspicious of
668 // implementing this for hashtables, because supporting it has no performance
669 // benefit over using an `Option<HashMap<K, V>>`, and is significantly more
672 /// A hash map implementation which uses linear probing with Robin
673 /// Hood bucket stealing.
675 /// The hashes are all keyed by the task-local random number generator
676 /// on creation by default, this means the ordering of the keys is
677 /// randomized, but makes the tables more resistant to
678 /// denial-of-service attacks (Hash DoS). This behaviour can be
679 /// overridden with one of the constructors.
681 /// It is required that the keys implement the `Eq` and `Hash` traits, although
682 /// this can frequently be achieved by using `#[deriving(Eq, Hash)]`.
684 /// Relevant papers/articles:
686 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
687 /// 2. Emmanuel Goossaert. ["Robin Hood
688 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
689 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
690 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
695 /// use std::collections::HashMap;
697 /// // type inference lets us omit an explicit type signature (which
698 /// // would be `HashMap<&str, &str>` in this example).
699 /// let mut book_reviews = HashMap::new();
701 /// // review some books.
702 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
703 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
704 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
705 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
707 /// // check for a specific one.
708 /// if !book_reviews.contains_key(&("Les Misérables")) {
709 /// println!("We've got {} reviews, but Les Misérables ain't one.",
710 /// book_reviews.len());
713 /// // oops, this review has a lot of spelling mistakes, let's delete it.
714 /// book_reviews.remove(&("The Adventures of Sherlock Holmes"));
716 /// // look up the values associated with some keys.
717 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
718 /// for book in to_find.iter() {
719 /// match book_reviews.find(book) {
720 /// Some(review) => println!("{}: {}", *book, *review),
721 /// None => println!("{} is unreviewed.", *book)
725 /// // iterate over everything.
726 /// for (book, review) in book_reviews.iter() {
727 /// println!("{}: \"{}\"", *book, *review);
731 pub struct HashMap<K, V, H = RandomSipHasher> {
732 // All hashes are keyed on these values, to prevent hash collision attacks.
735 table: table::RawTable<K, V>,
737 // We keep this at the end since it might as well have tail padding.
738 resize_policy: DefaultResizePolicy,
741 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
742 // Probe the `idx`th bucket for a given hash, returning the index of the
745 // This exploits the power-of-two size of the hashtable. As long as this
746 // is always true, we can use a bitmask of cap-1 to do modular arithmetic.
748 // Prefer using this with increasing values of `idx` rather than repeatedly
749 // calling `probe_next`. This reduces data-dependencies between loops, which
750 // can help the optimizer, and certainly won't hurt it. `probe_next` is
751 // simply for convenience, and is no more efficient than `probe`.
752 fn probe(&self, hash: &table::SafeHash, idx: uint) -> uint {
753 let hash_mask = self.table.capacity() - 1;
755 // So I heard a rumor that unsigned overflow is safe in rust..
756 ((hash.inspect() as uint) + idx) & hash_mask
759 // Generate the next probe in a sequence. Prefer using 'probe' by itself,
760 // but this can sometimes be useful.
761 fn probe_next(&self, probe: uint) -> uint {
762 let hash_mask = self.table.capacity() - 1;
763 (probe + 1) & hash_mask
766 fn make_hash<X: Hash<S>>(&self, x: &X) -> table::SafeHash {
767 table::make_hash(&self.hasher, x)
770 /// Get the distance of the bucket at the given index that it lies
771 /// from its 'ideal' location.
773 /// In the cited blog posts above, this is called the "distance to
774 /// initial bucket", or DIB.
775 fn bucket_distance(&self, index_of_elem: &table::FullIndex) -> uint {
776 // where the hash of the element that happens to reside at
777 // `index_of_elem` tried to place itself first.
778 let first_probe_index = self.probe(&index_of_elem.hash(), 0);
780 let raw_index = index_of_elem.raw_index();
782 if first_probe_index <= raw_index {
783 // probe just went forward
784 raw_index - first_probe_index
786 // probe wrapped around the hashtable
787 raw_index + (self.table.capacity() - first_probe_index)
791 /// Search for a pre-hashed key.
792 fn search_hashed_generic(&self, hash: &table::SafeHash, is_match: |&K| -> bool)
793 -> Option<table::FullIndex> {
794 for num_probes in range(0u, self.table.size()) {
795 let probe = self.probe(hash, num_probes);
797 let idx = match self.table.peek(probe) {
798 table::Empty(_) => return None, // hit an empty bucket
799 table::Full(idx) => idx
802 // We can finish the search early if we hit any bucket
803 // with a lower distance to initial bucket than we've probed.
804 if self.bucket_distance(&idx) < num_probes { return None }
806 // If the hash doesn't match, it can't be this one..
807 if *hash != idx.hash() { continue }
809 let (k, _) = self.table.read(&idx);
811 // If the key doesn't match, it can't be this one..
812 if !is_match(k) { continue }
820 fn search_hashed(&self, hash: &table::SafeHash, k: &K) -> Option<table::FullIndex> {
821 self.search_hashed_generic(hash, |k_| *k == *k_)
824 fn search_equiv<Q: Hash<S> + Equiv<K>>(&self, q: &Q) -> Option<table::FullIndex> {
825 self.search_hashed_generic(&self.make_hash(q), |k| q.equiv(k))
828 /// Search for a key, yielding the index if it's found in the hashtable.
829 /// If you already have the hash for the key lying around, use
831 fn search(&self, k: &K) -> Option<table::FullIndex> {
832 self.search_hashed(&self.make_hash(k), k)
835 fn pop_internal(&mut self, starting_index: table::FullIndex) -> Option<V> {
836 let starting_probe = starting_index.raw_index();
839 let mut probe = self.probe_next(starting_probe);
840 for _ in range(0u, self.table.size()) {
841 match self.table.peek(probe) {
842 table::Empty(_) => {}, // empty bucket. this is the end of our shifting.
843 table::Full(idx) => {
844 // Bucket that isn't us, which has a non-zero probe distance.
845 // This isn't the ending index, so keep searching.
846 if self.bucket_distance(&idx) != 0 {
847 probe = self.probe_next(probe);
851 // if we do have a bucket_distance of zero, we're at the end
852 // of what we need to shift.
861 let (_, _, retval) = self.table.take(starting_index);
863 let mut probe = starting_probe;
864 let mut next_probe = self.probe_next(probe);
866 // backwards-shift all the elements after our newly-deleted one.
867 while next_probe != ending_probe {
868 match self.table.peek(next_probe) {
870 // nothing to shift in. just empty it out.
871 match self.table.peek(probe) {
872 table::Empty(_) => {},
873 table::Full(idx) => { self.table.take(idx); }
876 table::Full(next_idx) => {
877 // something to shift. move it over!
878 let next_hash = next_idx.hash();
879 let (_, next_key, next_val) = self.table.take(next_idx);
880 match self.table.peek(probe) {
881 table::Empty(idx) => {
882 self.table.put(idx, next_hash, next_key, next_val);
884 table::Full(idx) => {
885 let (emptyidx, _, _) = self.table.take(idx);
886 self.table.put(emptyidx, next_hash, next_key, next_val);
893 next_probe = self.probe_next(next_probe);
896 // Done the backwards shift, but there's still an element left!
898 match self.table.peek(probe) {
899 table::Empty(_) => {},
900 table::Full(idx) => { self.table.take(idx); }
903 // Now we're done all our shifting. Return the value we grabbed
908 /// Like `pop`, but can operate on any type that is equivalent to a key.
910 pub fn pop_equiv<Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
911 if self.table.size() == 0 {
915 let potential_new_size = self.table.size() - 1;
916 self.make_some_room(potential_new_size);
918 let starting_index = match self.search_equiv(k) {
923 self.pop_internal(starting_index)
927 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Collection for HashMap<K, V, H> {
928 /// Return the number of elements in the map
929 fn len(&self) -> uint { self.table.size() }
932 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H> {
933 /// Clear the map, removing all key-value pairs. Keeps the allocated memory
935 fn clear(&mut self) {
936 // Prevent reallocations from happening from now on. Makes it possible
937 // for the map to be reused but has a downside: reserves permanently.
938 self.resize_policy.reserve(self.table.size());
940 for i in range(0, self.table.capacity()) {
941 match self.table.peek(i) {
942 table::Empty(_) => {},
943 table::Full(idx) => { self.table.take(idx); }
949 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Map<K, V> for HashMap<K, V, H> {
950 fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
951 self.search(k).map(|idx| {
952 let (_, v) = self.table.read(&idx);
957 fn contains_key(&self, k: &K) -> bool {
958 self.search(k).is_some()
962 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V, H> {
963 fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
964 match self.search(k) {
967 let (_, v) = self.table.read_mut(&idx);
973 fn swap(&mut self, k: K, v: V) -> Option<V> {
974 let hash = self.make_hash(&k);
975 let potential_new_size = self.table.size() + 1;
976 self.make_some_room(potential_new_size);
978 for dib in range_inclusive(0u, self.table.size()) {
979 let probe = self.probe(&hash, dib);
981 let idx = match self.table.peek(probe) {
982 table::Empty(idx) => {
984 self.table.put(idx, hash, k, v);
987 table::Full(idx) => idx
990 if idx.hash() == hash {
991 let (bucket_k, bucket_v) = self.table.read_mut(&idx);
993 // Found an existing value.
994 return Some(replace(bucket_v, v));
998 let probe_dib = self.bucket_distance(&idx);
1000 if probe_dib < dib {
1001 // Found a luckier bucket. This implies that the key does not
1002 // already exist in the hashtable. Just do a robin hood
1004 self.robin_hood(idx, probe_dib, hash, k, v);
1009 // We really shouldn't be here.
1010 fail!("Internal HashMap error: Out of space.");
1013 fn pop(&mut self, k: &K) -> Option<V> {
1014 if self.table.size() == 0 {
1018 let potential_new_size = self.table.size() - 1;
1019 self.make_some_room(potential_new_size);
1021 let starting_index = match self.search(k) {
1023 None => return None,
1026 self.pop_internal(starting_index)
1031 impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
1032 /// Create an empty HashMap.
1034 pub fn new() -> HashMap<K, V, RandomSipHasher> {
1035 HashMap::with_capacity(INITIAL_CAPACITY)
1038 /// Creates an empty hash map with the given initial capacity.
1040 pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
1041 let hasher = RandomSipHasher::new();
1042 HashMap::with_capacity_and_hasher(capacity, hasher)
1046 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
1047 /// Creates an empty hashmap which will use the given hasher to hash keys.
1049 /// The creates map has the default initial capacity.
1051 pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
1052 HashMap::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
1055 /// Create an empty HashMap with space for at least `capacity`
1056 /// elements, using `hasher` to hash the keys.
1058 /// Warning: `hasher` is normally randomly generated, and
1059 /// is designed to allow HashMaps to be resistant to attacks that
1060 /// cause many collisions and very poor performance. Setting it
1061 /// manually using this function can expose a DoS attack vector.
1063 pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
1064 let cap = num::next_power_of_two(max(INITIAL_CAPACITY, capacity));
1067 resize_policy: DefaultResizePolicy::new(cap),
1068 table: table::RawTable::new(cap),
1072 /// The hashtable will never try to shrink below this size. You can use
1073 /// this function to reduce reallocations if your hashtable frequently
1074 /// grows and shrinks by large amounts.
1076 /// This function has no effect on the operational semantics of the
1077 /// hashtable, only on performance.
1078 pub fn reserve(&mut self, new_minimum_capacity: uint) {
1079 let cap = num::next_power_of_two(
1080 max(INITIAL_CAPACITY, new_minimum_capacity));
1082 self.resize_policy.reserve(cap);
1084 if self.table.capacity() < cap {
1089 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
1090 /// 1) Make sure the new capacity is enough for all the elements, accounting
1091 /// for the load factor.
1092 /// 2) Ensure new_capacity is a power of two.
1093 fn resize(&mut self, new_capacity: uint) {
1094 assert!(self.table.size() <= new_capacity);
1095 assert!(num::is_power_of_two(new_capacity));
1097 let old_table = replace(&mut self.table, table::RawTable::new(new_capacity));
1098 let old_size = old_table.size();
1100 for (h, k, v) in old_table.move_iter() {
1101 self.insert_hashed_nocheck(h, k, v);
1104 assert_eq!(self.table.size(), old_size);
1107 /// Performs any necessary resize operations, such that there's space for
1108 /// new_size elements.
1109 fn make_some_room(&mut self, new_size: uint) {
1110 let (grow_at, shrink_at) = self.resize_policy.capacity_range(new_size);
1111 let cap = self.table.capacity();
1113 // An invalid value shouldn't make us run out of space.
1114 debug_assert!(grow_at >= new_size);
1117 let new_capacity = cap << 1;
1118 self.resize(new_capacity);
1119 } else if shrink_at <= cap {
1120 let new_capacity = cap >> 1;
1121 self.resize(new_capacity);
1125 /// Perform robin hood bucket stealing at the given 'index'. You must
1126 /// also pass that probe's "distance to initial bucket" so we don't have
1127 /// to recalculate it, as well as the total number of probes already done
1128 /// so we have some sort of upper bound on the number of probes to do.
1130 /// 'hash', 'k', and 'v' are the elements to robin hood into the hashtable.
1131 fn robin_hood(&mut self, mut index: table::FullIndex, mut dib_param: uint,
1132 mut hash: table::SafeHash, mut k: K, mut v: V) {
1134 let (old_hash, old_key, old_val) = {
1135 let (old_hash_ref, old_key_ref, old_val_ref) =
1136 self.table.read_all_mut(&index);
1138 let old_hash = replace(old_hash_ref, hash);
1139 let old_key = replace(old_key_ref, k);
1140 let old_val = replace(old_val_ref, v);
1142 (old_hash, old_key, old_val)
1145 let mut probe = self.probe_next(index.raw_index());
1147 for dib in range(dib_param + 1, self.table.size()) {
1148 let full_index = match self.table.peek(probe) {
1149 table::Empty(idx) => {
1151 self.table.put(idx, old_hash, old_key, old_val);
1154 table::Full(idx) => idx
1157 let probe_dib = self.bucket_distance(&full_index);
1159 // Robin hood! Steal the spot.
1160 if probe_dib < dib {
1162 dib_param = probe_dib;
1169 probe = self.probe_next(probe);
1172 fail!("HashMap fatal error: 100% load factor?");
1176 /// Insert a pre-hashed key-value pair, without first checking
1177 /// that there's enough room in the buckets. Returns a reference to the
1178 /// newly insert value.
1180 /// If the key already exists, the hashtable will be returned untouched
1181 /// and a reference to the existing element will be returned.
1182 fn insert_hashed_nocheck<'a>(
1183 &'a mut self, hash: table::SafeHash, k: K, v: V) -> &'a mut V {
1185 for dib in range_inclusive(0u, self.table.size()) {
1186 let probe = self.probe(&hash, dib);
1188 let idx = match self.table.peek(probe) {
1189 table::Empty(idx) => {
1191 let fullidx = self.table.put(idx, hash, k, v);
1192 let (_, val) = self.table.read_mut(&fullidx);
1195 table::Full(idx) => idx
1198 if idx.hash() == hash {
1199 let (bucket_k, bucket_v) = self.table.read_mut(&idx);
1200 // FIXME #12147 the conditional return confuses
1201 // borrowck if we return bucket_v directly
1202 let bv: *mut V = bucket_v;
1204 // Key already exists. Get its reference.
1205 return unsafe {&mut *bv};
1209 let probe_dib = self.bucket_distance(&idx);
1211 if probe_dib < dib {
1212 // Found a luckier bucket than me. Better steal his spot.
1213 self.robin_hood(idx, probe_dib, hash, k, v);
1215 // Now that it's stolen, just read the value's pointer
1216 // right out of the table!
1217 match self.table.peek(probe) {
1218 table::Empty(_) => fail!("Just stole a spot, but now that spot's empty."),
1219 table::Full(idx) => {
1220 let (_, v) = self.table.read_mut(&idx);
1227 // We really shouldn't be here.
1228 fail!("Internal HashMap error: Out of space.");
1231 /// Inserts an element which has already been hashed, returning a reference
1232 /// to that element inside the hashtable. This is more efficient that using
1233 /// `insert`, since the key will not be rehashed.
1234 fn insert_hashed<'a>(&'a mut self, hash: table::SafeHash, k: K, v: V) -> &'a mut V {
1235 let potential_new_size = self.table.size() + 1;
1236 self.make_some_room(potential_new_size);
1237 self.insert_hashed_nocheck(hash, k, v)
1240 /// Return the value corresponding to the key in the map, or insert
1241 /// and return the value if it doesn't exist.
1242 pub fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a mut V {
1243 self.find_with_or_insert_with(k, v, |_k, _v, _a| (), |_k, a| a)
1246 /// Return the value corresponding to the key in the map, or create,
1247 /// insert, and return a new value if it doesn't exist.
1248 pub fn find_or_insert_with<'a>(&'a mut self, k: K, f: |&K| -> V)
1250 self.find_with_or_insert_with(k, (), |_k, _v, _a| (), |k, _a| f(k))
1253 /// Insert a key-value pair into the map if the key is not already present.
1254 /// Otherwise, modify the existing value for the key.
1255 /// Returns the new or modified value for the key.
1256 pub fn insert_or_update_with<'a>(
1262 self.find_with_or_insert_with(k, v, |k, v, _a| f(k, v), |_k, a| a)
1265 /// Modify and return the value corresponding to the key in the map, or
1266 /// insert and return a new value if it doesn't exist.
1268 /// This method allows for all insertion behaviours of a hashmap;
1269 /// see methods like `insert`, `find_or_insert` and
1270 /// `insert_or_update_with` for less general and more friendly
1271 /// variations of this.
1276 /// use std::collections::HashMap;
1278 /// // map some strings to vectors of strings
1279 /// let mut map = HashMap::new();
1280 /// map.insert("a key", vec!["value"]);
1281 /// map.insert("z key", vec!["value"]);
1283 /// let new = vec!["a key", "b key", "z key"];
1285 /// for k in new.move_iter() {
1286 /// map.find_with_or_insert_with(
1288 /// // if the key does exist either prepend or append this
1289 /// // new value based on the first letter of the key.
1290 /// |key, already, new| {
1291 /// if key.as_slice().starts_with("z") {
1292 /// already.unshift(new);
1294 /// already.push(new);
1297 /// // if the key doesn't exist in the map yet, add it in
1298 /// // the obvious way.
1299 /// |_k, v| vec![v]);
1302 /// assert_eq!(map.len(), 3);
1303 /// assert_eq!(map.get(&"a key"), &vec!["value", "new value"]);
1304 /// assert_eq!(map.get(&"b key"), &vec!["new value"]);
1305 /// assert_eq!(map.get(&"z key"), &vec!["new value", "value"]);
1307 pub fn find_with_or_insert_with<'a, A>(&'a mut self,
1310 found: |&K, &mut V, A|,
1311 not_found: |&K, A| -> V)
1313 let hash = self.make_hash(&k);
1314 match self.search_hashed(&hash, &k) {
1316 let v = not_found(&k, a);
1317 self.insert_hashed(hash, k, v)
1320 let (_, v_ref) = self.table.read_mut(&idx);
1321 found(&k, v_ref, a);
1327 /// Retrieves a value for the given key, failing if the key is not present.
1328 pub fn get<'a>(&'a self, k: &K) -> &'a V {
1329 match self.find(k) {
1331 None => fail!("no entry found for key")
1335 /// Retrieves a (mutable) value for the given key, failing if the key is not present.
1336 pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V {
1337 match self.find_mut(k) {
1339 None => fail!("no entry found for key")
1343 /// Return true if the map contains a value for the specified key,
1344 /// using equivalence.
1345 pub fn contains_key_equiv<Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
1346 self.search_equiv(key).is_some()
1349 /// Return the value corresponding to the key in the map, using
1351 pub fn find_equiv<'a, Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
1352 match self.search_equiv(k) {
1355 let (_, v_ref) = self.table.read(&idx);
1361 /// An iterator visiting all keys in arbitrary order.
1362 /// Iterator element type is &'a K.
1363 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
1364 self.iter().map(|(k, _v)| k)
1367 /// An iterator visiting all values in arbitrary order.
1368 /// Iterator element type is &'a V.
1369 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
1370 self.iter().map(|(_k, v)| v)
1373 /// An iterator visiting all key-value pairs in arbitrary order.
1374 /// Iterator element type is (&'a K, &'a V).
1375 pub fn iter<'a>(&'a self) -> Entries<'a, K, V> {
1379 /// An iterator visiting all key-value pairs in arbitrary order,
1380 /// with mutable references to the values.
1381 /// Iterator element type is (&'a K, &'a mut V).
1382 pub fn mut_iter<'a>(&'a mut self) -> MutEntries<'a, K, V> {
1383 self.table.mut_iter()
1386 /// Creates a consuming iterator, that is, one that moves each key-value
1387 /// pair out of the map in arbitrary order. The map cannot be used after
1389 pub fn move_iter(self) -> MoveEntries<K, V> {
1390 self.table.move_iter().map(|(_, k, v)| (k, v))
1394 impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
1395 /// Like `find`, but returns a copy of the value.
1396 pub fn find_copy(&self, k: &K) -> Option<V> {
1397 self.find(k).map(|v| (*v).clone())
1400 /// Like `get`, but returns a copy of the value.
1401 pub fn get_copy(&self, k: &K) -> V {
1402 (*self.get(k)).clone()
1406 impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
1407 fn eq(&self, other: &HashMap<K, V, H>) -> bool {
1408 if self.len() != other.len() { return false; }
1411 .all(|(key, value)| {
1412 match other.find(key) {
1414 Some(v) => *value == *v
1420 impl<K: Eq + Hash<S>, V: Eq, S, H: Hasher<S>> Eq for HashMap<K, V, H> {}
1422 impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
1423 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1424 try!(write!(f, "{{"));
1426 for (i, (k, v)) in self.iter().enumerate() {
1427 if i != 0 { try!(write!(f, ", ")); }
1428 try!(write!(f, "{}: {}", *k, *v));
1435 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
1436 fn default() -> HashMap<K, V, H> {
1437 HashMap::with_hasher(Default::default())
1441 /// HashMap iterator
1442 pub type Entries<'a, K, V> = table::Entries<'a, K, V>;
1444 /// HashMap mutable values iterator
1445 pub type MutEntries<'a, K, V> = table::MutEntries<'a, K, V>;
1447 /// HashMap move iterator
1448 pub type MoveEntries<K, V> =
1449 iter::Map<'static, (table::SafeHash, K, V), (K, V), table::MoveEntries<K, V>>;
1451 /// HashMap keys iterator
1452 pub type Keys<'a, K, V> =
1453 iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
1455 /// HashMap values iterator
1456 pub type Values<'a, K, V> =
1457 iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
1459 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
1460 fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
1461 let (lower, _) = iter.size_hint();
1462 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1468 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Extendable<(K, V)> for HashMap<K, V, H> {
1469 fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
1470 for (k, v) in iter {
1476 /// HashSet iterator
1477 pub type SetItems<'a, K> =
1478 iter::Map<'static, (&'a K, &'a ()), &'a K, Entries<'a, K, ()>>;
1480 /// HashSet move iterator
1481 pub type SetMoveItems<K> =
1482 iter::Map<'static, (K, ()), K, MoveEntries<K, ()>>;
1484 /// An implementation of a hash set using the underlying representation of a
1485 /// HashMap where the value is (). As with the `HashMap` type, a `HashSet`
1486 /// requires that the elements implement the `Eq` and `Hash` traits.
1491 /// use std::collections::HashSet;
1493 /// // Type inference lets us omit an explicit type signature (which
1494 /// // would be `HashSet<&str>` in this example).
1495 /// let mut books = HashSet::new();
1497 /// // Add some books.
1498 /// books.insert("A Dance With Dragons");
1499 /// books.insert("To Kill a Mockingbird");
1500 /// books.insert("The Odyssey");
1501 /// books.insert("The Great Gatsby");
1503 /// // Check for a specific one.
1504 /// if !books.contains(&("The Winds of Winter")) {
1505 /// println!("We have {} books, but The Winds of Winter ain't one.",
1509 /// // Remove a book.
1510 /// books.remove(&"The Odyssey");
1512 /// // Iterate over everything.
1513 /// for book in books.iter() {
1514 /// println!("{}", *book);
1518 pub struct HashSet<T, H = RandomSipHasher> {
1519 map: HashMap<T, (), H>
1522 impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
1523 fn eq(&self, other: &HashSet<T, H>) -> bool {
1524 if self.len() != other.len() { return false; }
1526 self.iter().all(|key| other.contains(key))
1530 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
1532 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Collection for HashSet<T, H> {
1533 fn len(&self) -> uint { self.map.len() }
1536 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> {
1537 fn clear(&mut self) { self.map.clear() }
1540 impl<T: Eq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> {
1541 fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
1543 fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
1544 self.iter().all(|v| !other.contains(v))
1547 fn is_subset(&self, other: &HashSet<T, H>) -> bool {
1548 self.iter().all(|v| other.contains(v))
1552 impl<T: Eq + Hash<S>, S, H: Hasher<S>> MutableSet<T> for HashSet<T, H> {
1553 fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
1555 fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
1558 impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
1559 /// Create an empty HashSet
1564 /// # use std::collections::HashSet;
1565 /// let mut set: HashSet<int> = HashSet::new();
1568 pub fn new() -> HashSet<T, RandomSipHasher> {
1569 HashSet::with_capacity(INITIAL_CAPACITY)
1572 /// Create an empty HashSet with space for at least `n` elements in
1578 /// # use std::collections::HashSet;
1579 /// let mut set: HashSet<int> = HashSet::with_capacity(10);
1582 pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> {
1583 HashSet { map: HashMap::with_capacity(capacity) }
1587 impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
1588 /// Creates a new empty hash set which will use the given hasher to hash
1591 /// The hash set is also created with the default initial capacity.
1593 pub fn with_hasher(hasher: H) -> HashSet<T, H> {
1594 HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
1597 /// Create an empty HashSet with space for at least `capacity`
1598 /// elements in the hash table, using `hasher` to hash the keys.
1600 /// Warning: `hasher` is normally randomly generated, and
1601 /// is designed to allow `HashSet`s to be resistant to attacks that
1602 /// cause many collisions and very poor performance. Setting it
1603 /// manually using this function can expose a DoS attack vector.
1605 pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashSet<T, H> {
1606 HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
1609 /// Reserve space for at least `n` elements in the hash table.
1614 /// # use std::collections::HashSet;
1615 /// let mut set: HashSet<int> = HashSet::new();
1616 /// set.reserve(10);
1618 pub fn reserve(&mut self, n: uint) {
1622 /// Returns true if the hash set contains a value equivalent to the
1623 /// given query value.
1624 pub fn contains_equiv<Q: Hash<S> + Equiv<T>>(&self, value: &Q) -> bool {
1625 self.map.contains_key_equiv(value)
1628 /// An iterator visiting all elements in arbitrary order.
1629 /// Iterator element type is &'a T.
1634 /// # use std::collections::HashSet;
1635 /// let mut set = HashSet::new();
1636 /// set.insert("a");
1637 /// set.insert("b");
1639 /// // Will print in an arbitrary order.
1640 /// for x in set.iter() {
1641 /// println!("{}", x);
1644 pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
1648 /// Creates a consuming iterator, that is, one that moves each value out
1649 /// of the set in arbitrary order. The set cannot be used after calling
1655 /// # use std::collections::HashSet;
1656 /// let mut set = HashSet::new();
1657 /// set.insert("a".to_string());
1658 /// set.insert("b".to_string());
1660 /// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1661 /// let v: Vec<String> = set.move_iter().collect();
1663 /// // Will print in an arbitrary order.
1664 /// for x in v.iter() {
1665 /// println!("{}", x);
1668 pub fn move_iter(self) -> SetMoveItems<T> {
1669 self.map.move_iter().map(|(k, _)| k)
1672 /// Visit the values representing the difference.
1677 /// # use std::collections::HashSet;
1678 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
1679 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
1681 /// // Can be seen as `a - b`.
1682 /// for x in a.difference(&b) {
1683 /// println!("{}", x); // Print 1
1686 /// let diff: HashSet<int> = a.difference(&b).map(|&x| x).collect();
1687 /// assert_eq!(diff, [1i].iter().map(|&x| x).collect());
1689 /// // Note that difference is not symmetric,
1690 /// // and `b - a` means something else:
1691 /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect();
1692 /// assert_eq!(diff, [4i].iter().map(|&x| x).collect());
1694 pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> SetAlgebraItems<'a, T, H> {
1695 Repeat::new(other).zip(self.iter())
1696 .filter_map(|(other, elt)| {
1697 if !other.contains(elt) { Some(elt) } else { None }
1701 /// Visit the values representing the symmetric difference.
1706 /// # use std::collections::HashSet;
1707 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
1708 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
1710 /// // Print 1, 4 in arbitrary order.
1711 /// for x in a.symmetric_difference(&b) {
1712 /// println!("{}", x);
1715 /// let diff1: HashSet<int> = a.symmetric_difference(&b).map(|&x| x).collect();
1716 /// let diff2: HashSet<int> = b.symmetric_difference(&a).map(|&x| x).collect();
1718 /// assert_eq!(diff1, diff2);
1719 /// assert_eq!(diff1, [1i, 4].iter().map(|&x| x).collect());
1721 pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
1722 -> Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>> {
1723 self.difference(other).chain(other.difference(self))
1726 /// Visit the values representing the intersection.
1731 /// # use std::collections::HashSet;
1732 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
1733 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
1735 /// // Print 2, 3 in arbitrary order.
1736 /// for x in a.intersection(&b) {
1737 /// println!("{}", x);
1740 /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect();
1741 /// assert_eq!(diff, [2i, 3].iter().map(|&x| x).collect());
1743 pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>)
1744 -> SetAlgebraItems<'a, T, H> {
1745 Repeat::new(other).zip(self.iter())
1746 .filter_map(|(other, elt)| {
1747 if other.contains(elt) { Some(elt) } else { None }
1751 /// Visit the values representing the union.
1756 /// # use std::collections::HashSet;
1757 /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
1758 /// let b: HashSet<int> = [4i, 2, 3, 4].iter().map(|&x| x).collect();
1760 /// // Print 1, 2, 3, 4 in arbitrary order.
1761 /// for x in a.union(&b) {
1762 /// println!("{}", x);
1765 /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect();
1766 /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
1768 pub fn union<'a>(&'a self, other: &'a HashSet<T, H>)
1769 -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> {
1770 self.iter().chain(other.difference(self))
1774 impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
1775 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1776 try!(write!(f, "{{"));
1778 for (i, x) in self.iter().enumerate() {
1779 if i != 0 { try!(write!(f, ", ")); }
1780 try!(write!(f, "{}", *x));
1787 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
1788 fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
1789 let (lower, _) = iter.size_hint();
1790 let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
1796 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extendable<T> for HashSet<T, H> {
1797 fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
1804 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
1805 fn default() -> HashSet<T, H> {
1806 HashSet::with_hasher(Default::default())
1810 // `Repeat` is used to feed the filter closure an explicit capture
1811 // of a reference to the other set
1812 /// Set operations iterator
1813 pub type SetAlgebraItems<'a, T, H> =
1814 FilterMap<'static, (&'a HashSet<T, H>, &'a T), &'a T,
1815 Zip<Repeat<&'a HashSet<T, H>>, SetItems<'a, T>>>;
1824 use iter::{Iterator,range_inclusive,range_step_inclusive};
1827 struct KindaIntLike(int);
1829 impl Equiv<int> for KindaIntLike {
1830 fn equiv(&self, other: &int) -> bool {
1831 let KindaIntLike(this) = *self;
1835 impl<S: hash::Writer> hash::Hash<S> for KindaIntLike {
1836 fn hash(&self, state: &mut S) {
1837 let KindaIntLike(this) = *self;
1843 fn test_create_capacity_zero() {
1844 let mut m = HashMap::with_capacity(0);
1846 assert!(m.insert(1i, 1i));
1848 assert!(m.contains_key(&1));
1849 assert!(!m.contains_key(&0));
1854 let mut m = HashMap::new();
1855 assert_eq!(m.len(), 0);
1856 assert!(m.insert(1i, 2i));
1857 assert_eq!(m.len(), 1);
1858 assert!(m.insert(2i, 4i));
1859 assert_eq!(m.len(), 2);
1860 assert_eq!(*m.find(&1).unwrap(), 2);
1861 assert_eq!(*m.find(&2).unwrap(), 4);
1864 local_data_key!(drop_vector: RefCell<Vec<int>>)
1866 #[deriving(Hash, PartialEq, Eq)]
1873 fn new(k: uint) -> Dropable {
1874 let v = drop_vector.get().unwrap();
1875 v.borrow_mut().as_mut_slice()[k] += 1;
1881 impl Drop for Dropable {
1882 fn drop(&mut self) {
1883 let v = drop_vector.get().unwrap();
1884 v.borrow_mut().as_mut_slice()[self.k] -= 1;
1890 drop_vector.replace(Some(RefCell::new(Vec::from_elem(200, 0i))));
1893 let mut m = HashMap::new();
1895 let v = drop_vector.get().unwrap();
1896 for i in range(0u, 200) {
1897 assert_eq!(v.borrow().as_slice()[i], 0);
1901 for i in range(0u, 100) {
1902 let d1 = Dropable::new(i);
1903 let d2 = Dropable::new(i+100);
1907 let v = drop_vector.get().unwrap();
1908 for i in range(0u, 200) {
1909 assert_eq!(v.borrow().as_slice()[i], 1);
1913 for i in range(0u, 50) {
1914 let k = Dropable::new(i);
1917 assert!(v.is_some());
1919 let v = drop_vector.get().unwrap();
1920 assert_eq!(v.borrow().as_slice()[i], 1);
1921 assert_eq!(v.borrow().as_slice()[i+100], 1);
1924 let v = drop_vector.get().unwrap();
1925 for i in range(0u, 50) {
1926 assert_eq!(v.borrow().as_slice()[i], 0);
1927 assert_eq!(v.borrow().as_slice()[i+100], 0);
1930 for i in range(50u, 100) {
1931 assert_eq!(v.borrow().as_slice()[i], 1);
1932 assert_eq!(v.borrow().as_slice()[i+100], 1);
1936 let v = drop_vector.get().unwrap();
1937 for i in range(0u, 200) {
1938 assert_eq!(v.borrow().as_slice()[i], 0);
1943 fn test_empty_pop() {
1944 let mut m: HashMap<int, bool> = HashMap::new();
1945 assert_eq!(m.pop(&0), None);
1949 fn test_lots_of_insertions() {
1950 let mut m = HashMap::new();
1952 // Try this a few times to make sure we never screw up the hashmap's
1954 for _ in range(0i, 10) {
1955 assert!(m.is_empty());
1957 for i in range_inclusive(1i, 1000) {
1958 assert!(m.insert(i, i));
1960 for j in range_inclusive(1, i) {
1962 assert_eq!(r, Some(&j));
1965 for j in range_inclusive(i+1, 1000) {
1967 assert_eq!(r, None);
1971 for i in range_inclusive(1001i, 2000) {
1972 assert!(!m.contains_key(&i));
1976 for i in range_inclusive(1i, 1000) {
1977 assert!(m.remove(&i));
1979 for j in range_inclusive(1, i) {
1980 assert!(!m.contains_key(&j));
1983 for j in range_inclusive(i+1, 1000) {
1984 assert!(m.contains_key(&j));
1988 for i in range_inclusive(1i, 1000) {
1989 assert!(!m.contains_key(&i));
1992 for i in range_inclusive(1i, 1000) {
1993 assert!(m.insert(i, i));
1997 for i in range_step_inclusive(1000i, 1, -1) {
1998 assert!(m.remove(&i));
2000 for j in range_inclusive(i, 1000) {
2001 assert!(!m.contains_key(&j));
2004 for j in range_inclusive(1, i-1) {
2005 assert!(m.contains_key(&j));
2012 fn test_find_mut() {
2013 let mut m = HashMap::new();
2014 assert!(m.insert(1i, 12i));
2015 assert!(m.insert(2i, 8i));
2016 assert!(m.insert(5i, 14i));
2018 match m.find_mut(&5) {
2019 None => fail!(), Some(x) => *x = new
2021 assert_eq!(m.find(&5), Some(&new));
2025 fn test_insert_overwrite() {
2026 let mut m = HashMap::new();
2027 assert!(m.insert(1i, 2i));
2028 assert_eq!(*m.find(&1).unwrap(), 2);
2029 assert!(!m.insert(1i, 3i));
2030 assert_eq!(*m.find(&1).unwrap(), 3);
2034 fn test_insert_conflicts() {
2035 let mut m = HashMap::with_capacity(4);
2036 assert!(m.insert(1i, 2i));
2037 assert!(m.insert(5i, 3i));
2038 assert!(m.insert(9i, 4i));
2039 assert_eq!(*m.find(&9).unwrap(), 4);
2040 assert_eq!(*m.find(&5).unwrap(), 3);
2041 assert_eq!(*m.find(&1).unwrap(), 2);
2045 fn test_conflict_remove() {
2046 let mut m = HashMap::with_capacity(4);
2047 assert!(m.insert(1i, 2i));
2048 assert_eq!(*m.find(&1).unwrap(), 2);
2049 assert!(m.insert(5, 3));
2050 assert_eq!(*m.find(&1).unwrap(), 2);
2051 assert_eq!(*m.find(&5).unwrap(), 3);
2052 assert!(m.insert(9, 4));
2053 assert_eq!(*m.find(&1).unwrap(), 2);
2054 assert_eq!(*m.find(&5).unwrap(), 3);
2055 assert_eq!(*m.find(&9).unwrap(), 4);
2056 assert!(m.remove(&1));
2057 assert_eq!(*m.find(&9).unwrap(), 4);
2058 assert_eq!(*m.find(&5).unwrap(), 3);
2062 fn test_is_empty() {
2063 let mut m = HashMap::with_capacity(4);
2064 assert!(m.insert(1i, 2i));
2065 assert!(!m.is_empty());
2066 assert!(m.remove(&1));
2067 assert!(m.is_empty());
2072 let mut m = HashMap::new();
2074 assert_eq!(m.pop(&1), Some(2));
2075 assert_eq!(m.pop(&1), None);
2079 #[allow(experimental)]
2080 fn test_pop_equiv() {
2081 let mut m = HashMap::new();
2083 assert_eq!(m.pop_equiv(&KindaIntLike(1)), Some(2));
2084 assert_eq!(m.pop_equiv(&KindaIntLike(1)), None);
2089 let mut m = HashMap::new();
2090 assert_eq!(m.swap(1i, 2i), None);
2091 assert_eq!(m.swap(1i, 3i), Some(2));
2092 assert_eq!(m.swap(1i, 4i), Some(3));
2096 fn test_move_iter() {
2098 let mut hm = HashMap::new();
2106 let v = hm.move_iter().collect::<Vec<(char, int)>>();
2107 assert!([('a', 1), ('b', 2)] == v.as_slice() || [('b', 2), ('a', 1)] == v.as_slice());
2112 let mut m = HashMap::with_capacity(4);
2113 for i in range(0u, 32) {
2114 assert!(m.insert(i, i*2));
2116 assert_eq!(m.len(), 32);
2118 let mut observed: u32 = 0;
2120 for (k, v) in m.iter() {
2121 assert_eq!(*v, *k * 2);
2122 observed |= 1 << *k;
2124 assert_eq!(observed, 0xFFFF_FFFF);
2129 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
2130 let map = vec.move_iter().collect::<HashMap<int, char>>();
2131 let keys = map.keys().map(|&k| k).collect::<Vec<int>>();
2132 assert_eq!(keys.len(), 3);
2133 assert!(keys.contains(&1));
2134 assert!(keys.contains(&2));
2135 assert!(keys.contains(&3));
2140 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
2141 let map = vec.move_iter().collect::<HashMap<int, char>>();
2142 let values = map.values().map(|&v| v).collect::<Vec<char>>();
2143 assert_eq!(values.len(), 3);
2144 assert!(values.contains(&'a'));
2145 assert!(values.contains(&'b'));
2146 assert!(values.contains(&'c'));
2151 let mut m = HashMap::new();
2152 assert!(m.find(&1i).is_none());
2156 Some(v) => assert_eq!(*v, 2)
2162 let mut m1 = HashMap::new();
2167 let mut m2 = HashMap::new();
2180 let mut map: HashMap<int, int> = HashMap::new();
2181 let empty: HashMap<int, int> = HashMap::new();
2186 let map_str = format!("{}", map);
2188 assert!(map_str == "{1: 2, 3: 4}".to_string() || map_str == "{3: 4, 1: 2}".to_string());
2189 assert_eq!(format!("{}", empty), "{}".to_string());
2194 let mut m = HashMap::new();
2196 assert_eq!(m.len(), 0);
2197 assert!(m.is_empty());
2200 let old_cap = m.table.capacity();
2201 while old_cap == m.table.capacity() {
2206 assert_eq!(m.len(), i);
2207 assert!(!m.is_empty());
2211 fn test_resize_policy() {
2212 let mut m = HashMap::new();
2214 assert_eq!(m.len(), 0);
2215 assert!(m.is_empty());
2217 let initial_cap = m.table.capacity();
2218 m.reserve(initial_cap * 2);
2219 let cap = m.table.capacity();
2221 assert_eq!(cap, initial_cap * 2);
2224 for _ in range(0, cap * 3 / 4) {
2229 assert_eq!(m.len(), i);
2230 assert_eq!(m.table.capacity(), cap);
2232 for _ in range(0, cap / 4) {
2237 let new_cap = m.table.capacity();
2238 assert_eq!(new_cap, cap * 2);
2240 for _ in range(0, cap / 2) {
2243 assert_eq!(m.table.capacity(), new_cap);
2246 for _ in range(0, cap / 2 - 1) {
2251 assert_eq!(m.table.capacity(), cap);
2252 assert_eq!(m.len(), i);
2253 assert!(!m.is_empty());
2257 fn test_find_equiv() {
2258 let mut m = HashMap::new();
2260 let (foo, bar, baz) = (1i,2i,3i);
2261 m.insert("foo".to_string(), foo);
2262 m.insert("bar".to_string(), bar);
2263 m.insert("baz".to_string(), baz);
2266 assert_eq!(m.find_equiv(&("foo")), Some(&foo));
2267 assert_eq!(m.find_equiv(&("bar")), Some(&bar));
2268 assert_eq!(m.find_equiv(&("baz")), Some(&baz));
2270 assert_eq!(m.find_equiv(&("qux")), None);
2274 fn test_from_iter() {
2275 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2277 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2279 for &(k, v) in xs.iter() {
2280 assert_eq!(map.find(&k), Some(&v));
2285 fn test_size_hint() {
2286 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2288 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2290 let mut iter = map.iter();
2292 for _ in iter.by_ref().take(3) {}
2294 assert_eq!(iter.size_hint(), (3, Some(3)));
2298 fn test_mut_size_hint() {
2299 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2301 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2303 let mut iter = map.mut_iter();
2305 for _ in iter.by_ref().take(3) {}
2307 assert_eq!(iter.size_hint(), (3, Some(3)));
2316 use slice::ImmutableEqVector;
2317 use collections::Collection;
2320 fn test_disjoint() {
2321 let mut xs = HashSet::new();
2322 let mut ys = HashSet::new();
2323 assert!(xs.is_disjoint(&ys));
2324 assert!(ys.is_disjoint(&xs));
2325 assert!(xs.insert(5i));
2326 assert!(ys.insert(11i));
2327 assert!(xs.is_disjoint(&ys));
2328 assert!(ys.is_disjoint(&xs));
2329 assert!(xs.insert(7));
2330 assert!(xs.insert(19));
2331 assert!(xs.insert(4));
2332 assert!(ys.insert(2));
2333 assert!(ys.insert(-11));
2334 assert!(xs.is_disjoint(&ys));
2335 assert!(ys.is_disjoint(&xs));
2336 assert!(ys.insert(7));
2337 assert!(!xs.is_disjoint(&ys));
2338 assert!(!ys.is_disjoint(&xs));
2342 fn test_subset_and_superset() {
2343 let mut a = HashSet::new();
2344 assert!(a.insert(0i));
2345 assert!(a.insert(5));
2346 assert!(a.insert(11));
2347 assert!(a.insert(7));
2349 let mut b = HashSet::new();
2350 assert!(b.insert(0i));
2351 assert!(b.insert(7));
2352 assert!(b.insert(19));
2353 assert!(b.insert(250));
2354 assert!(b.insert(11));
2355 assert!(b.insert(200));
2357 assert!(!a.is_subset(&b));
2358 assert!(!a.is_superset(&b));
2359 assert!(!b.is_subset(&a));
2360 assert!(!b.is_superset(&a));
2362 assert!(b.insert(5));
2364 assert!(a.is_subset(&b));
2365 assert!(!a.is_superset(&b));
2366 assert!(!b.is_subset(&a));
2367 assert!(b.is_superset(&a));
2372 let mut a = HashSet::new();
2373 for i in range(0u, 32) {
2374 assert!(a.insert(i));
2376 let mut observed: u32 = 0;
2378 observed |= 1 << *k;
2380 assert_eq!(observed, 0xFFFF_FFFF);
2384 fn test_intersection() {
2385 let mut a = HashSet::new();
2386 let mut b = HashSet::new();
2388 assert!(a.insert(11i));
2389 assert!(a.insert(1));
2390 assert!(a.insert(3));
2391 assert!(a.insert(77));
2392 assert!(a.insert(103));
2393 assert!(a.insert(5));
2394 assert!(a.insert(-5));
2396 assert!(b.insert(2i));
2397 assert!(b.insert(11));
2398 assert!(b.insert(77));
2399 assert!(b.insert(-9));
2400 assert!(b.insert(-42));
2401 assert!(b.insert(5));
2402 assert!(b.insert(3));
2405 let expected = [3, 5, 11, 77];
2406 for x in a.intersection(&b) {
2407 assert!(expected.contains(x));
2410 assert_eq!(i, expected.len());
2414 fn test_difference() {
2415 let mut a = HashSet::new();
2416 let mut b = HashSet::new();
2418 assert!(a.insert(1i));
2419 assert!(a.insert(3));
2420 assert!(a.insert(5));
2421 assert!(a.insert(9));
2422 assert!(a.insert(11));
2424 assert!(b.insert(3i));
2425 assert!(b.insert(9));
2428 let expected = [1, 5, 11];
2429 for x in a.difference(&b) {
2430 assert!(expected.contains(x));
2433 assert_eq!(i, expected.len());
2437 fn test_symmetric_difference() {
2438 let mut a = HashSet::new();
2439 let mut b = HashSet::new();
2441 assert!(a.insert(1i));
2442 assert!(a.insert(3));
2443 assert!(a.insert(5));
2444 assert!(a.insert(9));
2445 assert!(a.insert(11));
2447 assert!(b.insert(-2i));
2448 assert!(b.insert(3));
2449 assert!(b.insert(9));
2450 assert!(b.insert(14));
2451 assert!(b.insert(22));
2454 let expected = [-2, 1, 5, 11, 14, 22];
2455 for x in a.symmetric_difference(&b) {
2456 assert!(expected.contains(x));
2459 assert_eq!(i, expected.len());
2464 let mut a = HashSet::new();
2465 let mut b = HashSet::new();
2467 assert!(a.insert(1i));
2468 assert!(a.insert(3));
2469 assert!(a.insert(5));
2470 assert!(a.insert(9));
2471 assert!(a.insert(11));
2472 assert!(a.insert(16));
2473 assert!(a.insert(19));
2474 assert!(a.insert(24));
2476 assert!(b.insert(-2i));
2477 assert!(b.insert(1));
2478 assert!(b.insert(5));
2479 assert!(b.insert(9));
2480 assert!(b.insert(13));
2481 assert!(b.insert(19));
2484 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
2485 for x in a.union(&b) {
2486 assert!(expected.contains(x));
2489 assert_eq!(i, expected.len());
2493 fn test_from_iter() {
2494 let xs = [1i, 2, 3, 4, 5, 6, 7, 8, 9];
2496 let set: HashSet<int> = xs.iter().map(|&x| x).collect();
2498 for x in xs.iter() {
2499 assert!(set.contains(x));
2504 fn test_move_iter() {
2506 let mut hs = HashSet::new();
2514 let v = hs.move_iter().collect::<Vec<char>>();
2515 assert!(['a', 'b'] == v.as_slice() || ['b', 'a'] == v.as_slice());
2520 // These constants once happened to expose a bug in insert().
2521 // I'm keeping them around to prevent a regression.
2522 let mut s1 = HashSet::new();
2528 let mut s2 = HashSet::new();
2542 let mut set: HashSet<int> = HashSet::new();
2543 let empty: HashSet<int> = HashSet::new();
2548 let set_str = format!("{}", set);
2550 assert!(set_str == "{1, 2}".to_string() || set_str == "{2, 1}".to_string());
2551 assert_eq!(format!("{}", empty), "{}".to_string());
2560 use self::test::Bencher;
2561 use iter::{range_inclusive};
2564 fn new_drop(b : &mut Bencher) {
2568 let m : HashMap<int, int> = HashMap::new();
2569 assert_eq!(m.len(), 0);
2574 fn new_insert_drop(b : &mut Bencher) {
2578 let mut m = HashMap::new();
2580 assert_eq!(m.len(), 1);
2585 fn insert(b: &mut Bencher) {
2588 let mut m = HashMap::new();
2590 for i in range_inclusive(1i, 1000) {
2603 fn find_existing(b: &mut Bencher) {
2606 let mut m = HashMap::new();
2608 for i in range_inclusive(1i, 1000) {
2613 for i in range_inclusive(1i, 1000) {
2620 fn find_nonexisting(b: &mut Bencher) {
2623 let mut m = HashMap::new();
2625 for i in range_inclusive(1i, 1000) {
2630 for i in range_inclusive(1001i, 2000) {
2637 fn hashmap_as_queue(b: &mut Bencher) {
2640 let mut m = HashMap::new();
2642 for i in range_inclusive(1i, 1000) {
2650 m.insert(k + 1000, k + 1000);
2656 fn find_pop_insert(b: &mut Bencher) {
2659 let mut m = HashMap::new();
2661 for i in range_inclusive(1i, 1000) {
2669 m.find(&(k + 2000));
2671 m.insert(k + 1000, k + 1000);