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, Map};
25 use mem::{mod, replace};
26 use num::{Int, UnsignedInt};
27 use ops::{Deref, FnMut, 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, F>(table: M,
302 -> SearchResult<K, V, M> where
303 M: Deref<RawTable<K, V>>,
304 F: FnMut(&K) -> bool,
306 let size = table.size();
307 let mut probe = Bucket::new(table, hash);
308 let ib = probe.index();
310 while probe.index() != ib + size {
311 let full = match probe.peek() {
312 Empty(b) => return TableRef(b.into_table()), // hit an empty bucket
316 if full.distance() + ib < full.index() {
317 // We can finish the search early if we hit any bucket
318 // with a lower distance to initial bucket than we've probed.
319 return TableRef(full.into_table());
322 // If the hash doesn't match, it can't be this one..
323 if *hash == full.hash() {
325 let (k, _) = full.read();
329 // If the key doesn't match, it can't be this one..
331 return FoundExisting(full);
338 TableRef(probe.into_table())
341 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
342 let (empty, retkey, retval) = starting_bucket.take();
343 let mut gap = match empty.gap_peek() {
345 None => return (retkey, retval)
348 while gap.full().distance() != 0 {
349 gap = match gap.shift() {
355 // Now we've done all our shifting. Return the value we grabbed earlier.
356 return (retkey, retval);
359 /// Perform robin hood bucket stealing at the given `bucket`. You must
360 /// also pass the position of that bucket's initial bucket so we don't have
361 /// to recalculate it.
363 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
364 fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
370 let starting_index = bucket.index();
372 let table = bucket.table(); // FIXME "lifetime too short".
375 // There can be at most `size - dib` buckets to displace, because
376 // in the worst case, there are `size` elements and we already are
377 // `distance` buckets away from the initial one.
378 let idx_end = starting_index + size - bucket.distance();
381 let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
383 let probe = bucket.next();
384 assert!(probe.index() != idx_end);
386 let full_bucket = match probe.peek() {
387 table::Empty(bucket) => {
389 let b = bucket.put(old_hash, old_key, old_val);
390 // Now that it's stolen, just read the value's pointer
391 // right out of the table!
392 let (_, v) = Bucket::at_index(b.into_table(), starting_index).peek()
397 table::Full(bucket) => bucket
400 let probe_ib = full_bucket.index() - full_bucket.distance();
402 bucket = full_bucket;
404 // Robin hood! Steal the spot.
416 /// A result that works like Option<FullBucket<..>> but preserves
417 /// the reference that grants us access to the table in any case.
418 enum SearchResult<K, V, M> {
419 // This is an entry that holds the given key:
420 FoundExisting(FullBucket<K, V, M>),
422 // There was no such entry. The reference is given back:
426 impl<K, V, M> SearchResult<K, V, M> {
427 fn into_option(self) -> Option<FullBucket<K, V, M>> {
429 FoundExisting(bucket) => Some(bucket),
435 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
436 fn make_hash<Sized? X: Hash<S>>(&self, x: &X) -> SafeHash {
437 table::make_hash(&self.hasher, x)
441 fn search_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, q: &Q)
442 -> Option<FullBucketImm<'a, K, V>> {
443 let hash = self.make_hash(q);
444 search_hashed(&self.table, &hash, |k| q.equiv(k)).into_option()
448 fn search_equiv_mut<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a mut self, q: &Q)
449 -> Option<FullBucketMut<'a, K, V>> {
450 let hash = self.make_hash(q);
451 search_hashed(&mut self.table, &hash, |k| q.equiv(k)).into_option()
454 /// Search for a key, yielding the index if it's found in the hashtable.
455 /// If you already have the hash for the key lying around, use
457 fn search<'a, Sized? Q>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
458 where Q: BorrowFrom<K> + Eq + Hash<S>
460 let hash = self.make_hash(q);
461 search_hashed(&self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
465 fn search_mut<'a, Sized? Q>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
466 where Q: BorrowFrom<K> + Eq + Hash<S>
468 let hash = self.make_hash(q);
469 search_hashed(&mut self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
473 // The caller should ensure that invariants by Robin Hood Hashing hold.
474 fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
475 let cap = self.table.capacity();
476 let mut buckets = Bucket::new(&mut self.table, &hash);
477 let ib = buckets.index();
479 while buckets.index() != ib + cap {
480 // We don't need to compare hashes for value swap.
481 // Not even DIBs for Robin Hood.
482 buckets = match buckets.peek() {
484 empty.put(hash, k, v);
487 Full(b) => b.into_bucket()
491 panic!("Internal HashMap error: Out of space.");
495 impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
496 /// Create an empty HashMap.
501 /// use std::collections::HashMap;
502 /// let mut map: HashMap<&str, int> = HashMap::new();
505 #[unstable = "matches collection reform specification, waiting for dust to settle"]
506 pub fn new() -> HashMap<K, V, RandomSipHasher> {
507 let hasher = RandomSipHasher::new();
508 HashMap::with_hasher(hasher)
511 /// Creates an empty hash map with the given initial capacity.
516 /// use std::collections::HashMap;
517 /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
520 #[unstable = "matches collection reform specification, waiting for dust to settle"]
521 pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> {
522 let hasher = RandomSipHasher::new();
523 HashMap::with_capacity_and_hasher(capacity, hasher)
527 impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
528 /// Creates an empty hashmap which will use the given hasher to hash keys.
530 /// The creates map has the default initial capacity.
535 /// use std::collections::HashMap;
536 /// use std::hash::sip::SipHasher;
538 /// let h = SipHasher::new();
539 /// let mut map = HashMap::with_hasher(h);
540 /// map.insert(1i, 2u);
543 pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
546 resize_policy: DefaultResizePolicy::new(),
547 table: RawTable::new(0),
551 /// Create an empty HashMap with space for at least `capacity`
552 /// elements, using `hasher` to hash the keys.
554 /// Warning: `hasher` is normally randomly generated, and
555 /// is designed to allow HashMaps to be resistant to attacks that
556 /// cause many collisions and very poor performance. Setting it
557 /// manually using this function can expose a DoS attack vector.
562 /// use std::collections::HashMap;
563 /// use std::hash::sip::SipHasher;
565 /// let h = SipHasher::new();
566 /// let mut map = HashMap::with_capacity_and_hasher(10, h);
567 /// map.insert(1i, 2u);
570 pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H> {
571 let resize_policy = DefaultResizePolicy::new();
572 let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
573 let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
574 assert!(internal_cap >= capacity, "capacity overflow");
577 resize_policy: resize_policy,
578 table: RawTable::new(internal_cap),
582 /// Returns the number of elements the map can hold without reallocating.
587 /// use std::collections::HashMap;
588 /// let map: HashMap<int, int> = HashMap::with_capacity(100);
589 /// assert!(map.capacity() >= 100);
592 #[unstable = "matches collection reform specification, waiting for dust to settle"]
593 pub fn capacity(&self) -> uint {
594 self.resize_policy.usable_capacity(self.table.capacity())
597 /// Reserves capacity for at least `additional` more elements to be inserted
598 /// in the `HashMap`. The collection may reserve more space to avoid
599 /// frequent reallocations.
603 /// Panics if the new allocation size overflows `uint`.
608 /// use std::collections::HashMap;
609 /// let mut map: HashMap<&str, int> = HashMap::new();
612 #[unstable = "matches collection reform specification, waiting for dust to settle"]
613 pub fn reserve(&mut self, additional: uint) {
614 let new_size = self.len().checked_add(additional).expect("capacity overflow");
615 let min_cap = self.resize_policy.min_capacity(new_size);
617 // An invalid value shouldn't make us run out of space. This includes
618 // an overflow check.
619 assert!(new_size <= min_cap);
621 if self.table.capacity() < min_cap {
622 let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
623 self.resize(new_capacity);
627 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
628 /// 1) Make sure the new capacity is enough for all the elements, accounting
629 /// for the load factor.
630 /// 2) Ensure new_capacity is a power of two.
631 fn resize(&mut self, new_capacity: uint) {
632 assert!(self.table.size() <= new_capacity);
633 assert!(new_capacity.is_power_of_two());
635 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
636 let old_size = old_table.size();
638 if old_table.capacity() == 0 || old_table.size() == 0 {
643 // Specialization of the other branch.
644 let mut bucket = Bucket::first(&mut old_table);
646 // "So a few of the first shall be last: for many be called,
649 // We'll most likely encounter a few buckets at the beginning that
650 // have their initial buckets near the end of the table. They were
651 // placed at the beginning as the probe wrapped around the table
652 // during insertion. We must skip forward to a bucket that won't
653 // get reinserted too early and won't unfairly steal others spot.
654 // This eliminates the need for robin hood.
656 bucket = match bucket.peek() {
658 if full.distance() == 0 {
659 // This bucket occupies its ideal spot.
660 // It indicates the start of another "cluster".
661 bucket = full.into_bucket();
664 // Leaving this bucket in the last cluster for later.
668 // Encountered a hole between clusters.
675 // This is how the buckets might be laid out in memory:
676 // ($ marks an initialized bucket)
678 // |$$$_$$$$$$_$$$$$|
680 // But we've skipped the entire initial cluster of buckets
681 // and will continue iteration in this order:
684 // ^ wrap around once end is reached
687 // ^ exit once table.size == 0
689 bucket = match bucket.peek() {
691 let h = bucket.hash();
692 let (b, k, v) = bucket.take();
693 self.insert_hashed_ordered(h, k, v);
695 let t = b.table(); // FIXME "lifetime too short".
696 if t.size() == 0 { break }
700 Empty(b) => b.into_bucket()
705 assert_eq!(self.table.size(), old_size);
708 /// Shrinks the capacity of the map as much as possible. It will drop
709 /// down as much as possible while maintaining the internal rules
710 /// and possibly leaving some space in accordance with the resize policy.
715 /// use std::collections::HashMap;
717 /// let mut map: HashMap<int, int> = HashMap::with_capacity(100);
718 /// map.insert(1, 2);
719 /// map.insert(3, 4);
720 /// assert!(map.capacity() >= 100);
721 /// map.shrink_to_fit();
722 /// assert!(map.capacity() >= 2);
724 #[unstable = "matches collection reform specification, waiting for dust to settle"]
725 pub fn shrink_to_fit(&mut self) {
726 let min_capacity = self.resize_policy.min_capacity(self.len());
727 let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
729 // An invalid value shouldn't make us run out of space.
730 debug_assert!(self.len() <= min_capacity);
732 if self.table.capacity() != min_capacity {
733 let old_table = replace(&mut self.table, RawTable::new(min_capacity));
734 let old_size = old_table.size();
736 // Shrink the table. Naive algorithm for resizing:
737 for (h, k, v) in old_table.into_iter() {
738 self.insert_hashed_nocheck(h, k, v);
741 debug_assert_eq!(self.table.size(), old_size);
745 /// Insert a pre-hashed key-value pair, without first checking
746 /// that there's enough room in the buckets. Returns a reference to the
747 /// newly insert value.
749 /// If the key already exists, the hashtable will be returned untouched
750 /// and a reference to the existing element will be returned.
751 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
752 self.insert_or_replace_with(hash, k, v, |_, _, _| ())
755 fn insert_or_replace_with<'a, F>(&'a mut self,
759 mut found_existing: F)
761 F: FnMut(&mut K, &mut V, V),
763 // Worst case, we'll find one empty bucket among `size + 1` buckets.
764 let size = self.table.size();
765 let mut probe = Bucket::new(&mut self.table, &hash);
766 let ib = probe.index();
769 let mut bucket = match probe.peek() {
772 let bucket = bucket.put(hash, k, v);
773 let (_, val) = bucket.into_mut_refs();
776 Full(bucket) => bucket
779 if bucket.hash() == hash {
781 let (bucket_k, _) = bucket.read_mut();
785 let (bucket_k, bucket_v) = bucket.into_mut_refs();
786 debug_assert!(k == *bucket_k);
787 // Key already exists. Get its reference.
788 found_existing(bucket_k, bucket_v, v);
793 let robin_ib = bucket.index() as int - bucket.distance() as int;
795 if (ib as int) < robin_ib {
796 // Found a luckier bucket than me. Better steal his spot.
797 return robin_hood(bucket, robin_ib as uint, hash, k, v);
800 probe = bucket.next();
801 assert!(probe.index() != ib + size + 1);
805 /// Deprecated: use `contains_key` and `BorrowFrom` instead.
806 #[deprecated = "use contains_key and BorrowFrom instead"]
807 pub fn contains_key_equiv<Sized? Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool {
808 self.search_equiv(key).is_some()
811 /// Deprecated: use `get` and `BorrowFrom` instead.
812 #[deprecated = "use get and BorrowFrom instead"]
813 pub fn find_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
814 match self.search_equiv(k) {
817 let (_, v_ref) = bucket.into_refs();
823 /// Deprecated: use `remove` and `BorrowFrom` instead.
824 #[deprecated = "use remove and BorrowFrom instead"]
825 pub fn pop_equiv<Sized? Q:Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V> {
826 if self.table.size() == 0 {
832 match self.search_equiv_mut(k) {
834 let (_k, val) = pop_internal(bucket);
841 /// An iterator visiting all keys in arbitrary order.
842 /// Iterator element type is `&'a K`.
847 /// use std::collections::HashMap;
849 /// let mut map = HashMap::new();
850 /// map.insert("a", 1i);
851 /// map.insert("b", 2);
852 /// map.insert("c", 3);
854 /// for key in map.keys() {
855 /// println!("{}", key);
858 #[unstable = "matches collection reform specification, waiting for dust to settle"]
859 pub fn keys(&self) -> Keys<K, V> {
860 fn first<A, B>((a, _): (A, B)) -> A { a }
862 Keys { inner: self.iter().map(first) }
865 /// An iterator visiting all values in arbitrary order.
866 /// Iterator element type is `&'a V`.
871 /// use std::collections::HashMap;
873 /// let mut map = HashMap::new();
874 /// map.insert("a", 1i);
875 /// map.insert("b", 2);
876 /// map.insert("c", 3);
878 /// for key in map.values() {
879 /// println!("{}", key);
882 #[unstable = "matches collection reform specification, waiting for dust to settle"]
883 pub fn values(&self) -> Values<K, V> {
884 fn second<A, B>((_, b): (A, B)) -> B { b }
886 Values { inner: self.iter().map(second) }
889 /// An iterator visiting all key-value pairs in arbitrary order.
890 /// Iterator element type is `(&'a K, &'a V)`.
895 /// use std::collections::HashMap;
897 /// let mut map = HashMap::new();
898 /// map.insert("a", 1i);
899 /// map.insert("b", 2);
900 /// map.insert("c", 3);
902 /// for (key, val) in map.iter() {
903 /// println!("key: {} val: {}", key, val);
906 #[unstable = "matches collection reform specification, waiting for dust to settle"]
907 pub fn iter(&self) -> Entries<K, V> {
908 Entries { inner: self.table.iter() }
911 /// An iterator visiting all key-value pairs in arbitrary order,
912 /// with mutable references to the values.
913 /// Iterator element type is `(&'a K, &'a mut V)`.
918 /// use std::collections::HashMap;
920 /// let mut map = HashMap::new();
921 /// map.insert("a", 1i);
922 /// map.insert("b", 2);
923 /// map.insert("c", 3);
925 /// // Update all values
926 /// for (_, val) in map.iter_mut() {
930 /// for (key, val) in map.iter() {
931 /// println!("key: {} val: {}", key, val);
934 #[unstable = "matches collection reform specification, waiting for dust to settle"]
935 pub fn iter_mut(&mut self) -> MutEntries<K, V> {
936 MutEntries { inner: self.table.iter_mut() }
939 /// Creates a consuming iterator, that is, one that moves each key-value
940 /// pair out of the map in arbitrary order. The map cannot be used after
946 /// use std::collections::HashMap;
948 /// let mut map = HashMap::new();
949 /// map.insert("a", 1i);
950 /// map.insert("b", 2);
951 /// map.insert("c", 3);
953 /// // Not possible with .iter()
954 /// let vec: Vec<(&str, int)> = map.into_iter().collect();
956 #[unstable = "matches collection reform specification, waiting for dust to settle"]
957 pub fn into_iter(self) -> MoveEntries<K, V> {
958 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
961 inner: self.table.into_iter().map(last_two)
965 /// Gets the given key's corresponding entry in the map for in-place manipulation
966 pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V> {
970 let hash = self.make_hash(&key);
971 search_entry_hashed(&mut self.table, hash, key)
974 /// Return the number of elements in the map.
979 /// use std::collections::HashMap;
981 /// let mut a = HashMap::new();
982 /// assert_eq!(a.len(), 0);
983 /// a.insert(1u, "a");
984 /// assert_eq!(a.len(), 1);
986 #[unstable = "matches collection reform specification, waiting for dust to settle"]
987 pub fn len(&self) -> uint { self.table.size() }
989 /// Return true if the map contains no elements.
994 /// use std::collections::HashMap;
996 /// let mut a = HashMap::new();
997 /// assert!(a.is_empty());
998 /// a.insert(1u, "a");
999 /// assert!(!a.is_empty());
1002 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1003 pub fn is_empty(&self) -> bool { self.len() == 0 }
1005 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1011 /// use std::collections::HashMap;
1013 /// let mut a = HashMap::new();
1014 /// a.insert(1u, "a");
1016 /// assert!(a.is_empty());
1018 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1019 pub fn clear(&mut self) {
1020 let cap = self.table.capacity();
1021 let mut buckets = Bucket::first(&mut self.table);
1023 while buckets.index() != cap {
1024 buckets = match buckets.peek() {
1025 Empty(b) => b.next(),
1027 let (b, _, _) = full.take();
1034 /// Deprecated: Renamed to `get`.
1035 #[deprecated = "Renamed to `get`"]
1036 pub fn find(&self, k: &K) -> Option<&V> {
1040 /// Returns a reference to the value corresponding to the key.
1042 /// The key may be any borrowed form of the map's key type, but
1043 /// `Hash` and `Eq` on the borrowed form *must* match those for
1049 /// use std::collections::HashMap;
1051 /// let mut map = HashMap::new();
1052 /// map.insert(1u, "a");
1053 /// assert_eq!(map.get(&1), Some(&"a"));
1054 /// assert_eq!(map.get(&2), None);
1056 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1057 pub fn get<Sized? Q>(&self, k: &Q) -> Option<&V>
1058 where Q: Hash<S> + Eq + BorrowFrom<K>
1060 self.search(k).map(|bucket| {
1061 let (_, v) = bucket.into_refs();
1066 /// Returns true if the map contains a value for the specified key.
1068 /// The key may be any borrowed form of the map's key type, but
1069 /// `Hash` and `Eq` on the borrowed form *must* match those for
1075 /// use std::collections::HashMap;
1077 /// let mut map = HashMap::new();
1078 /// map.insert(1u, "a");
1079 /// assert_eq!(map.contains_key(&1), true);
1080 /// assert_eq!(map.contains_key(&2), false);
1082 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1083 pub fn contains_key<Sized? Q>(&self, k: &Q) -> bool
1084 where Q: Hash<S> + Eq + BorrowFrom<K>
1086 self.search(k).is_some()
1089 /// Deprecated: Renamed to `get_mut`.
1090 #[deprecated = "Renamed to `get_mut`"]
1091 pub fn find_mut(&mut self, k: &K) -> Option<&mut V> {
1095 /// Returns a mutable reference to the value corresponding to the key.
1097 /// The key may be any borrowed form of the map's key type, but
1098 /// `Hash` and `Eq` on the borrowed form *must* match those for
1104 /// use std::collections::HashMap;
1106 /// let mut map = HashMap::new();
1107 /// map.insert(1u, "a");
1108 /// match map.get_mut(&1) {
1109 /// Some(x) => *x = "b",
1112 /// assert_eq!(map[1], "b");
1114 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1115 pub fn get_mut<Sized? Q>(&mut self, k: &Q) -> Option<&mut V>
1116 where Q: Hash<S> + Eq + BorrowFrom<K>
1118 match self.search_mut(k) {
1120 let (_, v) = bucket.into_mut_refs();
1127 /// Deprecated: Renamed to `insert`.
1128 #[deprecated = "Renamed to `insert`"]
1129 pub fn swap(&mut self, k: K, v: V) -> Option<V> {
1133 /// Inserts a key-value pair from the map. If the key already had a value
1134 /// present in the map, that value is returned. Otherwise, `None` is returned.
1139 /// use std::collections::HashMap;
1141 /// let mut map = HashMap::new();
1142 /// assert_eq!(map.insert(37u, "a"), None);
1143 /// assert_eq!(map.is_empty(), false);
1145 /// map.insert(37, "b");
1146 /// assert_eq!(map.insert(37, "c"), Some("b"));
1147 /// assert_eq!(map[37], "c");
1149 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1150 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1151 let hash = self.make_hash(&k);
1154 let mut retval = None;
1155 self.insert_or_replace_with(hash, k, v, |_, val_ref, val| {
1156 retval = Some(replace(val_ref, val));
1161 /// Deprecated: Renamed to `remove`.
1162 #[deprecated = "Renamed to `remove`"]
1163 pub fn pop(&mut self, k: &K) -> Option<V> {
1167 /// Removes a key from the map, returning the value at the key if the key
1168 /// was previously in the map.
1170 /// The key may be any borrowed form of the map's key type, but
1171 /// `Hash` and `Eq` on the borrowed form *must* match those for
1177 /// use std::collections::HashMap;
1179 /// let mut map = HashMap::new();
1180 /// map.insert(1u, "a");
1181 /// assert_eq!(map.remove(&1), Some("a"));
1182 /// assert_eq!(map.remove(&1), None);
1184 #[unstable = "matches collection reform specification, waiting for dust to settle"]
1185 pub fn remove<Sized? Q>(&mut self, k: &Q) -> Option<V>
1186 where Q: Hash<S> + Eq + BorrowFrom<K>
1188 if self.table.size() == 0 {
1192 self.search_mut(k).map(|bucket| {
1193 let (_k, val) = pop_internal(bucket);
1199 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
1200 -> Entry<'a, K, V> {
1201 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1202 let size = table.size();
1203 let mut probe = Bucket::new(table, &hash);
1204 let ib = probe.index();
1207 let bucket = match probe.peek() {
1210 return Vacant(VacantEntry {
1213 elem: NoElem(bucket),
1216 Full(bucket) => bucket
1219 if bucket.hash() == hash {
1221 let (bucket_k, _) = bucket.read();
1226 return Occupied(OccupiedEntry{
1232 let robin_ib = bucket.index() as int - bucket.distance() as int;
1234 if (ib as int) < robin_ib {
1235 // Found a luckier bucket than me. Better steal his spot.
1236 return Vacant(VacantEntry {
1239 elem: NeqElem(bucket, robin_ib as uint),
1243 probe = bucket.next();
1244 assert!(probe.index() != ib + size + 1);
1248 impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
1249 /// Deprecated: Use `map.get(k).cloned()`.
1251 /// Return a copy of the value corresponding to the key.
1252 #[deprecated = "Use `map.get(k).cloned()`"]
1253 pub fn find_copy(&self, k: &K) -> Option<V> {
1254 self.get(k).cloned()
1257 /// Deprecated: Use `map[k].clone()`.
1259 /// Return a copy of the value corresponding to the key.
1260 #[deprecated = "Use `map[k].clone()`"]
1261 pub fn get_copy(&self, k: &K) -> V {
1266 impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
1267 fn eq(&self, other: &HashMap<K, V, H>) -> bool {
1268 if self.len() != other.len() { return false; }
1270 self.iter().all(|(key, value)|
1271 other.get(key).map_or(false, |v| *value == *v)
1276 impl<K: Eq + Hash<S>, V: Eq, S, H: Hasher<S>> Eq for HashMap<K, V, H> {}
1278 impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
1279 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1280 try!(write!(f, "{{"));
1282 for (i, (k, v)) in self.iter().enumerate() {
1283 if i != 0 { try!(write!(f, ", ")); }
1284 try!(write!(f, "{}: {}", *k, *v));
1291 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
1292 fn default() -> HashMap<K, V, H> {
1293 HashMap::with_hasher(Default::default())
1297 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> Index<Q, V> for HashMap<K, V, H>
1298 where Q: BorrowFrom<K> + Hash<S> + Eq
1301 fn index<'a>(&'a self, index: &Q) -> &'a V {
1302 self.get(index).expect("no entry found for key")
1306 impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> IndexMut<Q, V> for HashMap<K, V, H>
1307 where Q: BorrowFrom<K> + Hash<S> + Eq
1310 fn index_mut<'a>(&'a mut self, index: &Q) -> &'a mut V {
1311 match self.get_mut(index) {
1313 None => panic!("no entry found for key")
1318 /// HashMap iterator
1319 pub struct Entries<'a, K: 'a, V: 'a> {
1320 inner: table::Entries<'a, K, V>
1323 /// HashMap mutable values iterator
1324 pub struct MutEntries<'a, K: 'a, V: 'a> {
1325 inner: table::MutEntries<'a, K, V>
1328 /// HashMap move iterator
1329 pub struct MoveEntries<K, V> {
1333 table::MoveEntries<K, V>,
1334 fn((SafeHash, K, V)) -> (K, V),
1338 /// HashMap keys iterator
1339 pub struct Keys<'a, K: 'a, V: 'a> {
1340 inner: Map<(&'a K, &'a V), &'a K, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
1343 /// HashMap values iterator
1344 pub struct Values<'a, K: 'a, V: 'a> {
1345 inner: Map<(&'a K, &'a V), &'a V, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
1348 /// A view into a single occupied location in a HashMap
1349 pub struct OccupiedEntry<'a, K:'a, V:'a> {
1350 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1353 /// A view into a single empty location in a HashMap
1354 pub struct VacantEntry<'a, K:'a, V:'a> {
1357 elem: VacantEntryState<K,V, &'a mut RawTable<K, V>>,
1360 /// A view into a single location in a map, which may be vacant or occupied
1361 pub enum Entry<'a, K:'a, V:'a> {
1362 /// An occupied Entry
1363 Occupied(OccupiedEntry<'a, K, V>),
1365 Vacant(VacantEntry<'a, K, V>),
1368 /// Possible states of a VacantEntry
1369 enum VacantEntryState<K, V, M> {
1370 /// The index is occupied, but the key to insert has precedence,
1371 /// and will kick the current one out on insertion
1372 NeqElem(FullBucket<K, V, M>, uint),
1373 /// The index is genuinely vacant
1374 NoElem(EmptyBucket<K, V, M>),
1377 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
1378 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1379 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1382 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
1383 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1384 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1387 impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
1388 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1389 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1392 impl<'a, K, V> Iterator<&'a K> for Keys<'a, K, V> {
1393 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1394 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1397 impl<'a, K, V> Iterator<&'a V> for Values<'a, K, V> {
1398 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1399 #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
1402 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1403 /// Gets a reference to the value in the entry
1404 pub fn get(&self) -> &V {
1405 let (_, v) = self.elem.read();
1409 /// Gets a mutable reference to the value in the entry
1410 pub fn get_mut(&mut self) -> &mut V {
1411 let (_, v) = self.elem.read_mut();
1415 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1416 /// with a lifetime bound to the map itself
1417 pub fn into_mut(self) -> &'a mut V {
1418 let (_, v) = self.elem.into_mut_refs();
1422 /// Sets the value of the entry, and returns the entry's old value
1423 pub fn set(&mut self, mut value: V) -> V {
1424 let old_value = self.get_mut();
1425 mem::swap(&mut value, old_value);
1429 /// Takes the value out of the entry, and returns it
1430 pub fn take(self) -> V {
1431 let (_, v) = pop_internal(self.elem);
1436 impl<'a, K, V> VacantEntry<'a, K, V> {
1437 /// Sets the value of the entry with the VacantEntry's key,
1438 /// and returns a mutable reference to it
1439 pub fn set(self, value: V) -> &'a mut V {
1441 NeqElem(bucket, ib) => {
1442 robin_hood(bucket, ib, self.hash, self.key, value)
1445 let full = bucket.put(self.hash, self.key, value);
1446 let (_, v) = full.into_mut_refs();
1453 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
1454 fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
1455 let (lower, _) = iter.size_hint();
1456 let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1462 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Extend<(K, V)> for HashMap<K, V, H> {
1463 fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
1464 for (k, v) in iter {
1475 use super::{Occupied, Vacant};
1478 use iter::{Iterator,range_inclusive,range_step_inclusive};
1480 use rand::{weak_rng, Rng};
1482 struct KindaIntLike(int);
1484 impl Equiv<int> for KindaIntLike {
1485 fn equiv(&self, other: &int) -> bool {
1486 let KindaIntLike(this) = *self;
1490 impl<S: hash::Writer> hash::Hash<S> for KindaIntLike {
1491 fn hash(&self, state: &mut S) {
1492 let KindaIntLike(this) = *self;
1498 fn test_create_capacity_zero() {
1499 let mut m = HashMap::with_capacity(0);
1501 assert!(m.insert(1i, 1i).is_none());
1503 assert!(m.contains_key(&1));
1504 assert!(!m.contains_key(&0));
1509 let mut m = HashMap::new();
1510 assert_eq!(m.len(), 0);
1511 assert!(m.insert(1i, 2i).is_none());
1512 assert_eq!(m.len(), 1);
1513 assert!(m.insert(2i, 4i).is_none());
1514 assert_eq!(m.len(), 2);
1515 assert_eq!(*m.get(&1).unwrap(), 2);
1516 assert_eq!(*m.get(&2).unwrap(), 4);
1519 thread_local!(static DROP_VECTOR: RefCell<Vec<int>> = RefCell::new(Vec::new()))
1521 #[deriving(Hash, PartialEq, Eq)]
1527 fn new(k: uint) -> Dropable {
1528 DROP_VECTOR.with(|slot| {
1529 slot.borrow_mut()[k] += 1;
1536 impl Drop for Dropable {
1537 fn drop(&mut self) {
1538 DROP_VECTOR.with(|slot| {
1539 slot.borrow_mut()[self.k] -= 1;
1544 impl Clone for Dropable {
1545 fn clone(&self) -> Dropable {
1546 Dropable::new(self.k)
1552 DROP_VECTOR.with(|slot| {
1553 *slot.borrow_mut() = Vec::from_elem(200, 0i);
1557 let mut m = HashMap::new();
1559 DROP_VECTOR.with(|v| {
1560 for i in range(0u, 200) {
1561 assert_eq!(v.borrow()[i], 0);
1565 for i in range(0u, 100) {
1566 let d1 = Dropable::new(i);
1567 let d2 = Dropable::new(i+100);
1571 DROP_VECTOR.with(|v| {
1572 for i in range(0u, 200) {
1573 assert_eq!(v.borrow()[i], 1);
1577 for i in range(0u, 50) {
1578 let k = Dropable::new(i);
1579 let v = m.remove(&k);
1581 assert!(v.is_some());
1583 DROP_VECTOR.with(|v| {
1584 assert_eq!(v.borrow()[i], 1);
1585 assert_eq!(v.borrow()[i+100], 1);
1589 DROP_VECTOR.with(|v| {
1590 for i in range(0u, 50) {
1591 assert_eq!(v.borrow()[i], 0);
1592 assert_eq!(v.borrow()[i+100], 0);
1595 for i in range(50u, 100) {
1596 assert_eq!(v.borrow()[i], 1);
1597 assert_eq!(v.borrow()[i+100], 1);
1602 DROP_VECTOR.with(|v| {
1603 for i in range(0u, 200) {
1604 assert_eq!(v.borrow()[i], 0);
1610 fn test_move_iter_drops() {
1611 DROP_VECTOR.with(|v| {
1612 *v.borrow_mut() = Vec::from_elem(200, 0i);
1616 let mut hm = HashMap::new();
1618 DROP_VECTOR.with(|v| {
1619 for i in range(0u, 200) {
1620 assert_eq!(v.borrow()[i], 0);
1624 for i in range(0u, 100) {
1625 let d1 = Dropable::new(i);
1626 let d2 = Dropable::new(i+100);
1630 DROP_VECTOR.with(|v| {
1631 for i in range(0u, 200) {
1632 assert_eq!(v.borrow()[i], 1);
1639 // By the way, ensure that cloning doesn't screw up the dropping.
1643 let mut half = hm.into_iter().take(50);
1645 DROP_VECTOR.with(|v| {
1646 for i in range(0u, 200) {
1647 assert_eq!(v.borrow()[i], 1);
1653 DROP_VECTOR.with(|v| {
1654 let nk = range(0u, 100).filter(|&i| {
1658 let nv = range(0u, 100).filter(|&i| {
1659 v.borrow()[i+100] == 1
1667 DROP_VECTOR.with(|v| {
1668 for i in range(0u, 200) {
1669 assert_eq!(v.borrow()[i], 0);
1675 fn test_empty_pop() {
1676 let mut m: HashMap<int, bool> = HashMap::new();
1677 assert_eq!(m.remove(&0), None);
1681 fn test_lots_of_insertions() {
1682 let mut m = HashMap::new();
1684 // Try this a few times to make sure we never screw up the hashmap's
1686 for _ in range(0i, 10) {
1687 assert!(m.is_empty());
1689 for i in range_inclusive(1i, 1000) {
1690 assert!(m.insert(i, i).is_none());
1692 for j in range_inclusive(1, i) {
1694 assert_eq!(r, Some(&j));
1697 for j in range_inclusive(i+1, 1000) {
1699 assert_eq!(r, None);
1703 for i in range_inclusive(1001i, 2000) {
1704 assert!(!m.contains_key(&i));
1708 for i in range_inclusive(1i, 1000) {
1709 assert!(m.remove(&i).is_some());
1711 for j in range_inclusive(1, i) {
1712 assert!(!m.contains_key(&j));
1715 for j in range_inclusive(i+1, 1000) {
1716 assert!(m.contains_key(&j));
1720 for i in range_inclusive(1i, 1000) {
1721 assert!(!m.contains_key(&i));
1724 for i in range_inclusive(1i, 1000) {
1725 assert!(m.insert(i, i).is_none());
1729 for i in range_step_inclusive(1000i, 1, -1) {
1730 assert!(m.remove(&i).is_some());
1732 for j in range_inclusive(i, 1000) {
1733 assert!(!m.contains_key(&j));
1736 for j in range_inclusive(1, i-1) {
1737 assert!(m.contains_key(&j));
1744 fn test_find_mut() {
1745 let mut m = HashMap::new();
1746 assert!(m.insert(1i, 12i).is_none());
1747 assert!(m.insert(2i, 8i).is_none());
1748 assert!(m.insert(5i, 14i).is_none());
1750 match m.get_mut(&5) {
1751 None => panic!(), Some(x) => *x = new
1753 assert_eq!(m.get(&5), Some(&new));
1757 fn test_insert_overwrite() {
1758 let mut m = HashMap::new();
1759 assert!(m.insert(1i, 2i).is_none());
1760 assert_eq!(*m.get(&1).unwrap(), 2);
1761 assert!(!m.insert(1i, 3i).is_none());
1762 assert_eq!(*m.get(&1).unwrap(), 3);
1766 fn test_insert_conflicts() {
1767 let mut m = HashMap::with_capacity(4);
1768 assert!(m.insert(1i, 2i).is_none());
1769 assert!(m.insert(5i, 3i).is_none());
1770 assert!(m.insert(9i, 4i).is_none());
1771 assert_eq!(*m.get(&9).unwrap(), 4);
1772 assert_eq!(*m.get(&5).unwrap(), 3);
1773 assert_eq!(*m.get(&1).unwrap(), 2);
1777 fn test_conflict_remove() {
1778 let mut m = HashMap::with_capacity(4);
1779 assert!(m.insert(1i, 2i).is_none());
1780 assert_eq!(*m.get(&1).unwrap(), 2);
1781 assert!(m.insert(5, 3).is_none());
1782 assert_eq!(*m.get(&1).unwrap(), 2);
1783 assert_eq!(*m.get(&5).unwrap(), 3);
1784 assert!(m.insert(9, 4).is_none());
1785 assert_eq!(*m.get(&1).unwrap(), 2);
1786 assert_eq!(*m.get(&5).unwrap(), 3);
1787 assert_eq!(*m.get(&9).unwrap(), 4);
1788 assert!(m.remove(&1).is_some());
1789 assert_eq!(*m.get(&9).unwrap(), 4);
1790 assert_eq!(*m.get(&5).unwrap(), 3);
1794 fn test_is_empty() {
1795 let mut m = HashMap::with_capacity(4);
1796 assert!(m.insert(1i, 2i).is_none());
1797 assert!(!m.is_empty());
1798 assert!(m.remove(&1).is_some());
1799 assert!(m.is_empty());
1804 let mut m = HashMap::new();
1806 assert_eq!(m.remove(&1), Some(2));
1807 assert_eq!(m.remove(&1), None);
1811 #[allow(experimental)]
1812 fn test_pop_equiv() {
1813 let mut m = HashMap::new();
1815 assert_eq!(m.pop_equiv(&KindaIntLike(1)), Some(2));
1816 assert_eq!(m.pop_equiv(&KindaIntLike(1)), None);
1821 let mut m = HashMap::with_capacity(4);
1822 for i in range(0u, 32) {
1823 assert!(m.insert(i, i*2).is_none());
1825 assert_eq!(m.len(), 32);
1827 let mut observed: u32 = 0;
1829 for (k, v) in m.iter() {
1830 assert_eq!(*v, *k * 2);
1831 observed |= 1 << *k;
1833 assert_eq!(observed, 0xFFFF_FFFF);
1838 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1839 let map = vec.into_iter().collect::<HashMap<int, char>>();
1840 let keys = map.keys().map(|&k| k).collect::<Vec<int>>();
1841 assert_eq!(keys.len(), 3);
1842 assert!(keys.contains(&1));
1843 assert!(keys.contains(&2));
1844 assert!(keys.contains(&3));
1849 let vec = vec![(1i, 'a'), (2i, 'b'), (3i, 'c')];
1850 let map = vec.into_iter().collect::<HashMap<int, char>>();
1851 let values = map.values().map(|&v| v).collect::<Vec<char>>();
1852 assert_eq!(values.len(), 3);
1853 assert!(values.contains(&'a'));
1854 assert!(values.contains(&'b'));
1855 assert!(values.contains(&'c'));
1860 let mut m = HashMap::new();
1861 assert!(m.get(&1i).is_none());
1865 Some(v) => assert_eq!(*v, 2)
1870 #[allow(deprecated)]
1871 fn test_find_copy() {
1872 let mut m = HashMap::new();
1873 assert!(m.get(&1i).is_none());
1875 for i in range(1i, 10000) {
1877 match m.find_copy(&i) {
1879 Some(v) => assert_eq!(v, i + 7)
1881 for j in range(1i, i/100) {
1882 match m.find_copy(&j) {
1884 Some(v) => assert_eq!(v, j + 7)
1892 let mut m1 = HashMap::new();
1897 let mut m2 = HashMap::new();
1910 let mut map: HashMap<int, int> = HashMap::new();
1911 let empty: HashMap<int, int> = HashMap::new();
1916 let map_str = format!("{}", map);
1918 assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}");
1919 assert_eq!(format!("{}", empty), "{}");
1924 let mut m = HashMap::new();
1926 assert_eq!(m.len(), 0);
1927 assert!(m.is_empty());
1930 let old_cap = m.table.capacity();
1931 while old_cap == m.table.capacity() {
1936 assert_eq!(m.len(), i);
1937 assert!(!m.is_empty());
1941 fn test_behavior_resize_policy() {
1942 let mut m = HashMap::new();
1944 assert_eq!(m.len(), 0);
1945 assert_eq!(m.table.capacity(), 0);
1946 assert!(m.is_empty());
1950 assert!(m.is_empty());
1951 let initial_cap = m.table.capacity();
1952 m.reserve(initial_cap);
1953 let cap = m.table.capacity();
1955 assert_eq!(cap, initial_cap * 2);
1958 for _ in range(0, cap * 3 / 4) {
1962 // three quarters full
1964 assert_eq!(m.len(), i);
1965 assert_eq!(m.table.capacity(), cap);
1967 for _ in range(0, cap / 4) {
1973 let new_cap = m.table.capacity();
1974 assert_eq!(new_cap, cap * 2);
1976 for _ in range(0, cap / 2 - 1) {
1979 assert_eq!(m.table.capacity(), new_cap);
1981 // A little more than one quarter full.
1983 assert_eq!(m.table.capacity(), cap);
1984 // again, a little more than half full
1985 for _ in range(0, cap / 2 - 1) {
1991 assert_eq!(m.len(), i);
1992 assert!(!m.is_empty());
1993 assert_eq!(m.table.capacity(), initial_cap);
1997 fn test_reserve_shrink_to_fit() {
1998 let mut m = HashMap::new();
2001 assert!(m.capacity() >= m.len());
2002 for i in range(0, 128) {
2007 let usable_cap = m.capacity();
2008 for i in range(128, 128+256) {
2010 assert_eq!(m.capacity(), usable_cap);
2013 for i in range(100, 128+256) {
2014 assert_eq!(m.remove(&i), Some(i));
2018 assert_eq!(m.len(), 100);
2019 assert!(!m.is_empty());
2020 assert!(m.capacity() >= m.len());
2022 for i in range(0, 100) {
2023 assert_eq!(m.remove(&i), Some(i));
2028 assert_eq!(m.len(), 1);
2029 assert!(m.capacity() >= m.len());
2030 assert_eq!(m.remove(&0), Some(0));
2034 fn test_find_equiv() {
2035 let mut m = HashMap::new();
2037 let (foo, bar, baz) = (1i,2i,3i);
2038 m.insert("foo".to_string(), foo);
2039 m.insert("bar".to_string(), bar);
2040 m.insert("baz".to_string(), baz);
2043 assert_eq!(m.get("foo"), Some(&foo));
2044 assert_eq!(m.get("bar"), Some(&bar));
2045 assert_eq!(m.get("baz"), Some(&baz));
2047 assert_eq!(m.get("qux"), None);
2051 fn test_from_iter() {
2052 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2054 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2056 for &(k, v) in xs.iter() {
2057 assert_eq!(map.get(&k), Some(&v));
2062 fn test_size_hint() {
2063 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2065 let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2067 let mut iter = map.iter();
2069 for _ in iter.by_ref().take(3) {}
2071 assert_eq!(iter.size_hint(), (3, Some(3)));
2075 fn test_mut_size_hint() {
2076 let xs = [(1i, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2078 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2080 let mut iter = map.iter_mut();
2082 for _ in iter.by_ref().take(3) {}
2084 assert_eq!(iter.size_hint(), (3, Some(3)));
2089 let mut map: HashMap<int, int> = HashMap::new();
2095 assert_eq!(map[2], 1);
2100 fn test_index_nonexistent() {
2101 let mut map: HashMap<int, int> = HashMap::new();
2112 let xs = [(1i, 10i), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2114 let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
2116 // Existing key (insert)
2117 match map.entry(1) {
2118 Vacant(_) => unreachable!(),
2119 Occupied(mut view) => {
2120 assert_eq!(view.get(), &10);
2121 assert_eq!(view.set(100), 10);
2124 assert_eq!(map.get(&1).unwrap(), &100);
2125 assert_eq!(map.len(), 6);
2128 // Existing key (update)
2129 match map.entry(2) {
2130 Vacant(_) => unreachable!(),
2131 Occupied(mut view) => {
2132 let v = view.get_mut();
2133 let new_v = (*v) * 10;
2137 assert_eq!(map.get(&2).unwrap(), &200);
2138 assert_eq!(map.len(), 6);
2140 // Existing key (take)
2141 match map.entry(3) {
2142 Vacant(_) => unreachable!(),
2144 assert_eq!(view.take(), 30);
2147 assert_eq!(map.get(&3), None);
2148 assert_eq!(map.len(), 5);
2151 // Inexistent key (insert)
2152 match map.entry(10) {
2153 Occupied(_) => unreachable!(),
2155 assert_eq!(*view.set(1000), 1000);
2158 assert_eq!(map.get(&10).unwrap(), &1000);
2159 assert_eq!(map.len(), 6);
2163 fn test_entry_take_doesnt_corrupt() {
2165 fn check(m: &HashMap<int, ()>) {
2167 assert!(m.contains_key(k),
2168 "{} is in keys() but not in the map?", k);
2172 let mut m = HashMap::new();
2173 let mut rng = weak_rng();
2175 // Populate the map with some items.
2176 for _ in range(0u, 50) {
2177 let x = rng.gen_range(-10, 10);
2181 for i in range(0u, 1000) {
2182 let x = rng.gen_range(-10, 10);
2186 println!("{}: remove {}", i, x);