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}
;
27 use result
::Result
::{self, Ok, Err}
;
39 use super::table
::BucketState
::{
43 use super::state
::HashState
;
45 const INITIAL_LOG2_CAP
: usize = 5;
46 #[unstable(feature = "std_misc")]
47 pub const INITIAL_CAPACITY
: usize = 1 << INITIAL_LOG2_CAP
; // 2^5
49 /// The default behavior of HashMap implements a load factor of 90.9%.
50 /// This behavior is characterized by the following condition:
52 /// - if size > 0.909 * capacity: grow the map
54 struct DefaultResizePolicy
;
56 impl DefaultResizePolicy
{
57 fn new() -> DefaultResizePolicy
{
62 fn min_capacity(&self, usable_size
: usize) -> usize {
63 // Here, we are rephrasing the logic by specifying the lower limit
66 // - if `cap < size * 1.1`: grow the map
70 /// An inverse of `min_capacity`, approximately.
72 fn usable_capacity(&self, cap
: usize) -> usize {
73 // As the number of entries approaches usable capacity,
74 // min_capacity(size) must be smaller than the internal capacity,
75 // so that the map is not resized:
76 // `min_capacity(usable_capacity(x)) <= x`.
77 // The left-hand side can only be smaller due to flooring by integer
80 // This doesn't have to be checked for overflow since allocation size
81 // in bytes will overflow earlier than multiplication by 10.
87 fn test_resize_policy() {
88 let rp
= DefaultResizePolicy
;
90 assert
!(rp
.min_capacity(rp
.usable_capacity(n
)) <= n
);
91 assert
!(rp
.usable_capacity(rp
.min_capacity(n
)) <= n
);
95 // The main performance trick in this hashmap is called Robin Hood Hashing.
96 // It gains its excellent performance from one essential operation:
98 // If an insertion collides with an existing element, and that element's
99 // "probe distance" (how far away the element is from its ideal location)
100 // is higher than how far we've already probed, swap the elements.
102 // This massively lowers variance in probe distance, and allows us to get very
103 // high load factors with good performance. The 90% load factor I use is rather
106 // > Why a load factor of approximately 90%?
108 // In general, all the distances to initial buckets will converge on the mean.
109 // At a load factor of α, the odds of finding the target bucket after k
110 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
111 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
112 // this down to make the math easier on the CPU and avoid its FPU.
113 // Since on average we start the probing in the middle of a cache line, this
114 // strategy pulls in two cache lines of hashes on every lookup. I think that's
115 // pretty good, but if you want to trade off some space, it could go down to one
116 // cache line on average with an α of 0.84.
118 // > Wait, what? Where did you get 1-α^k from?
120 // On the first probe, your odds of a collision with an existing element is α.
121 // The odds of doing this twice in a row is approximately α^2. For three times,
122 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
123 // colliding after k tries is 1-α^k.
125 // The paper from 1986 cited below mentions an implementation which keeps track
126 // of the distance-to-initial-bucket histogram. This approach is not suitable
127 // for modern architectures because it requires maintaining an internal data
128 // structure. This allows very good first guesses, but we are most concerned
129 // with guessing entire cache lines, not individual indexes. Furthermore, array
130 // accesses are no longer linear and in one direction, as we have now. There
131 // is also memory and cache pressure that this would entail that would be very
132 // difficult to properly see in a microbenchmark.
134 // ## Future Improvements (FIXME!)
136 // Allow the load factor to be changed dynamically and/or at initialization.
138 // Also, would it be possible for us to reuse storage when growing the
139 // underlying table? This is exactly the use case for 'realloc', and may
140 // be worth exploring.
142 // ## Future Optimizations (FIXME!)
144 // Another possible design choice that I made without any real reason is
145 // parameterizing the raw table over keys and values. Technically, all we need
146 // is the size and alignment of keys and values, and the code should be just as
147 // efficient (well, we might need one for power-of-two size and one for not...).
148 // This has the potential to reduce code bloat in rust executables, without
149 // really losing anything except 4 words (key size, key alignment, val size,
150 // val alignment) which can be passed in to every call of a `RawTable` function.
151 // This would definitely be an avenue worth exploring if people start complaining
152 // about the size of rust executables.
154 // Annotate exceedingly likely branches in `table::make_hash`
155 // and `search_hashed` to reduce instruction cache pressure
156 // and mispredictions once it becomes possible (blocked on issue #11092).
158 // Shrinking the table could simply reallocate in place after moving buckets
159 // to the first half.
161 // The growth algorithm (fragment of the Proof of Correctness)
162 // --------------------
164 // The growth algorithm is basically a fast path of the naive reinsertion-
165 // during-resize algorithm. Other paths should never be taken.
167 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
168 // by allocating a new table of capacity `2n`, and then individually reinsert
169 // each element in the old table into the new one. This guarantees that the
170 // new table is a valid robin hood hashtable with all the desired statistical
171 // properties. Remark that the order we reinsert the elements in should not
172 // matter. For simplicity and efficiency, we will consider only linear
173 // reinsertions, which consist of reinserting all elements in the old table
174 // into the new one by increasing order of index. However we will not be
175 // starting our reinsertions from index 0 in general. If we start from index
176 // i, for the purpose of reinsertion we will consider all elements with real
177 // index j < i to have virtual index n + j.
179 // Our hash generation scheme consists of generating a 64-bit hash and
180 // truncating the most significant bits. When moving to the new table, we
181 // simply introduce a new bit to the front of the hash. Therefore, if an
182 // elements has ideal index i in the old table, it can have one of two ideal
183 // locations in the new table. If the new bit is 0, then the new ideal index
184 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
185 // we are producing two independent tables of size n, and for each element we
186 // independently choose which table to insert it into with equal probability.
187 // However the rather than wrapping around themselves on overflowing their
188 // indexes, the first table overflows into the first, and the first into the
189 // second. Visually, our new table will look something like:
191 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
193 // Where x's are elements inserted into the first table, y's are elements
194 // inserted into the second, and _'s are empty sections. We now define a few
195 // key concepts that we will use later. Note that this is a very abstract
196 // perspective of the table. A real resized table would be at least half
199 // Theorem: A linear robin hood reinsertion from the first ideal element
200 // produces identical results to a linear naive reinsertion from the same
203 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
205 /// A hash map implementation which uses linear probing with Robin
206 /// Hood bucket stealing.
208 /// The hashes are all keyed by the thread-local random number generator
209 /// on creation by default. This means that the ordering of the keys is
210 /// randomized, but makes the tables more resistant to
211 /// denial-of-service attacks (Hash DoS). This behaviour can be
212 /// overridden with one of the constructors.
214 /// It is required that the keys implement the `Eq` and `Hash` traits, although
215 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
216 /// If you implement these yourself, it is important that the following
220 /// k1 == k2 -> hash(k1) == hash(k2)
223 /// In other words, if two keys are equal, their hashes must be equal.
225 /// It is a logic error for a key to be modified in such a way that the key's
226 /// hash, as determined by the `Hash` trait, or its equality, as determined by
227 /// the `Eq` trait, changes while it is in the map. This is normally only
228 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
230 /// Relevant papers/articles:
232 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
233 /// 2. Emmanuel Goossaert. ["Robin Hood
234 /// hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
235 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
236 /// deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
241 /// use std::collections::HashMap;
243 /// // type inference lets us omit an explicit type signature (which
244 /// // would be `HashMap<&str, &str>` in this example).
245 /// let mut book_reviews = HashMap::new();
247 /// // review some books.
248 /// book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
249 /// book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
250 /// book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
251 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
253 /// // check for a specific one.
254 /// if !book_reviews.contains_key("Les Misérables") {
255 /// println!("We've got {} reviews, but Les Misérables ain't one.",
256 /// book_reviews.len());
259 /// // oops, this review has a lot of spelling mistakes, let's delete it.
260 /// book_reviews.remove("The Adventures of Sherlock Holmes");
262 /// // look up the values associated with some keys.
263 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
264 /// for book in &to_find {
265 /// match book_reviews.get(book) {
266 /// Some(review) => println!("{}: {}", book, review),
267 /// None => println!("{} is unreviewed.", book)
271 /// // iterate over everything.
272 /// for (book, review) in &book_reviews {
273 /// println!("{}: \"{}\"", book, review);
277 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
278 /// We must also derive `PartialEq`.
281 /// use std::collections::HashMap;
283 /// #[derive(Hash, Eq, PartialEq, Debug)]
290 /// /// Create a new Viking.
291 /// fn new(name: &str, country: &str) -> Viking {
292 /// Viking { name: name.to_string(), country: country.to_string() }
296 /// // Use a HashMap to store the vikings' health points.
297 /// let mut vikings = HashMap::new();
299 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
300 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
301 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
303 /// // Use derived implementation to print the status of the vikings.
304 /// for (viking, health) in &vikings {
305 /// println!("{:?} has {} hp", viking, health);
309 #[stable(feature = "rust1", since = "1.0.0")]
310 pub struct HashMap
<K
, V
, S
= RandomState
> {
311 // All hashes are keyed on these values, to prevent hash collision attacks.
314 table
: RawTable
<K
, V
>,
316 resize_policy
: DefaultResizePolicy
,
319 /// Search for a pre-hashed key.
320 fn search_hashed
<K
, V
, M
, F
>(table
: M
,
323 -> SearchResult
<K
, V
, M
> where
324 M
: Deref
<Target
=RawTable
<K
, V
>>,
325 F
: FnMut(&K
) -> bool
,
327 // This is the only function where capacity can be zero. To avoid
328 // undefined behaviour when Bucket::new gets the raw bucket in this
329 // case, immediately return the appropriate search result.
330 if table
.capacity() == 0 {
331 return TableRef(table
);
334 let size
= table
.size();
335 let mut probe
= Bucket
::new(table
, hash
);
336 let ib
= probe
.index();
338 while probe
.index() != ib
+ size
{
339 let full
= match probe
.peek() {
340 Empty(b
) => return TableRef(b
.into_table()), // hit an empty bucket
344 if full
.distance() + ib
< full
.index() {
345 // We can finish the search early if we hit any bucket
346 // with a lower distance to initial bucket than we've probed.
347 return TableRef(full
.into_table());
350 // If the hash doesn't match, it can't be this one..
351 if hash
== full
.hash() {
352 // If the key doesn't match, it can't be this one..
353 if is_match(full
.read().0) {
354 return FoundExisting(full
);
361 TableRef(probe
.into_table())
364 fn pop_internal
<K
, V
>(starting_bucket
: FullBucketMut
<K
, V
>) -> (K
, V
) {
365 let (empty
, retkey
, retval
) = starting_bucket
.take();
366 let mut gap
= match empty
.gap_peek() {
368 None
=> return (retkey
, retval
)
371 while gap
.full().distance() != 0 {
372 gap
= match gap
.shift() {
378 // Now we've done all our shifting. Return the value we grabbed earlier.
382 /// Perform robin hood bucket stealing at the given `bucket`. You must
383 /// also pass the position of that bucket's initial bucket so we don't have
384 /// to recalculate it.
386 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
387 fn robin_hood
<'a
, K
: 'a
, V
: 'a
>(mut bucket
: FullBucketMut
<'a
, K
, V
>,
393 let starting_index
= bucket
.index();
395 let table
= bucket
.table(); // FIXME "lifetime too short".
398 // There can be at most `size - dib` buckets to displace, because
399 // in the worst case, there are `size` elements and we already are
400 // `distance` buckets away from the initial one.
401 let idx_end
= starting_index
+ size
- bucket
.distance();
404 let (old_hash
, old_key
, old_val
) = bucket
.replace(hash
, k
, v
);
406 let probe
= bucket
.next();
407 assert
!(probe
.index() != idx_end
);
409 let full_bucket
= match probe
.peek() {
412 let b
= bucket
.put(old_hash
, old_key
, old_val
);
413 // Now that it's stolen, just read the value's pointer
414 // right out of the table!
415 return Bucket
::at_index(b
.into_table(), starting_index
)
421 Full(bucket
) => bucket
424 let probe_ib
= full_bucket
.index() - full_bucket
.distance();
426 bucket
= full_bucket
;
428 // Robin hood! Steal the spot.
440 /// A result that works like Option<FullBucket<..>> but preserves
441 /// the reference that grants us access to the table in any case.
442 enum SearchResult
<K
, V
, M
> {
443 // This is an entry that holds the given key:
444 FoundExisting(FullBucket
<K
, V
, M
>),
446 // There was no such entry. The reference is given back:
450 impl<K
, V
, M
> SearchResult
<K
, V
, M
> {
451 fn into_option(self) -> Option
<FullBucket
<K
, V
, M
>> {
453 FoundExisting(bucket
) => Some(bucket
),
459 impl<K
, V
, S
> HashMap
<K
, V
, S
>
460 where K
: Eq
+ Hash
, S
: HashState
462 fn make_hash
<X
: ?Sized
>(&self, x
: &X
) -> SafeHash
where X
: Hash
{
463 table
::make_hash(&self.hash_state
, x
)
466 /// Search for a key, yielding the index if it's found in the hashtable.
467 /// If you already have the hash for the key lying around, use
469 fn search
<'a
, Q
: ?Sized
>(&'a
self, q
: &Q
) -> Option
<FullBucketImm
<'a
, K
, V
>>
470 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
472 let hash
= self.make_hash(q
);
473 search_hashed(&self.table
, hash
, |k
| q
.eq(k
.borrow()))
477 fn search_mut
<'a
, Q
: ?Sized
>(&'a
mut self, q
: &Q
) -> Option
<FullBucketMut
<'a
, K
, V
>>
478 where K
: Borrow
<Q
>, Q
: Eq
+ Hash
480 let hash
= self.make_hash(q
);
481 search_hashed(&mut self.table
, hash
, |k
| q
.eq(k
.borrow()))
485 // The caller should ensure that invariants by Robin Hood Hashing hold.
486 fn insert_hashed_ordered(&mut self, hash
: SafeHash
, k
: K
, v
: V
) {
487 let cap
= self.table
.capacity();
488 let mut buckets
= Bucket
::new(&mut self.table
, hash
);
489 let ib
= buckets
.index();
491 while buckets
.index() != ib
+ cap
{
492 // We don't need to compare hashes for value swap.
493 // Not even DIBs for Robin Hood.
494 buckets
= match buckets
.peek() {
496 empty
.put(hash
, k
, v
);
499 Full(b
) => b
.into_bucket()
503 panic
!("Internal HashMap error: Out of space.");
507 impl<K
: Hash
+ Eq
, V
> HashMap
<K
, V
, RandomState
> {
508 /// Creates an empty HashMap.
513 /// use std::collections::HashMap;
514 /// let mut map: HashMap<&str, isize> = HashMap::new();
517 #[stable(feature = "rust1", since = "1.0.0")]
518 pub fn new() -> HashMap
<K
, V
, RandomState
> {
522 /// Creates an empty hash map with the given initial capacity.
527 /// use std::collections::HashMap;
528 /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
531 #[stable(feature = "rust1", since = "1.0.0")]
532 pub fn with_capacity(capacity
: usize) -> HashMap
<K
, V
, RandomState
> {
533 HashMap
::with_capacity_and_hash_state(capacity
, Default
::default())
537 impl<K
, V
, S
> HashMap
<K
, V
, S
>
538 where K
: Eq
+ Hash
, S
: HashState
540 /// Creates an empty hashmap which will use the given hasher to hash keys.
542 /// The creates map has the default initial capacity.
547 /// # #![feature(std_misc)]
548 /// use std::collections::HashMap;
549 /// use std::collections::hash_map::RandomState;
551 /// let s = RandomState::new();
552 /// let mut map = HashMap::with_hash_state(s);
553 /// map.insert(1, 2);
556 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
557 pub fn with_hash_state(hash_state
: S
) -> HashMap
<K
, V
, S
> {
559 hash_state
: hash_state
,
560 resize_policy
: DefaultResizePolicy
::new(),
561 table
: RawTable
::new(0),
565 /// Creates an empty HashMap with space for at least `capacity`
566 /// elements, using `hasher` to hash the keys.
568 /// Warning: `hasher` is normally randomly generated, and
569 /// is designed to allow HashMaps to be resistant to attacks that
570 /// cause many collisions and very poor performance. Setting it
571 /// manually using this function can expose a DoS attack vector.
576 /// # #![feature(std_misc)]
577 /// use std::collections::HashMap;
578 /// use std::collections::hash_map::RandomState;
580 /// let s = RandomState::new();
581 /// let mut map = HashMap::with_capacity_and_hash_state(10, s);
582 /// map.insert(1, 2);
585 #[unstable(feature = "std_misc", reason = "hasher stuff is unclear")]
586 pub fn with_capacity_and_hash_state(capacity
: usize, hash_state
: S
)
587 -> HashMap
<K
, V
, S
> {
588 let resize_policy
= DefaultResizePolicy
::new();
589 let min_cap
= max(INITIAL_CAPACITY
, resize_policy
.min_capacity(capacity
));
590 let internal_cap
= min_cap
.checked_next_power_of_two().expect("capacity overflow");
591 assert
!(internal_cap
>= capacity
, "capacity overflow");
593 hash_state
: hash_state
,
594 resize_policy
: resize_policy
,
595 table
: RawTable
::new(internal_cap
),
599 /// Returns the number of elements the map can hold without reallocating.
604 /// use std::collections::HashMap;
605 /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
606 /// assert!(map.capacity() >= 100);
609 #[stable(feature = "rust1", since = "1.0.0")]
610 pub fn capacity(&self) -> usize {
611 self.resize_policy
.usable_capacity(self.table
.capacity())
614 /// Reserves capacity for at least `additional` more elements to be inserted
615 /// in the `HashMap`. The collection may reserve more space to avoid
616 /// frequent reallocations.
620 /// Panics if the new allocation size overflows `usize`.
625 /// use std::collections::HashMap;
626 /// let mut map: HashMap<&str, isize> = HashMap::new();
629 #[stable(feature = "rust1", since = "1.0.0")]
630 pub fn reserve(&mut self, additional
: usize) {
631 let new_size
= self.len().checked_add(additional
).expect("capacity overflow");
632 let min_cap
= self.resize_policy
.min_capacity(new_size
);
634 // An invalid value shouldn't make us run out of space. This includes
635 // an overflow check.
636 assert
!(new_size
<= min_cap
);
638 if self.table
.capacity() < min_cap
{
639 let new_capacity
= max(min_cap
.next_power_of_two(), INITIAL_CAPACITY
);
640 self.resize(new_capacity
);
644 /// Resizes the internal vectors to a new capacity. It's your responsibility to:
645 /// 1) Make sure the new capacity is enough for all the elements, accounting
646 /// for the load factor.
647 /// 2) Ensure new_capacity is a power of two or zero.
648 fn resize(&mut self, new_capacity
: usize) {
649 assert
!(self.table
.size() <= new_capacity
);
650 assert
!(new_capacity
.is_power_of_two() || new_capacity
== 0);
652 let mut old_table
= replace(&mut self.table
, RawTable
::new(new_capacity
));
653 let old_size
= old_table
.size();
655 if old_table
.capacity() == 0 || old_table
.size() == 0 {
660 // Specialization of the other branch.
661 let mut bucket
= Bucket
::first(&mut old_table
);
663 // "So a few of the first shall be last: for many be called,
666 // We'll most likely encounter a few buckets at the beginning that
667 // have their initial buckets near the end of the table. They were
668 // placed at the beginning as the probe wrapped around the table
669 // during insertion. We must skip forward to a bucket that won't
670 // get reinserted too early and won't unfairly steal others spot.
671 // This eliminates the need for robin hood.
673 bucket
= match bucket
.peek() {
675 if full
.distance() == 0 {
676 // This bucket occupies its ideal spot.
677 // It indicates the start of another "cluster".
678 bucket
= full
.into_bucket();
681 // Leaving this bucket in the last cluster for later.
685 // Encountered a hole between clusters.
692 // This is how the buckets might be laid out in memory:
693 // ($ marks an initialized bucket)
695 // |$$$_$$$$$$_$$$$$|
697 // But we've skipped the entire initial cluster of buckets
698 // and will continue iteration in this order:
701 // ^ wrap around once end is reached
704 // ^ exit once table.size == 0
706 bucket
= match bucket
.peek() {
708 let h
= bucket
.hash();
709 let (b
, k
, v
) = bucket
.take();
710 self.insert_hashed_ordered(h
, k
, v
);
712 let t
= b
.table(); // FIXME "lifetime too short".
713 if t
.size() == 0 { break }
717 Empty(b
) => b
.into_bucket()
722 assert_eq
!(self.table
.size(), old_size
);
725 /// Shrinks the capacity of the map as much as possible. It will drop
726 /// down as much as possible while maintaining the internal rules
727 /// and possibly leaving some space in accordance with the resize policy.
732 /// use std::collections::HashMap;
734 /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
735 /// map.insert(1, 2);
736 /// map.insert(3, 4);
737 /// assert!(map.capacity() >= 100);
738 /// map.shrink_to_fit();
739 /// assert!(map.capacity() >= 2);
741 #[stable(feature = "rust1", since = "1.0.0")]
742 pub fn shrink_to_fit(&mut self) {
743 let min_capacity
= self.resize_policy
.min_capacity(self.len());
744 let min_capacity
= max(min_capacity
.next_power_of_two(), INITIAL_CAPACITY
);
746 // An invalid value shouldn't make us run out of space.
747 debug_assert
!(self.len() <= min_capacity
);
749 if self.table
.capacity() != min_capacity
{
750 let old_table
= replace(&mut self.table
, RawTable
::new(min_capacity
));
751 let old_size
= old_table
.size();
753 // Shrink the table. Naive algorithm for resizing:
754 for (h
, k
, v
) in old_table
.into_iter() {
755 self.insert_hashed_nocheck(h
, k
, v
);
758 debug_assert_eq
!(self.table
.size(), old_size
);
762 /// Insert a pre-hashed key-value pair, without first checking
763 /// that there's enough room in the buckets. Returns a reference to the
764 /// newly insert value.
766 /// If the key already exists, the hashtable will be returned untouched
767 /// and a reference to the existing element will be returned.
768 fn insert_hashed_nocheck(&mut self, hash
: SafeHash
, k
: K
, v
: V
) -> &mut V
{
769 self.insert_or_replace_with(hash
, k
, v
, |_
, _
, _
| ())
772 fn insert_or_replace_with
<'a
, F
>(&'a
mut self,
776 mut found_existing
: F
)
778 F
: FnMut(&mut K
, &mut V
, V
),
780 // Worst case, we'll find one empty bucket among `size + 1` buckets.
781 let size
= self.table
.size();
782 let mut probe
= Bucket
::new(&mut self.table
, hash
);
783 let ib
= probe
.index();
786 let mut bucket
= match probe
.peek() {
789 return bucket
.put(hash
, k
, v
).into_mut_refs().1;
791 Full(bucket
) => bucket
795 if bucket
.hash() == hash
{
797 if k
== *bucket
.read_mut().0 {
798 let (bucket_k
, bucket_v
) = bucket
.into_mut_refs();
799 debug_assert
!(k
== *bucket_k
);
800 // Key already exists. Get its reference.
801 found_existing(bucket_k
, bucket_v
, v
);
806 let robin_ib
= bucket
.index() as isize - bucket
.distance() as isize;
808 if (ib
as isize) < robin_ib
{
809 // Found a luckier bucket than me. Better steal his spot.
810 return robin_hood(bucket
, robin_ib
as usize, hash
, k
, v
);
813 probe
= bucket
.next();
814 assert
!(probe
.index() != ib
+ size
+ 1);
818 /// An iterator visiting all keys in arbitrary order.
819 /// Iterator element type is `&'a K`.
824 /// use std::collections::HashMap;
826 /// let mut map = HashMap::new();
827 /// map.insert("a", 1);
828 /// map.insert("b", 2);
829 /// map.insert("c", 3);
831 /// for key in map.keys() {
832 /// println!("{}", key);
835 #[stable(feature = "rust1", since = "1.0.0")]
836 pub fn keys
<'a
>(&'a
self) -> Keys
<'a
, K
, V
> {
837 fn first
<A
, B
>((a
, _
): (A
, B
)) -> A { a }
838 let first
: fn((&'a K
,&'a V
)) -> &'a K
= first
; // coerce to fn ptr
840 Keys { inner: self.iter().map(first) }
843 /// An iterator visiting all values in arbitrary order.
844 /// Iterator element type is `&'a V`.
849 /// use std::collections::HashMap;
851 /// let mut map = HashMap::new();
852 /// map.insert("a", 1);
853 /// map.insert("b", 2);
854 /// map.insert("c", 3);
856 /// for val in map.values() {
857 /// println!("{}", val);
860 #[stable(feature = "rust1", since = "1.0.0")]
861 pub fn values
<'a
>(&'a
self) -> Values
<'a
, K
, V
> {
862 fn second
<A
, B
>((_
, b
): (A
, B
)) -> B { b }
863 let second
: fn((&'a K
,&'a V
)) -> &'a V
= second
; // coerce to fn ptr
865 Values { inner: self.iter().map(second) }
868 /// An iterator visiting all key-value pairs in arbitrary order.
869 /// Iterator element type is `(&'a K, &'a V)`.
874 /// use std::collections::HashMap;
876 /// let mut map = HashMap::new();
877 /// map.insert("a", 1);
878 /// map.insert("b", 2);
879 /// map.insert("c", 3);
881 /// for (key, val) in map.iter() {
882 /// println!("key: {} val: {}", key, val);
885 #[stable(feature = "rust1", since = "1.0.0")]
886 pub fn iter(&self) -> Iter
<K
, V
> {
887 Iter { inner: self.table.iter() }
890 /// An iterator visiting all key-value pairs in arbitrary order,
891 /// with mutable references to the values.
892 /// Iterator element type is `(&'a K, &'a mut V)`.
897 /// use std::collections::HashMap;
899 /// let mut map = HashMap::new();
900 /// map.insert("a", 1);
901 /// map.insert("b", 2);
902 /// map.insert("c", 3);
904 /// // Update all values
905 /// for (_, val) in map.iter_mut() {
909 /// for (key, val) in map.iter() {
910 /// println!("key: {} val: {}", key, val);
913 #[stable(feature = "rust1", since = "1.0.0")]
914 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
915 IterMut { inner: self.table.iter_mut() }
918 /// Gets the given key's corresponding entry in the map for in-place manipulation.
923 /// use std::collections::HashMap;
925 /// let mut letters = HashMap::new();
927 /// for ch in "a short treatise on fungi".chars() {
928 /// let counter = letters.entry(ch).or_insert(0);
932 /// assert_eq!(letters[&'s'], 2);
933 /// assert_eq!(letters[&'t'], 3);
934 /// assert_eq!(letters[&'u'], 1);
935 /// assert_eq!(letters.get(&'y'), None);
937 #[stable(feature = "rust1", since = "1.0.0")]
938 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
942 let hash
= self.make_hash(&key
);
943 search_entry_hashed(&mut self.table
, hash
, key
)
946 /// Returns the number of elements in the map.
951 /// use std::collections::HashMap;
953 /// let mut a = HashMap::new();
954 /// assert_eq!(a.len(), 0);
955 /// a.insert(1, "a");
956 /// assert_eq!(a.len(), 1);
958 #[stable(feature = "rust1", since = "1.0.0")]
959 pub fn len(&self) -> usize { self.table.size() }
961 /// Returns true if the map contains no elements.
966 /// use std::collections::HashMap;
968 /// let mut a = HashMap::new();
969 /// assert!(a.is_empty());
970 /// a.insert(1, "a");
971 /// assert!(!a.is_empty());
974 #[stable(feature = "rust1", since = "1.0.0")]
975 pub fn is_empty(&self) -> bool { self.len() == 0 }
977 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
978 /// allocated memory for reuse.
983 /// # #![feature(std_misc)]
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 /// if let Some(x) = map.get_mut(&1) {
1090 /// assert_eq!(map[&1], "b");
1092 #[stable(feature = "rust1", since = "1.0.0")]
1093 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
1094 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1096 self.search_mut(k
).map(|bucket
| bucket
.into_mut_refs().1)
1099 /// Inserts a key-value pair into the map. If the key already had a value
1100 /// present in the map, that value is returned. Otherwise, `None` is returned.
1105 /// use std::collections::HashMap;
1107 /// let mut map = HashMap::new();
1108 /// assert_eq!(map.insert(37, "a"), None);
1109 /// assert_eq!(map.is_empty(), false);
1111 /// map.insert(37, "b");
1112 /// assert_eq!(map.insert(37, "c"), Some("b"));
1113 /// assert_eq!(map[&37], "c");
1115 #[stable(feature = "rust1", since = "1.0.0")]
1116 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
1117 let hash
= self.make_hash(&k
);
1120 let mut retval
= None
;
1121 self.insert_or_replace_with(hash
, k
, v
, |_
, val_ref
, val
| {
1122 retval
= Some(replace(val_ref
, val
));
1127 /// Removes a key from the map, returning the value at the key if the key
1128 /// was previously in the map.
1130 /// The key may be any borrowed form of the map's key type, but
1131 /// `Hash` and `Eq` on the borrowed form *must* match those for
1137 /// use std::collections::HashMap;
1139 /// let mut map = HashMap::new();
1140 /// map.insert(1, "a");
1141 /// assert_eq!(map.remove(&1), Some("a"));
1142 /// assert_eq!(map.remove(&1), None);
1144 #[stable(feature = "rust1", since = "1.0.0")]
1145 pub fn remove
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<V
>
1146 where K
: Borrow
<Q
>, Q
: Hash
+ Eq
1148 if self.table
.size() == 0 {
1152 self.search_mut(k
).map(|bucket
| pop_internal(bucket
).1)
1156 fn search_entry_hashed
<'a
, K
: Eq
, V
>(table
: &'a
mut RawTable
<K
,V
>, hash
: SafeHash
, k
: K
)
1159 // Worst case, we'll find one empty bucket among `size + 1` buckets.
1160 let size
= table
.size();
1161 let mut probe
= Bucket
::new(table
, hash
);
1162 let ib
= probe
.index();
1165 let bucket
= match probe
.peek() {
1168 return Vacant(VacantEntry
{
1171 elem
: NoElem(bucket
),
1174 Full(bucket
) => bucket
1178 if bucket
.hash() == hash
{
1180 if k
== *bucket
.read().0 {
1181 return Occupied(OccupiedEntry
{
1187 let robin_ib
= bucket
.index() as isize - bucket
.distance() as isize;
1189 if (ib
as isize) < robin_ib
{
1190 // Found a luckier bucket than me. Better steal his spot.
1191 return Vacant(VacantEntry
{
1194 elem
: NeqElem(bucket
, robin_ib
as usize),
1198 probe
= bucket
.next();
1199 assert
!(probe
.index() != ib
+ size
+ 1);
1203 impl<K
, V
, S
> PartialEq
for HashMap
<K
, V
, S
>
1204 where K
: Eq
+ Hash
, V
: PartialEq
, S
: HashState
1206 fn eq(&self, other
: &HashMap
<K
, V
, S
>) -> bool
{
1207 if self.len() != other
.len() { return false; }
1209 self.iter().all(|(key
, value
)|
1210 other
.get(key
).map_or(false, |v
| *value
== *v
)
1215 #[stable(feature = "rust1", since = "1.0.0")]
1216 impl<K
, V
, S
> Eq
for HashMap
<K
, V
, S
>
1217 where K
: Eq
+ Hash
, V
: Eq
, S
: HashState
1220 #[stable(feature = "rust1", since = "1.0.0")]
1221 impl<K
, V
, S
> Debug
for HashMap
<K
, V
, S
>
1222 where K
: Eq
+ Hash
+ Debug
, V
: Debug
, S
: HashState
1224 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1225 self.iter().fold(f
.debug_map(), |b
, (k
, v
)| b
.entry(k
, v
)).finish()
1229 #[stable(feature = "rust1", since = "1.0.0")]
1230 impl<K
, V
, S
> Default
for HashMap
<K
, V
, S
>
1232 S
: HashState
+ Default
,
1234 fn default() -> HashMap
<K
, V
, S
> {
1235 HashMap
::with_hash_state(Default
::default())
1239 #[stable(feature = "rust1", since = "1.0.0")]
1240 impl<'a
, K
, Q
: ?Sized
, V
, S
> Index
<&'a Q
> for HashMap
<K
, V
, S
>
1241 where K
: Eq
+ Hash
+ Borrow
<Q
>,
1248 fn index(&self, index
: &Q
) -> &V
{
1249 self.get(index
).expect("no entry found for key")
1253 /// HashMap iterator.
1254 #[stable(feature = "rust1", since = "1.0.0")]
1255 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
1256 inner
: table
::Iter
<'a
, K
, V
>
1259 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1260 impl<'a
, K
, V
> Clone
for Iter
<'a
, K
, V
> {
1261 fn clone(&self) -> Iter
<'a
, K
, V
> {
1263 inner
: self.inner
.clone()
1268 /// HashMap mutable values iterator.
1269 #[stable(feature = "rust1", since = "1.0.0")]
1270 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
1271 inner
: table
::IterMut
<'a
, K
, V
>
1274 /// HashMap move iterator.
1275 #[stable(feature = "rust1", since = "1.0.0")]
1276 pub struct IntoIter
<K
, V
> {
1277 inner
: iter
::Map
<table
::IntoIter
<K
, V
>, fn((SafeHash
, K
, V
)) -> (K
, V
)>
1280 /// HashMap keys iterator.
1281 #[stable(feature = "rust1", since = "1.0.0")]
1282 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
1283 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a K
>
1286 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1287 impl<'a
, K
, V
> Clone
for Keys
<'a
, K
, V
> {
1288 fn clone(&self) -> Keys
<'a
, K
, V
> {
1290 inner
: self.inner
.clone()
1295 /// HashMap values iterator.
1296 #[stable(feature = "rust1", since = "1.0.0")]
1297 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
1298 inner
: Map
<Iter
<'a
, K
, V
>, fn((&'a K
, &'a V
)) -> &'a V
>
1301 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1302 impl<'a
, K
, V
> Clone
for Values
<'a
, K
, V
> {
1303 fn clone(&self) -> Values
<'a
, K
, V
> {
1305 inner
: self.inner
.clone()
1310 /// HashMap drain iterator.
1311 #[unstable(feature = "std_misc",
1312 reason
= "matches collection reform specification, waiting for dust to settle")]
1313 pub struct Drain
<'a
, K
: 'a
, V
: 'a
> {
1314 inner
: iter
::Map
<table
::Drain
<'a
, K
, V
>, fn((SafeHash
, K
, V
)) -> (K
, V
)>
1317 /// A view into a single occupied location in a HashMap.
1318 #[stable(feature = "rust1", since = "1.0.0")]
1319 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
1320 elem
: FullBucket
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1323 /// A view into a single empty location in a HashMap.
1324 #[stable(feature = "rust1", since = "1.0.0")]
1325 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
1328 elem
: VacantEntryState
<K
, V
, &'a
mut RawTable
<K
, V
>>,
1331 /// A view into a single location in a map, which may be vacant or occupied.
1332 #[stable(feature = "rust1", since = "1.0.0")]
1333 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
1334 /// An occupied Entry.
1335 #[stable(feature = "rust1", since = "1.0.0")]
1336 Occupied(OccupiedEntry
<'a
, K
, V
>),
1339 #[stable(feature = "rust1", since = "1.0.0")]
1340 Vacant(VacantEntry
<'a
, K
, V
>),
1343 /// Possible states of a VacantEntry.
1344 enum VacantEntryState
<K
, V
, M
> {
1345 /// The index is occupied, but the key to insert has precedence,
1346 /// and will kick the current one out on insertion.
1347 NeqElem(FullBucket
<K
, V
, M
>, usize),
1348 /// The index is genuinely vacant.
1349 NoElem(EmptyBucket
<K
, V
, M
>),
1352 #[stable(feature = "rust1", since = "1.0.0")]
1353 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
>
1354 where K
: Eq
+ Hash
, S
: HashState
1356 type Item
= (&'a K
, &'a V
);
1357 type IntoIter
= Iter
<'a
, K
, V
>;
1359 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1364 #[stable(feature = "rust1", since = "1.0.0")]
1365 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
>
1366 where K
: Eq
+ Hash
, S
: HashState
1368 type Item
= (&'a K
, &'a
mut V
);
1369 type IntoIter
= IterMut
<'a
, K
, V
>;
1371 fn into_iter(mut self) -> IterMut
<'a
, K
, V
> {
1376 #[stable(feature = "rust1", since = "1.0.0")]
1377 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
>
1378 where K
: Eq
+ Hash
, S
: HashState
1381 type IntoIter
= IntoIter
<K
, V
>;
1383 /// Creates a consuming iterator, that is, one that moves each key-value
1384 /// pair out of the map in arbitrary order. The map cannot be used after
1390 /// use std::collections::HashMap;
1392 /// let mut map = HashMap::new();
1393 /// map.insert("a", 1);
1394 /// map.insert("b", 2);
1395 /// map.insert("c", 3);
1397 /// // Not possible with .iter()
1398 /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1400 fn into_iter(self) -> IntoIter
<K
, V
> {
1401 fn last_two
<A
, B
, C
>((_
, b
, c
): (A
, B
, C
)) -> (B
, C
) { (b, c) }
1402 let last_two
: fn((SafeHash
, K
, V
)) -> (K
, V
) = last_two
;
1405 inner
: self.table
.into_iter().map(last_two
)
1410 #[stable(feature = "rust1", since = "1.0.0")]
1411 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
1412 type Item
= (&'a K
, &'a V
);
1414 #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1415 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1417 #[stable(feature = "rust1", since = "1.0.0")]
1418 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {
1419 #[inline] fn len(&self) -> usize { self.inner.len() }
1422 #[stable(feature = "rust1", since = "1.0.0")]
1423 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
1424 type Item
= (&'a K
, &'a
mut V
);
1426 #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1427 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1429 #[stable(feature = "rust1", since = "1.0.0")]
1430 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {
1431 #[inline] fn len(&self) -> usize { self.inner.len() }
1434 #[stable(feature = "rust1", since = "1.0.0")]
1435 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1438 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1439 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1441 #[stable(feature = "rust1", since = "1.0.0")]
1442 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1443 #[inline] fn len(&self) -> usize { self.inner.len() }
1446 #[stable(feature = "rust1", since = "1.0.0")]
1447 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1450 #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1451 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1453 #[stable(feature = "rust1", since = "1.0.0")]
1454 impl<'a
, K
, V
> ExactSizeIterator
for Keys
<'a
, K
, V
> {
1455 #[inline] fn len(&self) -> usize { self.inner.len() }
1458 #[stable(feature = "rust1", since = "1.0.0")]
1459 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1462 #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1463 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1465 #[stable(feature = "rust1", since = "1.0.0")]
1466 impl<'a
, K
, V
> ExactSizeIterator
for Values
<'a
, K
, V
> {
1467 #[inline] fn len(&self) -> usize { self.inner.len() }
1470 #[stable(feature = "rust1", since = "1.0.0")]
1471 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
1474 #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1475 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1477 #[stable(feature = "rust1", since = "1.0.0")]
1478 impl<'a
, K
, V
> ExactSizeIterator
for Drain
<'a
, K
, V
> {
1479 #[inline] fn len(&self) -> usize { self.inner.len() }
1482 impl<'a
, K
, V
> Entry
<'a
, K
, V
> {
1483 #[unstable(feature = "std_misc",
1484 reason
= "will soon be replaced by or_insert")]
1485 #[deprecated(since = "1.0",
1486 reason
= "replaced with more ergonomic `or_insert` and `or_insert_with`")]
1487 /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant
1488 pub fn get(self) -> Result
<&'a
mut V
, VacantEntry
<'a
, K
, V
>> {
1490 Occupied(entry
) => Ok(entry
.into_mut()),
1491 Vacant(entry
) => Err(entry
),
1495 #[stable(feature = "rust1", since = "1.0.0")]
1496 /// Ensures a value is in the entry by inserting the default if empty, and returns
1497 /// a mutable reference to the value in the entry.
1498 pub fn or_insert(self, default: V
) -> &'a
mut V
{
1500 Occupied(entry
) => entry
.into_mut(),
1501 Vacant(entry
) => entry
.insert(default),
1505 #[stable(feature = "rust1", since = "1.0.0")]
1506 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1507 /// and returns a mutable reference to the value in the entry.
1508 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
1510 Occupied(entry
) => entry
.into_mut(),
1511 Vacant(entry
) => entry
.insert(default()),
1516 impl<'a
, K
, V
> OccupiedEntry
<'a
, K
, V
> {
1517 /// Gets a reference to the value in the entry.
1518 #[stable(feature = "rust1", since = "1.0.0")]
1519 pub fn get(&self) -> &V
{
1523 /// Gets a mutable reference to the value in the entry.
1524 #[stable(feature = "rust1", since = "1.0.0")]
1525 pub fn get_mut(&mut self) -> &mut V
{
1526 self.elem
.read_mut().1
1529 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1530 /// with a lifetime bound to the map itself
1531 #[stable(feature = "rust1", since = "1.0.0")]
1532 pub fn into_mut(self) -> &'a
mut V
{
1533 self.elem
.into_mut_refs().1
1536 /// Sets the value of the entry, and returns the entry's old value
1537 #[stable(feature = "rust1", since = "1.0.0")]
1538 pub fn insert(&mut self, mut value
: V
) -> V
{
1539 let old_value
= self.get_mut();
1540 mem
::swap(&mut value
, old_value
);
1544 /// Takes the value out of the entry, and returns it
1545 #[stable(feature = "rust1", since = "1.0.0")]
1546 pub fn remove(self) -> V
{
1547 pop_internal(self.elem
).1
1551 impl<'a
, K
: 'a
, V
: 'a
> VacantEntry
<'a
, K
, V
> {
1552 /// Sets the value of the entry with the VacantEntry's key,
1553 /// and returns a mutable reference to it
1554 #[stable(feature = "rust1", since = "1.0.0")]
1555 pub fn insert(self, value
: V
) -> &'a
mut V
{
1557 NeqElem(bucket
, ib
) => {
1558 robin_hood(bucket
, ib
, self.hash
, self.key
, value
)
1561 bucket
.put(self.hash
, self.key
, value
).into_mut_refs().1
1567 #[stable(feature = "rust1", since = "1.0.0")]
1568 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
1569 where K
: Eq
+ Hash
, S
: HashState
+ Default
1571 fn from_iter
<T
: IntoIterator
<Item
=(K
, V
)>>(iterable
: T
) -> HashMap
<K
, V
, S
> {
1572 let iter
= iterable
.into_iter();
1573 let lower
= iter
.size_hint().0;
1574 let mut map
= HashMap
::with_capacity_and_hash_state(lower
,
1575 Default
::default());
1581 #[stable(feature = "rust1", since = "1.0.0")]
1582 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
1583 where K
: Eq
+ Hash
, S
: HashState
1585 fn extend
<T
: IntoIterator
<Item
=(K
, V
)>>(&mut self, iter
: T
) {
1586 for (k
, v
) in iter
{
1593 /// `RandomState` is the default state for `HashMap` types.
1595 /// A particular instance `RandomState` will create the same instances of
1596 /// `Hasher`, but the hashers created by two different `RandomState`
1597 /// instances are unlikely to produce the same result for the same values.
1599 #[unstable(feature = "std_misc",
1600 reason
= "hashing an hash maps may be altered")]
1601 pub struct RandomState
{
1606 #[unstable(feature = "std_misc",
1607 reason
= "hashing an hash maps may be altered")]
1609 /// Constructs a new `RandomState` that is initialized with random keys.
1611 #[allow(deprecated)]
1612 pub fn new() -> RandomState
{
1613 let mut r
= rand
::thread_rng();
1614 RandomState { k0: r.gen(), k1: r.gen() }
1618 #[unstable(feature = "std_misc",
1619 reason
= "hashing an hash maps may be altered")]
1620 impl HashState
for RandomState
{
1621 type Hasher
= SipHasher
;
1623 fn hasher(&self) -> SipHasher
{
1624 SipHasher
::new_with_keys(self.k0
, self.k1
)
1628 #[stable(feature = "rust1", since = "1.0.0")]
1629 impl Default
for RandomState
{
1631 fn default() -> RandomState
{
1641 use super::Entry
::{Occupied, Vacant}
;
1642 use iter
::{range_inclusive, repeat}
;
1644 use rand
::{thread_rng, Rng}
;
1647 fn test_create_capacity_zero() {
1648 let mut m
= HashMap
::with_capacity(0);
1650 assert
!(m
.insert(1, 1).is_none());
1652 assert
!(m
.contains_key(&1));
1653 assert
!(!m
.contains_key(&0));
1658 let mut m
= HashMap
::new();
1659 assert_eq
!(m
.len(), 0);
1660 assert
!(m
.insert(1, 2).is_none());
1661 assert_eq
!(m
.len(), 1);
1662 assert
!(m
.insert(2, 4).is_none());
1663 assert_eq
!(m
.len(), 2);
1664 assert_eq
!(*m
.get(&1).unwrap(), 2);
1665 assert_eq
!(*m
.get(&2).unwrap(), 4);
1668 thread_local
! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1670 #[derive(Hash, PartialEq, Eq)]
1676 fn new(k
: usize) -> Dropable
{
1677 DROP_VECTOR
.with(|slot
| {
1678 slot
.borrow_mut()[k
] += 1;
1685 impl Drop
for Dropable
{
1686 fn drop(&mut self) {
1687 DROP_VECTOR
.with(|slot
| {
1688 slot
.borrow_mut()[self.k
] -= 1;
1693 impl Clone
for Dropable
{
1694 fn clone(&self) -> Dropable
{
1695 Dropable
::new(self.k
)
1701 DROP_VECTOR
.with(|slot
| {
1702 *slot
.borrow_mut() = repeat(0).take(200).collect();
1706 let mut m
= HashMap
::new();
1708 DROP_VECTOR
.with(|v
| {
1710 assert_eq
!(v
.borrow()[i
], 0);
1715 let d1
= Dropable
::new(i
);
1716 let d2
= Dropable
::new(i
+100);
1720 DROP_VECTOR
.with(|v
| {
1722 assert_eq
!(v
.borrow()[i
], 1);
1727 let k
= Dropable
::new(i
);
1728 let v
= m
.remove(&k
);
1730 assert
!(v
.is_some());
1732 DROP_VECTOR
.with(|v
| {
1733 assert_eq
!(v
.borrow()[i
], 1);
1734 assert_eq
!(v
.borrow()[i
+100], 1);
1738 DROP_VECTOR
.with(|v
| {
1740 assert_eq
!(v
.borrow()[i
], 0);
1741 assert_eq
!(v
.borrow()[i
+100], 0);
1745 assert_eq
!(v
.borrow()[i
], 1);
1746 assert_eq
!(v
.borrow()[i
+100], 1);
1751 DROP_VECTOR
.with(|v
| {
1753 assert_eq
!(v
.borrow()[i
], 0);
1759 fn test_move_iter_drops() {
1760 DROP_VECTOR
.with(|v
| {
1761 *v
.borrow_mut() = repeat(0).take(200).collect();
1765 let mut hm
= HashMap
::new();
1767 DROP_VECTOR
.with(|v
| {
1769 assert_eq
!(v
.borrow()[i
], 0);
1774 let d1
= Dropable
::new(i
);
1775 let d2
= Dropable
::new(i
+100);
1779 DROP_VECTOR
.with(|v
| {
1781 assert_eq
!(v
.borrow()[i
], 1);
1788 // By the way, ensure that cloning doesn't screw up the dropping.
1792 let mut half
= hm
.into_iter().take(50);
1794 DROP_VECTOR
.with(|v
| {
1796 assert_eq
!(v
.borrow()[i
], 1);
1800 for _
in half
.by_ref() {}
1802 DROP_VECTOR
.with(|v
| {
1803 let nk
= (0..100).filter(|&i
| {
1807 let nv
= (0..100).filter(|&i
| {
1808 v
.borrow()[i
+100] == 1
1816 DROP_VECTOR
.with(|v
| {
1818 assert_eq
!(v
.borrow()[i
], 0);
1824 fn test_empty_pop() {
1825 let mut m
: HashMap
<isize, bool
> = HashMap
::new();
1826 assert_eq
!(m
.remove(&0), None
);
1830 fn test_lots_of_insertions() {
1831 let mut m
= HashMap
::new();
1833 // Try this a few times to make sure we never screw up the hashmap's
1836 assert
!(m
.is_empty());
1838 for i
in range_inclusive(1, 1000) {
1839 assert
!(m
.insert(i
, i
).is_none());
1841 for j
in range_inclusive(1, i
) {
1843 assert_eq
!(r
, Some(&j
));
1846 for j
in range_inclusive(i
+1, 1000) {
1848 assert_eq
!(r
, None
);
1852 for i
in range_inclusive(1001, 2000) {
1853 assert
!(!m
.contains_key(&i
));
1857 for i
in range_inclusive(1, 1000) {
1858 assert
!(m
.remove(&i
).is_some());
1860 for j
in range_inclusive(1, i
) {
1861 assert
!(!m
.contains_key(&j
));
1864 for j
in range_inclusive(i
+1, 1000) {
1865 assert
!(m
.contains_key(&j
));
1869 for i
in range_inclusive(1, 1000) {
1870 assert
!(!m
.contains_key(&i
));
1873 for i
in range_inclusive(1, 1000) {
1874 assert
!(m
.insert(i
, i
).is_none());
1878 for i
in (1..1001).rev() {
1879 assert
!(m
.remove(&i
).is_some());
1881 for j
in range_inclusive(i
, 1000) {
1882 assert
!(!m
.contains_key(&j
));
1885 for j
in range_inclusive(1, i
-1) {
1886 assert
!(m
.contains_key(&j
));
1893 fn test_find_mut() {
1894 let mut m
= HashMap
::new();
1895 assert
!(m
.insert(1, 12).is_none());
1896 assert
!(m
.insert(2, 8).is_none());
1897 assert
!(m
.insert(5, 14).is_none());
1899 match m
.get_mut(&5) {
1900 None
=> panic
!(), Some(x
) => *x
= new
1902 assert_eq
!(m
.get(&5), Some(&new
));
1906 fn test_insert_overwrite() {
1907 let mut m
= HashMap
::new();
1908 assert
!(m
.insert(1, 2).is_none());
1909 assert_eq
!(*m
.get(&1).unwrap(), 2);
1910 assert
!(!m
.insert(1, 3).is_none());
1911 assert_eq
!(*m
.get(&1).unwrap(), 3);
1915 fn test_insert_conflicts() {
1916 let mut m
= HashMap
::with_capacity(4);
1917 assert
!(m
.insert(1, 2).is_none());
1918 assert
!(m
.insert(5, 3).is_none());
1919 assert
!(m
.insert(9, 4).is_none());
1920 assert_eq
!(*m
.get(&9).unwrap(), 4);
1921 assert_eq
!(*m
.get(&5).unwrap(), 3);
1922 assert_eq
!(*m
.get(&1).unwrap(), 2);
1926 fn test_conflict_remove() {
1927 let mut m
= HashMap
::with_capacity(4);
1928 assert
!(m
.insert(1, 2).is_none());
1929 assert_eq
!(*m
.get(&1).unwrap(), 2);
1930 assert
!(m
.insert(5, 3).is_none());
1931 assert_eq
!(*m
.get(&1).unwrap(), 2);
1932 assert_eq
!(*m
.get(&5).unwrap(), 3);
1933 assert
!(m
.insert(9, 4).is_none());
1934 assert_eq
!(*m
.get(&1).unwrap(), 2);
1935 assert_eq
!(*m
.get(&5).unwrap(), 3);
1936 assert_eq
!(*m
.get(&9).unwrap(), 4);
1937 assert
!(m
.remove(&1).is_some());
1938 assert_eq
!(*m
.get(&9).unwrap(), 4);
1939 assert_eq
!(*m
.get(&5).unwrap(), 3);
1943 fn test_is_empty() {
1944 let mut m
= HashMap
::with_capacity(4);
1945 assert
!(m
.insert(1, 2).is_none());
1946 assert
!(!m
.is_empty());
1947 assert
!(m
.remove(&1).is_some());
1948 assert
!(m
.is_empty());
1953 let mut m
= HashMap
::new();
1955 assert_eq
!(m
.remove(&1), Some(2));
1956 assert_eq
!(m
.remove(&1), None
);
1961 let mut m
= HashMap
::with_capacity(4);
1963 assert
!(m
.insert(i
, i
*2).is_none());
1965 assert_eq
!(m
.len(), 32);
1967 let mut observed
: u32 = 0;
1970 assert_eq
!(*v
, *k
* 2);
1971 observed
|= 1 << *k
;
1973 assert_eq
!(observed
, 0xFFFF_FFFF);
1978 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
1979 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
1980 let keys
: Vec
<_
> = map
.keys().cloned().collect();
1981 assert_eq
!(keys
.len(), 3);
1982 assert
!(keys
.contains(&1));
1983 assert
!(keys
.contains(&2));
1984 assert
!(keys
.contains(&3));
1989 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
1990 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
1991 let values
: Vec
<_
> = map
.values().cloned().collect();
1992 assert_eq
!(values
.len(), 3);
1993 assert
!(values
.contains(&'a'
));
1994 assert
!(values
.contains(&'b'
));
1995 assert
!(values
.contains(&'c'
));
2000 let mut m
= HashMap
::new();
2001 assert
!(m
.get(&1).is_none());
2005 Some(v
) => assert_eq
!(*v
, 2)
2011 let mut m1
= HashMap
::new();
2016 let mut m2
= HashMap
::new();
2029 let mut map
= HashMap
::new();
2030 let empty
: HashMap
<i32, i32> = HashMap
::new();
2035 let map_str
= format
!("{:?}", map
);
2037 assert
!(map_str
== "{1: 2, 3: 4}" ||
2038 map_str
== "{3: 4, 1: 2}");
2039 assert_eq
!(format
!("{:?}", empty
), "{}");
2044 let mut m
= HashMap
::new();
2046 assert_eq
!(m
.len(), 0);
2047 assert
!(m
.is_empty());
2050 let old_cap
= m
.table
.capacity();
2051 while old_cap
== m
.table
.capacity() {
2056 assert_eq
!(m
.len(), i
);
2057 assert
!(!m
.is_empty());
2061 fn test_behavior_resize_policy() {
2062 let mut m
= HashMap
::new();
2064 assert_eq
!(m
.len(), 0);
2065 assert_eq
!(m
.table
.capacity(), 0);
2066 assert
!(m
.is_empty());
2070 assert
!(m
.is_empty());
2071 let initial_cap
= m
.table
.capacity();
2072 m
.reserve(initial_cap
);
2073 let cap
= m
.table
.capacity();
2075 assert_eq
!(cap
, initial_cap
* 2);
2078 for _
in 0..cap
* 3 / 4 {
2082 // three quarters full
2084 assert_eq
!(m
.len(), i
);
2085 assert_eq
!(m
.table
.capacity(), cap
);
2087 for _
in 0..cap
/ 4 {
2093 let new_cap
= m
.table
.capacity();
2094 assert_eq
!(new_cap
, cap
* 2);
2096 for _
in 0..cap
/ 2 - 1 {
2099 assert_eq
!(m
.table
.capacity(), new_cap
);
2101 // A little more than one quarter full.
2103 assert_eq
!(m
.table
.capacity(), cap
);
2104 // again, a little more than half full
2105 for _
in 0..cap
/ 2 - 1 {
2111 assert_eq
!(m
.len(), i
);
2112 assert
!(!m
.is_empty());
2113 assert_eq
!(m
.table
.capacity(), initial_cap
);
2117 fn test_reserve_shrink_to_fit() {
2118 let mut m
= HashMap
::new();
2121 assert
!(m
.capacity() >= m
.len());
2127 let usable_cap
= m
.capacity();
2128 for i
in 128..(128 + 256) {
2130 assert_eq
!(m
.capacity(), usable_cap
);
2133 for i
in 100..(128 + 256) {
2134 assert_eq
!(m
.remove(&i
), Some(i
));
2138 assert_eq
!(m
.len(), 100);
2139 assert
!(!m
.is_empty());
2140 assert
!(m
.capacity() >= m
.len());
2143 assert_eq
!(m
.remove(&i
), Some(i
));
2148 assert_eq
!(m
.len(), 1);
2149 assert
!(m
.capacity() >= m
.len());
2150 assert_eq
!(m
.remove(&0), Some(0));
2154 fn test_from_iter() {
2155 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2157 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2159 for &(k
, v
) in &xs
{
2160 assert_eq
!(map
.get(&k
), Some(&v
));
2165 fn test_size_hint() {
2166 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2168 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2170 let mut iter
= map
.iter();
2172 for _
in iter
.by_ref().take(3) {}
2174 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2178 fn test_iter_len() {
2179 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2181 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2183 let mut iter
= map
.iter();
2185 for _
in iter
.by_ref().take(3) {}
2187 assert_eq
!(iter
.len(), 3);
2191 fn test_mut_size_hint() {
2192 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2194 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2196 let mut iter
= map
.iter_mut();
2198 for _
in iter
.by_ref().take(3) {}
2200 assert_eq
!(iter
.size_hint(), (3, Some(3)));
2204 fn test_iter_mut_len() {
2205 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2207 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2209 let mut iter
= map
.iter_mut();
2211 for _
in iter
.by_ref().take(3) {}
2213 assert_eq
!(iter
.len(), 3);
2218 let mut map
= HashMap
::new();
2224 assert_eq
!(map
[&2], 1);
2229 fn test_index_nonexistent() {
2230 let mut map
= HashMap
::new();
2241 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2243 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
2245 // Existing key (insert)
2246 match map
.entry(1) {
2247 Vacant(_
) => unreachable
!(),
2248 Occupied(mut view
) => {
2249 assert_eq
!(view
.get(), &10);
2250 assert_eq
!(view
.insert(100), 10);
2253 assert_eq
!(map
.get(&1).unwrap(), &100);
2254 assert_eq
!(map
.len(), 6);
2257 // Existing key (update)
2258 match map
.entry(2) {
2259 Vacant(_
) => unreachable
!(),
2260 Occupied(mut view
) => {
2261 let v
= view
.get_mut();
2262 let new_v
= (*v
) * 10;
2266 assert_eq
!(map
.get(&2).unwrap(), &200);
2267 assert_eq
!(map
.len(), 6);
2269 // Existing key (take)
2270 match map
.entry(3) {
2271 Vacant(_
) => unreachable
!(),
2273 assert_eq
!(view
.remove(), 30);
2276 assert_eq
!(map
.get(&3), None
);
2277 assert_eq
!(map
.len(), 5);
2280 // Inexistent key (insert)
2281 match map
.entry(10) {
2282 Occupied(_
) => unreachable
!(),
2284 assert_eq
!(*view
.insert(1000), 1000);
2287 assert_eq
!(map
.get(&10).unwrap(), &1000);
2288 assert_eq
!(map
.len(), 6);
2292 fn test_entry_take_doesnt_corrupt() {
2293 #![allow(deprecated)] //rand
2295 fn check(m
: &HashMap
<isize, ()>) {
2297 assert
!(m
.contains_key(k
),
2298 "{} is in keys() but not in the map?", k
);
2302 let mut m
= HashMap
::new();
2303 let mut rng
= thread_rng();
2305 // Populate the map with some items.
2307 let x
= rng
.gen_range(-10, 10);
2312 let x
= rng
.gen_range(-10, 10);
2316 println
!("{}: remove {}", i
, x
);