1 // Copyright 2014-2015 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
14 use self::SearchResult::*;
15 use self::VacantEntryState::*;
19 use cmp::{max, Eq, PartialEq};
21 use fmt::{self, Debug};
22 use hash::{Hash, SipHasher};
23 use iter::{self, Iterator, ExactSizeIterator, IntoIterator, IteratorExt, FromIterator, Extend, Map};
25 use mem::{self, replace};
26 use ops::{Deref, FnMut, Index};
27 use option::Option::{self, Some, None};
28 use rand::{self, Rng};
29 use result::Result::{self, Ok, Err};
41 use super::table::BucketState::{
45 use super::state::HashState;
47 const INITIAL_LOG2_CAP: usize = 5;
48 #[unstable(feature = "std_misc")]
49 pub const INITIAL_CAPACITY: usize = 1 << INITIAL_LOG2_CAP; // 2^5
51 /// The default behavior of HashMap implements a load factor of 90.9%.
52 /// This behavior is characterized by the following condition:
54 /// - if size > 0.909 * capacity: grow the map
56 struct DefaultResizePolicy;
58 impl DefaultResizePolicy {
59 fn new() -> DefaultResizePolicy {
64 fn min_capacity(&self, usable_size: usize) -> usize {
65 // Here, we are rephrasing the logic by specifying the lower limit
68 // - if `cap < size * 1.1`: grow the map
72 /// An inverse of `min_capacity`, approximately.
74 fn usable_capacity(&self, cap: usize) -> usize {
75 // As the number of entries approaches usable capacity,
76 // min_capacity(size) must be smaller than the internal capacity,
77 // so that the map is not resized:
78 // `min_capacity(usable_capacity(x)) <= x`.
79 // The left-hand side can only be smaller due to flooring by integer
82 // This doesn't have to be checked for overflow since allocation size
83 // in bytes will overflow earlier than multiplication by 10.
89 fn test_resize_policy() {
90 let rp = DefaultResizePolicy;
92 assert!(rp.min_capacity(rp.usable_capacity(n)) <= n);
93 assert!(rp.usable_capacity(rp.min_capacity(n)) <= n);
97 // The main performance trick in this hashmap is called Robin Hood Hashing.
98 // It gains its excellent performance from one essential operation:
100 // If an insertion collides with an existing element, and that element's
101 // "probe distance" (how far away the element is from its ideal location)
102 // is higher than how far we've already probed, swap the elements.
104 // This massively lowers variance in probe distance, and allows us to get very
105 // high load factors with good performance. The 90% load factor I use is rather
108 // > Why a load factor of approximately 90%?
110 // In general, all the distances to initial buckets will converge on the mean.
111 // At a load factor of α, the odds of finding the target bucket after k
112 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
113 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
114 // this down to make the math easier on the CPU and avoid its FPU.
115 // Since on average we start the probing in the middle of a cache line, this
116 // strategy pulls in two cache lines of hashes on every lookup. I think that's
117 // pretty good, but if you want to trade off some space, it could go down to one
118 // cache line on average with an α of 0.84.
120 // > Wait, what? Where did you get 1-α^k from?
122 // On the first probe, your odds of a collision with an existing element is α.
123 // The odds of doing this twice in a row is approximately α^2. For three times,
124 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
125 // colliding after k tries is 1-α^k.
127 // The paper from 1986 cited below mentions an implementation which keeps track
128 // of the distance-to-initial-bucket histogram. This approach is not suitable
129 // for modern architectures because it requires maintaining an internal data
130 // structure. This allows very good first guesses, but we are most concerned
131 // with guessing entire cache lines, not individual indexes. Furthermore, array
132 // accesses are no longer linear and in one direction, as we have now. There
133 // is also memory and cache pressure that this would entail that would be very
134 // difficult to properly see in a microbenchmark.
136 // ## Future Improvements (FIXME!)
138 // Allow the load factor to be changed dynamically and/or at initialization.
140 // Also, would it be possible for us to reuse storage when growing the
141 // underlying table? This is exactly the use case for 'realloc', and may
142 // be worth exploring.
144 // ## Future Optimizations (FIXME!)
146 // Another possible design choice that I made without any real reason is
147 // parameterizing the raw table over keys and values. Technically, all we need
148 // is the size and alignment of keys and values, and the code should be just as
149 // efficient (well, we might need one for power-of-two size and one for not...).
150 // This has the potential to reduce code bloat in rust executables, without
151 // really losing anything except 4 words (key size, key alignment, val size,
152 // val alignment) which can be passed in to every call of a `RawTable` function.
153 // This would definitely be an avenue worth exploring if people start complaining
154 // about the size of rust executables.
156 // Annotate exceedingly likely branches in `table::make_hash`
157 // and `search_hashed` to reduce instruction cache pressure
158 // and mispredictions once it becomes possible (blocked on issue #11092).
160 // Shrinking the table could simply reallocate in place after moving buckets
161 // to the first half.
163 // The growth algorithm (fragment of the Proof of Correctness)
164 // --------------------
166 // The growth algorithm is basically a fast path of the naive reinsertion-
167 // during-resize algorithm. Other paths should never be taken.
169 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
170 // by allocating a new table of capacity `2n`, and then individually reinsert
171 // each element in the old table into the new one. This guarantees that the
172 // new table is a valid robin hood hashtable with all the desired statistical
173 // properties. Remark that the order we reinsert the elements in should not
174 // matter. For simplicity and efficiency, we will consider only linear
175 // reinsertions, which consist of reinserting all elements in the old table
176 // into the new one by increasing order of index. However we will not be
177 // starting our reinsertions from index 0 in general. If we start from index
178 // i, for the purpose of reinsertion we will consider all elements with real
179 // index j < i to have virtual index n + j.
181 // Our hash generation scheme consists of generating a 64-bit hash and
182 // truncating the most significant bits. When moving to the new table, we
183 // simply introduce a new bit to the front of the hash. Therefore, if an
184 // elements has ideal index i in the old table, it can have one of two ideal
185 // locations in the new table. If the new bit is 0, then the new ideal index
186 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
187 // we are producing two independent tables of size n, and for each element we
188 // independently choose which table to insert it into with equal probability.
189 // However the rather than wrapping around themselves on overflowing their
190 // indexes, the first table overflows into the first, and the first into the
191 // second. Visually, our new table will look something like:
193 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
195 // Where x's are elements inserted into the first table, y's are elements
196 // inserted into the second, and _'s are empty sections. We now define a few
197 // key concepts that we will use later. Note that this is a very abstract
198 // perspective of the table. A real resized table would be at least half
201 // Theorem: A linear robin hood reinsertion from the first ideal element
202 // produces identical results to a linear naive reinsertion from the same
205 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
207 /// A hash map implementation which uses linear probing with Robin
208 /// Hood bucket stealing.
210 /// The hashes are all keyed by the task-local random number generator
211 /// on creation by default. This means that the ordering of the keys is
212 /// randomized, but makes the tables more resistant to
213 /// denial-of-service attacks (Hash DoS). This behaviour can be
214 /// overridden with one of the constructors.
216 /// It is required that the keys implement the `Eq` and `Hash` traits, although
217 /// this can frequently be achieved by using `#[derive(Eq, Hash)]`.
219 /// It is a logic error for a key to be modified in such a way that the key's
220 /// hash, as determined by the `Hash` trait, or its equality, as determined by
221 /// the `Eq` trait, changes while it is in the map. This is normally only
222 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
224 /// Relevant papers/articles:
226 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
227 /// 2. Emmanuel Goossaert. ["Robin Hood
228 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
229 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
230 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
235 /// use std::collections::HashMap;
237 /// // type inference lets us omit an explicit type signature (which
238 /// // would be `HashMap<&str, &str>` in this example).
239 /// let mut book_reviews = HashMap::new();
241 /// // review some books.
242 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
243 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
244 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
245 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
247 /// // check for a specific one.
248 /// if !book_reviews.contains_key(&("Les Misérables")) {
249 /// println!("We've got {} reviews, but Les Misérables ain't one.",
250 /// book_reviews.len());
253 /// // oops, this review has a lot of spelling mistakes, let's delete it.
254 /// book_reviews.remove(&("The Adventures of Sherlock Holmes"));
256 /// // look up the values associated with some keys.
257 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
258 /// for book in to_find.iter() {
259 /// match book_reviews.get(book) {
260 /// Some(review) => println!("{}: {}", *book, *review),
261 /// None => println!("{} is unreviewed.", *book)
265 /// // iterate over everything.
266 /// for (book, review) in book_reviews.iter() {
267 /// println!("{}: \"{}\"", *book, *review);
271 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
272 /// We must also derive `PartialEq`.
275 /// use std::collections::HashMap;
277 /// #[derive(Hash, Eq, PartialEq, Debug)]
284 /// /// Create a new Viking.
285 /// fn new(name: &str, country: &str) -> Viking {
286 /// Viking { name: name.to_string(), country: country.to_string() }
290 /// // Use a HashMap to store the vikings' health points.
291 /// let mut vikings = HashMap::new();
293 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
294 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
295 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
297 /// // Use derived implementation to print the status of the vikings.
298 /// for (viking, health) in vikings.iter() {
299 /// println!("{:?} has {} hp", viking, health);
303 #[stable(feature = "rust1", since = "1.0.0")]
304 pub struct HashMap<K, V, S = RandomState> {
305 // All hashes are keyed on these values, to prevent hash collision attacks.
308 table: RawTable<K, V>,
310 resize_policy: DefaultResizePolicy,
313 /// Search for a pre-hashed key.
314 fn search_hashed<K, V, M, F>(table: M,
317 -> SearchResult<K, V, M> where
318 M: Deref<Target=RawTable<K, V>>,
319 F: FnMut(&K) -> bool,
321 // This is the only function where capacity can be zero. To avoid
322 // undefined behaviour when Bucket::new gets the raw bucket in this
323 // case, immediately return the appropriate search result.
324 if table.capacity() == 0 {
325 return TableRef(table);
328 let size = table.size();
329 let mut probe = Bucket::new(table, hash);
330 let ib = probe.index();
332 while probe.index() != ib + size {
333 let full = match probe.peek() {
334 Empty(b) => return TableRef(b.into_table()), // hit an empty bucket
338 if full.distance() + ib < full.index() {
339 // We can finish the search early if we hit any bucket
340 // with a lower distance to initial bucket than we've probed.
341 return TableRef(full.into_table());
344 // If the hash doesn't match, it can't be this one..
345 if hash == full.hash() {
346 // If the key doesn't match, it can't be this one..
347 if is_match(full.read().0) {
348 return FoundExisting(full);
355 TableRef(probe.into_table())
358 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
359 let (empty, retkey, retval) = starting_bucket.take();
360 let mut gap = match empty.gap_peek() {
362 None => return (retkey, retval)
365 while gap.full().distance() != 0 {
366 gap = match gap.shift() {
372 // Now we've done all our shifting. Return the value we grabbed earlier.
376 /// Perform robin hood bucket stealing at the given `bucket`. You must
377 /// also pass the position of that bucket's initial bucket so we don't have
378 /// to recalculate it.
380 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
381 fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
387 let starting_index = bucket.index();
389 let table = bucket.table(); // FIXME "lifetime too short".
392 // There can be at most `size - dib` buckets to displace, because
393 // in the worst case, there are `size` elements and we already are
394 // `distance` buckets away from the initial one.
395 let idx_end = starting_index + size - bucket.distance();
398 let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
400 let probe = bucket.next();
401 assert!(probe.index() != idx_end);
403 let full_bucket = match probe.peek() {
406 let b = bucket.put(old_hash, old_key, old_val);
407 // Now that it's stolen, just read the value's pointer
408 // right out of the table!
409 return Bucket::at_index(b.into_table(), starting_index)
415 Full(bucket) => bucket
418 let probe_ib = full_bucket.index() - full_bucket.distance();
420 bucket = full_bucket;
422 // Robin hood! Steal the spot.
434 /// A result that works like Option<FullBucket<..>> but preserves
435 /// the reference that grants us access to the table in any case.
436 enum SearchResult<K, V, M> {
437 // This is an entry that holds the given key:
438 FoundExisting(FullBucket<K, V, M>),
440 // There was no such entry. The reference is given back:
444 impl<K, V, M> SearchResult<K, V, M> {
445 fn into_option(self) -> Option<FullBucket<K, V, M>> {
447 FoundExisting(bucket) => Some(bucket),
453 impl<K, V, S> HashMap<K, V, S>
454 where K: Eq + Hash, S: HashState
456 fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash {
457 table::make_hash(&self.hash_state, x)
460 /// Search for a key, yielding the index if it's found in the hashtable.
461 /// If you already have the hash for the key lying around, use
463 fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
464 where K: Borrow<Q>, Q: Eq + Hash
466 let hash = self.make_hash(q);
467 search_hashed(&self.table, hash, |k| q.eq(k.borrow()))
471 fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
472 where K: Borrow<Q>, Q: Eq + Hash
474 let hash = self.make_hash(q);
475 search_hashed(&mut self.table, hash, |k| q.eq(k.borrow()))
479 // The caller should ensure that invariants by Robin Hood Hashing hold.
480 fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
481 let cap = self.table.capacity();
482 let mut buckets = Bucket::new(&mut self.table, hash);
483 let ib = buckets.index();
485 while buckets.index() != ib + cap {
486 // We don't need to compare hashes for value swap.
487 // Not even DIBs for Robin Hood.
488 buckets = match buckets.peek() {
490 empty.put(hash, k, v);
493 Full(b) => b.into_bucket()
497 panic!("Internal HashMap error: Out of space.");
501 impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
502 /// Create an empty HashMap.
507 /// use std::collections::HashMap;
508 /// let mut map: HashMap<&str, int> = HashMap::new();
511 #[stable(feature = "rust1", since = "1.0.0")]
512 pub fn new() -> HashMap<K, V, RandomState> {
516 /// Creates an empty hash map with the given initial capacity.
521 /// use std::collections::HashMap;
522 /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10);
525 #[stable(feature = "rust1", since = "1.0.0")]
526 pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
527 HashMap::with_capacity_and_hash_state(capacity, Default::default())
531 impl<K, V, S> HashMap<K, V, S>
532 where K: Eq + Hash, S: HashState
534 /// Creates an empty hashmap which will use the given hasher to hash keys.
536 /// The creates map has the default initial capacity.
541 /// use std::collections::HashMap;
542 /// use std::collections::hash_map::RandomState;
544 /// let s = RandomState::new();
545 /// let mut map = HashMap::with_hash_state(s);
546 /// map.insert(1, 2);
549 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
550 pub fn with_hash_state(hash_state: S) -> HashMap<K, V, S> {
552 hash_state: hash_state,
553 resize_policy: DefaultResizePolicy::new(),
554 table: RawTable::new(0),
558 /// Create an empty HashMap with space for at least `capacity`
559 /// elements, using `hasher` to hash the keys.
561 /// Warning: `hasher` is normally randomly generated, and
562 /// is designed to allow HashMaps to be resistant to attacks that
563 /// cause many collisions and very poor performance. Setting it
564 /// manually using this function can expose a DoS attack vector.
569 /// use std::collections::HashMap;
570 /// use std::collections::hash_map::RandomState;
572 /// let s = RandomState::new();
573 /// let mut map = HashMap::with_capacity_and_hash_state(10, s);
574 /// map.insert(1, 2);
577 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
578 pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S)
579 -> HashMap<K, V, S> {
580 let resize_policy = DefaultResizePolicy::new();
581 let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
582 let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
583 assert!(internal_cap >= capacity, "capacity overflow");
585 hash_state: hash_state,
586 resize_policy: resize_policy,
587 table: RawTable::new(internal_cap),
591 /// Returns the number of elements the map can hold without reallocating.
596 /// use std::collections::HashMap;
597 /// let map: HashMap<int, int> = HashMap::with_capacity(100);
598 /// assert!(map.capacity() >= 100);
601 #[stable(feature = "rust1", since = "1.0.0")]
602 pub fn capacity(&self) -> usize {
603 self.resize_policy.usable_capacity(self.table.capacity())
606 /// Reserves capacity for at least `additional` more elements to be inserted
607 /// in the `HashMap`. The collection may reserve more space to avoid
608 /// frequent reallocations.
612 /// Panics if the new allocation size overflows `usize`.
617 /// use std::collections::HashMap;
618 /// let mut map: HashMap<&str, int> = HashMap::new();
621 #[stable(feature = "rust1", since = "1.0.0")]
622 pub fn reserve(&mut self, additional: usize) {
623 let new_size = self.len().checked_add(additional).expect("capacity overflow");
624 let min_cap = self.resize_policy.min_capacity(new_size);
626 // An invalid value shouldn't make us run out of space. This includes
627 // an overflow check.
628 assert!(new_size <= min_cap);
630 if self.table.capacity() < min_cap {
631 let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
632 self.resize(new_capacity);
636 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
637 /// 1) Make sure the new capacity is enough for all the elements, accounting
638 /// for the load factor.
639 /// 2) Ensure new_capacity is a power of two or zero.
640 fn resize(&mut self, new_capacity: usize) {
641 assert!(self.table.size() <= new_capacity);
642 assert!(new_capacity.is_power_of_two() || new_capacity == 0);
644 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
645 let old_size = old_table.size();
647 if old_table.capacity() == 0 || old_table.size() == 0 {
652 // Specialization of the other branch.
653 let mut bucket = Bucket::first(&mut old_table);
655 // "So a few of the first shall be last: for many be called,
658 // We'll most likely encounter a few buckets at the beginning that
659 // have their initial buckets near the end of the table. They were
660 // placed at the beginning as the probe wrapped around the table
661 // during insertion. We must skip forward to a bucket that won't
662 // get reinserted too early and won't unfairly steal others spot.
663 // This eliminates the need for robin hood.
665 bucket = match bucket.peek() {
667 if full.distance() == 0 {
668 // This bucket occupies its ideal spot.
669 // It indicates the start of another "cluster".
670 bucket = full.into_bucket();
673 // Leaving this bucket in the last cluster for later.
677 // Encountered a hole between clusters.
684 // This is how the buckets might be laid out in memory:
685 // ($ marks an initialized bucket)
687 // |$$$_$$$$$$_$$$$$|
689 // But we've skipped the entire initial cluster of buckets
690 // and will continue iteration in this order:
693 // ^ wrap around once end is reached
696 // ^ exit once table.size == 0
698 bucket = match bucket.peek() {
700 let h = bucket.hash();
701 let (b, k, v) = bucket.take();
702 self.insert_hashed_ordered(h, k, v);
704 let t = b.table(); // FIXME "lifetime too short".
705 if t.size() == 0 { break }
709 Empty(b) => b.into_bucket()
714 assert_eq!(self.table.size(), old_size);
717 /// Shrinks the capacity of the map as much as possible. It will drop
718 /// down as much as possible while maintaining the internal rules
719 /// and possibly leaving some space in accordance with the resize policy.
724 /// use std::collections::HashMap;
726 /// let mut map: HashMap<int, int> = HashMap::with_capacity(100);
727 /// map.insert(1, 2);
728 /// map.insert(3, 4);
729 /// assert!(map.capacity() >= 100);
730 /// map.shrink_to_fit();
731 /// assert!(map.capacity() >= 2);
733 #[stable(feature = "rust1", since = "1.0.0")]
734 pub fn shrink_to_fit(&mut self) {
735 let min_capacity = self.resize_policy.min_capacity(self.len());
736 let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
738 // An invalid value shouldn't make us run out of space.
739 debug_assert!(self.len() <= min_capacity);
741 if self.table.capacity() != min_capacity {
742 let old_table = replace(&mut self.table, RawTable::new(min_capacity));
743 let old_size = old_table.size();
745 // Shrink the table. Naive algorithm for resizing:
746 for (h, k, v) in old_table.into_iter() {
747 self.insert_hashed_nocheck(h, k, v);
750 debug_assert_eq!(self.table.size(), old_size);
754 /// Insert a pre-hashed key-value pair, without first checking
755 /// that there's enough room in the buckets. Returns a reference to the
756 /// newly insert value.
758 /// If the key already exists, the hashtable will be returned untouched
759 /// and a reference to the existing element will be returned.
760 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
761 self.insert_or_replace_with(hash, k, v, |_, _, _| ())
764 fn insert_or_replace_with<'a, F>(&'a mut self,
768 mut found_existing: F)
770 F: FnMut(&mut K, &mut V, V),
772 // Worst case, we'll find one empty bucket among `size + 1` buckets.
773 let size = self.table.size();
774 let mut probe = Bucket::new(&mut self.table, hash);
775 let ib = probe.index();
778 let mut bucket = match probe.peek() {
781 return bucket.put(hash, k, v).into_mut_refs().1;
783 Full(bucket) => bucket
787 if bucket.hash() == hash {
789 if k == *bucket.read_mut().0 {
790 let (bucket_k, bucket_v) = bucket.into_mut_refs();
791 debug_assert!(k == *bucket_k);
792 // Key already exists. Get its reference.
793 found_existing(bucket_k, bucket_v, v);
798 let robin_ib = bucket.index() as int - bucket.distance() as int;
800 if (ib as int) < robin_ib {
801 // Found a luckier bucket than me. Better steal his spot.
802 return robin_hood(bucket, robin_ib as usize, hash, k, v);
805 probe = bucket.next();
806 assert!(probe.index() != ib + size + 1);
810 /// An iterator visiting all keys in arbitrary order.
811 /// Iterator element type is `&'a K`.
816 /// use std::collections::HashMap;
818 /// let mut map = HashMap::new();
819 /// map.insert("a", 1);
820 /// map.insert("b", 2);
821 /// map.insert("c", 3);
823 /// for key in map.keys() {
824 /// println!("{}", key);
827 #[stable(feature = "rust1", since = "1.0.0")]
828 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
829 fn first<A, B>((a, _): (A, B)) -> A { a }
830 let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr
832 Keys { inner: self.iter().map(first) }
835 /// An iterator visiting all values in arbitrary order.
836 /// Iterator element type is `&'a V`.
841 /// use std::collections::HashMap;
843 /// let mut map = HashMap::new();
844 /// map.insert("a", 1);
845 /// map.insert("b", 2);
846 /// map.insert("c", 3);
848 /// for val in map.values() {
849 /// println!("{}", val);
852 #[stable(feature = "rust1", since = "1.0.0")]
853 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
854 fn second<A, B>((_, b): (A, B)) -> B { b }
855 let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr
857 Values { inner: self.iter().map(second) }
860 /// An iterator visiting all key-value pairs in arbitrary order.
861 /// Iterator element type is `(&'a K, &'a V)`.
866 /// use std::collections::HashMap;
868 /// let mut map = HashMap::new();
869 /// map.insert("a", 1);
870 /// map.insert("b", 2);
871 /// map.insert("c", 3);
873 /// for (key, val) in map.iter() {
874 /// println!("key: {} val: {}", key, val);
877 #[stable(feature = "rust1", since = "1.0.0")]
878 pub fn iter(&self) -> Iter<K, V> {
879 Iter { inner: self.table.iter() }
882 /// An iterator visiting all key-value pairs in arbitrary order,
883 /// with mutable references to the values.
884 /// Iterator element type is `(&'a K, &'a mut V)`.
889 /// use std::collections::HashMap;
891 /// let mut map = HashMap::new();
892 /// map.insert("a", 1);
893 /// map.insert("b", 2);
894 /// map.insert("c", 3);
896 /// // Update all values
897 /// for (_, val) in map.iter_mut() {
901 /// for (key, val) in map.iter() {
902 /// println!("key: {} val: {}", key, val);
905 #[stable(feature = "rust1", since = "1.0.0")]
906 pub fn iter_mut(&mut self) -> IterMut<K, V> {
907 IterMut { inner: self.table.iter_mut() }
910 /// Creates a consuming iterator, that is, one that moves each key-value
911 /// pair out of the map in arbitrary order. The map cannot be used after
917 /// use std::collections::HashMap;
919 /// let mut map = HashMap::new();
920 /// map.insert("a", 1);
921 /// map.insert("b", 2);
922 /// map.insert("c", 3);
924 /// // Not possible with .iter()
925 /// let vec: Vec<(&str, int)> = map.into_iter().collect();
927 #[stable(feature = "rust1", since = "1.0.0")]
928 pub fn into_iter(self) -> IntoIter<K, V> {
929 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
930 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
933 inner: self.table.into_iter().map(last_two)
937 /// Gets the given key's corresponding entry in the map for in-place manipulation.
938 #[stable(feature = "rust1", since = "1.0.0")]
939 pub fn entry(&mut self, key: K) -> Entry<K, V> {
943 let hash = self.make_hash(&key);
944 search_entry_hashed(&mut self.table, hash, key)
947 /// Returns the number of elements in the map.
952 /// use std::collections::HashMap;
954 /// let mut a = HashMap::new();
955 /// assert_eq!(a.len(), 0);
956 /// a.insert(1, "a");
957 /// assert_eq!(a.len(), 1);
959 #[stable(feature = "rust1", since = "1.0.0")]
960 pub fn len(&self) -> usize { self.table.size() }
962 /// Returns true if the map contains no elements.
967 /// use std::collections::HashMap;
969 /// let mut a = HashMap::new();
970 /// assert!(a.is_empty());
971 /// a.insert(1, "a");
972 /// assert!(!a.is_empty());
975 #[stable(feature = "rust1", since = "1.0.0")]
976 pub fn is_empty(&self) -> bool { self.len() == 0 }
978 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
979 /// allocated memory for reuse.
984 /// use std::collections::HashMap;
986 /// let mut a = HashMap::new();
987 /// a.insert(1, "a");
988 /// a.insert(2, "b");
990 /// for (k, v) in a.drain().take(1) {
991 /// assert!(k == 1 || k == 2);
992 /// assert!(v == "a" || v == "b");
995 /// assert!(a.is_empty());
998 #[unstable(feature = "std_misc",
999 reason = "matches collection reform specification, waiting for dust to settle")]
1000 pub fn drain(&mut self) -> Drain<K, V> {
1001 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1002 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; // coerce to fn pointer
1005 inner: self.table.drain().map(last_two),
1009 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1015 /// use std::collections::HashMap;
1017 /// let mut a = HashMap::new();
1018 /// a.insert(1, "a");
1020 /// assert!(a.is_empty());
1022 #[stable(feature = "rust1", since = "1.0.0")]
1024 pub fn clear(&mut self) {
1028 /// Returns a reference to the value corresponding to the key.
1030 /// The key may be any borrowed form of the map's key type, but
1031 /// `Hash` and `Eq` on the borrowed form *must* match those for
1037 /// use std::collections::HashMap;
1039 /// let mut map = HashMap::new();
1040 /// map.insert(1, "a");
1041 /// assert_eq!(map.get(&1), Some(&"a"));
1042 /// assert_eq!(map.get(&2), None);
1044 #[stable(feature = "rust1", since = "1.0.0")]
1045 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
1046 where K: Borrow<Q>, Q: Hash + Eq
1048 self.search(k).map(|bucket| bucket.into_refs().1)
1051 /// Returns true if the map contains a value for the specified key.
1053 /// The key may be any borrowed form of the map's key type, but
1054 /// `Hash` and `Eq` on the borrowed form *must* match those for
1060 /// use std::collections::HashMap;
1062 /// let mut map = HashMap::new();
1063 /// map.insert(1, "a");
1064 /// assert_eq!(map.contains_key(&1), true);
1065 /// assert_eq!(map.contains_key(&2), false);
1067 #[stable(feature = "rust1", since = "1.0.0")]
1068 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1069 where K: Borrow<Q>, Q: Hash + Eq
1071 self.search(k).is_some()
1074 /// Returns a mutable reference to the value corresponding to the key.
1076 /// The key may be any borrowed form of the map's key type, but
1077 /// `Hash` and `Eq` on the borrowed form *must* match those for
1083 /// use std::collections::HashMap;
1085 /// let mut map = HashMap::new();
1086 /// map.insert(1, "a");
1087 /// match map.get_mut(&1) {
1088 /// Some(x) => *x = "b",
1091 /// assert_eq!(map[1], "b");
1093 #[stable(feature = "rust1", since = "1.0.0")]
1094 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1095 where K: Borrow<Q>, Q: Hash + Eq
1097 self.search_mut(k).map(|bucket| bucket.into_mut_refs().1)
1100 /// Inserts a key-value pair from the map. If the key already had a value
1101 /// present in the map, that value is returned. Otherwise, `None` is returned.
1106 /// use std::collections::HashMap;
1108 /// let mut map = HashMap::new();
1109 /// assert_eq!(map.insert(37, "a"), None);
1110 /// assert_eq!(map.is_empty(), false);
1112 /// map.insert(37, "b");
1113 /// assert_eq!(map.insert(37, "c"), Some("b"));
1114 /// assert_eq!(map[37], "c");
1116 #[stable(feature = "rust1", since = "1.0.0")]
1117 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1118 let hash = self.make_hash(&k);
1121 let mut retval = None;
1122 self.insert_or_replace_with(hash, k, v, |_, val_ref, val| {
1123 retval = Some(replace(val_ref, val));
1128 /// Removes a key from the map, returning the value at the key if the key
1129 /// was previously in the map.
1131 /// The key may be any borrowed form of the map's key type, but
1132 /// `Hash` and `Eq` on the borrowed form *must* match those for
1138 /// use std::collections::HashMap;
1140 /// let mut map = HashMap::new();
1141 /// map.insert(1, "a");
1142 /// assert_eq!(map.remove(&1), Some("a"));
1143 /// assert_eq!(map.remove(&1), None);
1145 #[stable(feature = "rust1", since = "1.0.0")]
1146 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1147 where K: Borrow<Q>, Q: Hash + Eq
1149 if self.table.size() == 0 {
1153 self.search_mut(k).map(|bucket| pop_internal(bucket).1)
1157 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
1160 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1161 let size = table.size();
1162 let mut probe = Bucket::new(table, hash);
1163 let ib = probe.index();
1166 let bucket = match probe.peek() {
1169 return Vacant(VacantEntry {
1172 elem: NoElem(bucket),
1175 Full(bucket) => bucket
1179 if bucket.hash() == hash {
1181 if k == *bucket.read().0 {
1182 return Occupied(OccupiedEntry{
1188 let robin_ib = bucket.index() as int - bucket.distance() as int;
1190 if (ib as int) < robin_ib {
1191 // Found a luckier bucket than me. Better steal his spot.
1192 return Vacant(VacantEntry {
1195 elem: NeqElem(bucket, robin_ib as usize),
1199 probe = bucket.next();
1200 assert!(probe.index() != ib + size + 1);
1204 impl<K, V, S> PartialEq for HashMap<K, V, S>
1205 where K: Eq + Hash, V: PartialEq, S: HashState
1207 fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1208 if self.len() != other.len() { return false; }
1210 self.iter().all(|(key, value)|
1211 other.get(key).map_or(false, |v| *value == *v)
1216 #[stable(feature = "rust1", since = "1.0.0")]
1217 impl<K, V, S> Eq for HashMap<K, V, S>
1218 where K: Eq + Hash, V: Eq, S: HashState
1221 #[stable(feature = "rust1", since = "1.0.0")]
1222 impl<K, V, S> Debug for HashMap<K, V, S>
1223 where K: Eq + Hash + Debug, V: Debug, S: HashState
1225 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1226 try!(write!(f, "{{"));
1228 for (i, (k, v)) in self.iter().enumerate() {
1229 if i != 0 { try!(write!(f, ", ")); }
1230 try!(write!(f, "{:?}: {:?}", *k, *v));
1237 #[stable(feature = "rust1", since = "1.0.0")]
1238 impl<K, V, S> Default for HashMap<K, V, S>
1240 S: HashState + Default,
1242 fn default() -> HashMap<K, V, S> {
1243 HashMap::with_hash_state(Default::default())
1247 #[stable(feature = "rust1", since = "1.0.0")]
1248 impl<K, Q: ?Sized, V, S> Index<Q> for HashMap<K, V, S>
1249 where K: Eq + Hash + Borrow<Q>,
1256 fn index<'a>(&'a self, index: &Q) -> &'a V {
1257 self.get(index).expect("no entry found for key")
1261 /// HashMap iterator.
1262 #[stable(feature = "rust1", since = "1.0.0")]
1263 pub struct Iter<'a, K: 'a, V: 'a> {
1264 inner: table::Iter<'a, K, V>
1267 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1268 impl<'a, K, V> Clone for Iter<'a, K, V> {
1269 fn clone(&self) -> Iter<'a, K, V> {
1271 inner: self.inner.clone()
1276 /// HashMap mutable values iterator.
1277 #[stable(feature = "rust1", since = "1.0.0")]
1278 pub struct IterMut<'a, K: 'a, V: 'a> {
1279 inner: table::IterMut<'a, K, V>
1282 /// HashMap move iterator.
1283 #[stable(feature = "rust1", since = "1.0.0")]
1284 pub struct IntoIter<K, V> {
1285 inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)>
1288 /// HashMap keys iterator.
1289 #[stable(feature = "rust1", since = "1.0.0")]
1290 pub struct Keys<'a, K: 'a, V: 'a> {
1291 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
1294 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1295 impl<'a, K, V> Clone for Keys<'a, K, V> {
1296 fn clone(&self) -> Keys<'a, K, V> {
1298 inner: self.inner.clone()
1303 /// HashMap values iterator.
1304 #[stable(feature = "rust1", since = "1.0.0")]
1305 pub struct Values<'a, K: 'a, V: 'a> {
1306 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
1309 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1310 impl<'a, K, V> Clone for Values<'a, K, V> {
1311 fn clone(&self) -> Values<'a, K, V> {
1313 inner: self.inner.clone()
1318 /// HashMap drain iterator.
1319 #[unstable(feature = "std_misc",
1320 reason = "matches collection reform specification, waiting for dust to settle")]
1321 pub struct Drain<'a, K: 'a, V: 'a> {
1322 inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)>
1325 /// A view into a single occupied location in a HashMap.
1326 #[stable(feature = "rust1", since = "1.0.0")]
1327 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1328 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1331 /// A view into a single empty location in a HashMap.
1332 #[stable(feature = "rust1", since = "1.0.0")]
1333 pub struct VacantEntry<'a, K: 'a, V: 'a> {
1336 elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
1339 /// A view into a single location in a map, which may be vacant or occupied.
1340 #[stable(feature = "rust1", since = "1.0.0")]
1341 pub enum Entry<'a, K: 'a, V: 'a> {
1342 /// An occupied Entry.
1343 #[stable(feature = "rust1", since = "1.0.0")]
1344 Occupied(OccupiedEntry<'a, K, V>),
1347 #[stable(feature = "rust1", since = "1.0.0")]
1348 Vacant(VacantEntry<'a, K, V>),
1351 /// Possible states of a VacantEntry.
1352 enum VacantEntryState<K, V, M> {
1353 /// The index is occupied, but the key to insert has precedence,
1354 /// and will kick the current one out on insertion.
1355 NeqElem(FullBucket<K, V, M>, usize),
1356 /// The index is genuinely vacant.
1357 NoElem(EmptyBucket<K, V, M>),
1360 #[stable(feature = "rust1", since = "1.0.0")]
1361 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>
1362 where K: Eq + Hash, S: HashState
1364 type Item = (&'a K, &'a V);
1365 type IntoIter = Iter<'a, K, V>;
1367 fn into_iter(self) -> Iter<'a, K, V> {
1372 #[stable(feature = "rust1", since = "1.0.0")]
1373 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>
1374 where K: Eq + Hash, S: HashState
1376 type Item = (&'a K, &'a mut V);
1377 type IntoIter = IterMut<'a, K, V>;
1379 fn into_iter(mut self) -> IterMut<'a, K, V> {
1384 #[stable(feature = "rust1", since = "1.0.0")]
1385 impl<K, V, S> IntoIterator for HashMap<K, V, S>
1386 where K: Eq + Hash, S: HashState
1389 type IntoIter = IntoIter<K, V>;
1391 fn into_iter(self) -> IntoIter<K, V> {
1396 #[stable(feature = "rust1", since = "1.0.0")]
1397 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1398 type Item = (&'a K, &'a V);
1400 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1401 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1403 #[stable(feature = "rust1", since = "1.0.0")]
1404 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
1405 #[inline] fn len(&self) -> usize { self.inner.len() }
1408 #[stable(feature = "rust1", since = "1.0.0")]
1409 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1410 type Item = (&'a K, &'a mut V);
1412 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1413 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1415 #[stable(feature = "rust1", since = "1.0.0")]
1416 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1417 #[inline] fn len(&self) -> usize { self.inner.len() }
1420 #[stable(feature = "rust1", since = "1.0.0")]
1421 impl<K, V> Iterator for IntoIter<K, V> {
1424 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1425 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1427 #[stable(feature = "rust1", since = "1.0.0")]
1428 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1429 #[inline] fn len(&self) -> usize { self.inner.len() }
1432 #[stable(feature = "rust1", since = "1.0.0")]
1433 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1436 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1437 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1439 #[stable(feature = "rust1", since = "1.0.0")]
1440 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1441 #[inline] fn len(&self) -> usize { self.inner.len() }
1444 #[stable(feature = "rust1", since = "1.0.0")]
1445 impl<'a, K, V> Iterator for Values<'a, K, V> {
1448 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1449 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1451 #[stable(feature = "rust1", since = "1.0.0")]
1452 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1453 #[inline] fn len(&self) -> usize { self.inner.len() }
1456 #[stable(feature = "rust1", since = "1.0.0")]
1457 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1460 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1461 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1463 #[stable(feature = "rust1", since = "1.0.0")]
1464 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1465 #[inline] fn len(&self) -> usize { self.inner.len() }
1468 impl<'a, K, V> Entry<'a, K, V> {
1469 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant.
1470 #[unstable(feature = "std_misc",
1471 reason = "will soon be replaced by or_insert")]
1472 pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> {
1474 Occupied(entry) => Ok(entry.into_mut()),
1475 Vacant(entry) => Err(entry),
1480 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1481 /// Gets a reference to the value in the entry.
1482 #[stable(feature = "rust1", since = "1.0.0")]
1483 pub fn get(&self) -> &V {
1487 /// Gets a mutable reference to the value in the entry.
1488 #[stable(feature = "rust1", since = "1.0.0")]
1489 pub fn get_mut(&mut self) -> &mut V {
1490 self.elem.read_mut().1
1493 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1494 /// with a lifetime bound to the map itself
1495 #[stable(feature = "rust1", since = "1.0.0")]
1496 pub fn into_mut(self) -> &'a mut V {
1497 self.elem.into_mut_refs().1
1500 /// Sets the value of the entry, and returns the entry's old value
1501 #[stable(feature = "rust1", since = "1.0.0")]
1502 pub fn insert(&mut self, mut value: V) -> V {
1503 let old_value = self.get_mut();
1504 mem::swap(&mut value, old_value);
1508 /// Takes the value out of the entry, and returns it
1509 #[stable(feature = "rust1", since = "1.0.0")]
1510 pub fn remove(self) -> V {
1511 pop_internal(self.elem).1
1515 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
1516 /// Sets the value of the entry with the VacantEntry's key,
1517 /// and returns a mutable reference to it
1518 #[stable(feature = "rust1", since = "1.0.0")]
1519 pub fn insert(self, value: V) -> &'a mut V {
1521 NeqElem(bucket, ib) => {
1522 robin_hood(bucket, ib, self.hash, self.key, value)
1525 bucket.put(self.hash, self.key, value).into_mut_refs().1
1531 #[stable(feature = "rust1", since = "1.0.0")]
1532 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
1533 where K: Eq + Hash, S: HashState + Default
1535 fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> HashMap<K, V, S> {
1536 let iter = iterable.into_iter();
1537 let lower = iter.size_hint().0;
1538 let mut map = HashMap::with_capacity_and_hash_state(lower,
1539 Default::default());
1545 #[stable(feature = "rust1", since = "1.0.0")]
1546 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
1547 where K: Eq + Hash, S: HashState
1549 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1550 for (k, v) in iter {
1557 /// `RandomState` is the default state for `HashMap` types.
1559 /// A particular instance `RandomState` will create the same instances of
1560 /// `Hasher`, but the hashers created by two different `RandomState`
1561 /// instances are unlikely to produce the same result for the same values.
1563 #[unstable(feature = "std_misc",
1564 reason = "hashing an hash maps may be altered")]
1565 pub struct RandomState {
1570 #[unstable(feature = "std_misc",
1571 reason = "hashing an hash maps may be altered")]
1573 /// Construct a new `RandomState` that is initialized with random keys.
1575 #[allow(deprecated)]
1576 pub fn new() -> RandomState {
1577 let mut r = rand::thread_rng();
1578 RandomState { k0: r.gen(), k1: r.gen() }
1582 #[unstable(feature = "std_misc",
1583 reason = "hashing an hash maps may be altered")]
1584 impl HashState for RandomState {
1585 type Hasher = SipHasher;
1586 fn hasher(&self) -> SipHasher {
1587 SipHasher::new_with_keys(self.k0, self.k1)
1591 #[unstable(feature = "std_misc",
1592 reason = "hashing an hash maps may be altered")]
1593 impl Default for RandomState {
1595 fn default() -> RandomState {
1605 use super::Entry::{Occupied, Vacant};
1606 use iter::{range_inclusive, range_step_inclusive, repeat};
1608 use rand::{weak_rng, Rng};
1611 fn test_create_capacity_zero() {
1612 let mut m = HashMap::with_capacity(0);
1614 assert!(m.insert(1, 1).is_none());
1616 assert!(m.contains_key(&1));
1617 assert!(!m.contains_key(&0));
1622 let mut m = HashMap::new();
1623 assert_eq!(m.len(), 0);
1624 assert!(m.insert(1, 2).is_none());
1625 assert_eq!(m.len(), 1);
1626 assert!(m.insert(2, 4).is_none());
1627 assert_eq!(m.len(), 2);
1628 assert_eq!(*m.get(&1).unwrap(), 2);
1629 assert_eq!(*m.get(&2).unwrap(), 4);
1632 thread_local! { static DROP_VECTOR: RefCell<Vec<int>> = RefCell::new(Vec::new()) }
1634 #[derive(Hash, PartialEq, Eq)]
1640 fn new(k: usize) -> Dropable {
1641 DROP_VECTOR.with(|slot| {
1642 slot.borrow_mut()[k] += 1;
1649 impl Drop for Dropable {
1650 fn drop(&mut self) {
1651 DROP_VECTOR.with(|slot| {
1652 slot.borrow_mut()[self.k] -= 1;
1657 impl Clone for Dropable {
1658 fn clone(&self) -> Dropable {
1659 Dropable::new(self.k)
1665 DROP_VECTOR.with(|slot| {
1666 *slot.borrow_mut() = repeat(0).take(200).collect();
1670 let mut m = HashMap::new();
1672 DROP_VECTOR.with(|v| {
1674 assert_eq!(v.borrow()[i], 0);
1679 let d1 = Dropable::new(i);
1680 let d2 = Dropable::new(i+100);
1684 DROP_VECTOR.with(|v| {
1686 assert_eq!(v.borrow()[i], 1);
1691 let k = Dropable::new(i);
1692 let v = m.remove(&k);
1694 assert!(v.is_some());
1696 DROP_VECTOR.with(|v| {
1697 assert_eq!(v.borrow()[i], 1);
1698 assert_eq!(v.borrow()[i+100], 1);
1702 DROP_VECTOR.with(|v| {
1704 assert_eq!(v.borrow()[i], 0);
1705 assert_eq!(v.borrow()[i+100], 0);
1709 assert_eq!(v.borrow()[i], 1);
1710 assert_eq!(v.borrow()[i+100], 1);
1715 DROP_VECTOR.with(|v| {
1717 assert_eq!(v.borrow()[i], 0);
1723 fn test_move_iter_drops() {
1724 DROP_VECTOR.with(|v| {
1725 *v.borrow_mut() = repeat(0).take(200).collect();
1729 let mut hm = HashMap::new();
1731 DROP_VECTOR.with(|v| {
1733 assert_eq!(v.borrow()[i], 0);
1738 let d1 = Dropable::new(i);
1739 let d2 = Dropable::new(i+100);
1743 DROP_VECTOR.with(|v| {
1745 assert_eq!(v.borrow()[i], 1);
1752 // By the way, ensure that cloning doesn't screw up the dropping.
1756 let mut half = hm.into_iter().take(50);
1758 DROP_VECTOR.with(|v| {
1760 assert_eq!(v.borrow()[i], 1);
1764 for _ in half.by_ref() {}
1766 DROP_VECTOR.with(|v| {
1767 let nk = (0..100).filter(|&i| {
1771 let nv = (0..100).filter(|&i| {
1772 v.borrow()[i+100] == 1
1780 DROP_VECTOR.with(|v| {
1782 assert_eq!(v.borrow()[i], 0);
1788 fn test_empty_pop() {
1789 let mut m: HashMap<int, bool> = HashMap::new();
1790 assert_eq!(m.remove(&0), None);
1794 fn test_lots_of_insertions() {
1795 let mut m = HashMap::new();
1797 // Try this a few times to make sure we never screw up the hashmap's
1800 assert!(m.is_empty());
1802 for i in range_inclusive(1, 1000) {
1803 assert!(m.insert(i, i).is_none());
1805 for j in range_inclusive(1, i) {
1807 assert_eq!(r, Some(&j));
1810 for j in range_inclusive(i+1, 1000) {
1812 assert_eq!(r, None);
1816 for i in range_inclusive(1001, 2000) {
1817 assert!(!m.contains_key(&i));
1821 for i in range_inclusive(1, 1000) {
1822 assert!(m.remove(&i).is_some());
1824 for j in range_inclusive(1, i) {
1825 assert!(!m.contains_key(&j));
1828 for j in range_inclusive(i+1, 1000) {
1829 assert!(m.contains_key(&j));
1833 for i in range_inclusive(1, 1000) {
1834 assert!(!m.contains_key(&i));
1837 for i in range_inclusive(1, 1000) {
1838 assert!(m.insert(i, i).is_none());
1842 for i in range_step_inclusive(1000, 1, -1) {
1843 assert!(m.remove(&i).is_some());
1845 for j in range_inclusive(i, 1000) {
1846 assert!(!m.contains_key(&j));
1849 for j in range_inclusive(1, i-1) {
1850 assert!(m.contains_key(&j));
1857 fn test_find_mut() {
1858 let mut m = HashMap::new();
1859 assert!(m.insert(1, 12).is_none());
1860 assert!(m.insert(2, 8).is_none());
1861 assert!(m.insert(5, 14).is_none());
1863 match m.get_mut(&5) {
1864 None => panic!(), Some(x) => *x = new
1866 assert_eq!(m.get(&5), Some(&new));
1870 fn test_insert_overwrite() {
1871 let mut m = HashMap::new();
1872 assert!(m.insert(1, 2).is_none());
1873 assert_eq!(*m.get(&1).unwrap(), 2);
1874 assert!(!m.insert(1, 3).is_none());
1875 assert_eq!(*m.get(&1).unwrap(), 3);
1879 fn test_insert_conflicts() {
1880 let mut m = HashMap::with_capacity(4);
1881 assert!(m.insert(1, 2).is_none());
1882 assert!(m.insert(5, 3).is_none());
1883 assert!(m.insert(9, 4).is_none());
1884 assert_eq!(*m.get(&9).unwrap(), 4);
1885 assert_eq!(*m.get(&5).unwrap(), 3);
1886 assert_eq!(*m.get(&1).unwrap(), 2);
1890 fn test_conflict_remove() {
1891 let mut m = HashMap::with_capacity(4);
1892 assert!(m.insert(1, 2).is_none());
1893 assert_eq!(*m.get(&1).unwrap(), 2);
1894 assert!(m.insert(5, 3).is_none());
1895 assert_eq!(*m.get(&1).unwrap(), 2);
1896 assert_eq!(*m.get(&5).unwrap(), 3);
1897 assert!(m.insert(9, 4).is_none());
1898 assert_eq!(*m.get(&1).unwrap(), 2);
1899 assert_eq!(*m.get(&5).unwrap(), 3);
1900 assert_eq!(*m.get(&9).unwrap(), 4);
1901 assert!(m.remove(&1).is_some());
1902 assert_eq!(*m.get(&9).unwrap(), 4);
1903 assert_eq!(*m.get(&5).unwrap(), 3);
1907 fn test_is_empty() {
1908 let mut m = HashMap::with_capacity(4);
1909 assert!(m.insert(1, 2).is_none());
1910 assert!(!m.is_empty());
1911 assert!(m.remove(&1).is_some());
1912 assert!(m.is_empty());
1917 let mut m = HashMap::new();
1919 assert_eq!(m.remove(&1), Some(2));
1920 assert_eq!(m.remove(&1), None);
1925 let mut m = HashMap::with_capacity(4);
1927 assert!(m.insert(i, i*2).is_none());
1929 assert_eq!(m.len(), 32);
1931 let mut observed: u32 = 0;
1934 assert_eq!(*v, *k * 2);
1935 observed |= 1 << *k;
1937 assert_eq!(observed, 0xFFFF_FFFF);
1942 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1943 let map: HashMap<_, _> = vec.into_iter().collect();
1944 let keys: Vec<_> = map.keys().cloned().collect();
1945 assert_eq!(keys.len(), 3);
1946 assert!(keys.contains(&1));
1947 assert!(keys.contains(&2));
1948 assert!(keys.contains(&3));
1953 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
1954 let map: HashMap<_, _> = vec.into_iter().collect();
1955 let values: Vec<_> = map.values().cloned().collect();
1956 assert_eq!(values.len(), 3);
1957 assert!(values.contains(&'a'));
1958 assert!(values.contains(&'b'));
1959 assert!(values.contains(&'c'));
1964 let mut m = HashMap::new();
1965 assert!(m.get(&1).is_none());
1969 Some(v) => assert_eq!(*v, 2)
1975 let mut m1 = HashMap::new();
1980 let mut m2 = HashMap::new();
1993 let mut map = HashMap::new();
1994 let empty: HashMap<i32, i32> = HashMap::new();
1999 let map_str = format!("{:?}", map);
2001 assert!(map_str == "{1: 2, 3: 4}" ||
2002 map_str == "{3: 4, 1: 2}");
2003 assert_eq!(format!("{:?}", empty), "{}");
2008 let mut m = HashMap::new();
2010 assert_eq!(m.len(), 0);
2011 assert!(m.is_empty());
2014 let old_cap = m.table.capacity();
2015 while old_cap == m.table.capacity() {
2020 assert_eq!(m.len(), i);
2021 assert!(!m.is_empty());
2025 fn test_behavior_resize_policy() {
2026 let mut m = HashMap::new();
2028 assert_eq!(m.len(), 0);
2029 assert_eq!(m.table.capacity(), 0);
2030 assert!(m.is_empty());
2034 assert!(m.is_empty());
2035 let initial_cap = m.table.capacity();
2036 m.reserve(initial_cap);
2037 let cap = m.table.capacity();
2039 assert_eq!(cap, initial_cap * 2);
2042 for _ in 0..cap * 3 / 4 {
2046 // three quarters full
2048 assert_eq!(m.len(), i);
2049 assert_eq!(m.table.capacity(), cap);
2051 for _ in 0..cap / 4 {
2057 let new_cap = m.table.capacity();
2058 assert_eq!(new_cap, cap * 2);
2060 for _ in 0..cap / 2 - 1 {
2063 assert_eq!(m.table.capacity(), new_cap);
2065 // A little more than one quarter full.
2067 assert_eq!(m.table.capacity(), cap);
2068 // again, a little more than half full
2069 for _ in 0..cap / 2 - 1 {
2075 assert_eq!(m.len(), i);
2076 assert!(!m.is_empty());
2077 assert_eq!(m.table.capacity(), initial_cap);
2081 fn test_reserve_shrink_to_fit() {
2082 let mut m = HashMap::new();
2085 assert!(m.capacity() >= m.len());
2091 let usable_cap = m.capacity();
2092 for i in 128..(128 + 256) {
2094 assert_eq!(m.capacity(), usable_cap);
2097 for i in 100..(128 + 256) {
2098 assert_eq!(m.remove(&i), Some(i));
2102 assert_eq!(m.len(), 100);
2103 assert!(!m.is_empty());
2104 assert!(m.capacity() >= m.len());
2107 assert_eq!(m.remove(&i), Some(i));
2112 assert_eq!(m.len(), 1);
2113 assert!(m.capacity() >= m.len());
2114 assert_eq!(m.remove(&0), Some(0));
2118 fn test_from_iter() {
2119 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2121 let map: HashMap<_, _> = xs.iter().cloned().collect();
2123 for &(k, v) in &xs {
2124 assert_eq!(map.get(&k), Some(&v));
2129 fn test_size_hint() {
2130 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2132 let map: HashMap<_, _> = xs.iter().cloned().collect();
2134 let mut iter = map.iter();
2136 for _ in iter.by_ref().take(3) {}
2138 assert_eq!(iter.size_hint(), (3, Some(3)));
2142 fn test_iter_len() {
2143 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2145 let map: HashMap<_, _> = xs.iter().cloned().collect();
2147 let mut iter = map.iter();
2149 for _ in iter.by_ref().take(3) {}
2151 assert_eq!(iter.len(), 3);
2155 fn test_mut_size_hint() {
2156 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2158 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2160 let mut iter = map.iter_mut();
2162 for _ in iter.by_ref().take(3) {}
2164 assert_eq!(iter.size_hint(), (3, Some(3)));
2168 fn test_iter_mut_len() {
2169 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2171 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2173 let mut iter = map.iter_mut();
2175 for _ in iter.by_ref().take(3) {}
2177 assert_eq!(iter.len(), 3);
2182 let mut map = HashMap::new();
2188 assert_eq!(map[2], 1);
2193 fn test_index_nonexistent() {
2194 let mut map = HashMap::new();
2205 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2207 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2209 // Existing key (insert)
2210 match map.entry(1) {
2211 Vacant(_) => unreachable!(),
2212 Occupied(mut view) => {
2213 assert_eq!(view.get(), &10);
2214 assert_eq!(view.insert(100), 10);
2217 assert_eq!(map.get(&1).unwrap(), &100);
2218 assert_eq!(map.len(), 6);
2221 // Existing key (update)
2222 match map.entry(2) {
2223 Vacant(_) => unreachable!(),
2224 Occupied(mut view) => {
2225 let v = view.get_mut();
2226 let new_v = (*v) * 10;
2230 assert_eq!(map.get(&2).unwrap(), &200);
2231 assert_eq!(map.len(), 6);
2233 // Existing key (take)
2234 match map.entry(3) {
2235 Vacant(_) => unreachable!(),
2237 assert_eq!(view.remove(), 30);
2240 assert_eq!(map.get(&3), None);
2241 assert_eq!(map.len(), 5);
2244 // Inexistent key (insert)
2245 match map.entry(10) {
2246 Occupied(_) => unreachable!(),
2248 assert_eq!(*view.insert(1000), 1000);
2251 assert_eq!(map.get(&10).unwrap(), &1000);
2252 assert_eq!(map.len(), 6);
2256 fn test_entry_take_doesnt_corrupt() {
2257 #![allow(deprecated)] //rand
2259 fn check(m: &HashMap<isize, ()>) {
2261 assert!(m.contains_key(k),
2262 "{} is in keys() but not in the map?", k);
2266 let mut m = HashMap::new();
2267 let mut rng = weak_rng();
2269 // Populate the map with some items.
2271 let x = rng.gen_range(-10, 10);
2276 let x = rng.gen_range(-10, 10);
2280 println!("{}: remove {}", i, x);