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.
12 use self::SearchResult::*;
13 use self::VacantEntryState::*;
17 use cmp::{max, Eq, PartialEq};
19 use fmt::{self, Debug};
20 use hash::{Hash, SipHasher};
21 use iter::{self, Iterator, ExactSizeIterator, IntoIterator, FromIterator, Extend, Map};
23 use mem::{self, replace};
24 use ops::{Deref, FnMut, FnOnce, Index};
25 use option::Option::{self, Some, None};
26 use rand::{self, Rng};
38 use super::table::BucketState::{
42 use super::state::HashState;
44 const INITIAL_LOG2_CAP: usize = 5;
45 const INITIAL_CAPACITY: usize = 1 << INITIAL_LOG2_CAP; // 2^5
47 /// The default behavior of HashMap implements a load factor of 90.9%.
48 /// This behavior is characterized by the following condition:
50 /// - if size > 0.909 * capacity: grow the map
52 struct DefaultResizePolicy;
54 impl DefaultResizePolicy {
55 fn new() -> DefaultResizePolicy {
60 fn min_capacity(&self, usable_size: usize) -> usize {
61 // Here, we are rephrasing the logic by specifying the lower limit
64 // - if `cap < size * 1.1`: grow the map
68 /// An inverse of `min_capacity`, approximately.
70 fn usable_capacity(&self, cap: usize) -> usize {
71 // As the number of entries approaches usable capacity,
72 // min_capacity(size) must be smaller than the internal capacity,
73 // so that the map is not resized:
74 // `min_capacity(usable_capacity(x)) <= x`.
75 // The left-hand side can only be smaller due to flooring by integer
78 // This doesn't have to be checked for overflow since allocation size
79 // in bytes will overflow earlier than multiplication by 10.
85 fn test_resize_policy() {
86 let rp = DefaultResizePolicy;
88 assert!(rp.min_capacity(rp.usable_capacity(n)) <= n);
89 assert!(rp.usable_capacity(rp.min_capacity(n)) <= n);
93 // The main performance trick in this hashmap is called Robin Hood Hashing.
94 // It gains its excellent performance from one essential operation:
96 // If an insertion collides with an existing element, and that element's
97 // "probe distance" (how far away the element is from its ideal location)
98 // is higher than how far we've already probed, swap the elements.
100 // This massively lowers variance in probe distance, and allows us to get very
101 // high load factors with good performance. The 90% load factor I use is rather
104 // > Why a load factor of approximately 90%?
106 // In general, all the distances to initial buckets will converge on the mean.
107 // At a load factor of α, the odds of finding the target bucket after k
108 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
109 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
110 // this down to make the math easier on the CPU and avoid its FPU.
111 // Since on average we start the probing in the middle of a cache line, this
112 // strategy pulls in two cache lines of hashes on every lookup. I think that's
113 // pretty good, but if you want to trade off some space, it could go down to one
114 // cache line on average with an α of 0.84.
116 // > Wait, what? Where did you get 1-α^k from?
118 // On the first probe, your odds of a collision with an existing element is α.
119 // The odds of doing this twice in a row is approximately α^2. For three times,
120 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
121 // colliding after k tries is 1-α^k.
123 // The paper from 1986 cited below mentions an implementation which keeps track
124 // of the distance-to-initial-bucket histogram. This approach is not suitable
125 // for modern architectures because it requires maintaining an internal data
126 // structure. This allows very good first guesses, but we are most concerned
127 // with guessing entire cache lines, not individual indexes. Furthermore, array
128 // accesses are no longer linear and in one direction, as we have now. There
129 // is also memory and cache pressure that this would entail that would be very
130 // difficult to properly see in a microbenchmark.
132 // ## Future Improvements (FIXME!)
134 // Allow the load factor to be changed dynamically and/or at initialization.
136 // Also, would it be possible for us to reuse storage when growing the
137 // underlying table? This is exactly the use case for 'realloc', and may
138 // be worth exploring.
140 // ## Future Optimizations (FIXME!)
142 // Another possible design choice that I made without any real reason is
143 // parameterizing the raw table over keys and values. Technically, all we need
144 // is the size and alignment of keys and values, and the code should be just as
145 // efficient (well, we might need one for power-of-two size and one for not...).
146 // This has the potential to reduce code bloat in rust executables, without
147 // really losing anything except 4 words (key size, key alignment, val size,
148 // val alignment) which can be passed in to every call of a `RawTable` function.
149 // This would definitely be an avenue worth exploring if people start complaining
150 // about the size of rust executables.
152 // Annotate exceedingly likely branches in `table::make_hash`
153 // and `search_hashed` to reduce instruction cache pressure
154 // and mispredictions once it becomes possible (blocked on issue #11092).
156 // Shrinking the table could simply reallocate in place after moving buckets
157 // to the first half.
159 // The growth algorithm (fragment of the Proof of Correctness)
160 // --------------------
162 // The growth algorithm is basically a fast path of the naive reinsertion-
163 // during-resize algorithm. Other paths should never be taken.
165 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
166 // by allocating a new table of capacity `2n`, and then individually reinsert
167 // each element in the old table into the new one. This guarantees that the
168 // new table is a valid robin hood hashtable with all the desired statistical
169 // properties. Remark that the order we reinsert the elements in should not
170 // matter. For simplicity and efficiency, we will consider only linear
171 // reinsertions, which consist of reinserting all elements in the old table
172 // into the new one by increasing order of index. However we will not be
173 // starting our reinsertions from index 0 in general. If we start from index
174 // i, for the purpose of reinsertion we will consider all elements with real
175 // index j < i to have virtual index n + j.
177 // Our hash generation scheme consists of generating a 64-bit hash and
178 // truncating the most significant bits. When moving to the new table, we
179 // simply introduce a new bit to the front of the hash. Therefore, if an
180 // elements has ideal index i in the old table, it can have one of two ideal
181 // locations in the new table. If the new bit is 0, then the new ideal index
182 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
183 // we are producing two independent tables of size n, and for each element we
184 // independently choose which table to insert it into with equal probability.
185 // However the rather than wrapping around themselves on overflowing their
186 // indexes, the first table overflows into the first, and the first into the
187 // second. Visually, our new table will look something like:
189 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
191 // Where x's are elements inserted into the first table, y's are elements
192 // inserted into the second, and _'s are empty sections. We now define a few
193 // key concepts that we will use later. Note that this is a very abstract
194 // perspective of the table. A real resized table would be at least half
197 // Theorem: A linear robin hood reinsertion from the first ideal element
198 // produces identical results to a linear naive reinsertion from the same
201 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
203 /// A hash map implementation which uses linear probing with Robin
204 /// Hood bucket stealing.
206 /// The hashes are all keyed by the thread-local random number generator
207 /// on creation by default. This means that the ordering of the keys is
208 /// randomized, but makes the tables more resistant to
209 /// denial-of-service attacks (Hash DoS). This behavior can be
210 /// overridden with one of the constructors.
212 /// It is required that the keys implement the `Eq` and `Hash` traits, although
213 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
214 /// If you implement these yourself, it is important that the following
218 /// k1 == k2 -> hash(k1) == hash(k2)
221 /// In other words, if two keys are equal, their hashes must be equal.
223 /// It is a logic error for a key to be modified in such a way that the key's
224 /// hash, as determined by the `Hash` trait, or its equality, as determined by
225 /// the `Eq` trait, changes while it is in the map. This is normally only
226 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
228 /// Relevant papers/articles:
230 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
231 /// 2. Emmanuel Goossaert. ["Robin Hood
232 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
233 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
234 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
239 /// use std::collections::HashMap;
241 /// // type inference lets us omit an explicit type signature (which
242 /// // would be `HashMap<&str, &str>` in this example).
243 /// let mut book_reviews = HashMap::new();
245 /// // review some books.
246 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
247 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
248 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
249 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
251 /// // check for a specific one.
252 /// if !book_reviews.contains_key("Les Misérables") {
253 /// println!("We've got {} reviews, but Les Misérables ain't one.",
254 /// book_reviews.len());
257 /// // oops, this review has a lot of spelling mistakes, let's delete it.
258 /// book_reviews.remove("The Adventures of Sherlock Holmes");
260 /// // look up the values associated with some keys.
261 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
262 /// for book in &to_find {
263 /// match book_reviews.get(book) {
264 /// Some(review) => println!("{}: {}", book, review),
265 /// None => println!("{} is unreviewed.", book)
269 /// // iterate over everything.
270 /// for (book, review) in &book_reviews {
271 /// println!("{}: \"{}\"", book, review);
275 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
276 /// for more complex methods of getting, setting, updating and removing keys and
280 /// use std::collections::HashMap;
282 /// // type inference lets us omit an explicit type signature (which
283 /// // would be `HashMap<&str, u8>` in this example).
284 /// let mut player_stats = HashMap::new();
286 /// fn random_stat_buff() -> u8 {
287 /// // could actually return some random value here - let's just return
288 /// // some fixed value for now
292 /// // insert a key only if it doesn't already exist
293 /// player_stats.entry("health").or_insert(100);
295 /// // insert a key using a function that provides a new value only if it
296 /// // doesn't already exist
297 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
299 /// // update a key, guarding against the key possibly not being set
300 /// let stat = player_stats.entry("attack").or_insert(100);
301 /// *stat += random_stat_buff();
304 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
305 /// We must also derive `PartialEq`.
308 /// use std::collections::HashMap;
310 /// #[derive(Hash, Eq, PartialEq, Debug)]
317 /// /// Create a new Viking.
318 /// fn new(name: &str, country: &str) -> Viking {
319 /// Viking { name: name.to_string(), country: country.to_string() }
323 /// // Use a HashMap to store the vikings' health points.
324 /// let mut vikings = HashMap::new();
326 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
327 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
328 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
330 /// // Use derived implementation to print the status of the vikings.
331 /// for (viking, health) in &vikings {
332 /// println!("{:?} has {} hp", viking, health);
336 #[stable(feature = "rust1", since = "1.0.0")]
337 pub struct HashMap<K, V, S = RandomState> {
338 // All hashes are keyed on these values, to prevent hash collision attacks.
341 table: RawTable<K, V>,
343 resize_policy: DefaultResizePolicy,
346 /// Search for a pre-hashed key.
347 fn search_hashed<K, V, M, F>(table: M,
350 -> SearchResult<K, V, M> where
351 M: Deref<Target=RawTable<K, V>>,
352 F: FnMut(&K) -> bool,
354 // This is the only function where capacity can be zero. To avoid
355 // undefined behavior when Bucket::new gets the raw bucket in this
356 // case, immediately return the appropriate search result.
357 if table.capacity() == 0 {
358 return TableRef(table);
361 let size = table.size();
362 let mut probe = Bucket::new(table, hash);
363 let ib = probe.index();
365 while probe.index() != ib + size {
366 let full = match probe.peek() {
367 Empty(b) => return TableRef(b.into_table()), // hit an empty bucket
371 if full.distance() + ib < full.index() {
372 // We can finish the search early if we hit any bucket
373 // with a lower distance to initial bucket than we've probed.
374 return TableRef(full.into_table());
377 // If the hash doesn't match, it can't be this one..
378 if hash == full.hash() {
379 // If the key doesn't match, it can't be this one..
380 if is_match(full.read().0) {
381 return FoundExisting(full);
388 TableRef(probe.into_table())
391 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
392 let (empty, retkey, retval) = starting_bucket.take();
393 let mut gap = match empty.gap_peek() {
395 None => return (retkey, retval)
398 while gap.full().distance() != 0 {
399 gap = match gap.shift() {
405 // Now we've done all our shifting. Return the value we grabbed earlier.
409 /// Perform robin hood bucket stealing at the given `bucket`. You must
410 /// also pass the position of that bucket's initial bucket so we don't have
411 /// to recalculate it.
413 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
414 fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
420 let starting_index = bucket.index();
422 let table = bucket.table(); // FIXME "lifetime too short".
425 // There can be at most `size - dib` buckets to displace, because
426 // in the worst case, there are `size` elements and we already are
427 // `distance` buckets away from the initial one.
428 let idx_end = starting_index + size - bucket.distance();
431 let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
433 let probe = bucket.next();
434 assert!(probe.index() != idx_end);
436 let full_bucket = match probe.peek() {
439 let b = bucket.put(old_hash, old_key, old_val);
440 // Now that it's stolen, just read the value's pointer
441 // right out of the table!
442 return Bucket::at_index(b.into_table(), starting_index)
448 Full(bucket) => bucket
451 let probe_ib = full_bucket.index() - full_bucket.distance();
453 bucket = full_bucket;
455 // Robin hood! Steal the spot.
467 /// A result that works like Option<FullBucket<..>> but preserves
468 /// the reference that grants us access to the table in any case.
469 enum SearchResult<K, V, M> {
470 // This is an entry that holds the given key:
471 FoundExisting(FullBucket<K, V, M>),
473 // There was no such entry. The reference is given back:
477 impl<K, V, M> SearchResult<K, V, M> {
478 fn into_option(self) -> Option<FullBucket<K, V, M>> {
480 FoundExisting(bucket) => Some(bucket),
486 impl<K, V, S> HashMap<K, V, S>
487 where K: Eq + Hash, S: HashState
489 fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash {
490 table::make_hash(&self.hash_state, x)
493 /// Search for a key, yielding the index if it's found in the hashtable.
494 /// If you already have the hash for the key lying around, use
496 fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
497 where K: Borrow<Q>, Q: Eq + Hash
499 let hash = self.make_hash(q);
500 search_hashed(&self.table, hash, |k| q.eq(k.borrow()))
504 fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
505 where K: Borrow<Q>, Q: Eq + Hash
507 let hash = self.make_hash(q);
508 search_hashed(&mut self.table, hash, |k| q.eq(k.borrow()))
512 // The caller should ensure that invariants by Robin Hood Hashing hold.
513 fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
514 let cap = self.table.capacity();
515 let mut buckets = Bucket::new(&mut self.table, hash);
516 let ib = buckets.index();
518 while buckets.index() != ib + cap {
519 // We don't need to compare hashes for value swap.
520 // Not even DIBs for Robin Hood.
521 buckets = match buckets.peek() {
523 empty.put(hash, k, v);
526 Full(b) => b.into_bucket()
530 panic!("Internal HashMap error: Out of space.");
534 impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
535 /// Creates an empty HashMap.
540 /// use std::collections::HashMap;
541 /// let mut map: HashMap<&str, isize> = HashMap::new();
544 #[stable(feature = "rust1", since = "1.0.0")]
545 pub fn new() -> HashMap<K, V, RandomState> {
549 /// Creates an empty hash map with the given initial capacity.
554 /// use std::collections::HashMap;
555 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
558 #[stable(feature = "rust1", since = "1.0.0")]
559 pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
560 HashMap::with_capacity_and_hash_state(capacity, Default::default())
564 impl<K, V, S> HashMap<K, V, S>
565 where K: Eq + Hash, S: HashState
567 /// Creates an empty hashmap which will use the given hasher to hash keys.
569 /// The created map has the default initial capacity.
574 /// #![feature(hashmap_hasher)]
576 /// use std::collections::HashMap;
577 /// use std::collections::hash_map::RandomState;
579 /// let s = RandomState::new();
580 /// let mut map = HashMap::with_hash_state(s);
581 /// map.insert(1, 2);
584 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
586 pub fn with_hash_state(hash_state: S) -> HashMap<K, V, S> {
588 hash_state: hash_state,
589 resize_policy: DefaultResizePolicy::new(),
590 table: RawTable::new(0),
594 /// Creates an empty HashMap with space for at least `capacity`
595 /// elements, using `hasher` to hash the keys.
597 /// Warning: `hasher` is normally randomly generated, and
598 /// is designed to allow HashMaps to be resistant to attacks that
599 /// cause many collisions and very poor performance. Setting it
600 /// manually using this function can expose a DoS attack vector.
605 /// #![feature(hashmap_hasher)]
607 /// use std::collections::HashMap;
608 /// use std::collections::hash_map::RandomState;
610 /// let s = RandomState::new();
611 /// let mut map = HashMap::with_capacity_and_hash_state(10, s);
612 /// map.insert(1, 2);
615 #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear",
617 pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S)
618 -> HashMap<K, V, S> {
619 let resize_policy = DefaultResizePolicy::new();
620 let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
621 let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
622 assert!(internal_cap >= capacity, "capacity overflow");
624 hash_state: hash_state,
625 resize_policy: resize_policy,
626 table: RawTable::new(internal_cap),
630 /// Returns the number of elements the map can hold without reallocating.
632 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
633 /// more, but is guaranteed to be able to hold at least this many.
638 /// use std::collections::HashMap;
639 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
640 /// assert!(map.capacity() >= 100);
643 #[stable(feature = "rust1", since = "1.0.0")]
644 pub fn capacity(&self) -> usize {
645 self.resize_policy.usable_capacity(self.table.capacity())
648 /// Reserves capacity for at least `additional` more elements to be inserted
649 /// in the `HashMap`. The collection may reserve more space to avoid
650 /// frequent reallocations.
654 /// Panics if the new allocation size overflows `usize`.
659 /// use std::collections::HashMap;
660 /// let mut map: HashMap<&str, isize> = HashMap::new();
663 #[stable(feature = "rust1", since = "1.0.0")]
664 pub fn reserve(&mut self, additional: usize) {
665 let new_size = self.len().checked_add(additional).expect("capacity overflow");
666 let min_cap = self.resize_policy.min_capacity(new_size);
668 // An invalid value shouldn't make us run out of space. This includes
669 // an overflow check.
670 assert!(new_size <= min_cap);
672 if self.table.capacity() < min_cap {
673 let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
674 self.resize(new_capacity);
678 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
679 /// 1) Make sure the new capacity is enough for all the elements, accounting
680 /// for the load factor.
681 /// 2) Ensure new_capacity is a power of two or zero.
682 fn resize(&mut self, new_capacity: usize) {
683 assert!(self.table.size() <= new_capacity);
684 assert!(new_capacity.is_power_of_two() || new_capacity == 0);
686 let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
687 let old_size = old_table.size();
689 if old_table.capacity() == 0 || old_table.size() == 0 {
694 // Specialization of the other branch.
695 let mut bucket = Bucket::first(&mut old_table);
697 // "So a few of the first shall be last: for many be called,
700 // We'll most likely encounter a few buckets at the beginning that
701 // have their initial buckets near the end of the table. They were
702 // placed at the beginning as the probe wrapped around the table
703 // during insertion. We must skip forward to a bucket that won't
704 // get reinserted too early and won't unfairly steal others spot.
705 // This eliminates the need for robin hood.
707 bucket = match bucket.peek() {
709 if full.distance() == 0 {
710 // This bucket occupies its ideal spot.
711 // It indicates the start of another "cluster".
712 bucket = full.into_bucket();
715 // Leaving this bucket in the last cluster for later.
719 // Encountered a hole between clusters.
726 // This is how the buckets might be laid out in memory:
727 // ($ marks an initialized bucket)
729 // |$$$_$$$$$$_$$$$$|
731 // But we've skipped the entire initial cluster of buckets
732 // and will continue iteration in this order:
735 // ^ wrap around once end is reached
738 // ^ exit once table.size == 0
740 bucket = match bucket.peek() {
742 let h = bucket.hash();
743 let (b, k, v) = bucket.take();
744 self.insert_hashed_ordered(h, k, v);
746 let t = b.table(); // FIXME "lifetime too short".
747 if t.size() == 0 { break }
751 Empty(b) => b.into_bucket()
756 assert_eq!(self.table.size(), old_size);
759 /// Shrinks the capacity of the map as much as possible. It will drop
760 /// down as much as possible while maintaining the internal rules
761 /// and possibly leaving some space in accordance with the resize policy.
766 /// use std::collections::HashMap;
768 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
769 /// map.insert(1, 2);
770 /// map.insert(3, 4);
771 /// assert!(map.capacity() >= 100);
772 /// map.shrink_to_fit();
773 /// assert!(map.capacity() >= 2);
775 #[stable(feature = "rust1", since = "1.0.0")]
776 pub fn shrink_to_fit(&mut self) {
777 let min_capacity = self.resize_policy.min_capacity(self.len());
778 let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
780 // An invalid value shouldn't make us run out of space.
781 debug_assert!(self.len() <= min_capacity);
783 if self.table.capacity() != min_capacity {
784 let old_table = replace(&mut self.table, RawTable::new(min_capacity));
785 let old_size = old_table.size();
787 // Shrink the table. Naive algorithm for resizing:
788 for (h, k, v) in old_table.into_iter() {
789 self.insert_hashed_nocheck(h, k, v);
792 debug_assert_eq!(self.table.size(), old_size);
796 /// Insert a pre-hashed key-value pair, without first checking
797 /// that there's enough room in the buckets. Returns a reference to the
798 /// newly insert value.
800 /// If the key already exists, the hashtable will be returned untouched
801 /// and a reference to the existing element will be returned.
802 fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
803 self.insert_or_replace_with(hash, k, v, |_, _, _, _| ())
806 fn insert_or_replace_with<'a, F>(&'a mut self,
810 mut found_existing: F)
812 F: FnMut(&mut K, &mut V, K, V),
814 // Worst case, we'll find one empty bucket among `size + 1` buckets.
815 let size = self.table.size();
816 let mut probe = Bucket::new(&mut self.table, hash);
817 let ib = probe.index();
820 let mut bucket = match probe.peek() {
823 return bucket.put(hash, k, v).into_mut_refs().1;
825 Full(bucket) => bucket
829 if bucket.hash() == hash {
831 if k == *bucket.read_mut().0 {
832 let (bucket_k, bucket_v) = bucket.into_mut_refs();
833 debug_assert!(k == *bucket_k);
834 // Key already exists. Get its reference.
835 found_existing(bucket_k, bucket_v, k, v);
840 let robin_ib = bucket.index() as isize - bucket.distance() as isize;
842 if (ib as isize) < robin_ib {
843 // Found a luckier bucket than me. Better steal his spot.
844 return robin_hood(bucket, robin_ib as usize, hash, k, v);
847 probe = bucket.next();
848 assert!(probe.index() != ib + size + 1);
852 /// An iterator visiting all keys in arbitrary order.
853 /// Iterator element type is `&'a K`.
858 /// use std::collections::HashMap;
860 /// let mut map = HashMap::new();
861 /// map.insert("a", 1);
862 /// map.insert("b", 2);
863 /// map.insert("c", 3);
865 /// for key in map.keys() {
866 /// println!("{}", key);
869 #[stable(feature = "rust1", since = "1.0.0")]
870 pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
871 fn first<A, B>((a, _): (A, B)) -> A { a }
872 let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr
874 Keys { inner: self.iter().map(first) }
877 /// An iterator visiting all values in arbitrary order.
878 /// Iterator element type is `&'a V`.
883 /// use std::collections::HashMap;
885 /// let mut map = HashMap::new();
886 /// map.insert("a", 1);
887 /// map.insert("b", 2);
888 /// map.insert("c", 3);
890 /// for val in map.values() {
891 /// println!("{}", val);
894 #[stable(feature = "rust1", since = "1.0.0")]
895 pub fn values<'a>(&'a self) -> Values<'a, K, V> {
896 fn second<A, B>((_, b): (A, B)) -> B { b }
897 let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr
899 Values { inner: self.iter().map(second) }
902 /// An iterator visiting all key-value pairs in arbitrary order.
903 /// Iterator element type is `(&'a K, &'a V)`.
908 /// use std::collections::HashMap;
910 /// let mut map = HashMap::new();
911 /// map.insert("a", 1);
912 /// map.insert("b", 2);
913 /// map.insert("c", 3);
915 /// for (key, val) in map.iter() {
916 /// println!("key: {} val: {}", key, val);
919 #[stable(feature = "rust1", since = "1.0.0")]
920 pub fn iter(&self) -> Iter<K, V> {
921 Iter { inner: self.table.iter() }
924 /// An iterator visiting all key-value pairs in arbitrary order,
925 /// with mutable references to the values.
926 /// Iterator element type is `(&'a K, &'a mut V)`.
931 /// use std::collections::HashMap;
933 /// let mut map = HashMap::new();
934 /// map.insert("a", 1);
935 /// map.insert("b", 2);
936 /// map.insert("c", 3);
938 /// // Update all values
939 /// for (_, val) in map.iter_mut() {
943 /// for (key, val) in &map {
944 /// println!("key: {} val: {}", key, val);
947 #[stable(feature = "rust1", since = "1.0.0")]
948 pub fn iter_mut(&mut self) -> IterMut<K, V> {
949 IterMut { inner: self.table.iter_mut() }
952 /// Gets the given key's corresponding entry in the map for in-place manipulation.
957 /// use std::collections::HashMap;
959 /// let mut letters = HashMap::new();
961 /// for ch in "a short treatise on fungi".chars() {
962 /// let counter = letters.entry(ch).or_insert(0);
966 /// assert_eq!(letters[&'s'], 2);
967 /// assert_eq!(letters[&'t'], 3);
968 /// assert_eq!(letters[&'u'], 1);
969 /// assert_eq!(letters.get(&'y'), None);
971 #[stable(feature = "rust1", since = "1.0.0")]
972 pub fn entry(&mut self, key: K) -> Entry<K, V> {
976 let hash = self.make_hash(&key);
977 search_entry_hashed(&mut self.table, hash, key)
980 /// Returns the number of elements in the map.
985 /// use std::collections::HashMap;
987 /// let mut a = HashMap::new();
988 /// assert_eq!(a.len(), 0);
989 /// a.insert(1, "a");
990 /// assert_eq!(a.len(), 1);
992 #[stable(feature = "rust1", since = "1.0.0")]
993 pub fn len(&self) -> usize { self.table.size() }
995 /// Returns true if the map contains no elements.
1000 /// use std::collections::HashMap;
1002 /// let mut a = HashMap::new();
1003 /// assert!(a.is_empty());
1004 /// a.insert(1, "a");
1005 /// assert!(!a.is_empty());
1008 #[stable(feature = "rust1", since = "1.0.0")]
1009 pub fn is_empty(&self) -> bool { self.len() == 0 }
1011 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
1012 /// allocated memory for reuse.
1017 /// use std::collections::HashMap;
1019 /// let mut a = HashMap::new();
1020 /// a.insert(1, "a");
1021 /// a.insert(2, "b");
1023 /// for (k, v) in a.drain().take(1) {
1024 /// assert!(k == 1 || k == 2);
1025 /// assert!(v == "a" || v == "b");
1028 /// assert!(a.is_empty());
1031 #[stable(feature = "drain", since = "1.6.0")]
1032 pub fn drain(&mut self) -> Drain<K, V> {
1033 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1034 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; // coerce to fn pointer
1037 inner: self.table.drain().map(last_two),
1041 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1047 /// use std::collections::HashMap;
1049 /// let mut a = HashMap::new();
1050 /// a.insert(1, "a");
1052 /// assert!(a.is_empty());
1054 #[stable(feature = "rust1", since = "1.0.0")]
1056 pub fn clear(&mut self) {
1060 /// Returns a reference to the value corresponding to the key.
1062 /// The key may be any borrowed form of the map's key type, but
1063 /// `Hash` and `Eq` on the borrowed form *must* match those for
1069 /// use std::collections::HashMap;
1071 /// let mut map = HashMap::new();
1072 /// map.insert(1, "a");
1073 /// assert_eq!(map.get(&1), Some(&"a"));
1074 /// assert_eq!(map.get(&2), None);
1076 #[stable(feature = "rust1", since = "1.0.0")]
1077 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
1078 where K: Borrow<Q>, Q: Hash + Eq
1080 self.search(k).map(|bucket| bucket.into_refs().1)
1083 /// Returns true if the map contains a value for the specified key.
1085 /// The key may be any borrowed form of the map's key type, but
1086 /// `Hash` and `Eq` on the borrowed form *must* match those for
1092 /// use std::collections::HashMap;
1094 /// let mut map = HashMap::new();
1095 /// map.insert(1, "a");
1096 /// assert_eq!(map.contains_key(&1), true);
1097 /// assert_eq!(map.contains_key(&2), false);
1099 #[stable(feature = "rust1", since = "1.0.0")]
1100 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1101 where K: Borrow<Q>, Q: Hash + Eq
1103 self.search(k).is_some()
1106 /// Returns a mutable reference to the value corresponding to the key.
1108 /// The key may be any borrowed form of the map's key type, but
1109 /// `Hash` and `Eq` on the borrowed form *must* match those for
1115 /// use std::collections::HashMap;
1117 /// let mut map = HashMap::new();
1118 /// map.insert(1, "a");
1119 /// if let Some(x) = map.get_mut(&1) {
1122 /// assert_eq!(map[&1], "b");
1124 #[stable(feature = "rust1", since = "1.0.0")]
1125 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1126 where K: Borrow<Q>, Q: Hash + Eq
1128 self.search_mut(k).map(|bucket| bucket.into_mut_refs().1)
1131 /// Inserts a key-value pair into the map.
1133 /// If the map did not have this key present, `None` is returned.
1135 /// If the map did have this key present, the key is not updated, the
1136 /// value is updated and the old value is returned.
1137 /// See the [module-level documentation] for more.
1139 /// [module-level documentation]: index.html#insert-and-complex-keys
1144 /// use std::collections::HashMap;
1146 /// let mut map = HashMap::new();
1147 /// assert_eq!(map.insert(37, "a"), None);
1148 /// assert_eq!(map.is_empty(), false);
1150 /// map.insert(37, "b");
1151 /// assert_eq!(map.insert(37, "c"), Some("b"));
1152 /// assert_eq!(map[&37], "c");
1154 #[stable(feature = "rust1", since = "1.0.0")]
1155 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1156 let hash = self.make_hash(&k);
1159 let mut retval = None;
1160 self.insert_or_replace_with(hash, k, v, |_, val_ref, _, val| {
1161 retval = Some(replace(val_ref, val));
1166 /// Removes a key from the map, returning the value at the key if the key
1167 /// was previously in the map.
1169 /// The key may be any borrowed form of the map's key type, but
1170 /// `Hash` and `Eq` on the borrowed form *must* match those for
1176 /// use std::collections::HashMap;
1178 /// let mut map = HashMap::new();
1179 /// map.insert(1, "a");
1180 /// assert_eq!(map.remove(&1), Some("a"));
1181 /// assert_eq!(map.remove(&1), None);
1183 #[stable(feature = "rust1", since = "1.0.0")]
1184 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1185 where K: Borrow<Q>, Q: Hash + Eq
1187 if self.table.size() == 0 {
1191 self.search_mut(k).map(|bucket| pop_internal(bucket).1)
1195 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
1198 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1199 let size = table.size();
1200 let mut probe = Bucket::new(table, hash);
1201 let ib = probe.index();
1204 let bucket = match probe.peek() {
1207 return Vacant(VacantEntry {
1210 elem: NoElem(bucket),
1213 Full(bucket) => bucket
1217 if bucket.hash() == hash {
1219 if k == *bucket.read().0 {
1220 return Occupied(OccupiedEntry{
1226 let robin_ib = bucket.index() as isize - bucket.distance() as isize;
1228 if (ib as isize) < robin_ib {
1229 // Found a luckier bucket than me. Better steal his spot.
1230 return Vacant(VacantEntry {
1233 elem: NeqElem(bucket, robin_ib as usize),
1237 probe = bucket.next();
1238 assert!(probe.index() != ib + size + 1);
1242 #[stable(feature = "rust1", since = "1.0.0")]
1243 impl<K, V, S> PartialEq for HashMap<K, V, S>
1244 where K: Eq + Hash, V: PartialEq, S: HashState
1246 fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1247 if self.len() != other.len() { return false; }
1249 self.iter().all(|(key, value)|
1250 other.get(key).map_or(false, |v| *value == *v)
1255 #[stable(feature = "rust1", since = "1.0.0")]
1256 impl<K, V, S> Eq for HashMap<K, V, S>
1257 where K: Eq + Hash, V: Eq, S: HashState
1260 #[stable(feature = "rust1", since = "1.0.0")]
1261 impl<K, V, S> Debug for HashMap<K, V, S>
1262 where K: Eq + Hash + Debug, V: Debug, S: HashState
1264 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1265 f.debug_map().entries(self.iter()).finish()
1269 #[stable(feature = "rust1", since = "1.0.0")]
1270 impl<K, V, S> Default for HashMap<K, V, S>
1272 S: HashState + Default,
1274 fn default() -> HashMap<K, V, S> {
1275 HashMap::with_hash_state(Default::default())
1279 #[stable(feature = "rust1", since = "1.0.0")]
1280 impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S>
1281 where K: Eq + Hash + Borrow<Q>,
1288 fn index(&self, index: &Q) -> &V {
1289 self.get(index).expect("no entry found for key")
1293 /// HashMap iterator.
1294 #[stable(feature = "rust1", since = "1.0.0")]
1295 pub struct Iter<'a, K: 'a, V: 'a> {
1296 inner: table::Iter<'a, K, V>
1299 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1300 #[stable(feature = "rust1", since = "1.0.0")]
1301 impl<'a, K, V> Clone for Iter<'a, K, V> {
1302 fn clone(&self) -> Iter<'a, K, V> {
1304 inner: self.inner.clone()
1309 /// HashMap mutable values iterator.
1310 #[stable(feature = "rust1", since = "1.0.0")]
1311 pub struct IterMut<'a, K: 'a, V: 'a> {
1312 inner: table::IterMut<'a, K, V>
1315 /// HashMap move iterator.
1316 #[stable(feature = "rust1", since = "1.0.0")]
1317 pub struct IntoIter<K, V> {
1318 inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)>
1321 /// HashMap keys iterator.
1322 #[stable(feature = "rust1", since = "1.0.0")]
1323 pub struct Keys<'a, K: 'a, V: 'a> {
1324 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
1327 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1328 #[stable(feature = "rust1", since = "1.0.0")]
1329 impl<'a, K, V> Clone for Keys<'a, K, V> {
1330 fn clone(&self) -> Keys<'a, K, V> {
1332 inner: self.inner.clone()
1337 /// HashMap values iterator.
1338 #[stable(feature = "rust1", since = "1.0.0")]
1339 pub struct Values<'a, K: 'a, V: 'a> {
1340 inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
1343 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1344 #[stable(feature = "rust1", since = "1.0.0")]
1345 impl<'a, K, V> Clone for Values<'a, K, V> {
1346 fn clone(&self) -> Values<'a, K, V> {
1348 inner: self.inner.clone()
1353 /// HashMap drain iterator.
1354 #[stable(feature = "drain", since = "1.6.0")]
1355 pub struct Drain<'a, K: 'a, V: 'a> {
1356 inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)>
1359 /// A view into a single occupied location in a HashMap.
1360 #[stable(feature = "rust1", since = "1.0.0")]
1361 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1362 elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1365 /// A view into a single empty location in a HashMap.
1366 #[stable(feature = "rust1", since = "1.0.0")]
1367 pub struct VacantEntry<'a, K: 'a, V: 'a> {
1370 elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
1373 /// A view into a single location in a map, which may be vacant or occupied.
1374 #[stable(feature = "rust1", since = "1.0.0")]
1375 pub enum Entry<'a, K: 'a, V: 'a> {
1376 /// An occupied Entry.
1377 #[stable(feature = "rust1", since = "1.0.0")]
1379 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] OccupiedEntry<'a, K, V>
1383 #[stable(feature = "rust1", since = "1.0.0")]
1385 #[cfg_attr(not(stage0), stable(feature = "rust1", since = "1.0.0"))] VacantEntry<'a, K, V>
1389 /// Possible states of a VacantEntry.
1390 enum VacantEntryState<K, V, M> {
1391 /// The index is occupied, but the key to insert has precedence,
1392 /// and will kick the current one out on insertion.
1393 NeqElem(FullBucket<K, V, M>, usize),
1394 /// The index is genuinely vacant.
1395 NoElem(EmptyBucket<K, V, M>),
1398 #[stable(feature = "rust1", since = "1.0.0")]
1399 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>
1400 where K: Eq + Hash, S: HashState
1402 type Item = (&'a K, &'a V);
1403 type IntoIter = Iter<'a, K, V>;
1405 fn into_iter(self) -> Iter<'a, K, V> {
1410 #[stable(feature = "rust1", since = "1.0.0")]
1411 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>
1412 where K: Eq + Hash, S: HashState
1414 type Item = (&'a K, &'a mut V);
1415 type IntoIter = IterMut<'a, K, V>;
1417 fn into_iter(mut self) -> IterMut<'a, K, V> {
1422 #[stable(feature = "rust1", since = "1.0.0")]
1423 impl<K, V, S> IntoIterator for HashMap<K, V, S>
1424 where K: Eq + Hash, S: HashState
1427 type IntoIter = IntoIter<K, V>;
1429 /// Creates a consuming iterator, that is, one that moves each key-value
1430 /// pair out of the map in arbitrary order. The map cannot be used after
1436 /// use std::collections::HashMap;
1438 /// let mut map = HashMap::new();
1439 /// map.insert("a", 1);
1440 /// map.insert("b", 2);
1441 /// map.insert("c", 3);
1443 /// // Not possible with .iter()
1444 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1446 fn into_iter(self) -> IntoIter<K, V> {
1447 fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1448 let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
1451 inner: self.table.into_iter().map(last_two)
1456 #[stable(feature = "rust1", since = "1.0.0")]
1457 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1458 type Item = (&'a K, &'a V);
1460 #[inline] fn next(&mut self) -> Option<(&'a K, &'a 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 Iter<'a, K, V> {
1465 #[inline] fn len(&self) -> usize { self.inner.len() }
1468 #[stable(feature = "rust1", since = "1.0.0")]
1469 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1470 type Item = (&'a K, &'a mut V);
1472 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1473 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1475 #[stable(feature = "rust1", since = "1.0.0")]
1476 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1477 #[inline] fn len(&self) -> usize { self.inner.len() }
1480 #[stable(feature = "rust1", since = "1.0.0")]
1481 impl<K, V> Iterator for IntoIter<K, V> {
1484 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1485 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1487 #[stable(feature = "rust1", since = "1.0.0")]
1488 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1489 #[inline] fn len(&self) -> usize { self.inner.len() }
1492 #[stable(feature = "rust1", since = "1.0.0")]
1493 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1496 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1497 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1499 #[stable(feature = "rust1", since = "1.0.0")]
1500 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1501 #[inline] fn len(&self) -> usize { self.inner.len() }
1504 #[stable(feature = "rust1", since = "1.0.0")]
1505 impl<'a, K, V> Iterator for Values<'a, K, V> {
1508 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1509 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1511 #[stable(feature = "rust1", since = "1.0.0")]
1512 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1513 #[inline] fn len(&self) -> usize { self.inner.len() }
1516 #[stable(feature = "rust1", since = "1.0.0")]
1517 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1520 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1521 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1523 #[stable(feature = "rust1", since = "1.0.0")]
1524 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1525 #[inline] fn len(&self) -> usize { self.inner.len() }
1528 impl<'a, K, V> Entry<'a, K, V> {
1529 #[stable(feature = "rust1", since = "1.0.0")]
1530 /// Ensures a value is in the entry by inserting the default if empty, and returns
1531 /// a mutable reference to the value in the entry.
1532 pub fn or_insert(self, default: V) -> &'a mut V {
1534 Occupied(entry) => entry.into_mut(),
1535 Vacant(entry) => entry.insert(default),
1539 #[stable(feature = "rust1", since = "1.0.0")]
1540 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1541 /// and returns a mutable reference to the value in the entry.
1542 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1544 Occupied(entry) => entry.into_mut(),
1545 Vacant(entry) => entry.insert(default()),
1550 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1551 /// Gets a reference to the value in the entry.
1552 #[stable(feature = "rust1", since = "1.0.0")]
1553 pub fn get(&self) -> &V {
1557 /// Gets a mutable reference to the value in the entry.
1558 #[stable(feature = "rust1", since = "1.0.0")]
1559 pub fn get_mut(&mut self) -> &mut V {
1560 self.elem.read_mut().1
1563 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1564 /// with a lifetime bound to the map itself
1565 #[stable(feature = "rust1", since = "1.0.0")]
1566 pub fn into_mut(self) -> &'a mut V {
1567 self.elem.into_mut_refs().1
1570 /// Sets the value of the entry, and returns the entry's old value
1571 #[stable(feature = "rust1", since = "1.0.0")]
1572 pub fn insert(&mut self, mut value: V) -> V {
1573 let old_value = self.get_mut();
1574 mem::swap(&mut value, old_value);
1578 /// Takes the value out of the entry, and returns it
1579 #[stable(feature = "rust1", since = "1.0.0")]
1580 pub fn remove(self) -> V {
1581 pop_internal(self.elem).1
1585 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
1586 /// Sets the value of the entry with the VacantEntry's key,
1587 /// and returns a mutable reference to it
1588 #[stable(feature = "rust1", since = "1.0.0")]
1589 pub fn insert(self, value: V) -> &'a mut V {
1591 NeqElem(bucket, ib) => {
1592 robin_hood(bucket, ib, self.hash, self.key, value)
1595 bucket.put(self.hash, self.key, value).into_mut_refs().1
1601 #[stable(feature = "rust1", since = "1.0.0")]
1602 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
1603 where K: Eq + Hash, S: HashState + Default
1605 fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> HashMap<K, V, S> {
1606 let iter = iterable.into_iter();
1607 let lower = iter.size_hint().0;
1608 let mut map = HashMap::with_capacity_and_hash_state(lower,
1609 Default::default());
1615 #[stable(feature = "rust1", since = "1.0.0")]
1616 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
1617 where K: Eq + Hash, S: HashState
1619 fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1620 for (k, v) in iter {
1626 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1627 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
1628 where K: Eq + Hash + Copy, V: Copy, S: HashState
1630 fn extend<T: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: T) {
1631 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1635 /// `RandomState` is the default state for `HashMap` types.
1637 /// A particular instance `RandomState` will create the same instances of
1638 /// `Hasher`, but the hashers created by two different `RandomState`
1639 /// instances are unlikely to produce the same result for the same values.
1641 #[unstable(feature = "hashmap_hasher",
1642 reason = "hashing an hash maps may be altered",
1644 pub struct RandomState {
1649 #[unstable(feature = "hashmap_hasher",
1650 reason = "hashing an hash maps may be altered",
1653 /// Constructs a new `RandomState` that is initialized with random keys.
1655 #[allow(deprecated)] // rand
1656 pub fn new() -> RandomState {
1657 let mut r = rand::thread_rng();
1658 RandomState { k0: r.gen(), k1: r.gen() }
1662 #[unstable(feature = "hashmap_hasher",
1663 reason = "hashing an hash maps may be altered",
1665 impl HashState for RandomState {
1666 type Hasher = SipHasher;
1668 fn hasher(&self) -> SipHasher {
1669 SipHasher::new_with_keys(self.k0, self.k1)
1673 #[stable(feature = "rust1", since = "1.0.0")]
1674 impl Default for RandomState {
1676 fn default() -> RandomState {
1681 impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
1682 where K: Eq + Hash + Borrow<Q>, S: HashState, Q: Eq + Hash
1686 fn get(&self, key: &Q) -> Option<&K> {
1687 self.search(key).map(|bucket| bucket.into_refs().0)
1690 fn take(&mut self, key: &Q) -> Option<K> {
1691 if self.table.size() == 0 {
1695 self.search_mut(key).map(|bucket| pop_internal(bucket).0)
1698 fn replace(&mut self, key: K) -> Option<K> {
1699 let hash = self.make_hash(&key);
1702 let mut retkey = None;
1703 self.insert_or_replace_with(hash, key, (), |key_ref, _, key, _| {
1704 retkey = Some(replace(key_ref, key));
1715 use super::Entry::{Occupied, Vacant};
1717 use rand::{thread_rng, Rng};
1720 fn test_create_capacity_zero() {
1721 let mut m = HashMap::with_capacity(0);
1723 assert!(m.insert(1, 1).is_none());
1725 assert!(m.contains_key(&1));
1726 assert!(!m.contains_key(&0));
1731 let mut m = HashMap::new();
1732 assert_eq!(m.len(), 0);
1733 assert!(m.insert(1, 2).is_none());
1734 assert_eq!(m.len(), 1);
1735 assert!(m.insert(2, 4).is_none());
1736 assert_eq!(m.len(), 2);
1737 assert_eq!(*m.get(&1).unwrap(), 2);
1738 assert_eq!(*m.get(&2).unwrap(), 4);
1741 thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1743 #[derive(Hash, PartialEq, Eq)]
1749 fn new(k: usize) -> Dropable {
1750 DROP_VECTOR.with(|slot| {
1751 slot.borrow_mut()[k] += 1;
1758 impl Drop for Dropable {
1759 fn drop(&mut self) {
1760 DROP_VECTOR.with(|slot| {
1761 slot.borrow_mut()[self.k] -= 1;
1766 impl Clone for Dropable {
1767 fn clone(&self) -> Dropable {
1768 Dropable::new(self.k)
1774 DROP_VECTOR.with(|slot| {
1775 *slot.borrow_mut() = vec![0; 200];
1779 let mut m = HashMap::new();
1781 DROP_VECTOR.with(|v| {
1783 assert_eq!(v.borrow()[i], 0);
1788 let d1 = Dropable::new(i);
1789 let d2 = Dropable::new(i+100);
1793 DROP_VECTOR.with(|v| {
1795 assert_eq!(v.borrow()[i], 1);
1800 let k = Dropable::new(i);
1801 let v = m.remove(&k);
1803 assert!(v.is_some());
1805 DROP_VECTOR.with(|v| {
1806 assert_eq!(v.borrow()[i], 1);
1807 assert_eq!(v.borrow()[i+100], 1);
1811 DROP_VECTOR.with(|v| {
1813 assert_eq!(v.borrow()[i], 0);
1814 assert_eq!(v.borrow()[i+100], 0);
1818 assert_eq!(v.borrow()[i], 1);
1819 assert_eq!(v.borrow()[i+100], 1);
1824 DROP_VECTOR.with(|v| {
1826 assert_eq!(v.borrow()[i], 0);
1832 fn test_move_iter_drops() {
1833 DROP_VECTOR.with(|v| {
1834 *v.borrow_mut() = vec![0; 200];
1838 let mut hm = HashMap::new();
1840 DROP_VECTOR.with(|v| {
1842 assert_eq!(v.borrow()[i], 0);
1847 let d1 = Dropable::new(i);
1848 let d2 = Dropable::new(i+100);
1852 DROP_VECTOR.with(|v| {
1854 assert_eq!(v.borrow()[i], 1);
1861 // By the way, ensure that cloning doesn't screw up the dropping.
1865 let mut half = hm.into_iter().take(50);
1867 DROP_VECTOR.with(|v| {
1869 assert_eq!(v.borrow()[i], 1);
1873 for _ in half.by_ref() {}
1875 DROP_VECTOR.with(|v| {
1876 let nk = (0..100).filter(|&i| {
1880 let nv = (0..100).filter(|&i| {
1881 v.borrow()[i+100] == 1
1889 DROP_VECTOR.with(|v| {
1891 assert_eq!(v.borrow()[i], 0);
1897 fn test_empty_pop() {
1898 let mut m: HashMap<isize, bool> = HashMap::new();
1899 assert_eq!(m.remove(&0), None);
1903 fn test_lots_of_insertions() {
1904 let mut m = HashMap::new();
1906 // Try this a few times to make sure we never screw up the hashmap's
1909 assert!(m.is_empty());
1912 assert!(m.insert(i, i).is_none());
1916 assert_eq!(r, Some(&j));
1919 for j in i+1..1001 {
1921 assert_eq!(r, None);
1925 for i in 1001..2001 {
1926 assert!(!m.contains_key(&i));
1931 assert!(m.remove(&i).is_some());
1934 assert!(!m.contains_key(&j));
1937 for j in i+1..1001 {
1938 assert!(m.contains_key(&j));
1943 assert!(!m.contains_key(&i));
1947 assert!(m.insert(i, i).is_none());
1951 for i in (1..1001).rev() {
1952 assert!(m.remove(&i).is_some());
1955 assert!(!m.contains_key(&j));
1959 assert!(m.contains_key(&j));
1966 fn test_find_mut() {
1967 let mut m = HashMap::new();
1968 assert!(m.insert(1, 12).is_none());
1969 assert!(m.insert(2, 8).is_none());
1970 assert!(m.insert(5, 14).is_none());
1972 match m.get_mut(&5) {
1973 None => panic!(), Some(x) => *x = new
1975 assert_eq!(m.get(&5), Some(&new));
1979 fn test_insert_overwrite() {
1980 let mut m = HashMap::new();
1981 assert!(m.insert(1, 2).is_none());
1982 assert_eq!(*m.get(&1).unwrap(), 2);
1983 assert!(!m.insert(1, 3).is_none());
1984 assert_eq!(*m.get(&1).unwrap(), 3);
1988 fn test_insert_conflicts() {
1989 let mut m = HashMap::with_capacity(4);
1990 assert!(m.insert(1, 2).is_none());
1991 assert!(m.insert(5, 3).is_none());
1992 assert!(m.insert(9, 4).is_none());
1993 assert_eq!(*m.get(&9).unwrap(), 4);
1994 assert_eq!(*m.get(&5).unwrap(), 3);
1995 assert_eq!(*m.get(&1).unwrap(), 2);
1999 fn test_conflict_remove() {
2000 let mut m = HashMap::with_capacity(4);
2001 assert!(m.insert(1, 2).is_none());
2002 assert_eq!(*m.get(&1).unwrap(), 2);
2003 assert!(m.insert(5, 3).is_none());
2004 assert_eq!(*m.get(&1).unwrap(), 2);
2005 assert_eq!(*m.get(&5).unwrap(), 3);
2006 assert!(m.insert(9, 4).is_none());
2007 assert_eq!(*m.get(&1).unwrap(), 2);
2008 assert_eq!(*m.get(&5).unwrap(), 3);
2009 assert_eq!(*m.get(&9).unwrap(), 4);
2010 assert!(m.remove(&1).is_some());
2011 assert_eq!(*m.get(&9).unwrap(), 4);
2012 assert_eq!(*m.get(&5).unwrap(), 3);
2016 fn test_is_empty() {
2017 let mut m = HashMap::with_capacity(4);
2018 assert!(m.insert(1, 2).is_none());
2019 assert!(!m.is_empty());
2020 assert!(m.remove(&1).is_some());
2021 assert!(m.is_empty());
2026 let mut m = HashMap::new();
2028 assert_eq!(m.remove(&1), Some(2));
2029 assert_eq!(m.remove(&1), None);
2034 let mut m = HashMap::with_capacity(4);
2036 assert!(m.insert(i, i*2).is_none());
2038 assert_eq!(m.len(), 32);
2040 let mut observed: u32 = 0;
2043 assert_eq!(*v, *k * 2);
2044 observed |= 1 << *k;
2046 assert_eq!(observed, 0xFFFF_FFFF);
2051 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2052 let map: HashMap<_, _> = vec.into_iter().collect();
2053 let keys: Vec<_> = map.keys().cloned().collect();
2054 assert_eq!(keys.len(), 3);
2055 assert!(keys.contains(&1));
2056 assert!(keys.contains(&2));
2057 assert!(keys.contains(&3));
2062 let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2063 let map: HashMap<_, _> = vec.into_iter().collect();
2064 let values: Vec<_> = map.values().cloned().collect();
2065 assert_eq!(values.len(), 3);
2066 assert!(values.contains(&'a'));
2067 assert!(values.contains(&'b'));
2068 assert!(values.contains(&'c'));
2073 let mut m = HashMap::new();
2074 assert!(m.get(&1).is_none());
2078 Some(v) => assert_eq!(*v, 2)
2084 let mut m1 = HashMap::new();
2089 let mut m2 = HashMap::new();
2102 let mut map = HashMap::new();
2103 let empty: HashMap<i32, i32> = HashMap::new();
2108 let map_str = format!("{:?}", map);
2110 assert!(map_str == "{1: 2, 3: 4}" ||
2111 map_str == "{3: 4, 1: 2}");
2112 assert_eq!(format!("{:?}", empty), "{}");
2117 let mut m = HashMap::new();
2119 assert_eq!(m.len(), 0);
2120 assert!(m.is_empty());
2123 let old_cap = m.table.capacity();
2124 while old_cap == m.table.capacity() {
2129 assert_eq!(m.len(), i);
2130 assert!(!m.is_empty());
2134 fn test_behavior_resize_policy() {
2135 let mut m = HashMap::new();
2137 assert_eq!(m.len(), 0);
2138 assert_eq!(m.table.capacity(), 0);
2139 assert!(m.is_empty());
2143 assert!(m.is_empty());
2144 let initial_cap = m.table.capacity();
2145 m.reserve(initial_cap);
2146 let cap = m.table.capacity();
2148 assert_eq!(cap, initial_cap * 2);
2151 for _ in 0..cap * 3 / 4 {
2155 // three quarters full
2157 assert_eq!(m.len(), i);
2158 assert_eq!(m.table.capacity(), cap);
2160 for _ in 0..cap / 4 {
2166 let new_cap = m.table.capacity();
2167 assert_eq!(new_cap, cap * 2);
2169 for _ in 0..cap / 2 - 1 {
2172 assert_eq!(m.table.capacity(), new_cap);
2174 // A little more than one quarter full.
2176 assert_eq!(m.table.capacity(), cap);
2177 // again, a little more than half full
2178 for _ in 0..cap / 2 - 1 {
2184 assert_eq!(m.len(), i);
2185 assert!(!m.is_empty());
2186 assert_eq!(m.table.capacity(), initial_cap);
2190 fn test_reserve_shrink_to_fit() {
2191 let mut m = HashMap::new();
2194 assert!(m.capacity() >= m.len());
2200 let usable_cap = m.capacity();
2201 for i in 128..(128 + 256) {
2203 assert_eq!(m.capacity(), usable_cap);
2206 for i in 100..(128 + 256) {
2207 assert_eq!(m.remove(&i), Some(i));
2211 assert_eq!(m.len(), 100);
2212 assert!(!m.is_empty());
2213 assert!(m.capacity() >= m.len());
2216 assert_eq!(m.remove(&i), Some(i));
2221 assert_eq!(m.len(), 1);
2222 assert!(m.capacity() >= m.len());
2223 assert_eq!(m.remove(&0), Some(0));
2227 fn test_from_iter() {
2228 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2230 let map: HashMap<_, _> = xs.iter().cloned().collect();
2232 for &(k, v) in &xs {
2233 assert_eq!(map.get(&k), Some(&v));
2238 fn test_size_hint() {
2239 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2241 let map: HashMap<_, _> = xs.iter().cloned().collect();
2243 let mut iter = map.iter();
2245 for _ in iter.by_ref().take(3) {}
2247 assert_eq!(iter.size_hint(), (3, Some(3)));
2251 fn test_iter_len() {
2252 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2254 let map: HashMap<_, _> = xs.iter().cloned().collect();
2256 let mut iter = map.iter();
2258 for _ in iter.by_ref().take(3) {}
2260 assert_eq!(iter.len(), 3);
2264 fn test_mut_size_hint() {
2265 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2267 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2269 let mut iter = map.iter_mut();
2271 for _ in iter.by_ref().take(3) {}
2273 assert_eq!(iter.size_hint(), (3, Some(3)));
2277 fn test_iter_mut_len() {
2278 let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2280 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2282 let mut iter = map.iter_mut();
2284 for _ in iter.by_ref().take(3) {}
2286 assert_eq!(iter.len(), 3);
2291 let mut map = HashMap::new();
2297 assert_eq!(map[&2], 1);
2302 fn test_index_nonexistent() {
2303 let mut map = HashMap::new();
2314 let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2316 let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2318 // Existing key (insert)
2319 match map.entry(1) {
2320 Vacant(_) => unreachable!(),
2321 Occupied(mut view) => {
2322 assert_eq!(view.get(), &10);
2323 assert_eq!(view.insert(100), 10);
2326 assert_eq!(map.get(&1).unwrap(), &100);
2327 assert_eq!(map.len(), 6);
2330 // Existing key (update)
2331 match map.entry(2) {
2332 Vacant(_) => unreachable!(),
2333 Occupied(mut view) => {
2334 let v = view.get_mut();
2335 let new_v = (*v) * 10;
2339 assert_eq!(map.get(&2).unwrap(), &200);
2340 assert_eq!(map.len(), 6);
2342 // Existing key (take)
2343 match map.entry(3) {
2344 Vacant(_) => unreachable!(),
2346 assert_eq!(view.remove(), 30);
2349 assert_eq!(map.get(&3), None);
2350 assert_eq!(map.len(), 5);
2353 // Inexistent key (insert)
2354 match map.entry(10) {
2355 Occupied(_) => unreachable!(),
2357 assert_eq!(*view.insert(1000), 1000);
2360 assert_eq!(map.get(&10).unwrap(), &1000);
2361 assert_eq!(map.len(), 6);
2365 fn test_entry_take_doesnt_corrupt() {
2366 #![allow(deprecated)] //rand
2368 fn check(m: &HashMap<isize, ()>) {
2370 assert!(m.contains_key(k),
2371 "{} is in keys() but not in the map?", k);
2375 let mut m = HashMap::new();
2376 let mut rng = thread_rng();
2378 // Populate the map with some items.
2380 let x = rng.gen_range(-10, 10);
2385 let x = rng.gen_range(-10, 10);
2389 println!("{}: remove {}", i, x);
2399 fn test_extend_ref() {
2400 let mut a = HashMap::new();
2402 let mut b = HashMap::new();
2404 b.insert(3, "three");
2408 assert_eq!(a.len(), 3);
2409 assert_eq!(a[&1], "one");
2410 assert_eq!(a[&2], "two");
2411 assert_eq!(a[&3], "three");