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, FromIterator, Extend};
25 use mem::{mod, replace};
27 use ops::{Deref, Index, IndexMut};
28 use option::{Some, None, Option};
29 use result::{Result, Ok, Err};
44 // FIXME(conventions): update capacity management to match other collections (no auto-shrink)
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 conditions:
52 /// - if size > 0.909 * capacity: grow
53 /// - if size < 0.25 * capacity: shrink (if this won't bring capacity lower
56 struct DefaultResizePolicy {
57 /// Doubled minimal capacity. The capacity must never drop below
58 /// the minimum capacity. (The check happens before the capacity
59 /// is potentially halved.)
60 minimum_capacity2: uint
63 impl DefaultResizePolicy {
64 fn new(new_capacity: uint) -> DefaultResizePolicy {
66 minimum_capacity2: new_capacity << 1
71 fn capacity_range(&self, new_size: uint) -> (uint, uint) {
72 // Here, we are rephrasing the logic by specifying the ranges:
74 // - if `size * 1.1 < cap < size * 4`: don't resize
75 // - if `cap < minimum_capacity * 2`: don't shrink
76 // - otherwise, resize accordingly
77 ((new_size * 11) / 10, max(new_size << 2, self.minimum_capacity2))
81 fn reserve(&mut self, new_capacity: uint) {
82 self.minimum_capacity2 = new_capacity << 1;
86 // The main performance trick in this hashmap is called Robin Hood Hashing.
87 // It gains its excellent performance from one essential operation:
89 // If an insertion collides with an existing element, and that element's
90 // "probe distance" (how far away the element is from its ideal location)
91 // is higher than how far we've already probed, swap the elements.
93 // This massively lowers variance in probe distance, and allows us to get very
94 // high load factors with good performance. The 90% load factor I use is rather
97 // > Why a load factor of approximately 90%?
99 // In general, all the distances to initial buckets will converge on the mean.
100 // At a load factor of α, the odds of finding the target bucket after k
101 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
102 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
103 // this down to make the math easier on the CPU and avoid its FPU.
104 // Since on average we start the probing in the middle of a cache line, this
105 // strategy pulls in two cache lines of hashes on every lookup. I think that's
106 // pretty good, but if you want to trade off some space, it could go down to one
107 // cache line on average with an α of 0.84.
109 // > Wait, what? Where did you get 1-α^k from?
111 // On the first probe, your odds of a collision with an existing element is α.
112 // The odds of doing this twice in a row is approximately α^2. For three times,
113 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
114 // colliding after k tries is 1-α^k.
116 // The paper from 1986 cited below mentions an implementation which keeps track
117 // of the distance-to-initial-bucket histogram. This approach is not suitable
118 // for modern architectures because it requires maintaining an internal data
119 // structure. This allows very good first guesses, but we are most concerned
120 // with guessing entire cache lines, not individual indexes. Furthermore, array
121 // accesses are no longer linear and in one direction, as we have now. There
122 // is also memory and cache pressure that this would entail that would be very
123 // difficult to properly see in a microbenchmark.
125 // ## Future Improvements (FIXME!)
127 // Allow the load factor to be changed dynamically and/or at initialization.
129 // Also, would it be possible for us to reuse storage when growing the
130 // underlying table? This is exactly the use case for 'realloc', and may
131 // be worth exploring.
133 // ## Future Optimizations (FIXME!)
135 // Another possible design choice that I made without any real reason is
136 // parameterizing the raw table over keys and values. Technically, all we need
137 // is the size and alignment of keys and values, and the code should be just as
138 // efficient (well, we might need one for power-of-two size and one for not...).
139 // This has the potential to reduce code bloat in rust executables, without
140 // really losing anything except 4 words (key size, key alignment, val size,
141 // val alignment) which can be passed in to every call of a `RawTable` function.
142 // This would definitely be an avenue worth exploring if people start complaining
143 // about the size of rust executables.
145 // Annotate exceedingly likely branches in `table::make_hash`
146 // and `search_hashed` to reduce instruction cache pressure
147 // and mispredictions once it becomes possible (blocked on issue #11092).
149 // Shrinking the table could simply reallocate in place after moving buckets
150 // to the first half.
152 // The growth algorithm (fragment of the Proof of Correctness)
153 // --------------------
155 // The growth algorithm is basically a fast path of the naive reinsertion-
156 // during-resize algorithm. Other paths should never be taken.
158 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
159 // by allocating a new table of capacity `2n`, and then individually reinsert
160 // each element in the old table into the new one. This guarantees that the
161 // new table is a valid robin hood hashtable with all the desired statistical
162 // properties. Remark that the order we reinsert the elements in should not
163 // matter. For simplicity and efficiency, we will consider only linear
164 // reinsertions, which consist of reinserting all elements in the old table
165 // into the new one by increasing order of index. However we will not be
166 // starting our reinsertions from index 0 in general. If we start from index
167 // i, for the purpose of reinsertion we will consider all elements with real
168 // index j < i to have virtual index n + j.
170 // Our hash generation scheme consists of generating a 64-bit hash and
171 // truncating the most significant bits. When moving to the new table, we
172 // simply introduce a new bit to the front of the hash. Therefore, if an
173 // elements has ideal index i in the old table, it can have one of two ideal
174 // locations in the new table. If the new bit is 0, then the new ideal index
175 // is i. If the new bit is 1, then the new ideal index is n + i. Intutively,
176 // we are producing two independent tables of size n, and for each element we
177 // independently choose which table to insert it into with equal probability.
178 // However the rather than wrapping around themselves on overflowing their
179 // indexes, the first table overflows into the first, and the first into the
180 // second. Visually, our new table will look something like:
182 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
184 // Where x's are elements inserted into the first table, y's are elements
185 // inserted into the second, and _'s are empty sections. We now define a few
186 // key concepts that we will use later. Note that this is a very abstract
187 // perspective of the table. A real resized table would be at least half
190 // Theorem: A linear robin hood reinsertion from the first ideal element
191 // produces identical results to a linear naive reinsertion from the same
194 // FIXME(Gankro, pczarn): review the proof and put it all in a separate doc.rs
196 /// A hash map implementation which uses linear probing with Robin
197 /// Hood bucket stealing.
199 /// The hashes are all keyed by the task-local random number generator
200 /// on creation by default. This means that the ordering of the keys is
201 /// randomized, but makes the tables more resistant to
202 /// denial-of-service attacks (Hash DoS). This behaviour can be
203 /// overridden with one of the constructors.
205 /// It is required that the keys implement the `Eq` and `Hash` traits, although
206 /// this can frequently be achieved by using `#[deriving(Eq, Hash)]`.
208 /// Relevant papers/articles:
210 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
211 /// 2. Emmanuel Goossaert. ["Robin Hood
212 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
213 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
214 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
219 /// use std::collections::HashMap;
221 /// // type inference lets us omit an explicit type signature (which
222 /// // would be `HashMap<&str, &str>` in this example).
223 /// let mut book_reviews = HashMap::new();
225 /// // review some books.
226 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
227 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
228 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
229 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
231 /// // check for a specific one.
232 /// if !book_reviews.contains_key(&("Les Misérables")) {
233 /// println!("We've got {} reviews, but Les Misérables ain't one.",
234 /// book_reviews.len());
237 /// // oops, this review has a lot of spelling mistakes, let's delete it.
238 /// book_reviews.remove(&("The Adventures of Sherlock Holmes"));
240 /// // look up the values associated with some keys.
241 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
242 /// for book in to_find.iter() {
243 /// match book_reviews.get(book) {
244 /// Some(review) => println!("{}: {}", *book, *review),
245 /// None => println!("{} is unreviewed.", *book)
249 /// // iterate over everything.
250 /// for (book, review) in book_reviews.iter() {
251 /// println!("{}: \"{}\"", *book, *review);
255 /// The easiest way to use `HashMap` with a custom type is to derive `Eq` and `Hash`.
256 /// We must also derive `PartialEq`.
259 /// use std::collections::HashMap;
261 /// #[deriving(Hash, Eq, PartialEq, Show)]
262 /// struct Viking<'a> {
267 /// let mut vikings = HashMap::new();
269 /// vikings.insert("Norway", Viking { name: "Einar", power: 9u });
270 /// vikings.insert("Denmark", Viking { name: "Olaf", power: 4u });
271 /// vikings.insert("Iceland", Viking { name: "Harald", power: 8u });
273 /// // Use derived implementation to print the vikings.
274 /// for (land, viking) in vikings.iter() {
275 /// println!("{} at {}", viking, land);
279 pub struct HashMap<K, V, H = RandomSipHasher> {
280 // All hashes are keyed on these values, to prevent hash collision attacks.
283 table: RawTable<K, V>,
285 // We keep this at the end since it might as well have tail padding.
286 resize_policy: DefaultResizePolicy,
289 /// Search for a pre-hashed key.
290 fn search_hashed<K, V, M: Deref<RawTable<K, V>>>(table: M,
292 is_match: |&K| -> bool)
293 -> SearchResult<K, V, M> {
294 let size = table.size();
295 let mut probe = Bucket::new(table, hash);
296 let ib = probe.index();
298 while probe.index() != ib + size {
299 let full = match probe.peek() {
300 Empty(b) => return TableRef(b.into_table()), // hit an empty bucket
304 if full.distance() + ib < full.index() {
305 // We can finish the search early if we hit any bucket
306 // with a lower distance to initial bucket than we've probed.
307 return TableRef(full.into_table());
310 // If the hash doesn't match, it can't be this one..
311 if *hash == full.hash() {
313 let (k, _) = full.read();
317 // If the key doesn't match, it can't be this one..
319 return FoundExisting(full);
326 TableRef(probe.into_table())
329 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
330 let (empty, retkey, retval) = starting_bucket.take();
331 let mut gap = match empty.gap_peek() {
333 None => return (retkey, retval)
336 while gap.full().distance() != 0 {
337 gap = match gap.shift() {
343 // Now we've done all our shifting. Return the value we grabbed earlier.
344 return (retkey, retval);
347 /// Perform robin hood bucket stealing at the given `bucket`. You must
348 /// also pass the position of that bucket's initial bucket so we don't have
349 /// to recalculate it.
351 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
352 fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
358 let starting_index = bucket.index();
360 let table = bucket.table(); // FIXME "lifetime too short".
363 // There can be at most `size - dib` buckets to displace, because
364 // in the worst case, there are `size` elements and we already are
365 // `distance` buckets away from the initial one.
366 let idx_end = starting_index + size - bucket.distance();
369 let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
371 let probe = bucket.next();
372 assert!(probe.index() != idx_end);
374 let full_bucket = match probe.peek() {
375 table::Empty(bucket) => {
377 let b = bucket.put(old_hash, old_key, old_val);
378 // Now that it's stolen, just read the value's pointer
379 // right out of the table!
380 let (_, v) = Bucket::at_index(b.into_table(), starting_index).peek()
385 table::Full(bucket) => bucket
388 let probe_ib = full_bucket.index() - full_bucket.distance();
390 bucket = full_bucket;
392 // Robin hood! Steal the spot.
404 /// A result that works like Option<FullBucket<..>> but preserves
405 /// the reference that grants us access to the table in any case.
406 enum SearchResult<K, V, M> {
407 // This is an entry that holds the given key:
408 FoundExisting(FullBucket<K, V, M>),
410 // There was no such entry. The reference is given back:
414 impl<K, V, M> SearchResult<K, V, M> {
415 fn into_option(self) -> Option<FullBucket<K, V, M>> {
417 FoundExisting(bucket) => Some(bucket),
423 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
424 fn make_hash<Sized? X: Hash<S>>(&self, x: &X) -> SafeHash {
425 table::make_hash(&self.hasher, x)
428 fn search_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, q: &Q)
429 -> Option<FullBucketImm<'a, K, V>> {
430 let hash = self.make_hash(q);
431 search_hashed(&self.table, &hash, |k| q.equiv(k)).into_option()
434 fn search_equiv_mut<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a mut self, q: &Q)
435 -> Option<FullBucketMut<'a, K, V>> {
436 let hash = self.make_hash(q);
437 search_hashed(&mut self.table, &hash, |k| q.equiv(k)).into_option()
440 /// Search for a key, yielding the index if it's found in the hashtable.
441 /// If you already have the hash for the key lying around, use
443 fn search<'a, Sized? Q>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
444 where Q: BorrowFrom<K> + Eq + Hash<S>
446 let hash = self.make_hash(q);
447 search_hashed(&self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
451 fn search_mut<'a, Sized? Q>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
452 where Q: BorrowFrom<K> + Eq + Hash<S>
454 let hash = self.make_hash(q);
455 search_hashed(&mut self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
459 // The caller should ensure that invariants by Robin Hood Hashing hold.
460 fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
461 let cap = self.table.capacity();
462 let mut buckets = Bucket::new(&mut self.table, &hash);
463 let ib = buckets.index();
465 while buckets.index() != ib + cap {
466 // We don't need to compare hashes for value swap.
467 // Not even DIBs for Robin Hood.
468 buckets = match buckets.peek() {
470 empty.put(hash, k, v);
473 Full(b) => b.into_bucket()
477 panic!("Internal HashMap error: Out of space.");
481 impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
482 /// Create an empty HashMap.
487 /// use std::collections::HashMap;
488 /// let mut map: HashMap<&str, int> = HashMap::new();
491 #[unstable = "matches collection reform specification, waiting for dust to settle"]
492 pub fn new() -> HashMap<K, V, RandomSipHasher> {
493 let hasher = RandomSipHasher::new();
494 HashMap::with_hasher(hasher)
497 /// Creates an empty hash map with the given initial capacity.
502 /// use std::collections::HashMap;
503 /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
506 #[unstable = "matches collection reform specification, waiting for dust to settle"]
507 pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
508 let hasher = RandomSipHasher::new();
509 HashMap::with_capacity_and_hasher(capacity, hasher)
513 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
514 /// Creates an empty hashmap which will use the given hasher to hash keys.
516 /// The creates map has the default initial capacity.
521 /// use std::collections::HashMap;
522 /// use std::hash::sip::SipHasher;
524 /// let h = SipHasher::new();
525 /// let mut map = HashMap::with_hasher(h);
526 /// map.insert(1i, 2u);
529 pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
532 resize_policy: DefaultResizePolicy::new(INITIAL_CAPACITY),
533 table: RawTable::new(0),
537 /// Create an empty HashMap with space for at least `capacity`
538 /// elements, using `hasher` to hash the keys.
540 /// Warning: `hasher` is normally randomly generated, and
541 /// is designed to allow HashMaps to be resistant to attacks that
542 /// cause many collisions and very poor performance. Setting it
543 /// manually using this function can expose a DoS attack vector.
548 /// use std::collections::HashMap;
549 /// use std::hash::sip::SipHasher;
551 /// let h = SipHasher::new();
552 /// let mut map = HashMap::with_capacity_and_hasher(10, h);
553 /// map.insert(1i, 2u);
556 pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
557 let cap = max(INITIAL_CAPACITY, capacity).next_power_of_two();
560 resize_policy: DefaultResizePolicy::new(cap),
561 table: RawTable::new(cap),
565 /// The hashtable will never try to shrink below this size. You can use
566 /// this function to reduce reallocations if your hashtable frequently
567 /// grows and shrinks by large amounts.
569 /// This function has no effect on the operational semantics of the
570 /// hashtable, only on performance.
575 /// use std::collections::HashMap;
576 /// let mut map: HashMap<&str, int> = HashMap::new();
579 pub fn reserve(&mut self, new_minimum_capacity: uint) {
580 let cap = max(INITIAL_CAPACITY, new_minimum_capacity).next_power_of_two();
582 self.resize_policy.reserve(cap);
584 if self.table.capacity() < cap {
589 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
590 /// 1) Make sure the new capacity is enough for all the elements, accounting
591 /// for the load factor.
592 /// 2) Ensure new_capacity is a power of two.
593 fn resize(&mut self, new_capacity: uint) {
594 assert!(self.table.size() <= new_capacity);
595 assert!(new_capacity.is_power_of_two());
597 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
598 let old_size = old_table.size();
600 if old_table.capacity() == 0 || old_table.size() == 0 {
604 if new_capacity < old_table.capacity() {
605 // Shrink the table. Naive algorithm for resizing:
606 for (h, k, v) in old_table.into_iter() {
607 self.insert_hashed_nocheck(h, k, v);
611 // Specialization of the other branch.
612 let mut bucket = Bucket::first(&mut old_table);
614 // "So a few of the first shall be last: for many be called,
617 // We'll most likely encounter a few buckets at the beginning that
618 // have their initial buckets near the end of the table. They were
619 // placed at the beginning as the probe wrapped around the table
620 // during insertion. We must skip forward to a bucket that won't
621 // get reinserted too early and won't unfairly steal others spot.
622 // This eliminates the need for robin hood.
624 bucket = match bucket.peek() {
626 if full.distance() == 0 {
627 // This bucket occupies its ideal spot.
628 // It indicates the start of another "cluster".
629 bucket = full.into_bucket();
632 // Leaving this bucket in the last cluster for later.
636 // Encountered a hole between clusters.
643 // This is how the buckets might be laid out in memory:
644 // ($ marks an initialized bucket)
646 // |$$$_$$$$$$_$$$$$|
648 // But we've skipped the entire initial cluster of buckets
649 // and will continue iteration in this order:
652 // ^ wrap around once end is reached
655 // ^ exit once table.size == 0
657 bucket = match bucket.peek() {
659 let h = bucket.hash();
660 let (b, k, v) = bucket.take();
661 self.insert_hashed_ordered(h, k, v);
663 let t = b.table(); // FIXME "lifetime too short".
664 if t.size() == 0 { break }
668 Empty(b) => b.into_bucket()
674 assert_eq!(self.table.size(), old_size);
677 /// Performs any necessary resize operations, such that there's space for
678 /// new_size elements.
679 fn make_some_room(&mut self, new_size: uint) {
680 let (grow_at, shrink_at) = self.resize_policy.capacity_range(new_size);
681 let cap = self.table.capacity();
683 // An invalid value shouldn't make us run out of space.
684 debug_assert!(grow_at >= new_size);
687 let new_capacity = max(cap << 1, INITIAL_CAPACITY);
688 self.resize(new_capacity);
689 } else if shrink_at <= cap {
690 let new_capacity = cap >> 1;
691 self.resize(new_capacity);
695 /// Insert a pre-hashed key-value pair, without first checking
696 /// that there's enough room in the buckets. Returns a reference to the
697 /// newly insert value.
699 /// If the key already exists, the hashtable will be returned untouched
700 /// and a reference to the existing element will be returned.
701 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
702 self.insert_or_replace_with(hash, k, v, |_, _, _| ())
705 fn insert_or_replace_with<'a>(&'a mut self,
709 found_existing: |&mut K, &mut V, V|)
711 // Worst case, we'll find one empty bucket among `size + 1` buckets.
712 let size = self.table.size();
713 let mut probe = Bucket::new(&mut self.table, &hash);
714 let ib = probe.index();
717 let mut bucket = match probe.peek() {
720 let bucket = bucket.put(hash, k, v);
721 let (_, val) = bucket.into_mut_refs();
724 Full(bucket) => bucket
727 if bucket.hash() == hash {
729 let (bucket_k, _) = bucket.read_mut();
733 let (bucket_k, bucket_v) = bucket.into_mut_refs();
734 debug_assert!(k == *bucket_k);
735 // Key already exists. Get its reference.
736 found_existing(bucket_k, bucket_v, v);
741 let robin_ib = bucket.index() as int - bucket.distance() as int;
743 if (ib as int) < robin_ib {
744 // Found a luckier bucket than me. Better steal his spot.
745 return robin_hood(bucket, robin_ib as uint, hash, k, v);
748 probe = bucket.next();
749 assert!(probe.index() != ib + size + 1);
753 /// Deprecated: use `contains_key` and `BorrowFrom` instead.
754 #[deprecated = "use contains_key and BorrowFrom instead"]
755 pub fn contains_key_equiv<Sized? Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
756 self.search_equiv(key).is_some()
759 /// Deprecated: use `get` and `BorrowFrom` instead.
760 #[deprecated = "use get and BorrowFrom instead"]
761 pub fn find_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
762 match self.search_equiv(k) {
765 let (_, v_ref) = bucket.into_refs();
771 /// Deprecated: use `remove` and `BorrowFrom` instead.
772 #[deprecated = "use remove and BorrowFrom instead"]
773 pub fn pop_equiv<Sized? Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
774 if self.table.size() == 0 {
778 let potential_new_size = self.table.size() - 1;
779 self.make_some_room(potential_new_size);
781 match self.search_equiv_mut(k) {
783 let (_k, val) = pop_internal(bucket);
790 /// An iterator visiting all keys in arbitrary order.
791 /// Iterator element type is `&'a K`.
796 /// use std::collections::HashMap;
798 /// let mut map = HashMap::new();
799 /// map.insert("a", 1i);
800 /// map.insert("b", 2);
801 /// map.insert("c", 3);
803 /// for key in map.keys() {
804 /// println!("{}", key);
807 #[unstable = "matches collection reform specification, waiting for dust to settle"]
808 pub fn keys(&self) -> Keys<K, V> {
809 self.iter().map(|(k, _v)| k)
812 /// An iterator visiting all values in arbitrary order.
813 /// Iterator element type is `&'a V`.
818 /// use std::collections::HashMap;
820 /// let mut map = HashMap::new();
821 /// map.insert("a", 1i);
822 /// map.insert("b", 2);
823 /// map.insert("c", 3);
825 /// for key in map.values() {
826 /// println!("{}", key);
829 #[unstable = "matches collection reform specification, waiting for dust to settle"]
830 pub fn values(&self) -> Values<K, V> {
831 self.iter().map(|(_k, v)| v)
834 /// An iterator visiting all key-value pairs in arbitrary order.
835 /// Iterator element type is `(&'a K, &'a V)`.
840 /// use std::collections::HashMap;
842 /// let mut map = HashMap::new();
843 /// map.insert("a", 1i);
844 /// map.insert("b", 2);
845 /// map.insert("c", 3);
847 /// for (key, val) in map.iter() {
848 /// println!("key: {} val: {}", key, val);
851 #[unstable = "matches collection reform specification, waiting for dust to settle"]
852 pub fn iter(&self) -> Entries<K, V> {
853 Entries { inner: self.table.iter() }
856 /// An iterator visiting all key-value pairs in arbitrary order,
857 /// with mutable references to the values.
858 /// Iterator element type is `(&'a K, &'a mut V)`.
863 /// use std::collections::HashMap;
865 /// let mut map = HashMap::new();
866 /// map.insert("a", 1i);
867 /// map.insert("b", 2);
868 /// map.insert("c", 3);
870 /// // Update all values
871 /// for (_, val) in map.iter_mut() {
875 /// for (key, val) in map.iter() {
876 /// println!("key: {} val: {}", key, val);
879 #[unstable = "matches collection reform specification, waiting for dust to settle"]
880 pub fn iter_mut(&mut self) -> MutEntries<K, V> {
881 MutEntries { inner: self.table.iter_mut() }
884 /// Creates a consuming iterator, that is, one that moves each key-value
885 /// pair out of the map in arbitrary order. The map cannot be used after
891 /// use std::collections::HashMap;
893 /// let mut map = HashMap::new();
894 /// map.insert("a", 1i);
895 /// map.insert("b", 2);
896 /// map.insert("c", 3);
898 /// // Not possible with .iter()
899 /// let vec: Vec<(&str, int)> = map.into_iter().collect();
901 #[unstable = "matches collection reform specification, waiting for dust to settle"]
902 pub fn into_iter(self) -> MoveEntries<K, V> {
904 inner: self.table.into_iter().map(|(_, k, v)| (k, v))
908 /// Gets the given key's corresponding entry in the map for in-place manipulation
909 pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V> {
910 // Gotta resize now, and we don't know which direction, so try both?
911 let size = self.table.size();
912 self.make_some_room(size + 1);
914 self.make_some_room(size - 1);
917 let hash = self.make_hash(&key);
918 search_entry_hashed(&mut self.table, hash, key)
921 /// Return the number of elements in the map.
926 /// use std::collections::HashMap;
928 /// let mut a = HashMap::new();
929 /// assert_eq!(a.len(), 0);
930 /// a.insert(1u, "a");
931 /// assert_eq!(a.len(), 1);
933 #[unstable = "matches collection reform specification, waiting for dust to settle"]
934 pub fn len(&self) -> uint { self.table.size() }
936 /// Return true if the map contains no elements.
941 /// use std::collections::HashMap;
943 /// let mut a = HashMap::new();
944 /// assert!(a.is_empty());
945 /// a.insert(1u, "a");
946 /// assert!(!a.is_empty());
949 #[unstable = "matches collection reform specification, waiting for dust to settle"]
950 pub fn is_empty(&self) -> bool { self.len() == 0 }
952 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
958 /// use std::collections::HashMap;
960 /// let mut a = HashMap::new();
961 /// a.insert(1u, "a");
963 /// assert!(a.is_empty());
965 #[unstable = "matches collection reform specification, waiting for dust to settle"]
966 pub fn clear(&mut self) {
967 // Prevent reallocations from happening from now on. Makes it possible
968 // for the map to be reused but has a downside: reserves permanently.
969 self.resize_policy.reserve(self.table.size());
971 let cap = self.table.capacity();
972 let mut buckets = Bucket::first(&mut self.table);
974 while buckets.index() != cap {
975 buckets = match buckets.peek() {
976 Empty(b) => b.next(),
978 let (b, _, _) = full.take();
985 /// Deprecated: Renamed to `get`.
986 #[deprecated = "Renamed to `get`"]
987 pub fn find(&self, k: &K) -> Option<&V> {
991 /// Returns a reference to the value corresponding to the key.
993 /// The key may be any borrowed form of the map's key type, but
994 /// `Hash` and `Eq` on the borrowed form *must* match those for
1000 /// use std::collections::HashMap;
1002 /// let mut map = HashMap::new();
1003 /// map.insert(1u, "a");
1004 /// assert_eq!(map.get(&1), Some(&"a"));
1005 /// assert_eq!(map.get(&2), None);
1007 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1008 pub fn get<Sized? Q>(&self, k: &Q) -> Option<&V>
1009 where Q: Hash<S> + Eq + BorrowFrom<K>
1011 self.search(k).map(|bucket| {
1012 let (_, v) = bucket.into_refs();
1017 /// Returns true if the map contains a value for the specified key.
1019 /// The key may be any borrowed form of the map's key type, but
1020 /// `Hash` and `Eq` on the borrowed form *must* match those for
1026 /// use std::collections::HashMap;
1028 /// let mut map = HashMap::new();
1029 /// map.insert(1u, "a");
1030 /// assert_eq!(map.contains_key(&1), true);
1031 /// assert_eq!(map.contains_key(&2), false);
1033 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1034 pub fn contains_key<Sized? Q>(&self, k: &Q) -> bool
1035 where Q: Hash<S> + Eq + BorrowFrom<K>
1037 self.search(k).is_some()
1040 /// Deprecated: Renamed to `get_mut`.
1041 #[deprecated = "Renamed to `get_mut`"]
1042 pub fn find_mut(&mut self, k: &K) -> Option<&mut V> {
1046 /// Returns a mutable reference to the value corresponding to the key.
1048 /// The key may be any borrowed form of the map's key type, but
1049 /// `Hash` and `Eq` on the borrowed form *must* match those for
1055 /// use std::collections::HashMap;
1057 /// let mut map = HashMap::new();
1058 /// map.insert(1u, "a");
1059 /// match map.get_mut(&1) {
1060 /// Some(x) => *x = "b",
1063 /// assert_eq!(map[1], "b");
1065 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1066 pub fn get_mut<Sized? Q>(&mut self, k: &Q) -> Option<&mut V>
1067 where Q: Hash<S> + Eq + BorrowFrom<K>
1069 match self.search_mut(k) {
1071 let (_, v) = bucket.into_mut_refs();
1078 /// Deprecated: Renamed to `insert`.
1079 #[deprecated = "Renamed to `insert`"]
1080 pub fn swap(&mut self, k: K, v: V) -> Option<V> {
1084 /// Inserts a key-value pair from the map. If the key already had a value
1085 /// present in the map, that value is returned. Otherwise, `None` is returned.
1090 /// use std::collections::HashMap;
1092 /// let mut map = HashMap::new();
1093 /// assert_eq!(map.insert(37u, "a"), None);
1094 /// assert_eq!(map.is_empty(), false);
1096 /// map.insert(37, "b");
1097 /// assert_eq!(map.insert(37, "c"), Some("b"));
1098 /// assert_eq!(map[37], "c");
1100 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1101 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1102 let hash = self.make_hash(&k);
1103 let potential_new_size = self.table.size() + 1;
1104 self.make_some_room(potential_new_size);
1106 let mut retval = None;
1107 self.insert_or_replace_with(hash, k, v, |_, val_ref, val| {
1108 retval = Some(replace(val_ref, val));
1113 /// Deprecated: Renamed to `remove`.
1114 #[deprecated = "Renamed to `remove`"]
1115 pub fn pop(&mut self, k: &K) -> Option<V> {
1119 /// Removes a key from the map, returning the value at the key if the key
1120 /// was previously in the map.
1122 /// The key may be any borrowed form of the map's key type, but
1123 /// `Hash` and `Eq` on the borrowed form *must* match those for
1129 /// use std::collections::HashMap;
1131 /// let mut map = HashMap::new();
1132 /// map.insert(1u, "a");
1133 /// assert_eq!(map.remove(&1), Some("a"));
1134 /// assert_eq!(map.remove(&1), None);
1136 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1137 pub fn remove<Sized? Q>(&mut self, k: &Q) -> Option<V>
1138 where Q: Hash<S> + Eq + BorrowFrom<K>
1140 if self.table.size() == 0 {
1144 let potential_new_size = self.table.size() - 1;
1145 self.make_some_room(potential_new_size);
1147 self.search_mut(k).map(|bucket| {
1148 let (_k, val) = pop_internal(bucket);
1154 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
1155 -> Entry<'a, K, V> {
1156 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1157 let size = table.size();
1158 let mut probe = Bucket::new(table, &hash);
1159 let ib = probe.index();
1162 let bucket = match probe.peek() {
1165 return Vacant(VacantEntry {
1168 elem: NoElem(bucket),
1171 Full(bucket) => bucket
1174 if bucket.hash() == hash {
1176 let (bucket_k, _) = bucket.read();
1181 return Occupied(OccupiedEntry{
1187 let robin_ib = bucket.index() as int - bucket.distance() as int;
1189 if (ib as int) < robin_ib {
1190 // Found a luckier bucket than me. Better steal his spot.
1191 return Vacant(VacantEntry {
1194 elem: NeqElem(bucket, robin_ib as uint),
1198 probe = bucket.next();
1199 assert!(probe.index() != ib + size + 1);
1203 impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
1204 /// Deprecated: Use `map.get(k).cloned()`.
1206 /// Return a copy of the value corresponding to the key.
1207 #[deprecated = "Use `map.get(k).cloned()`"]
1208 pub fn find_copy(&self, k: &K) -> Option<V> {
1209 self.get(k).cloned()
1212 /// Deprecated: Use `map[k].clone()`.
1214 /// Return a copy of the value corresponding to the key.
1215 #[deprecated = "Use `map[k].clone()`"]
1216 pub fn get_copy(&self, k: &K) -> V {
1221 impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
1222 fn eq(&self, other: &HashMap<K, V, H>) -> bool {
1223 if self.len() != other.len() { return false; }
1225 self.iter().all(|(key, value)|
1226 other.get(key).map_or(false, |v| *value == *v)
1231 impl<K: Eq + Hash<S>, V: Eq, S, H: Hasher<S>> Eq for HashMap<K, V, H> {}
1233 impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
1234 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1235 try!(write!(f, "{{"));
1237 for (i, (k, v)) in self.iter().enumerate() {
1238 if i != 0 { try!(write!(f, ", ")); }
1239 try!(write!(f, "{}: {}", *k, *v));
1246 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
1247 fn default() -> HashMap<K, V, H> {
1248 HashMap::with_hasher(Default::default())
1252 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> Index<Q, V> for HashMap<K, V, H>
1253 where Q: BorrowFrom<K> + Hash<S> + Eq
1256 fn index<'a>(&'a self, index: &Q) -> &'a V {
1257 self.get(index).expect("no entry found for key")
1261 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> IndexMut<Q, V> for HashMap<K, V, H>
1262 where Q: BorrowFrom<K> + Hash<S> + Eq
1265 fn index_mut<'a>(&'a mut self, index: &Q) -> &'a mut V {
1266 match self.get_mut(index) {
1268 None => panic!("no entry found for key")
1273 /// HashMap iterator
1274 pub struct Entries<'a, K: 'a, V: 'a> {
1275 inner: table::Entries<'a, K, V>
1278 /// HashMap mutable values iterator
1279 pub struct MutEntries<'a, K: 'a, V: 'a> {
1280 inner: table::MutEntries<'a, K, V>
1283 /// HashMap move iterator
1284 pub struct MoveEntries<K, V> {
1285 inner: iter::Map<'static, (SafeHash, K, V), (K, V), table::MoveEntries<K, V>>
1288 /// A view into a single occupied location in a HashMap
1289 pub struct OccupiedEntry<'a, K:'a, V:'a> {
1290 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1293 /// A view into a single empty location in a HashMap
1294 pub struct VacantEntry<'a, K:'a, V:'a> {
1297 elem: VacantEntryState<K,V, &'a mut RawTable<K, V>>,
1300 /// A view into a single location in a map, which may be vacant or occupied
1301 pub enum Entry<'a, K:'a, V:'a> {
1302 /// An occupied Entry
1303 Occupied(OccupiedEntry<'a, K, V>),
1305 Vacant(VacantEntry<'a, K, V>),
1308 /// Possible states of a VacantEntry
1309 enum VacantEntryState<K, V, M> {
1310 /// The index is occupied, but the key to insert has precedence,
1311 /// and will kick the current one out on insertion
1312 NeqElem(FullBucket<K, V, M>, uint),
1313 /// The index is genuinely vacant
1314 NoElem(EmptyBucket<K, V, M>),
1317 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
1319 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1323 fn size_hint(&self) -> (uint, Option<uint>) {
1324 self.inner.size_hint()
1328 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
1330 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1334 fn size_hint(&self) -> (uint, Option<uint>) {
1335 self.inner.size_hint()
1339 impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
1341 fn next(&mut self) -> Option<(K, V)> {
1345 fn size_hint(&self) -> (uint, Option<uint>) {
1346 self.inner.size_hint()
1350 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1351 /// Gets a reference to the value in the entry
1352 pub fn get(&self) -> &V {
1353 let (_, v) = self.elem.read();
1357 /// Gets a mutable reference to the value in the entry
1358 pub fn get_mut(&mut self) -> &mut V {
1359 let (_, v) = self.elem.read_mut();
1363 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1364 /// with a lifetime bound to the map itself
1365 pub fn into_mut(self) -> &'a mut V {
1366 let (_, v) = self.elem.into_mut_refs();
1370 /// Sets the value of the entry, and returns the entry's old value
1371 pub fn set(&mut self, mut value: V) -> V {
1372 let old_value = self.get_mut();
1373 mem::swap(&mut value, old_value);
1377 /// Takes the value out of the entry, and returns it
1378 pub fn take(self) -> V {
1379 let (_, _, v) = self.elem.take();
1384 impl<'a, K, V> VacantEntry<'a, K, V> {
1385 /// Sets the value of the entry with the VacantEntry's key,
1386 /// and returns a mutable reference to it
1387 pub fn set(self, value: V) -> &'a mut V {
1389 NeqElem(bucket, ib) => {
1390 robin_hood(bucket, ib, self.hash, self.key, value)
1393 let full = bucket.put(self.hash, self.key, value);
1394 let (_, v) = full.into_mut_refs();
1401 /// HashMap keys iterator
1402 pub type Keys<'a, K, V> =
1403 iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
1405 /// HashMap values iterator
1406 pub type Values<'a, K, V> =
1407 iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
1409 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
1410 fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
1411 let (lower, _) = iter.size_hint();
1412 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1418 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Extend<(K, V)> for HashMap<K, V, H> {
1419 fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
1420 for (k, v) in iter {
1431 use super::{Occupied, Vacant};
1434 use iter::{Iterator,range_inclusive,range_step_inclusive};
1437 struct KindaIntLike(int);
1439 impl Equiv<int> for KindaIntLike {
1440 fn equiv(&self, other: &int) -> bool {
1441 let KindaIntLike(this) = *self;
1445 impl<S: hash::Writer> hash::Hash<S> for KindaIntLike {
1446 fn hash(&self, state: &mut S) {
1447 let KindaIntLike(this) = *self;
1453 fn test_create_capacity_zero() {
1454 let mut m = HashMap::with_capacity(0);
1456 assert!(m.insert(1i, 1i).is_none());
1458 assert!(m.contains_key(&1));
1459 assert!(!m.contains_key(&0));
1464 let mut m = HashMap::new();
1465 assert_eq!(m.len(), 0);
1466 assert!(m.insert(1i, 2i).is_none());
1467 assert_eq!(m.len(), 1);
1468 assert!(m.insert(2i, 4i).is_none());
1469 assert_eq!(m.len(), 2);
1470 assert_eq!(*m.get(&1).unwrap(), 2);
1471 assert_eq!(*m.get(&2).unwrap(), 4);
1474 thread_local!(static DROP_VECTOR: RefCell<Vec<int>> = RefCell::new(Vec::new()))
1476 #[deriving(Hash, PartialEq, Eq)]
1482 fn new(k: uint) -> Dropable {
1483 DROP_VECTOR.with(|slot| {
1484 slot.borrow_mut()[k] += 1;
1491 impl Drop for Dropable {
1492 fn drop(&mut self) {
1493 DROP_VECTOR.with(|slot| {
1494 slot.borrow_mut()[self.k] -= 1;
1499 impl Clone for Dropable {
1500 fn clone(&self) -> Dropable {
1501 Dropable::new(self.k)
1507 DROP_VECTOR.with(|slot| {
1508 *slot.borrow_mut() = Vec::from_elem(200, 0i);
1512 let mut m = HashMap::new();
1514 DROP_VECTOR.with(|v| {
1515 for i in range(0u, 200) {
1516 assert_eq!(v.borrow().as_slice()[i], 0);
1520 for i in range(0u, 100) {
1521 let d1 = Dropable::new(i);
1522 let d2 = Dropable::new(i+100);
1526 DROP_VECTOR.with(|v| {
1527 for i in range(0u, 200) {
1528 assert_eq!(v.borrow().as_slice()[i], 1);
1532 for i in range(0u, 50) {
1533 let k = Dropable::new(i);
1534 let v = m.remove(&k);
1536 assert!(v.is_some());
1538 DROP_VECTOR.with(|v| {
1539 assert_eq!(v.borrow().as_slice()[i], 1);
1540 assert_eq!(v.borrow().as_slice()[i+100], 1);
1544 DROP_VECTOR.with(|v| {
1545 for i in range(0u, 50) {
1546 assert_eq!(v.borrow().as_slice()[i], 0);
1547 assert_eq!(v.borrow().as_slice()[i+100], 0);
1550 for i in range(50u, 100) {
1551 assert_eq!(v.borrow().as_slice()[i], 1);
1552 assert_eq!(v.borrow().as_slice()[i+100], 1);
1557 DROP_VECTOR.with(|v| {
1558 for i in range(0u, 200) {
1559 assert_eq!(v.borrow().as_slice()[i], 0);
1565 fn test_move_iter_drops() {
1566 DROP_VECTOR.with(|v| {
1567 *v.borrow_mut() = Vec::from_elem(200, 0i);
1571 let mut hm = HashMap::new();
1573 DROP_VECTOR.with(|v| {
1574 for i in range(0u, 200) {
1575 assert_eq!(v.borrow().as_slice()[i], 0);
1579 for i in range(0u, 100) {
1580 let d1 = Dropable::new(i);
1581 let d2 = Dropable::new(i+100);
1585 DROP_VECTOR.with(|v| {
1586 for i in range(0u, 200) {
1587 assert_eq!(v.borrow().as_slice()[i], 1);
1594 // By the way, ensure that cloning doesn't screw up the dropping.
1598 let mut half = hm.into_iter().take(50);
1600 DROP_VECTOR.with(|v| {
1601 for i in range(0u, 200) {
1602 assert_eq!(v.borrow().as_slice()[i], 1);
1608 DROP_VECTOR.with(|v| {
1609 let nk = range(0u, 100).filter(|&i| {
1610 v.borrow().as_slice()[i] == 1
1613 let nv = range(0u, 100).filter(|&i| {
1614 v.borrow().as_slice()[i+100] == 1
1622 DROP_VECTOR.with(|v| {
1623 for i in range(0u, 200) {
1624 assert_eq!(v.borrow().as_slice()[i], 0);
1630 fn test_empty_pop() {
1631 let mut m: HashMap<int, bool> = HashMap::new();
1632 assert_eq!(m.remove(&0), None);
1636 fn test_lots_of_insertions() {
1637 let mut m = HashMap::new();
1639 // Try this a few times to make sure we never screw up the hashmap's
1641 for _ in range(0i, 10) {
1642 assert!(m.is_empty());
1644 for i in range_inclusive(1i, 1000) {
1645 assert!(m.insert(i, i).is_none());
1647 for j in range_inclusive(1, i) {
1649 assert_eq!(r, Some(&j));
1652 for j in range_inclusive(i+1, 1000) {
1654 assert_eq!(r, None);
1658 for i in range_inclusive(1001i, 2000) {
1659 assert!(!m.contains_key(&i));
1663 for i in range_inclusive(1i, 1000) {
1664 assert!(m.remove(&i).is_some());
1666 for j in range_inclusive(1, i) {
1667 assert!(!m.contains_key(&j));
1670 for j in range_inclusive(i+1, 1000) {
1671 assert!(m.contains_key(&j));
1675 for i in range_inclusive(1i, 1000) {
1676 assert!(!m.contains_key(&i));
1679 for i in range_inclusive(1i, 1000) {
1680 assert!(m.insert(i, i).is_none());
1684 for i in range_step_inclusive(1000i, 1, -1) {
1685 assert!(m.remove(&i).is_some());
1687 for j in range_inclusive(i, 1000) {
1688 assert!(!m.contains_key(&j));
1691 for j in range_inclusive(1, i-1) {
1692 assert!(m.contains_key(&j));
1699 fn test_find_mut() {
1700 let mut m = HashMap::new();
1701 assert!(m.insert(1i, 12i).is_none());
1702 assert!(m.insert(2i, 8i).is_none());
1703 assert!(m.insert(5i, 14i).is_none());
1705 match m.get_mut(&5) {
1706 None => panic!(), Some(x) => *x = new
1708 assert_eq!(m.get(&5), Some(&new));
1712 fn test_insert_overwrite() {
1713 let mut m = HashMap::new();
1714 assert!(m.insert(1i, 2i).is_none());
1715 assert_eq!(*m.get(&1).unwrap(), 2);
1716 assert!(!m.insert(1i, 3i).is_none());
1717 assert_eq!(*m.get(&1).unwrap(), 3);
1721 fn test_insert_conflicts() {
1722 let mut m = HashMap::with_capacity(4);
1723 assert!(m.insert(1i, 2i).is_none());
1724 assert!(m.insert(5i, 3i).is_none());
1725 assert!(m.insert(9i, 4i).is_none());
1726 assert_eq!(*m.get(&9).unwrap(), 4);
1727 assert_eq!(*m.get(&5).unwrap(), 3);
1728 assert_eq!(*m.get(&1).unwrap(), 2);
1732 fn test_conflict_remove() {
1733 let mut m = HashMap::with_capacity(4);
1734 assert!(m.insert(1i, 2i).is_none());
1735 assert_eq!(*m.get(&1).unwrap(), 2);
1736 assert!(m.insert(5, 3).is_none());
1737 assert_eq!(*m.get(&1).unwrap(), 2);
1738 assert_eq!(*m.get(&5).unwrap(), 3);
1739 assert!(m.insert(9, 4).is_none());
1740 assert_eq!(*m.get(&1).unwrap(), 2);
1741 assert_eq!(*m.get(&5).unwrap(), 3);
1742 assert_eq!(*m.get(&9).unwrap(), 4);
1743 assert!(m.remove(&1).is_some());
1744 assert_eq!(*m.get(&9).unwrap(), 4);
1745 assert_eq!(*m.get(&5).unwrap(), 3);
1749 fn test_is_empty() {
1750 let mut m = HashMap::with_capacity(4);
1751 assert!(m.insert(1i, 2i).is_none());
1752 assert!(!m.is_empty());
1753 assert!(m.remove(&1).is_some());
1754 assert!(m.is_empty());
1759 let mut m = HashMap::new();
1761 assert_eq!(m.remove(&1), Some(2));
1762 assert_eq!(m.remove(&1), None);
1766 #[allow(experimental)]
1767 fn test_pop_equiv() {
1768 let mut m = HashMap::new();
1770 assert_eq!(m.pop_equiv(&KindaIntLike(1)), Some(2));
1771 assert_eq!(m.pop_equiv(&KindaIntLike(1)), None);
1776 let mut m = HashMap::with_capacity(4);
1777 for i in range(0u, 32) {
1778 assert!(m.insert(i, i*2).is_none());
1780 assert_eq!(m.len(), 32);
1782 let mut observed: u32 = 0;
1784 for (k, v) in m.iter() {
1785 assert_eq!(*v, *k * 2);
1786 observed |= 1 << *k;
1788 assert_eq!(observed, 0xFFFF_FFFF);
1793 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1794 let map = vec.into_iter().collect::<HashMap<int, char>>();
1795 let keys = map.keys().map(|&k| k).collect::<Vec<int>>();
1796 assert_eq!(keys.len(), 3);
1797 assert!(keys.contains(&1));
1798 assert!(keys.contains(&2));
1799 assert!(keys.contains(&3));
1804 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1805 let map = vec.into_iter().collect::<HashMap<int, char>>();
1806 let values = map.values().map(|&v| v).collect::<Vec<char>>();
1807 assert_eq!(values.len(), 3);
1808 assert!(values.contains(&'a'));
1809 assert!(values.contains(&'b'));
1810 assert!(values.contains(&'c'));
1815 let mut m = HashMap::new();
1816 assert!(m.get(&1i).is_none());
1820 Some(v) => assert_eq!(*v, 2)
1825 #[allow(deprecated)]
1826 fn test_find_copy() {
1827 let mut m = HashMap::new();
1828 assert!(m.get(&1i).is_none());
1830 for i in range(1i, 10000) {
1832 match m.find_copy(&i) {
1834 Some(v) => assert_eq!(v, i + 7)
1836 for j in range(1i, i/100) {
1837 match m.find_copy(&j) {
1839 Some(v) => assert_eq!(v, j + 7)
1847 let mut m1 = HashMap::new();
1852 let mut m2 = HashMap::new();
1865 let mut map: HashMap<int, int> = HashMap::new();
1866 let empty: HashMap<int, int> = HashMap::new();
1871 let map_str = format!("{}", map);
1873 assert!(map_str == "{1: 2, 3: 4}".to_string() || map_str == "{3: 4, 1: 2}".to_string());
1874 assert_eq!(format!("{}", empty), "{}".to_string());
1879 let mut m = HashMap::new();
1881 assert_eq!(m.len(), 0);
1882 assert!(m.is_empty());
1885 let old_cap = m.table.capacity();
1886 while old_cap == m.table.capacity() {
1891 assert_eq!(m.len(), i);
1892 assert!(!m.is_empty());
1896 fn test_resize_policy() {
1897 let mut m = HashMap::new();
1899 assert_eq!(m.len(), 0);
1900 assert_eq!(m.table.capacity(), 0);
1901 assert!(m.is_empty());
1905 assert!(m.is_empty());
1906 let initial_cap = m.table.capacity();
1907 m.reserve(initial_cap * 2);
1908 let cap = m.table.capacity();
1910 assert_eq!(cap, initial_cap * 2);
1913 for _ in range(0, cap * 3 / 4) {
1917 // three quarters full
1919 assert_eq!(m.len(), i);
1920 assert_eq!(m.table.capacity(), cap);
1922 for _ in range(0, cap / 4) {
1928 let new_cap = m.table.capacity();
1929 assert_eq!(new_cap, cap * 2);
1931 for _ in range(0, cap / 2 - 1) {
1934 assert_eq!(m.table.capacity(), new_cap);
1936 // A little more than one quarter full.
1937 // Shrinking starts as we remove more elements:
1938 for _ in range(0, cap / 2 - 1) {
1943 assert_eq!(m.len(), i);
1944 assert!(!m.is_empty());
1945 assert_eq!(m.table.capacity(), cap);
1949 fn test_find_equiv() {
1950 let mut m = HashMap::new();
1952 let (foo, bar, baz) = (1i,2i,3i);
1953 m.insert("foo".to_string(), foo);
1954 m.insert("bar".to_string(), bar);
1955 m.insert("baz".to_string(), baz);
1958 assert_eq!(m.get("foo"), Some(&foo));
1959 assert_eq!(m.get("bar"), Some(&bar));
1960 assert_eq!(m.get("baz"), Some(&baz));
1962 assert_eq!(m.get("qux"), None);
1966 fn test_from_iter() {
1967 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1969 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
1971 for &(k, v) in xs.iter() {
1972 assert_eq!(map.get(&k), Some(&v));
1977 fn test_size_hint() {
1978 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1980 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
1982 let mut iter = map.iter();
1984 for _ in iter.by_ref().take(3) {}
1986 assert_eq!(iter.size_hint(), (3, Some(3)));
1990 fn test_mut_size_hint() {
1991 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1993 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
1995 let mut iter = map.iter_mut();
1997 for _ in iter.by_ref().take(3) {}
1999 assert_eq!(iter.size_hint(), (3, Some(3)));
2004 let mut map: HashMap<int, int> = HashMap::new();
2010 assert_eq!(map[2], 1);
2015 fn test_index_nonexistent() {
2016 let mut map: HashMap<int, int> = HashMap::new();
2027 let xs = [(1i, 10i), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2029 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2031 // Existing key (insert)
2032 match map.entry(1) {
2033 Vacant(_) => unreachable!(),
2034 Occupied(mut view) => {
2035 assert_eq!(view.get(), &10);
2036 assert_eq!(view.set(100), 10);
2039 assert_eq!(map.get(&1).unwrap(), &100);
2040 assert_eq!(map.len(), 6);
2043 // Existing key (update)
2044 match map.entry(2) {
2045 Vacant(_) => unreachable!(),
2046 Occupied(mut view) => {
2047 let v = view.get_mut();
2048 let new_v = (*v) * 10;
2052 assert_eq!(map.get(&2).unwrap(), &200);
2053 assert_eq!(map.len(), 6);
2055 // Existing key (take)
2056 match map.entry(3) {
2057 Vacant(_) => unreachable!(),
2059 assert_eq!(view.take(), 30);
2062 assert_eq!(map.get(&3), None);
2063 assert_eq!(map.len(), 5);
2066 // Inexistent key (insert)
2067 match map.entry(10) {
2068 Occupied(_) => unreachable!(),
2070 assert_eq!(*view.set(1000), 1000);
2073 assert_eq!(map.get(&10).unwrap(), &1000);
2074 assert_eq!(map.len(), 6);