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 pub use self::Entry::*;
14 use self::SearchResult::*;
15 use self::VacantEntryState::*;
17 use borrow::BorrowFrom;
19 use cmp::{max, Eq, Equiv, PartialEq};
22 use hash::{Hash, Hasher, RandomSipHasher};
23 use iter::{mod, Iterator, IteratorExt, FromIterator, Extend};
25 use mem::{mod, replace};
26 use num::{Int, UnsignedInt};
27 use ops::{Deref, Index, IndexMut};
29 use option::Option::{Some, None};
31 use result::Result::{Ok, Err};
46 const INITIAL_LOG2_CAP: uint = 5;
47 pub const INITIAL_CAPACITY: uint = 1 << INITIAL_LOG2_CAP; // 2^5
49 /// The default behavior of HashMap implements a load factor of 90.9%.
50 /// This behavior is characterized by the following condition:
52 /// - if size > 0.909 * capacity: grow the map
54 struct DefaultResizePolicy;
56 impl DefaultResizePolicy {
57 fn new() -> DefaultResizePolicy {
62 fn min_capacity(&self, usable_size: uint) -> uint {
63 // Here, we are rephrasing the logic by specifying the lower limit
66 // - if `cap < size * 1.1`: grow the map
70 /// An inverse of `min_capacity`, approximately.
72 fn usable_capacity(&self, cap: uint) -> uint {
73 // As the number of entries approaches usable capacity,
74 // min_capacity(size) must be smaller than the internal capacity,
75 // so that the map is not resized:
76 // `min_capacity(usable_capacity(x)) <= x`.
77 // The lef-hand side can only be smaller due to flooring by integer
80 // This doesn't have to be checked for overflow since allocation size
81 // in bytes will overflow earlier than multiplication by 10.
87 fn test_resize_policy() {
89 let rp = DefaultResizePolicy;
90 for n in range(0u, 1000) {
91 assert!(rp.min_capacity(rp.usable_capacity(n)) <= n);
92 assert!(rp.usable_capacity(rp.min_capacity(n)) <= n);
96 // The main performance trick in this hashmap is called Robin Hood Hashing.
97 // It gains its excellent performance from one essential operation:
99 // If an insertion collides with an existing element, and that element's
100 // "probe distance" (how far away the element is from its ideal location)
101 // is higher than how far we've already probed, swap the elements.
103 // This massively lowers variance in probe distance, and allows us to get very
104 // high load factors with good performance. The 90% load factor I use is rather
107 // > Why a load factor of approximately 90%?
109 // In general, all the distances to initial buckets will converge on the mean.
110 // At a load factor of α, the odds of finding the target bucket after k
111 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
112 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
113 // this down to make the math easier on the CPU and avoid its FPU.
114 // Since on average we start the probing in the middle of a cache line, this
115 // strategy pulls in two cache lines of hashes on every lookup. I think that's
116 // pretty good, but if you want to trade off some space, it could go down to one
117 // cache line on average with an α of 0.84.
119 // > Wait, what? Where did you get 1-α^k from?
121 // On the first probe, your odds of a collision with an existing element is α.
122 // The odds of doing this twice in a row is approximately α^2. For three times,
123 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
124 // colliding after k tries is 1-α^k.
126 // The paper from 1986 cited below mentions an implementation which keeps track
127 // of the distance-to-initial-bucket histogram. This approach is not suitable
128 // for modern architectures because it requires maintaining an internal data
129 // structure. This allows very good first guesses, but we are most concerned
130 // with guessing entire cache lines, not individual indexes. Furthermore, array
131 // accesses are no longer linear and in one direction, as we have now. There
132 // is also memory and cache pressure that this would entail that would be very
133 // difficult to properly see in a microbenchmark.
135 // ## Future Improvements (FIXME!)
137 // Allow the load factor to be changed dynamically and/or at initialization.
139 // Also, would it be possible for us to reuse storage when growing the
140 // underlying table? This is exactly the use case for 'realloc', and may
141 // be worth exploring.
143 // ## Future Optimizations (FIXME!)
145 // Another possible design choice that I made without any real reason is
146 // parameterizing the raw table over keys and values. Technically, all we need
147 // is the size and alignment of keys and values, and the code should be just as
148 // efficient (well, we might need one for power-of-two size and one for not...).
149 // This has the potential to reduce code bloat in rust executables, without
150 // really losing anything except 4 words (key size, key alignment, val size,
151 // val alignment) which can be passed in to every call of a `RawTable` function.
152 // This would definitely be an avenue worth exploring if people start complaining
153 // about the size of rust executables.
155 // Annotate exceedingly likely branches in `table::make_hash`
156 // and `search_hashed` to reduce instruction cache pressure
157 // and mispredictions once it becomes possible (blocked on issue #11092).
159 // Shrinking the table could simply reallocate in place after moving buckets
160 // to the first half.
162 // The growth algorithm (fragment of the Proof of Correctness)
163 // --------------------
165 // The growth algorithm is basically a fast path of the naive reinsertion-
166 // during-resize algorithm. Other paths should never be taken.
168 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
169 // by allocating a new table of capacity `2n`, and then individually reinsert
170 // each element in the old table into the new one. This guarantees that the
171 // new table is a valid robin hood hashtable with all the desired statistical
172 // properties. Remark that the order we reinsert the elements in should not
173 // matter. For simplicity and efficiency, we will consider only linear
174 // reinsertions, which consist of reinserting all elements in the old table
175 // into the new one by increasing order of index. However we will not be
176 // starting our reinsertions from index 0 in general. If we start from index
177 // i, for the purpose of reinsertion we will consider all elements with real
178 // index j < i to have virtual index n + j.
180 // Our hash generation scheme consists of generating a 64-bit hash and
181 // truncating the most significant bits. When moving to the new table, we
182 // simply introduce a new bit to the front of the hash. Therefore, if an
183 // elements has ideal index i in the old table, it can have one of two ideal
184 // locations in the new table. If the new bit is 0, then the new ideal index
185 // is i. If the new bit is 1, then the new ideal index is n + i. Intutively,
186 // we are producing two independent tables of size n, and for each element we
187 // independently choose which table to insert it into with equal probability.
188 // However the rather than wrapping around themselves on overflowing their
189 // indexes, the first table overflows into the first, and the first into the
190 // second. Visually, our new table will look something like:
192 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
194 // Where x's are elements inserted into the first table, y's are elements
195 // inserted into the second, and _'s are empty sections. We now define a few
196 // key concepts that we will use later. Note that this is a very abstract
197 // perspective of the table. A real resized table would be at least half
200 // Theorem: A linear robin hood reinsertion from the first ideal element
201 // produces identical results to a linear naive reinsertion from the same
204 // FIXME(Gankro, pczarn): review the proof and put it all in a separate doc.rs
206 /// A hash map implementation which uses linear probing with Robin
207 /// Hood bucket stealing.
209 /// The hashes are all keyed by the task-local random number generator
210 /// on creation by default. This means that the ordering of the keys is
211 /// randomized, but makes the tables more resistant to
212 /// denial-of-service attacks (Hash DoS). This behaviour can be
213 /// overridden with one of the constructors.
215 /// It is required that the keys implement the `Eq` and `Hash` traits, although
216 /// this can frequently be achieved by using `#[deriving(Eq, Hash)]`.
218 /// Relevant papers/articles:
220 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
221 /// 2. Emmanuel Goossaert. ["Robin Hood
222 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
223 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
224 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
229 /// use std::collections::HashMap;
231 /// // type inference lets us omit an explicit type signature (which
232 /// // would be `HashMap<&str, &str>` in this example).
233 /// let mut book_reviews = HashMap::new();
235 /// // review some books.
236 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
237 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
238 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
239 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
241 /// // check for a specific one.
242 /// if !book_reviews.contains_key(&("Les Misérables")) {
243 /// println!("We've got {} reviews, but Les Misérables ain't one.",
244 /// book_reviews.len());
247 /// // oops, this review has a lot of spelling mistakes, let's delete it.
248 /// book_reviews.remove(&("The Adventures of Sherlock Holmes"));
250 /// // look up the values associated with some keys.
251 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
252 /// for book in to_find.iter() {
253 /// match book_reviews.get(book) {
254 /// Some(review) => println!("{}: {}", *book, *review),
255 /// None => println!("{} is unreviewed.", *book)
259 /// // iterate over everything.
260 /// for (book, review) in book_reviews.iter() {
261 /// println!("{}: \"{}\"", *book, *review);
265 /// The easiest way to use `HashMap` with a custom type is to derive `Eq` and `Hash`.
266 /// We must also derive `PartialEq`.
269 /// use std::collections::HashMap;
271 /// #[deriving(Hash, Eq, PartialEq, Show)]
272 /// struct Viking<'a> {
277 /// let mut vikings = HashMap::new();
279 /// vikings.insert("Norway", Viking { name: "Einar", power: 9u });
280 /// vikings.insert("Denmark", Viking { name: "Olaf", power: 4u });
281 /// vikings.insert("Iceland", Viking { name: "Harald", power: 8u });
283 /// // Use derived implementation to print the vikings.
284 /// for (land, viking) in vikings.iter() {
285 /// println!("{} at {}", viking, land);
289 pub struct HashMap<K, V, H = RandomSipHasher> {
290 // All hashes are keyed on these values, to prevent hash collision attacks.
293 table: RawTable<K, V>,
295 resize_policy: DefaultResizePolicy,
298 /// Search for a pre-hashed key.
299 fn search_hashed<K, V, M: Deref<RawTable<K, V>>>(table: M,
301 is_match: |&K| -> bool)
302 -> SearchResult<K, V, M> {
303 let size = table.size();
304 let mut probe = Bucket::new(table, hash);
305 let ib = probe.index();
307 while probe.index() != ib + size {
308 let full = match probe.peek() {
309 Empty(b) => return TableRef(b.into_table()), // hit an empty bucket
313 if full.distance() + ib < full.index() {
314 // We can finish the search early if we hit any bucket
315 // with a lower distance to initial bucket than we've probed.
316 return TableRef(full.into_table());
319 // If the hash doesn't match, it can't be this one..
320 if *hash == full.hash() {
322 let (k, _) = full.read();
326 // If the key doesn't match, it can't be this one..
328 return FoundExisting(full);
335 TableRef(probe.into_table())
338 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
339 let (empty, retkey, retval) = starting_bucket.take();
340 let mut gap = match empty.gap_peek() {
342 None => return (retkey, retval)
345 while gap.full().distance() != 0 {
346 gap = match gap.shift() {
352 // Now we've done all our shifting. Return the value we grabbed earlier.
353 return (retkey, retval);
356 /// Perform robin hood bucket stealing at the given `bucket`. You must
357 /// also pass the position of that bucket's initial bucket so we don't have
358 /// to recalculate it.
360 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
361 fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
367 let starting_index = bucket.index();
369 let table = bucket.table(); // FIXME "lifetime too short".
372 // There can be at most `size - dib` buckets to displace, because
373 // in the worst case, there are `size` elements and we already are
374 // `distance` buckets away from the initial one.
375 let idx_end = starting_index + size - bucket.distance();
378 let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
380 let probe = bucket.next();
381 assert!(probe.index() != idx_end);
383 let full_bucket = match probe.peek() {
384 table::Empty(bucket) => {
386 let b = bucket.put(old_hash, old_key, old_val);
387 // Now that it's stolen, just read the value's pointer
388 // right out of the table!
389 let (_, v) = Bucket::at_index(b.into_table(), starting_index).peek()
394 table::Full(bucket) => bucket
397 let probe_ib = full_bucket.index() - full_bucket.distance();
399 bucket = full_bucket;
401 // Robin hood! Steal the spot.
413 /// A result that works like Option<FullBucket<..>> but preserves
414 /// the reference that grants us access to the table in any case.
415 enum SearchResult<K, V, M> {
416 // This is an entry that holds the given key:
417 FoundExisting(FullBucket<K, V, M>),
419 // There was no such entry. The reference is given back:
423 impl<K, V, M> SearchResult<K, V, M> {
424 fn into_option(self) -> Option<FullBucket<K, V, M>> {
426 FoundExisting(bucket) => Some(bucket),
432 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
433 fn make_hash<Sized? X: Hash<S>>(&self, x: &X) -> SafeHash {
434 table::make_hash(&self.hasher, x)
438 fn search_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, q: &Q)
439 -> Option<FullBucketImm<'a, K, V>> {
440 let hash = self.make_hash(q);
441 search_hashed(&self.table, &hash, |k| q.equiv(k)).into_option()
445 fn search_equiv_mut<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a mut self, q: &Q)
446 -> Option<FullBucketMut<'a, K, V>> {
447 let hash = self.make_hash(q);
448 search_hashed(&mut self.table, &hash, |k| q.equiv(k)).into_option()
451 /// Search for a key, yielding the index if it's found in the hashtable.
452 /// If you already have the hash for the key lying around, use
454 fn search<'a, Sized? Q>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
455 where Q: BorrowFrom<K> + Eq + Hash<S>
457 let hash = self.make_hash(q);
458 search_hashed(&self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
462 fn search_mut<'a, Sized? Q>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
463 where Q: BorrowFrom<K> + Eq + Hash<S>
465 let hash = self.make_hash(q);
466 search_hashed(&mut self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
470 // The caller should ensure that invariants by Robin Hood Hashing hold.
471 fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
472 let cap = self.table.capacity();
473 let mut buckets = Bucket::new(&mut self.table, &hash);
474 let ib = buckets.index();
476 while buckets.index() != ib + cap {
477 // We don't need to compare hashes for value swap.
478 // Not even DIBs for Robin Hood.
479 buckets = match buckets.peek() {
481 empty.put(hash, k, v);
484 Full(b) => b.into_bucket()
488 panic!("Internal HashMap error: Out of space.");
492 impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
493 /// Create an empty HashMap.
498 /// use std::collections::HashMap;
499 /// let mut map: HashMap<&str, int> = HashMap::new();
502 #[unstable = "matches collection reform specification, waiting for dust to settle"]
503 pub fn new() -> HashMap<K, V, RandomSipHasher> {
504 let hasher = RandomSipHasher::new();
505 HashMap::with_hasher(hasher)
508 /// Creates an empty hash map with the given initial capacity.
513 /// use std::collections::HashMap;
514 /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
517 #[unstable = "matches collection reform specification, waiting for dust to settle"]
518 pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
519 let hasher = RandomSipHasher::new();
520 HashMap::with_capacity_and_hasher(capacity, hasher)
524 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
525 /// Creates an empty hashmap which will use the given hasher to hash keys.
527 /// The creates map has the default initial capacity.
532 /// use std::collections::HashMap;
533 /// use std::hash::sip::SipHasher;
535 /// let h = SipHasher::new();
536 /// let mut map = HashMap::with_hasher(h);
537 /// map.insert(1i, 2u);
540 pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
543 resize_policy: DefaultResizePolicy::new(),
544 table: RawTable::new(0),
548 /// Create an empty HashMap with space for at least `capacity`
549 /// elements, using `hasher` to hash the keys.
551 /// Warning: `hasher` is normally randomly generated, and
552 /// is designed to allow HashMaps to be resistant to attacks that
553 /// cause many collisions and very poor performance. Setting it
554 /// manually using this function can expose a DoS attack vector.
559 /// use std::collections::HashMap;
560 /// use std::hash::sip::SipHasher;
562 /// let h = SipHasher::new();
563 /// let mut map = HashMap::with_capacity_and_hasher(10, h);
564 /// map.insert(1i, 2u);
567 pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
568 let resize_policy = DefaultResizePolicy::new();
569 let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
570 let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
571 assert!(internal_cap >= capacity, "capacity overflow");
574 resize_policy: resize_policy,
575 table: RawTable::new(internal_cap),
579 /// Returns the number of elements the map can hold without reallocating.
584 /// use std::collections::HashMap;
585 /// let map: HashMap<int, int> = HashMap::with_capacity(100);
586 /// assert!(map.capacity() >= 100);
589 #[unstable = "matches collection reform specification, waiting for dust to settle"]
590 pub fn capacity(&self) -> uint {
591 self.resize_policy.usable_capacity(self.table.capacity())
594 /// Reserves capacity for at least `additional` more elements to be inserted
595 /// in the `HashMap`. The collection may reserve more space to avoid
596 /// frequent reallocations.
600 /// Panics if the new allocation size overflows `uint`.
605 /// use std::collections::HashMap;
606 /// let mut map: HashMap<&str, int> = HashMap::new();
609 #[unstable = "matches collection reform specification, waiting for dust to settle"]
610 pub fn reserve(&mut self, additional: uint) {
611 let new_size = self.len().checked_add(additional).expect("capacity overflow");
612 let min_cap = self.resize_policy.min_capacity(new_size);
614 // An invalid value shouldn't make us run out of space. This includes
615 // an overflow check.
616 assert!(new_size <= min_cap);
618 if self.table.capacity() < min_cap {
619 let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
620 self.resize(new_capacity);
624 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
625 /// 1) Make sure the new capacity is enough for all the elements, accounting
626 /// for the load factor.
627 /// 2) Ensure new_capacity is a power of two.
628 fn resize(&mut self, new_capacity: uint) {
629 assert!(self.table.size() <= new_capacity);
630 assert!(new_capacity.is_power_of_two());
632 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
633 let old_size = old_table.size();
635 if old_table.capacity() == 0 || old_table.size() == 0 {
640 // Specialization of the other branch.
641 let mut bucket = Bucket::first(&mut old_table);
643 // "So a few of the first shall be last: for many be called,
646 // We'll most likely encounter a few buckets at the beginning that
647 // have their initial buckets near the end of the table. They were
648 // placed at the beginning as the probe wrapped around the table
649 // during insertion. We must skip forward to a bucket that won't
650 // get reinserted too early and won't unfairly steal others spot.
651 // This eliminates the need for robin hood.
653 bucket = match bucket.peek() {
655 if full.distance() == 0 {
656 // This bucket occupies its ideal spot.
657 // It indicates the start of another "cluster".
658 bucket = full.into_bucket();
661 // Leaving this bucket in the last cluster for later.
665 // Encountered a hole between clusters.
672 // This is how the buckets might be laid out in memory:
673 // ($ marks an initialized bucket)
675 // |$$$_$$$$$$_$$$$$|
677 // But we've skipped the entire initial cluster of buckets
678 // and will continue iteration in this order:
681 // ^ wrap around once end is reached
684 // ^ exit once table.size == 0
686 bucket = match bucket.peek() {
688 let h = bucket.hash();
689 let (b, k, v) = bucket.take();
690 self.insert_hashed_ordered(h, k, v);
692 let t = b.table(); // FIXME "lifetime too short".
693 if t.size() == 0 { break }
697 Empty(b) => b.into_bucket()
702 assert_eq!(self.table.size(), old_size);
705 /// Shrinks the capacity of the map as much as possible. It will drop
706 /// down as much as possible while maintaining the internal rules
707 /// and possibly leaving some space in accordance with the resize policy.
712 /// use std::collections::HashMap;
714 /// let mut map: HashMap<int, int> = HashMap::with_capacity(100);
715 /// map.insert(1, 2);
716 /// map.insert(3, 4);
717 /// assert!(map.capacity() >= 100);
718 /// map.shrink_to_fit();
719 /// assert!(map.capacity() >= 2);
721 #[unstable = "matches collection reform specification, waiting for dust to settle"]
722 pub fn shrink_to_fit(&mut self) {
723 let min_capacity = self.resize_policy.min_capacity(self.len());
724 let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
726 // An invalid value shouldn't make us run out of space.
727 debug_assert!(self.len() <= min_capacity);
729 if self.table.capacity() != min_capacity {
730 let old_table = replace(&mut self.table, RawTable::new(min_capacity));
731 let old_size = old_table.size();
733 // Shrink the table. Naive algorithm for resizing:
734 for (h, k, v) in old_table.into_iter() {
735 self.insert_hashed_nocheck(h, k, v);
738 debug_assert_eq!(self.table.size(), old_size);
742 /// Insert a pre-hashed key-value pair, without first checking
743 /// that there's enough room in the buckets. Returns a reference to the
744 /// newly insert value.
746 /// If the key already exists, the hashtable will be returned untouched
747 /// and a reference to the existing element will be returned.
748 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
749 self.insert_or_replace_with(hash, k, v, |_, _, _| ())
752 fn insert_or_replace_with<'a>(&'a mut self,
756 found_existing: |&mut K, &mut V, V|)
758 // Worst case, we'll find one empty bucket among `size + 1` buckets.
759 let size = self.table.size();
760 let mut probe = Bucket::new(&mut self.table, &hash);
761 let ib = probe.index();
764 let mut bucket = match probe.peek() {
767 let bucket = bucket.put(hash, k, v);
768 let (_, val) = bucket.into_mut_refs();
771 Full(bucket) => bucket
774 if bucket.hash() == hash {
776 let (bucket_k, _) = bucket.read_mut();
780 let (bucket_k, bucket_v) = bucket.into_mut_refs();
781 debug_assert!(k == *bucket_k);
782 // Key already exists. Get its reference.
783 found_existing(bucket_k, bucket_v, v);
788 let robin_ib = bucket.index() as int - bucket.distance() as int;
790 if (ib as int) < robin_ib {
791 // Found a luckier bucket than me. Better steal his spot.
792 return robin_hood(bucket, robin_ib as uint, hash, k, v);
795 probe = bucket.next();
796 assert!(probe.index() != ib + size + 1);
800 /// Deprecated: use `contains_key` and `BorrowFrom` instead.
801 #[deprecated = "use contains_key and BorrowFrom instead"]
802 pub fn contains_key_equiv<Sized? Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
803 self.search_equiv(key).is_some()
806 /// Deprecated: use `get` and `BorrowFrom` instead.
807 #[deprecated = "use get and BorrowFrom instead"]
808 pub fn find_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
809 match self.search_equiv(k) {
812 let (_, v_ref) = bucket.into_refs();
818 /// Deprecated: use `remove` and `BorrowFrom` instead.
819 #[deprecated = "use remove and BorrowFrom instead"]
820 pub fn pop_equiv<Sized? Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
821 if self.table.size() == 0 {
827 match self.search_equiv_mut(k) {
829 let (_k, val) = pop_internal(bucket);
836 /// An iterator visiting all keys in arbitrary order.
837 /// Iterator element type is `&'a K`.
842 /// use std::collections::HashMap;
844 /// let mut map = HashMap::new();
845 /// map.insert("a", 1i);
846 /// map.insert("b", 2);
847 /// map.insert("c", 3);
849 /// for key in map.keys() {
850 /// println!("{}", key);
853 #[unstable = "matches collection reform specification, waiting for dust to settle"]
854 pub fn keys(&self) -> Keys<K, V> {
855 self.iter().map(|(k, _v)| k)
858 /// An iterator visiting all values in arbitrary order.
859 /// Iterator element type is `&'a V`.
864 /// use std::collections::HashMap;
866 /// let mut map = HashMap::new();
867 /// map.insert("a", 1i);
868 /// map.insert("b", 2);
869 /// map.insert("c", 3);
871 /// for key in map.values() {
872 /// println!("{}", key);
875 #[unstable = "matches collection reform specification, waiting for dust to settle"]
876 pub fn values(&self) -> Values<K, V> {
877 self.iter().map(|(_k, v)| v)
880 /// An iterator visiting all key-value pairs in arbitrary order.
881 /// Iterator element type is `(&'a K, &'a V)`.
886 /// use std::collections::HashMap;
888 /// let mut map = HashMap::new();
889 /// map.insert("a", 1i);
890 /// map.insert("b", 2);
891 /// map.insert("c", 3);
893 /// for (key, val) in map.iter() {
894 /// println!("key: {} val: {}", key, val);
897 #[unstable = "matches collection reform specification, waiting for dust to settle"]
898 pub fn iter(&self) -> Entries<K, V> {
899 Entries { inner: self.table.iter() }
902 /// An iterator visiting all key-value pairs in arbitrary order,
903 /// with mutable references to the values.
904 /// Iterator element type is `(&'a K, &'a mut V)`.
909 /// use std::collections::HashMap;
911 /// let mut map = HashMap::new();
912 /// map.insert("a", 1i);
913 /// map.insert("b", 2);
914 /// map.insert("c", 3);
916 /// // Update all values
917 /// for (_, val) in map.iter_mut() {
921 /// for (key, val) in map.iter() {
922 /// println!("key: {} val: {}", key, val);
925 #[unstable = "matches collection reform specification, waiting for dust to settle"]
926 pub fn iter_mut(&mut self) -> MutEntries<K, V> {
927 MutEntries { inner: self.table.iter_mut() }
930 /// Creates a consuming iterator, that is, one that moves each key-value
931 /// pair out of the map in arbitrary order. The map cannot be used after
937 /// use std::collections::HashMap;
939 /// let mut map = HashMap::new();
940 /// map.insert("a", 1i);
941 /// map.insert("b", 2);
942 /// map.insert("c", 3);
944 /// // Not possible with .iter()
945 /// let vec: Vec<(&str, int)> = map.into_iter().collect();
947 #[unstable = "matches collection reform specification, waiting for dust to settle"]
948 pub fn into_iter(self) -> MoveEntries<K, V> {
950 inner: self.table.into_iter().map(|(_, k, v)| (k, v))
954 /// Gets the given key's corresponding entry in the map for in-place manipulation
955 pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V> {
959 let hash = self.make_hash(&key);
960 search_entry_hashed(&mut self.table, hash, key)
963 /// Return the number of elements in the map.
968 /// use std::collections::HashMap;
970 /// let mut a = HashMap::new();
971 /// assert_eq!(a.len(), 0);
972 /// a.insert(1u, "a");
973 /// assert_eq!(a.len(), 1);
975 #[unstable = "matches collection reform specification, waiting for dust to settle"]
976 pub fn len(&self) -> uint { self.table.size() }
978 /// Return true if the map contains no elements.
983 /// use std::collections::HashMap;
985 /// let mut a = HashMap::new();
986 /// assert!(a.is_empty());
987 /// a.insert(1u, "a");
988 /// assert!(!a.is_empty());
991 #[unstable = "matches collection reform specification, waiting for dust to settle"]
992 pub fn is_empty(&self) -> bool { self.len() == 0 }
994 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1000 /// use std::collections::HashMap;
1002 /// let mut a = HashMap::new();
1003 /// a.insert(1u, "a");
1005 /// assert!(a.is_empty());
1007 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1008 pub fn clear(&mut self) {
1009 let cap = self.table.capacity();
1010 let mut buckets = Bucket::first(&mut self.table);
1012 while buckets.index() != cap {
1013 buckets = match buckets.peek() {
1014 Empty(b) => b.next(),
1016 let (b, _, _) = full.take();
1023 /// Deprecated: Renamed to `get`.
1024 #[deprecated = "Renamed to `get`"]
1025 pub fn find(&self, k: &K) -> Option<&V> {
1029 /// Returns a reference to the value corresponding to the key.
1031 /// The key may be any borrowed form of the map's key type, but
1032 /// `Hash` and `Eq` on the borrowed form *must* match those for
1038 /// use std::collections::HashMap;
1040 /// let mut map = HashMap::new();
1041 /// map.insert(1u, "a");
1042 /// assert_eq!(map.get(&1), Some(&"a"));
1043 /// assert_eq!(map.get(&2), None);
1045 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1046 pub fn get<Sized? Q>(&self, k: &Q) -> Option<&V>
1047 where Q: Hash<S> + Eq + BorrowFrom<K>
1049 self.search(k).map(|bucket| {
1050 let (_, v) = bucket.into_refs();
1055 /// Returns true if the map contains a value for the specified key.
1057 /// The key may be any borrowed form of the map's key type, but
1058 /// `Hash` and `Eq` on the borrowed form *must* match those for
1064 /// use std::collections::HashMap;
1066 /// let mut map = HashMap::new();
1067 /// map.insert(1u, "a");
1068 /// assert_eq!(map.contains_key(&1), true);
1069 /// assert_eq!(map.contains_key(&2), false);
1071 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1072 pub fn contains_key<Sized? Q>(&self, k: &Q) -> bool
1073 where Q: Hash<S> + Eq + BorrowFrom<K>
1075 self.search(k).is_some()
1078 /// Deprecated: Renamed to `get_mut`.
1079 #[deprecated = "Renamed to `get_mut`"]
1080 pub fn find_mut(&mut self, k: &K) -> Option<&mut V> {
1084 /// Returns a mutable reference to the value corresponding to the key.
1086 /// The key may be any borrowed form of the map's key type, but
1087 /// `Hash` and `Eq` on the borrowed form *must* match those for
1093 /// use std::collections::HashMap;
1095 /// let mut map = HashMap::new();
1096 /// map.insert(1u, "a");
1097 /// match map.get_mut(&1) {
1098 /// Some(x) => *x = "b",
1101 /// assert_eq!(map[1], "b");
1103 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1104 pub fn get_mut<Sized? Q>(&mut self, k: &Q) -> Option<&mut V>
1105 where Q: Hash<S> + Eq + BorrowFrom<K>
1107 match self.search_mut(k) {
1109 let (_, v) = bucket.into_mut_refs();
1116 /// Deprecated: Renamed to `insert`.
1117 #[deprecated = "Renamed to `insert`"]
1118 pub fn swap(&mut self, k: K, v: V) -> Option<V> {
1122 /// Inserts a key-value pair from the map. If the key already had a value
1123 /// present in the map, that value is returned. Otherwise, `None` is returned.
1128 /// use std::collections::HashMap;
1130 /// let mut map = HashMap::new();
1131 /// assert_eq!(map.insert(37u, "a"), None);
1132 /// assert_eq!(map.is_empty(), false);
1134 /// map.insert(37, "b");
1135 /// assert_eq!(map.insert(37, "c"), Some("b"));
1136 /// assert_eq!(map[37], "c");
1138 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1139 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1140 let hash = self.make_hash(&k);
1143 let mut retval = None;
1144 self.insert_or_replace_with(hash, k, v, |_, val_ref, val| {
1145 retval = Some(replace(val_ref, val));
1150 /// Deprecated: Renamed to `remove`.
1151 #[deprecated = "Renamed to `remove`"]
1152 pub fn pop(&mut self, k: &K) -> Option<V> {
1156 /// Removes a key from the map, returning the value at the key if the key
1157 /// was previously in the map.
1159 /// The key may be any borrowed form of the map's key type, but
1160 /// `Hash` and `Eq` on the borrowed form *must* match those for
1166 /// use std::collections::HashMap;
1168 /// let mut map = HashMap::new();
1169 /// map.insert(1u, "a");
1170 /// assert_eq!(map.remove(&1), Some("a"));
1171 /// assert_eq!(map.remove(&1), None);
1173 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1174 pub fn remove<Sized? Q>(&mut self, k: &Q) -> Option<V>
1175 where Q: Hash<S> + Eq + BorrowFrom<K>
1177 if self.table.size() == 0 {
1181 self.search_mut(k).map(|bucket| {
1182 let (_k, val) = pop_internal(bucket);
1188 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
1189 -> Entry<'a, K, V> {
1190 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1191 let size = table.size();
1192 let mut probe = Bucket::new(table, &hash);
1193 let ib = probe.index();
1196 let bucket = match probe.peek() {
1199 return Vacant(VacantEntry {
1202 elem: NoElem(bucket),
1205 Full(bucket) => bucket
1208 if bucket.hash() == hash {
1210 let (bucket_k, _) = bucket.read();
1215 return Occupied(OccupiedEntry{
1221 let robin_ib = bucket.index() as int - bucket.distance() as int;
1223 if (ib as int) < robin_ib {
1224 // Found a luckier bucket than me. Better steal his spot.
1225 return Vacant(VacantEntry {
1228 elem: NeqElem(bucket, robin_ib as uint),
1232 probe = bucket.next();
1233 assert!(probe.index() != ib + size + 1);
1237 impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
1238 /// Deprecated: Use `map.get(k).cloned()`.
1240 /// Return a copy of the value corresponding to the key.
1241 #[deprecated = "Use `map.get(k).cloned()`"]
1242 pub fn find_copy(&self, k: &K) -> Option<V> {
1243 self.get(k).cloned()
1246 /// Deprecated: Use `map[k].clone()`.
1248 /// Return a copy of the value corresponding to the key.
1249 #[deprecated = "Use `map[k].clone()`"]
1250 pub fn get_copy(&self, k: &K) -> V {
1255 impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
1256 fn eq(&self, other: &HashMap<K, V, H>) -> bool {
1257 if self.len() != other.len() { return false; }
1259 self.iter().all(|(key, value)|
1260 other.get(key).map_or(false, |v| *value == *v)
1265 impl<K: Eq + Hash<S>, V: Eq, S, H: Hasher<S>> Eq for HashMap<K, V, H> {}
1267 impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
1268 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1269 try!(write!(f, "{{"));
1271 for (i, (k, v)) in self.iter().enumerate() {
1272 if i != 0 { try!(write!(f, ", ")); }
1273 try!(write!(f, "{}: {}", *k, *v));
1280 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
1281 fn default() -> HashMap<K, V, H> {
1282 HashMap::with_hasher(Default::default())
1286 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> Index<Q, V> for HashMap<K, V, H>
1287 where Q: BorrowFrom<K> + Hash<S> + Eq
1290 fn index<'a>(&'a self, index: &Q) -> &'a V {
1291 self.get(index).expect("no entry found for key")
1295 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> IndexMut<Q, V> for HashMap<K, V, H>
1296 where Q: BorrowFrom<K> + Hash<S> + Eq
1299 fn index_mut<'a>(&'a mut self, index: &Q) -> &'a mut V {
1300 match self.get_mut(index) {
1302 None => panic!("no entry found for key")
1307 /// HashMap iterator
1308 pub struct Entries<'a, K: 'a, V: 'a> {
1309 inner: table::Entries<'a, K, V>
1312 /// HashMap mutable values iterator
1313 pub struct MutEntries<'a, K: 'a, V: 'a> {
1314 inner: table::MutEntries<'a, K, V>
1317 /// HashMap move iterator
1318 pub struct MoveEntries<K, V> {
1319 inner: iter::Map<'static, (SafeHash, K, V), (K, V), table::MoveEntries<K, V>>
1322 /// A view into a single occupied location in a HashMap
1323 pub struct OccupiedEntry<'a, K:'a, V:'a> {
1324 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1327 /// A view into a single empty location in a HashMap
1328 pub struct VacantEntry<'a, K:'a, V:'a> {
1331 elem: VacantEntryState<K,V, &'a mut RawTable<K, V>>,
1334 /// A view into a single location in a map, which may be vacant or occupied
1335 pub enum Entry<'a, K:'a, V:'a> {
1336 /// An occupied Entry
1337 Occupied(OccupiedEntry<'a, K, V>),
1339 Vacant(VacantEntry<'a, K, V>),
1342 /// Possible states of a VacantEntry
1343 enum VacantEntryState<K, V, M> {
1344 /// The index is occupied, but the key to insert has precedence,
1345 /// and will kick the current one out on insertion
1346 NeqElem(FullBucket<K, V, M>, uint),
1347 /// The index is genuinely vacant
1348 NoElem(EmptyBucket<K, V, M>),
1351 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
1353 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1357 fn size_hint(&self) -> (uint, Option<uint>) {
1358 self.inner.size_hint()
1362 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
1364 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1368 fn size_hint(&self) -> (uint, Option<uint>) {
1369 self.inner.size_hint()
1373 impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
1375 fn next(&mut self) -> Option<(K, V)> {
1379 fn size_hint(&self) -> (uint, Option<uint>) {
1380 self.inner.size_hint()
1384 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1385 /// Gets a reference to the value in the entry
1386 pub fn get(&self) -> &V {
1387 let (_, v) = self.elem.read();
1391 /// Gets a mutable reference to the value in the entry
1392 pub fn get_mut(&mut self) -> &mut V {
1393 let (_, v) = self.elem.read_mut();
1397 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1398 /// with a lifetime bound to the map itself
1399 pub fn into_mut(self) -> &'a mut V {
1400 let (_, v) = self.elem.into_mut_refs();
1404 /// Sets the value of the entry, and returns the entry's old value
1405 pub fn set(&mut self, mut value: V) -> V {
1406 let old_value = self.get_mut();
1407 mem::swap(&mut value, old_value);
1411 /// Takes the value out of the entry, and returns it
1412 pub fn take(self) -> V {
1413 let (_, v) = pop_internal(self.elem);
1418 impl<'a, K, V> VacantEntry<'a, K, V> {
1419 /// Sets the value of the entry with the VacantEntry's key,
1420 /// and returns a mutable reference to it
1421 pub fn set(self, value: V) -> &'a mut V {
1423 NeqElem(bucket, ib) => {
1424 robin_hood(bucket, ib, self.hash, self.key, value)
1427 let full = bucket.put(self.hash, self.key, value);
1428 let (_, v) = full.into_mut_refs();
1435 /// HashMap keys iterator
1436 pub type Keys<'a, K, V> =
1437 iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
1439 /// HashMap values iterator
1440 pub type Values<'a, K, V> =
1441 iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
1443 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
1444 fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
1445 let (lower, _) = iter.size_hint();
1446 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1452 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Extend<(K, V)> for HashMap<K, V, H> {
1453 fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
1454 for (k, v) in iter {
1465 use super::{Occupied, Vacant};
1468 use iter::{Iterator,range_inclusive,range_step_inclusive};
1470 use rand::{weak_rng, Rng};
1472 struct KindaIntLike(int);
1474 impl Equiv<int> for KindaIntLike {
1475 fn equiv(&self, other: &int) -> bool {
1476 let KindaIntLike(this) = *self;
1480 impl<S: hash::Writer> hash::Hash<S> for KindaIntLike {
1481 fn hash(&self, state: &mut S) {
1482 let KindaIntLike(this) = *self;
1488 fn test_create_capacity_zero() {
1489 let mut m = HashMap::with_capacity(0);
1491 assert!(m.insert(1i, 1i).is_none());
1493 assert!(m.contains_key(&1));
1494 assert!(!m.contains_key(&0));
1499 let mut m = HashMap::new();
1500 assert_eq!(m.len(), 0);
1501 assert!(m.insert(1i, 2i).is_none());
1502 assert_eq!(m.len(), 1);
1503 assert!(m.insert(2i, 4i).is_none());
1504 assert_eq!(m.len(), 2);
1505 assert_eq!(*m.get(&1).unwrap(), 2);
1506 assert_eq!(*m.get(&2).unwrap(), 4);
1509 thread_local!(static DROP_VECTOR: RefCell<Vec<int>> = RefCell::new(Vec::new()))
1511 #[deriving(Hash, PartialEq, Eq)]
1517 fn new(k: uint) -> Dropable {
1518 DROP_VECTOR.with(|slot| {
1519 slot.borrow_mut()[k] += 1;
1526 impl Drop for Dropable {
1527 fn drop(&mut self) {
1528 DROP_VECTOR.with(|slot| {
1529 slot.borrow_mut()[self.k] -= 1;
1534 impl Clone for Dropable {
1535 fn clone(&self) -> Dropable {
1536 Dropable::new(self.k)
1542 DROP_VECTOR.with(|slot| {
1543 *slot.borrow_mut() = Vec::from_elem(200, 0i);
1547 let mut m = HashMap::new();
1549 DROP_VECTOR.with(|v| {
1550 for i in range(0u, 200) {
1551 assert_eq!(v.borrow()[i], 0);
1555 for i in range(0u, 100) {
1556 let d1 = Dropable::new(i);
1557 let d2 = Dropable::new(i+100);
1561 DROP_VECTOR.with(|v| {
1562 for i in range(0u, 200) {
1563 assert_eq!(v.borrow()[i], 1);
1567 for i in range(0u, 50) {
1568 let k = Dropable::new(i);
1569 let v = m.remove(&k);
1571 assert!(v.is_some());
1573 DROP_VECTOR.with(|v| {
1574 assert_eq!(v.borrow()[i], 1);
1575 assert_eq!(v.borrow()[i+100], 1);
1579 DROP_VECTOR.with(|v| {
1580 for i in range(0u, 50) {
1581 assert_eq!(v.borrow()[i], 0);
1582 assert_eq!(v.borrow()[i+100], 0);
1585 for i in range(50u, 100) {
1586 assert_eq!(v.borrow()[i], 1);
1587 assert_eq!(v.borrow()[i+100], 1);
1592 DROP_VECTOR.with(|v| {
1593 for i in range(0u, 200) {
1594 assert_eq!(v.borrow()[i], 0);
1600 fn test_move_iter_drops() {
1601 DROP_VECTOR.with(|v| {
1602 *v.borrow_mut() = Vec::from_elem(200, 0i);
1606 let mut hm = HashMap::new();
1608 DROP_VECTOR.with(|v| {
1609 for i in range(0u, 200) {
1610 assert_eq!(v.borrow()[i], 0);
1614 for i in range(0u, 100) {
1615 let d1 = Dropable::new(i);
1616 let d2 = Dropable::new(i+100);
1620 DROP_VECTOR.with(|v| {
1621 for i in range(0u, 200) {
1622 assert_eq!(v.borrow()[i], 1);
1629 // By the way, ensure that cloning doesn't screw up the dropping.
1633 let mut half = hm.into_iter().take(50);
1635 DROP_VECTOR.with(|v| {
1636 for i in range(0u, 200) {
1637 assert_eq!(v.borrow()[i], 1);
1643 DROP_VECTOR.with(|v| {
1644 let nk = range(0u, 100).filter(|&i| {
1648 let nv = range(0u, 100).filter(|&i| {
1649 v.borrow()[i+100] == 1
1657 DROP_VECTOR.with(|v| {
1658 for i in range(0u, 200) {
1659 assert_eq!(v.borrow()[i], 0);
1665 fn test_empty_pop() {
1666 let mut m: HashMap<int, bool> = HashMap::new();
1667 assert_eq!(m.remove(&0), None);
1671 fn test_lots_of_insertions() {
1672 let mut m = HashMap::new();
1674 // Try this a few times to make sure we never screw up the hashmap's
1676 for _ in range(0i, 10) {
1677 assert!(m.is_empty());
1679 for i in range_inclusive(1i, 1000) {
1680 assert!(m.insert(i, i).is_none());
1682 for j in range_inclusive(1, i) {
1684 assert_eq!(r, Some(&j));
1687 for j in range_inclusive(i+1, 1000) {
1689 assert_eq!(r, None);
1693 for i in range_inclusive(1001i, 2000) {
1694 assert!(!m.contains_key(&i));
1698 for i in range_inclusive(1i, 1000) {
1699 assert!(m.remove(&i).is_some());
1701 for j in range_inclusive(1, i) {
1702 assert!(!m.contains_key(&j));
1705 for j in range_inclusive(i+1, 1000) {
1706 assert!(m.contains_key(&j));
1710 for i in range_inclusive(1i, 1000) {
1711 assert!(!m.contains_key(&i));
1714 for i in range_inclusive(1i, 1000) {
1715 assert!(m.insert(i, i).is_none());
1719 for i in range_step_inclusive(1000i, 1, -1) {
1720 assert!(m.remove(&i).is_some());
1722 for j in range_inclusive(i, 1000) {
1723 assert!(!m.contains_key(&j));
1726 for j in range_inclusive(1, i-1) {
1727 assert!(m.contains_key(&j));
1734 fn test_find_mut() {
1735 let mut m = HashMap::new();
1736 assert!(m.insert(1i, 12i).is_none());
1737 assert!(m.insert(2i, 8i).is_none());
1738 assert!(m.insert(5i, 14i).is_none());
1740 match m.get_mut(&5) {
1741 None => panic!(), Some(x) => *x = new
1743 assert_eq!(m.get(&5), Some(&new));
1747 fn test_insert_overwrite() {
1748 let mut m = HashMap::new();
1749 assert!(m.insert(1i, 2i).is_none());
1750 assert_eq!(*m.get(&1).unwrap(), 2);
1751 assert!(!m.insert(1i, 3i).is_none());
1752 assert_eq!(*m.get(&1).unwrap(), 3);
1756 fn test_insert_conflicts() {
1757 let mut m = HashMap::with_capacity(4);
1758 assert!(m.insert(1i, 2i).is_none());
1759 assert!(m.insert(5i, 3i).is_none());
1760 assert!(m.insert(9i, 4i).is_none());
1761 assert_eq!(*m.get(&9).unwrap(), 4);
1762 assert_eq!(*m.get(&5).unwrap(), 3);
1763 assert_eq!(*m.get(&1).unwrap(), 2);
1767 fn test_conflict_remove() {
1768 let mut m = HashMap::with_capacity(4);
1769 assert!(m.insert(1i, 2i).is_none());
1770 assert_eq!(*m.get(&1).unwrap(), 2);
1771 assert!(m.insert(5, 3).is_none());
1772 assert_eq!(*m.get(&1).unwrap(), 2);
1773 assert_eq!(*m.get(&5).unwrap(), 3);
1774 assert!(m.insert(9, 4).is_none());
1775 assert_eq!(*m.get(&1).unwrap(), 2);
1776 assert_eq!(*m.get(&5).unwrap(), 3);
1777 assert_eq!(*m.get(&9).unwrap(), 4);
1778 assert!(m.remove(&1).is_some());
1779 assert_eq!(*m.get(&9).unwrap(), 4);
1780 assert_eq!(*m.get(&5).unwrap(), 3);
1784 fn test_is_empty() {
1785 let mut m = HashMap::with_capacity(4);
1786 assert!(m.insert(1i, 2i).is_none());
1787 assert!(!m.is_empty());
1788 assert!(m.remove(&1).is_some());
1789 assert!(m.is_empty());
1794 let mut m = HashMap::new();
1796 assert_eq!(m.remove(&1), Some(2));
1797 assert_eq!(m.remove(&1), None);
1801 #[allow(experimental)]
1802 fn test_pop_equiv() {
1803 let mut m = HashMap::new();
1805 assert_eq!(m.pop_equiv(&KindaIntLike(1)), Some(2));
1806 assert_eq!(m.pop_equiv(&KindaIntLike(1)), None);
1811 let mut m = HashMap::with_capacity(4);
1812 for i in range(0u, 32) {
1813 assert!(m.insert(i, i*2).is_none());
1815 assert_eq!(m.len(), 32);
1817 let mut observed: u32 = 0;
1819 for (k, v) in m.iter() {
1820 assert_eq!(*v, *k * 2);
1821 observed |= 1 << *k;
1823 assert_eq!(observed, 0xFFFF_FFFF);
1828 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1829 let map = vec.into_iter().collect::<HashMap<int, char>>();
1830 let keys = map.keys().map(|&k| k).collect::<Vec<int>>();
1831 assert_eq!(keys.len(), 3);
1832 assert!(keys.contains(&1));
1833 assert!(keys.contains(&2));
1834 assert!(keys.contains(&3));
1839 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1840 let map = vec.into_iter().collect::<HashMap<int, char>>();
1841 let values = map.values().map(|&v| v).collect::<Vec<char>>();
1842 assert_eq!(values.len(), 3);
1843 assert!(values.contains(&'a'));
1844 assert!(values.contains(&'b'));
1845 assert!(values.contains(&'c'));
1850 let mut m = HashMap::new();
1851 assert!(m.get(&1i).is_none());
1855 Some(v) => assert_eq!(*v, 2)
1860 #[allow(deprecated)]
1861 fn test_find_copy() {
1862 let mut m = HashMap::new();
1863 assert!(m.get(&1i).is_none());
1865 for i in range(1i, 10000) {
1867 match m.find_copy(&i) {
1869 Some(v) => assert_eq!(v, i + 7)
1871 for j in range(1i, i/100) {
1872 match m.find_copy(&j) {
1874 Some(v) => assert_eq!(v, j + 7)
1882 let mut m1 = HashMap::new();
1887 let mut m2 = HashMap::new();
1900 let mut map: HashMap<int, int> = HashMap::new();
1901 let empty: HashMap<int, int> = HashMap::new();
1906 let map_str = format!("{}", map);
1908 assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
1909 assert_eq!(format!("{}", empty), "{}");
1914 let mut m = HashMap::new();
1916 assert_eq!(m.len(), 0);
1917 assert!(m.is_empty());
1920 let old_cap = m.table.capacity();
1921 while old_cap == m.table.capacity() {
1926 assert_eq!(m.len(), i);
1927 assert!(!m.is_empty());
1931 fn test_behavior_resize_policy() {
1932 let mut m = HashMap::new();
1934 assert_eq!(m.len(), 0);
1935 assert_eq!(m.table.capacity(), 0);
1936 assert!(m.is_empty());
1940 assert!(m.is_empty());
1941 let initial_cap = m.table.capacity();
1942 m.reserve(initial_cap);
1943 let cap = m.table.capacity();
1945 assert_eq!(cap, initial_cap * 2);
1948 for _ in range(0, cap * 3 / 4) {
1952 // three quarters full
1954 assert_eq!(m.len(), i);
1955 assert_eq!(m.table.capacity(), cap);
1957 for _ in range(0, cap / 4) {
1963 let new_cap = m.table.capacity();
1964 assert_eq!(new_cap, cap * 2);
1966 for _ in range(0, cap / 2 - 1) {
1969 assert_eq!(m.table.capacity(), new_cap);
1971 // A little more than one quarter full.
1973 assert_eq!(m.table.capacity(), cap);
1974 // again, a little more than half full
1975 for _ in range(0, cap / 2 - 1) {
1981 assert_eq!(m.len(), i);
1982 assert!(!m.is_empty());
1983 assert_eq!(m.table.capacity(), initial_cap);
1987 fn test_reserve_shrink_to_fit() {
1988 let mut m = HashMap::new();
1991 assert!(m.capacity() >= m.len());
1992 for i in range(0, 128) {
1997 let usable_cap = m.capacity();
1998 for i in range(128, 128+256) {
2000 assert_eq!(m.capacity(), usable_cap);
2003 for i in range(100, 128+256) {
2004 assert_eq!(m.remove(&i), Some(i));
2008 assert_eq!(m.len(), 100);
2009 assert!(!m.is_empty());
2010 assert!(m.capacity() >= m.len());
2012 for i in range(0, 100) {
2013 assert_eq!(m.remove(&i), Some(i));
2018 assert_eq!(m.len(), 1);
2019 assert!(m.capacity() >= m.len());
2020 assert_eq!(m.remove(&0), Some(0));
2024 fn test_find_equiv() {
2025 let mut m = HashMap::new();
2027 let (foo, bar, baz) = (1i,2i,3i);
2028 m.insert("foo".to_string(), foo);
2029 m.insert("bar".to_string(), bar);
2030 m.insert("baz".to_string(), baz);
2033 assert_eq!(m.get("foo"), Some(&foo));
2034 assert_eq!(m.get("bar"), Some(&bar));
2035 assert_eq!(m.get("baz"), Some(&baz));
2037 assert_eq!(m.get("qux"), None);
2041 fn test_from_iter() {
2042 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2044 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2046 for &(k, v) in xs.iter() {
2047 assert_eq!(map.get(&k), Some(&v));
2052 fn test_size_hint() {
2053 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2055 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2057 let mut iter = map.iter();
2059 for _ in iter.by_ref().take(3) {}
2061 assert_eq!(iter.size_hint(), (3, Some(3)));
2065 fn test_mut_size_hint() {
2066 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2068 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2070 let mut iter = map.iter_mut();
2072 for _ in iter.by_ref().take(3) {}
2074 assert_eq!(iter.size_hint(), (3, Some(3)));
2079 let mut map: HashMap<int, int> = HashMap::new();
2085 assert_eq!(map[2], 1);
2090 fn test_index_nonexistent() {
2091 let mut map: HashMap<int, int> = HashMap::new();
2102 let xs = [(1i, 10i), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2104 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2106 // Existing key (insert)
2107 match map.entry(1) {
2108 Vacant(_) => unreachable!(),
2109 Occupied(mut view) => {
2110 assert_eq!(view.get(), &10);
2111 assert_eq!(view.set(100), 10);
2114 assert_eq!(map.get(&1).unwrap(), &100);
2115 assert_eq!(map.len(), 6);
2118 // Existing key (update)
2119 match map.entry(2) {
2120 Vacant(_) => unreachable!(),
2121 Occupied(mut view) => {
2122 let v = view.get_mut();
2123 let new_v = (*v) * 10;
2127 assert_eq!(map.get(&2).unwrap(), &200);
2128 assert_eq!(map.len(), 6);
2130 // Existing key (take)
2131 match map.entry(3) {
2132 Vacant(_) => unreachable!(),
2134 assert_eq!(view.take(), 30);
2137 assert_eq!(map.get(&3), None);
2138 assert_eq!(map.len(), 5);
2141 // Inexistent key (insert)
2142 match map.entry(10) {
2143 Occupied(_) => unreachable!(),
2145 assert_eq!(*view.set(1000), 1000);
2148 assert_eq!(map.get(&10).unwrap(), &1000);
2149 assert_eq!(map.len(), 6);
2153 fn test_entry_take_doesnt_corrupt() {
2155 fn check(m: &HashMap<int, ()>) {
2157 assert!(m.contains_key(k),
2158 "{} is in keys() but not in the map?", k);
2162 let mut m = HashMap::new();
2163 let mut rng = weak_rng();
2165 // Populate the map with some items.
2166 for _ in range(0u, 50) {
2167 let x = rng.gen_range(-10, 10);
2171 for i in range(0u, 1000) {
2172 let x = rng.gen_range(-10, 10);
2176 println!("{}: remove {}", i, x);