src/libstd/collections/hash/map.rs

   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.
   4 //
   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.
  10
  11 use self::Entry::*;
  12 use self::VacantEntryState::*;
  13
  14 use borrow::Borrow;
  15 use cmp::max;
  16 use fmt::{self, Debug};
  17 use hash::{Hash, SipHasher, BuildHasher};
  18 use iter::{self, Map, FromIterator};
  19 use mem::{self, replace};
  20 use ops::{Deref, Index};
  21 use rand::{self, Rng};
  22
  23 use super::table::{
  24     self,
  25     Bucket,
  26     EmptyBucket,
  27     FullBucket,
  28     FullBucketMut,
  29     RawTable,
  30     SafeHash
  31 };
  32 use super::table::BucketState::{
  33     Empty,
  34     Full,
  35 };
  36
  37 const INITIAL_LOG2_CAP: usize = 5;
  38 const INITIAL_CAPACITY: usize = 1 << INITIAL_LOG2_CAP; // 2^5
  39
  40 /// The default behavior of HashMap implements a load factor of 90.9%.
  41 /// This behavior is characterized by the following condition:
  42 ///
  43 /// - if size > 0.909 * capacity: grow the map
  44 #[derive(Clone)]
  45 struct DefaultResizePolicy;
  46
  47 impl DefaultResizePolicy {
  48     fn new() -> DefaultResizePolicy {
  49         DefaultResizePolicy
  50     }
  51
  52     #[inline]
  53     fn min_capacity(&self, usable_size: usize) -> usize {
  54         // Here, we are rephrasing the logic by specifying the lower limit
  55         // on capacity:
  56         //
  57         // - if `cap < size * 1.1`: grow the map
  58         usable_size * 11 / 10
  59     }
  60
  61     /// An inverse of `min_capacity`, approximately.
  62     #[inline]
  63     fn usable_capacity(&self, cap: usize) -> usize {
  64         // As the number of entries approaches usable capacity,
  65         // min_capacity(size) must be smaller than the internal capacity,
  66         // so that the map is not resized:
  67         // `min_capacity(usable_capacity(x)) <= x`.
  68         // The left-hand side can only be smaller due to flooring by integer
  69         // division.
  70         //
  71         // This doesn't have to be checked for overflow since allocation size
  72         // in bytes will overflow earlier than multiplication by 10.
  73         //
  74         // As per https://github.com/rust-lang/rust/pull/30991 this is updated
  75         // to be: (cap * den + den - 1) / num
  76         (cap * 10 + 10 - 1) / 11
  77     }
  78 }
  79
  80 #[test]
  81 fn test_resize_policy() {
  82     let rp = DefaultResizePolicy;
  83     for n in 0..1000 {
  84         assert!(rp.min_capacity(rp.usable_capacity(n)) <= n);
  85         assert!(rp.usable_capacity(rp.min_capacity(n)) <= n);
  86     }
  87 }
  88
  89 // The main performance trick in this hashmap is called Robin Hood Hashing.
  90 // It gains its excellent performance from one essential operation:
  91 //
  92 //    If an insertion collides with an existing element, and that element's
  93 //    "probe distance" (how far away the element is from its ideal location)
  94 //    is higher than how far we've already probed, swap the elements.
  95 //
  96 // This massively lowers variance in probe distance, and allows us to get very
  97 // high load factors with good performance. The 90% load factor I use is rather
  98 // conservative.
  99 //
 100 // > Why a load factor of approximately 90%?
 101 //
 102 // In general, all the distances to initial buckets will converge on the mean.
 103 // At a load factor of α, the odds of finding the target bucket after k
 104 // probes is approximately 1-α^k. If we set this equal to 50% (since we converge
 105 // on the mean) and set k=8 (64-byte cache line / 8-byte hash), α=0.92. I round
 106 // this down to make the math easier on the CPU and avoid its FPU.
 107 // Since on average we start the probing in the middle of a cache line, this
 108 // strategy pulls in two cache lines of hashes on every lookup. I think that's
 109 // pretty good, but if you want to trade off some space, it could go down to one
 110 // cache line on average with an α of 0.84.
 111 //
 112 // > Wait, what? Where did you get 1-α^k from?
 113 //
 114 // On the first probe, your odds of a collision with an existing element is α.
 115 // The odds of doing this twice in a row is approximately α^2. For three times,
 116 // α^3, etc. Therefore, the odds of colliding k times is α^k. The odds of NOT
 117 // colliding after k tries is 1-α^k.
 118 //
 119 // The paper from 1986 cited below mentions an implementation which keeps track
 120 // of the distance-to-initial-bucket histogram. This approach is not suitable
 121 // for modern architectures because it requires maintaining an internal data
 122 // structure. This allows very good first guesses, but we are most concerned
 123 // with guessing entire cache lines, not individual indexes. Furthermore, array
 124 // accesses are no longer linear and in one direction, as we have now. There
 125 // is also memory and cache pressure that this would entail that would be very
 126 // difficult to properly see in a microbenchmark.
 127 //
 128 // ## Future Improvements (FIXME!)
 129 //
 130 // Allow the load factor to be changed dynamically and/or at initialization.
 131 //
 132 // Also, would it be possible for us to reuse storage when growing the
 133 // underlying table? This is exactly the use case for 'realloc', and may
 134 // be worth exploring.
 135 //
 136 // ## Future Optimizations (FIXME!)
 137 //
 138 // Another possible design choice that I made without any real reason is
 139 // parameterizing the raw table over keys and values. Technically, all we need
 140 // is the size and alignment of keys and values, and the code should be just as
 141 // efficient (well, we might need one for power-of-two size and one for not...).
 142 // This has the potential to reduce code bloat in rust executables, without
 143 // really losing anything except 4 words (key size, key alignment, val size,
 144 // val alignment) which can be passed in to every call of a `RawTable` function.
 145 // This would definitely be an avenue worth exploring if people start complaining
 146 // about the size of rust executables.
 147 //
 148 // Annotate exceedingly likely branches in `table::make_hash`
 149 // and `search_hashed` to reduce instruction cache pressure
 150 // and mispredictions once it becomes possible (blocked on issue #11092).
 151 //
 152 // Shrinking the table could simply reallocate in place after moving buckets
 153 // to the first half.
 154 //
 155 // The growth algorithm (fragment of the Proof of Correctness)
 156 // --------------------
 157 //
 158 // The growth algorithm is basically a fast path of the naive reinsertion-
 159 // during-resize algorithm. Other paths should never be taken.
 160 //
 161 // Consider growing a robin hood hashtable of capacity n. Normally, we do this
 162 // by allocating a new table of capacity `2n`, and then individually reinsert
 163 // each element in the old table into the new one. This guarantees that the
 164 // new table is a valid robin hood hashtable with all the desired statistical
 165 // properties. Remark that the order we reinsert the elements in should not
 166 // matter. For simplicity and efficiency, we will consider only linear
 167 // reinsertions, which consist of reinserting all elements in the old table
 168 // into the new one by increasing order of index. However we will not be
 169 // starting our reinsertions from index 0 in general. If we start from index
 170 // i, for the purpose of reinsertion we will consider all elements with real
 171 // index j < i to have virtual index n + j.
 172 //
 173 // Our hash generation scheme consists of generating a 64-bit hash and
 174 // truncating the most significant bits. When moving to the new table, we
 175 // simply introduce a new bit to the front of the hash. Therefore, if an
 176 // elements has ideal index i in the old table, it can have one of two ideal
 177 // locations in the new table. If the new bit is 0, then the new ideal index
 178 // is i. If the new bit is 1, then the new ideal index is n + i. Intuitively,
 179 // we are producing two independent tables of size n, and for each element we
 180 // independently choose which table to insert it into with equal probability.
 181 // However the rather than wrapping around themselves on overflowing their
 182 // indexes, the first table overflows into the first, and the first into the
 183 // second. Visually, our new table will look something like:
 184 //
 185 // [yy_xxx_xxxx_xxx|xx_yyy_yyyy_yyy]
 186 //
 187 // Where x's are elements inserted into the first table, y's are elements
 188 // inserted into the second, and _'s are empty sections. We now define a few
 189 // key concepts that we will use later. Note that this is a very abstract
 190 // perspective of the table. A real resized table would be at least half
 191 // empty.
 192 //
 193 // Theorem: A linear robin hood reinsertion from the first ideal element
 194 // produces identical results to a linear naive reinsertion from the same
 195 // element.
 196 //
 197 // FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
 198
 199 /// A hash map implementation which uses linear probing with Robin
 200 /// Hood bucket stealing.
 201 ///
 202 /// The hashes are all keyed by the thread-local random number generator
 203 /// on creation by default. This means that the ordering of the keys is
 204 /// randomized, but makes the tables more resistant to
 205 /// denial-of-service attacks (Hash DoS). This behavior can be
 206 /// overridden with one of the constructors.
 207 ///
 208 /// It is required that the keys implement the `Eq` and `Hash` traits, although
 209 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
 210 /// If you implement these yourself, it is important that the following
 211 /// property holds:
 212 ///
 213 /// ```text
 214 /// k1 == k2 -> hash(k1) == hash(k2)
 215 /// ```
 216 ///
 217 /// In other words, if two keys are equal, their hashes must be equal.
 218 ///
 219 /// It is a logic error for a key to be modified in such a way that the key's
 220 /// hash, as determined by the `Hash` trait, or its equality, as determined by
 221 /// the `Eq` trait, changes while it is in the map. This is normally only
 222 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
 223 ///
 224 /// Relevant papers/articles:
 225 ///
 226 /// 1. Pedro Celis. ["Robin Hood Hashing"](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)
 227 /// 2. Emmanuel Goossaert. ["Robin Hood
 228 ///    hashing"](http://codecapsule.com/2013/11/11/robin-hood-hashing/)
 229 /// 3. Emmanuel Goossaert. ["Robin Hood hashing: backward shift
 230 ///    deletion"](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)
 231 ///
 232 /// # Examples
 233 ///
 234 /// ```
 235 /// use std::collections::HashMap;
 236 ///
 237 /// // type inference lets us omit an explicit type signature (which
 238 /// // would be `HashMap<&str, &str>` in this example).
 239 /// let mut book_reviews = HashMap::new();
 240 ///
 241 /// // review some books.
 242 /// book_reviews.insert("Adventures of Huckleberry Finn",    "My favorite book.");
 243 /// book_reviews.insert("Grimms' Fairy Tales",               "Masterpiece.");
 244 /// book_reviews.insert("Pride and Prejudice",               "Very enjoyable.");
 245 /// book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
 246 ///
 247 /// // check for a specific one.
 248 /// if !book_reviews.contains_key("Les Misérables") {
 249 ///     println!("We've got {} reviews, but Les Misérables ain't one.",
 250 ///              book_reviews.len());
 251 /// }
 252 ///
 253 /// // oops, this review has a lot of spelling mistakes, let's delete it.
 254 /// book_reviews.remove("The Adventures of Sherlock Holmes");
 255 ///
 256 /// // look up the values associated with some keys.
 257 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
 258 /// for book in &to_find {
 259 ///     match book_reviews.get(book) {
 260 ///         Some(review) => println!("{}: {}", book, review),
 261 ///         None => println!("{} is unreviewed.", book)
 262 ///     }
 263 /// }
 264 ///
 265 /// // iterate over everything.
 266 /// for (book, review) in &book_reviews {
 267 ///     println!("{}: \"{}\"", book, review);
 268 /// }
 269 /// ```
 270 ///
 271 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
 272 /// for more complex methods of getting, setting, updating and removing keys and
 273 /// their values:
 274 ///
 275 /// ```
 276 /// use std::collections::HashMap;
 277 ///
 278 /// // type inference lets us omit an explicit type signature (which
 279 /// // would be `HashMap<&str, u8>` in this example).
 280 /// let mut player_stats = HashMap::new();
 281 ///
 282 /// fn random_stat_buff() -> u8 {
 283 ///     // could actually return some random value here - let's just return
 284 ///     // some fixed value for now
 285 ///     42
 286 /// }
 287 ///
 288 /// // insert a key only if it doesn't already exist
 289 /// player_stats.entry("health").or_insert(100);
 290 ///
 291 /// // insert a key using a function that provides a new value only if it
 292 /// // doesn't already exist
 293 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
 294 ///
 295 /// // update a key, guarding against the key possibly not being set
 296 /// let stat = player_stats.entry("attack").or_insert(100);
 297 /// *stat += random_stat_buff();
 298 /// ```
 299 ///
 300 /// The easiest way to use `HashMap` with a custom type as key is to derive `Eq` and `Hash`.
 301 /// We must also derive `PartialEq`.
 302 ///
 303 /// ```
 304 /// use std::collections::HashMap;
 305 ///
 306 /// #[derive(Hash, Eq, PartialEq, Debug)]
 307 /// struct Viking {
 308 ///     name: String,
 309 ///     country: String,
 310 /// }
 311 ///
 312 /// impl Viking {
 313 ///     /// Create a new Viking.
 314 ///     fn new(name: &str, country: &str) -> Viking {
 315 ///         Viking { name: name.to_string(), country: country.to_string() }
 316 ///     }
 317 /// }
 318 ///
 319 /// // Use a HashMap to store the vikings' health points.
 320 /// let mut vikings = HashMap::new();
 321 ///
 322 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
 323 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
 324 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
 325 ///
 326 /// // Use derived implementation to print the status of the vikings.
 327 /// for (viking, health) in &vikings {
 328 ///     println!("{:?} has {} hp", viking, health);
 329 /// }
 330 /// ```
 331 #[derive(Clone)]
 332 #[stable(feature = "rust1", since = "1.0.0")]
 333 pub struct HashMap<K, V, S = RandomState> {
 334     // All hashes are keyed on these values, to prevent hash collision attacks.
 335     hash_builder: S,
 336
 337     table: RawTable<K, V>,
 338
 339     resize_policy: DefaultResizePolicy,
 340 }
 341
 342 /// Search for a pre-hashed key.
 343 #[inline]
 344 fn search_hashed<K, V, M, F>(table: M,
 345                              hash: SafeHash,
 346                              mut is_match: F)
 347                              -> InternalEntry<K, V, M> where
 348     M: Deref<Target=RawTable<K, V>>,
 349     F: FnMut(&K) -> bool,
 350 {
 351     // This is the only function where capacity can be zero. To avoid
 352     // undefined behavior when Bucket::new gets the raw bucket in this
 353     // case, immediately return the appropriate search result.
 354     if table.capacity() == 0 {
 355         return InternalEntry::TableIsEmpty;
 356     }
 357
 358     let size = table.size() as isize;
 359     let mut probe = Bucket::new(table, hash);
 360     let ib = probe.index() as isize;
 361
 362     loop {
 363         let full = match probe.peek() {
 364             Empty(bucket) => {
 365                 // Found a hole!
 366                 return InternalEntry::Vacant {
 367                     hash: hash,
 368                     elem: NoElem(bucket),
 369                 };
 370             }
 371             Full(bucket) => bucket
 372         };
 373
 374         let robin_ib = full.index() as isize - full.displacement() as isize;
 375
 376         if ib < robin_ib {
 377             // Found a luckier bucket than me.
 378             // We can finish the search early if we hit any bucket
 379             // with a lower distance to initial bucket than we've probed.
 380             return InternalEntry::Vacant {
 381                 hash: hash,
 382                 elem: NeqElem(full, robin_ib as usize),
 383             };
 384         }
 385
 386         // If the hash doesn't match, it can't be this one..
 387         if hash == full.hash() {
 388             // If the key doesn't match, it can't be this one..
 389             if is_match(full.read().0) {
 390                 return InternalEntry::Occupied {
 391                     elem: full
 392                 };
 393             }
 394         }
 395
 396         probe = full.next();
 397         debug_assert!(probe.index() as isize != ib + size + 1);
 398     }
 399 }
 400
 401 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
 402     let (empty, retkey, retval) = starting_bucket.take();
 403     let mut gap = match empty.gap_peek() {
 404         Some(b) => b,
 405         None => return (retkey, retval)
 406     };
 407
 408     while gap.full().displacement() != 0 {
 409         gap = match gap.shift() {
 410             Some(b) => b,
 411             None => break
 412         };
 413     }
 414
 415     // Now we've done all our shifting. Return the value we grabbed earlier.
 416     (retkey, retval)
 417 }
 418
 419 /// Perform robin hood bucket stealing at the given `bucket`. You must
 420 /// also pass the position of that bucket's initial bucket so we don't have
 421 /// to recalculate it.
 422 ///
 423 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
 424 fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
 425                         mut ib: usize,
 426                         mut hash: SafeHash,
 427                         mut key: K,
 428                         mut val: V)
 429                         -> &'a mut V {
 430     let starting_index = bucket.index();
 431     let size = {
 432         let table = bucket.table(); // FIXME "lifetime too short".
 433         table.size()
 434     };
 435     // Save the *starting point*.
 436     let mut bucket = bucket.stash();
 437     // There can be at most `size - dib` buckets to displace, because
 438     // in the worst case, there are `size` elements and we already are
 439     // `displacement` buckets away from the initial one.
 440     let idx_end = starting_index + size - bucket.displacement();
 441
 442     loop {
 443         let (old_hash, old_key, old_val) = bucket.replace(hash, key, val);
 444         hash = old_hash;
 445         key = old_key;
 446         val = old_val;
 447
 448         loop {
 449             let probe = bucket.next();
 450             debug_assert!(probe.index() != idx_end);
 451
 452             let full_bucket = match probe.peek() {
 453                 Empty(bucket) => {
 454                     // Found a hole!
 455                     let bucket = bucket.put(hash, key, val);
 456                     // Now that it's stolen, just read the value's pointer
 457                     // right out of the table! Go back to the *starting point*.
 458                     //
 459                     // This use of `into_table` is misleading. It turns the
 460                     // bucket, which is a FullBucket on top of a
 461                     // FullBucketMut, into just one FullBucketMut. The "table"
 462                     // refers to the inner FullBucketMut in this context.
 463                     return bucket.into_table().into_mut_refs().1;
 464                 },
 465                 Full(bucket) => bucket
 466             };
 467
 468             let probe_ib = full_bucket.index() - full_bucket.displacement();
 469
 470             bucket = full_bucket;
 471
 472             // Robin hood! Steal the spot.
 473             if ib < probe_ib {
 474                 ib = probe_ib;
 475                 break;
 476             }
 477         }
 478     }
 479 }
 480
 481 impl<K, V, S> HashMap<K, V, S>
 482     where K: Eq + Hash, S: BuildHasher
 483 {
 484     fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash {
 485         table::make_hash(&self.hash_builder, x)
 486     }
 487
 488     /// Search for a key, yielding the index if it's found in the hashtable.
 489     /// If you already have the hash for the key lying around, use
 490     /// search_hashed.
 491     #[inline]
 492     fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> InternalEntry<K, V, &'a RawTable<K, V>>
 493         where K: Borrow<Q>, Q: Eq + Hash
 494     {
 495         let hash = self.make_hash(q);
 496         search_hashed(&self.table, hash, |k| q.eq(k.borrow()))
 497     }
 498
 499     #[inline]
 500     fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> InternalEntry<K, V, &'a mut RawTable<K, V>>
 501         where K: Borrow<Q>, Q: Eq + Hash
 502     {
 503         let hash = self.make_hash(q);
 504         search_hashed(&mut self.table, hash, |k| q.eq(k.borrow()))
 505     }
 506
 507     // The caller should ensure that invariants by Robin Hood Hashing hold.
 508     fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
 509         let cap = self.table.capacity();
 510         let mut buckets = Bucket::new(&mut self.table, hash);
 511         let ib = buckets.index();
 512
 513         while buckets.index() != ib + cap {
 514             // We don't need to compare hashes for value swap.
 515             // Not even DIBs for Robin Hood.
 516             buckets = match buckets.peek() {
 517                 Empty(empty) => {
 518                     empty.put(hash, k, v);
 519                     return;
 520                 }
 521                 Full(b) => b.into_bucket()
 522             };
 523             buckets.next();
 524         }
 525         panic!("Internal HashMap error: Out of space.");
 526     }
 527 }
 528
 529 impl<K: Hash + Eq, V> HashMap<K, V, RandomState> {
 530     /// Creates an empty HashMap.
 531     ///
 532     /// # Examples
 533     ///
 534     /// ```
 535     /// use std::collections::HashMap;
 536     /// let mut map: HashMap<&str, isize> = HashMap::new();
 537     /// ```
 538     #[inline]
 539     #[stable(feature = "rust1", since = "1.0.0")]
 540     pub fn new() -> HashMap<K, V, RandomState> {
 541         Default::default()
 542     }
 543
 544     /// Creates an empty hash map with the given initial capacity.
 545     ///
 546     /// # Examples
 547     ///
 548     /// ```
 549     /// use std::collections::HashMap;
 550     /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10);
 551     /// ```
 552     #[inline]
 553     #[stable(feature = "rust1", since = "1.0.0")]
 554     pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
 555         HashMap::with_capacity_and_hasher(capacity, Default::default())
 556     }
 557 }
 558
 559 impl<K, V, S> HashMap<K, V, S>
 560     where K: Eq + Hash, S: BuildHasher
 561 {
 562     /// Creates an empty hashmap which will use the given hash builder to hash
 563     /// keys.
 564     ///
 565     /// The created map has the default initial capacity.
 566     ///
 567     /// Warning: `hash_builder` is normally randomly generated, and
 568     /// is designed to allow HashMaps to be resistant to attacks that
 569     /// cause many collisions and very poor performance. Setting it
 570     /// manually using this function can expose a DoS attack vector.
 571     ///
 572     /// # Examples
 573     ///
 574     /// ```
 575     /// use std::collections::HashMap;
 576     /// use std::collections::hash_map::RandomState;
 577     ///
 578     /// let s = RandomState::new();
 579     /// let mut map = HashMap::with_hasher(s);
 580     /// map.insert(1, 2);
 581     /// ```
 582     #[inline]
 583     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
 584     pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
 585         HashMap {
 586             hash_builder: hash_builder,
 587             resize_policy: DefaultResizePolicy::new(),
 588             table: RawTable::new(0),
 589         }
 590     }
 591
 592     /// Creates an empty HashMap with space for at least `capacity`
 593     /// elements, using `hasher` to hash the keys.
 594     ///
 595     /// Warning: `hasher` is normally randomly generated, and
 596     /// is designed to allow HashMaps to be resistant to attacks that
 597     /// cause many collisions and very poor performance. Setting it
 598     /// manually using this function can expose a DoS attack vector.
 599     ///
 600     /// # Examples
 601     ///
 602     /// ```
 603     /// use std::collections::HashMap;
 604     /// use std::collections::hash_map::RandomState;
 605     ///
 606     /// let s = RandomState::new();
 607     /// let mut map = HashMap::with_capacity_and_hasher(10, s);
 608     /// map.insert(1, 2);
 609     /// ```
 610     #[inline]
 611     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
 612     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S)
 613                                     -> HashMap<K, V, S> {
 614         let resize_policy = DefaultResizePolicy::new();
 615         let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
 616         let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
 617         assert!(internal_cap >= capacity, "capacity overflow");
 618         HashMap {
 619             hash_builder: hash_builder,
 620             resize_policy: resize_policy,
 621             table: RawTable::new(internal_cap),
 622         }
 623     }
 624
 625     /// Returns a reference to the map's hasher.
 626     #[unstable(feature = "hashmap_public_hasher", reason = "don't want to make insta-stable",
 627                issue = "31262")]
 628     pub fn hasher(&self) -> &S {
 629         &self.hash_builder
 630     }
 631
 632     /// Returns the number of elements the map can hold without reallocating.
 633     ///
 634     /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
 635     /// more, but is guaranteed to be able to hold at least this many.
 636     ///
 637     /// # Examples
 638     ///
 639     /// ```
 640     /// use std::collections::HashMap;
 641     /// let map: HashMap<isize, isize> = HashMap::with_capacity(100);
 642     /// assert!(map.capacity() >= 100);
 643     /// ```
 644     #[inline]
 645     #[stable(feature = "rust1", since = "1.0.0")]
 646     pub fn capacity(&self) -> usize {
 647         self.resize_policy.usable_capacity(self.table.capacity())
 648     }
 649
 650     /// Reserves capacity for at least `additional` more elements to be inserted
 651     /// in the `HashMap`. The collection may reserve more space to avoid
 652     /// frequent reallocations.
 653     ///
 654     /// # Panics
 655     ///
 656     /// Panics if the new allocation size overflows `usize`.
 657     ///
 658     /// # Examples
 659     ///
 660     /// ```
 661     /// use std::collections::HashMap;
 662     /// let mut map: HashMap<&str, isize> = HashMap::new();
 663     /// map.reserve(10);
 664     /// ```
 665     #[stable(feature = "rust1", since = "1.0.0")]
 666     pub fn reserve(&mut self, additional: usize) {
 667         let new_size = self.len().checked_add(additional).expect("capacity overflow");
 668         let min_cap = self.resize_policy.min_capacity(new_size);
 669
 670         // An invalid value shouldn't make us run out of space. This includes
 671         // an overflow check.
 672         assert!(new_size <= min_cap);
 673
 674         if self.table.capacity() < min_cap {
 675             let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
 676             self.resize(new_capacity);
 677         }
 678     }
 679
 680     /// Resizes the internal vectors to a new capacity. It's your responsibility to:
 681     ///   1) Make sure the new capacity is enough for all the elements, accounting
 682     ///      for the load factor.
 683     ///   2) Ensure new_capacity is a power of two or zero.
 684     fn resize(&mut self, new_capacity: usize) {
 685         assert!(self.table.size() <= new_capacity);
 686         assert!(new_capacity.is_power_of_two() || new_capacity == 0);
 687
 688         let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
 689         let old_size = old_table.size();
 690
 691         if old_table.capacity() == 0 || old_table.size() == 0 {
 692             return;
 693         }
 694
 695         // Grow the table.
 696         // Specialization of the other branch.
 697         let mut bucket = Bucket::first(&mut old_table);
 698
 699         // "So a few of the first shall be last: for many be called,
 700         // but few chosen."
 701         //
 702         // We'll most likely encounter a few buckets at the beginning that
 703         // have their initial buckets near the end of the table. They were
 704         // placed at the beginning as the probe wrapped around the table
 705         // during insertion. We must skip forward to a bucket that won't
 706         // get reinserted too early and won't unfairly steal others spot.
 707         // This eliminates the need for robin hood.
 708         loop {
 709             bucket = match bucket.peek() {
 710                 Full(full) => {
 711                     if full.displacement() == 0 {
 712                         // This bucket occupies its ideal spot.
 713                         // It indicates the start of another "cluster".
 714                         bucket = full.into_bucket();
 715                         break;
 716                     }
 717                     // Leaving this bucket in the last cluster for later.
 718                     full.into_bucket()
 719                 }
 720                 Empty(b) => {
 721                     // Encountered a hole between clusters.
 722                     b.into_bucket()
 723                 }
 724             };
 725             bucket.next();
 726         }
 727
 728         // This is how the buckets might be laid out in memory:
 729         // ($ marks an initialized bucket)
 730         //  ________________
 731         // |$$$_$$$$$$_$$$$$|
 732         //
 733         // But we've skipped the entire initial cluster of buckets
 734         // and will continue iteration in this order:
 735         //  ________________
 736         //     |$$$$$$_$$$$$
 737         //                  ^ wrap around once end is reached
 738         //  ________________
 739         //  $$$_____________|
 740         //    ^ exit once table.size == 0
 741         loop {
 742             bucket = match bucket.peek() {
 743                 Full(bucket) => {
 744                     let h = bucket.hash();
 745                     let (b, k, v) = bucket.take();
 746                     self.insert_hashed_ordered(h, k, v);
 747                     {
 748                         let t = b.table(); // FIXME "lifetime too short".
 749                         if t.size() == 0 { break }
 750                     };
 751                     b.into_bucket()
 752                 }
 753                 Empty(b) => b.into_bucket()
 754             };
 755             bucket.next();
 756         }
 757
 758         assert_eq!(self.table.size(), old_size);
 759     }
 760
 761     /// Shrinks the capacity of the map as much as possible. It will drop
 762     /// down as much as possible while maintaining the internal rules
 763     /// and possibly leaving some space in accordance with the resize policy.
 764     ///
 765     /// # Examples
 766     ///
 767     /// ```
 768     /// use std::collections::HashMap;
 769     ///
 770     /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100);
 771     /// map.insert(1, 2);
 772     /// map.insert(3, 4);
 773     /// assert!(map.capacity() >= 100);
 774     /// map.shrink_to_fit();
 775     /// assert!(map.capacity() >= 2);
 776     /// ```
 777     #[stable(feature = "rust1", since = "1.0.0")]
 778     pub fn shrink_to_fit(&mut self) {
 779         let min_capacity = self.resize_policy.min_capacity(self.len());
 780         let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
 781
 782         // An invalid value shouldn't make us run out of space.
 783         debug_assert!(self.len() <= min_capacity);
 784
 785         if self.table.capacity() != min_capacity {
 786             let old_table = replace(&mut self.table, RawTable::new(min_capacity));
 787             let old_size = old_table.size();
 788
 789             // Shrink the table. Naive algorithm for resizing:
 790             for (h, k, v) in old_table.into_iter() {
 791                 self.insert_hashed_nocheck(h, k, v);
 792             }
 793
 794             debug_assert_eq!(self.table.size(), old_size);
 795         }
 796     }
 797
 798     /// Insert a pre-hashed key-value pair, without first checking
 799     /// that there's enough room in the buckets. Returns a reference to the
 800     /// newly insert value.
 801     ///
 802     /// If the key already exists, the hashtable will be returned untouched
 803     /// and a reference to the existing element will be returned.
 804     fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> Option<V> {
 805         let entry = search_hashed(&mut self.table, hash, |key| *key == k).into_entry(k);
 806         match entry {
 807             Some(Occupied(mut elem)) => {
 808                 Some(elem.insert(v))
 809             }
 810             Some(Vacant(elem)) => {
 811                 elem.insert(v);
 812                 None
 813             }
 814             None => {
 815                 unreachable!()
 816             }
 817         }
 818     }
 819
 820     /// An iterator visiting all keys in arbitrary order.
 821     /// Iterator element type is `&'a K`.
 822     ///
 823     /// # Examples
 824     ///
 825     /// ```
 826     /// use std::collections::HashMap;
 827     ///
 828     /// let mut map = HashMap::new();
 829     /// map.insert("a", 1);
 830     /// map.insert("b", 2);
 831     /// map.insert("c", 3);
 832     ///
 833     /// for key in map.keys() {
 834     ///     println!("{}", key);
 835     /// }
 836     /// ```
 837     #[stable(feature = "rust1", since = "1.0.0")]
 838     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
 839         fn first<A, B>((a, _): (A, B)) -> A { a }
 840         let first: fn((&'a K,&'a V)) -> &'a K = first; // coerce to fn ptr
 841
 842         Keys { inner: self.iter().map(first) }
 843     }
 844
 845     /// An iterator visiting all values in arbitrary order.
 846     /// Iterator element type is `&'a V`.
 847     ///
 848     /// # Examples
 849     ///
 850     /// ```
 851     /// use std::collections::HashMap;
 852     ///
 853     /// let mut map = HashMap::new();
 854     /// map.insert("a", 1);
 855     /// map.insert("b", 2);
 856     /// map.insert("c", 3);
 857     ///
 858     /// for val in map.values() {
 859     ///     println!("{}", val);
 860     /// }
 861     /// ```
 862     #[stable(feature = "rust1", since = "1.0.0")]
 863     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
 864         fn second<A, B>((_, b): (A, B)) -> B { b }
 865         let second: fn((&'a K,&'a V)) -> &'a V = second; // coerce to fn ptr
 866
 867         Values { inner: self.iter().map(second) }
 868     }
 869
 870     /// An iterator visiting all key-value pairs in arbitrary order.
 871     /// Iterator element type is `(&'a K, &'a V)`.
 872     ///
 873     /// # Examples
 874     ///
 875     /// ```
 876     /// use std::collections::HashMap;
 877     ///
 878     /// let mut map = HashMap::new();
 879     /// map.insert("a", 1);
 880     /// map.insert("b", 2);
 881     /// map.insert("c", 3);
 882     ///
 883     /// for (key, val) in map.iter() {
 884     ///     println!("key: {} val: {}", key, val);
 885     /// }
 886     /// ```
 887     #[stable(feature = "rust1", since = "1.0.0")]
 888     pub fn iter(&self) -> Iter<K, V> {
 889         Iter { inner: self.table.iter() }
 890     }
 891
 892     /// An iterator visiting all key-value pairs in arbitrary order,
 893     /// with mutable references to the values.
 894     /// Iterator element type is `(&'a K, &'a mut V)`.
 895     ///
 896     /// # Examples
 897     ///
 898     /// ```
 899     /// use std::collections::HashMap;
 900     ///
 901     /// let mut map = HashMap::new();
 902     /// map.insert("a", 1);
 903     /// map.insert("b", 2);
 904     /// map.insert("c", 3);
 905     ///
 906     /// // Update all values
 907     /// for (_, val) in map.iter_mut() {
 908     ///     *val *= 2;
 909     /// }
 910     ///
 911     /// for (key, val) in &map {
 912     ///     println!("key: {} val: {}", key, val);
 913     /// }
 914     /// ```
 915     #[stable(feature = "rust1", since = "1.0.0")]
 916     pub fn iter_mut(&mut self) -> IterMut<K, V> {
 917         IterMut { inner: self.table.iter_mut() }
 918     }
 919
 920     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 921     ///
 922     /// # Examples
 923     ///
 924     /// ```
 925     /// use std::collections::HashMap;
 926     ///
 927     /// let mut letters = HashMap::new();
 928     ///
 929     /// for ch in "a short treatise on fungi".chars() {
 930     ///     let counter = letters.entry(ch).or_insert(0);
 931     ///     *counter += 1;
 932     /// }
 933     ///
 934     /// assert_eq!(letters[&'s'], 2);
 935     /// assert_eq!(letters[&'t'], 3);
 936     /// assert_eq!(letters[&'u'], 1);
 937     /// assert_eq!(letters.get(&'y'), None);
 938     /// ```
 939     #[stable(feature = "rust1", since = "1.0.0")]
 940     pub fn entry(&mut self, key: K) -> Entry<K, V> {
 941         // Gotta resize now.
 942         self.reserve(1);
 943         self.search_mut(&key).into_entry(key).expect("unreachable")
 944     }
 945
 946     /// Returns the number of elements in the map.
 947     ///
 948     /// # Examples
 949     ///
 950     /// ```
 951     /// use std::collections::HashMap;
 952     ///
 953     /// let mut a = HashMap::new();
 954     /// assert_eq!(a.len(), 0);
 955     /// a.insert(1, "a");
 956     /// assert_eq!(a.len(), 1);
 957     /// ```
 958     #[stable(feature = "rust1", since = "1.0.0")]
 959     pub fn len(&self) -> usize { self.table.size() }
 960
 961     /// Returns true if the map contains no elements.
 962     ///
 963     /// # Examples
 964     ///
 965     /// ```
 966     /// use std::collections::HashMap;
 967     ///
 968     /// let mut a = HashMap::new();
 969     /// assert!(a.is_empty());
 970     /// a.insert(1, "a");
 971     /// assert!(!a.is_empty());
 972     /// ```
 973     #[inline]
 974     #[stable(feature = "rust1", since = "1.0.0")]
 975     pub fn is_empty(&self) -> bool { self.len() == 0 }
 976
 977     /// Clears the map, returning all key-value pairs as an iterator. Keeps the
 978     /// allocated memory for reuse.
 979     ///
 980     /// # Examples
 981     ///
 982     /// ```
 983     /// use std::collections::HashMap;
 984     ///
 985     /// let mut a = HashMap::new();
 986     /// a.insert(1, "a");
 987     /// a.insert(2, "b");
 988     ///
 989     /// for (k, v) in a.drain().take(1) {
 990     ///     assert!(k == 1 || k == 2);
 991     ///     assert!(v == "a" || v == "b");
 992     /// }
 993     ///
 994     /// assert!(a.is_empty());
 995     /// ```
 996     #[inline]
 997     #[stable(feature = "drain", since = "1.6.0")]
 998     pub fn drain(&mut self) -> Drain<K, V> {
 999         fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1000         let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two; // coerce to fn pointer
1001
1002         Drain {
1003             inner: self.table.drain().map(last_two),
1004         }
1005     }
1006
1007     /// Clears the map, removing all key-value pairs. Keeps the allocated memory
1008     /// for reuse.
1009     ///
1010     /// # Examples
1011     ///
1012     /// ```
1013     /// use std::collections::HashMap;
1014     ///
1015     /// let mut a = HashMap::new();
1016     /// a.insert(1, "a");
1017     /// a.clear();
1018     /// assert!(a.is_empty());
1019     /// ```
1020     #[stable(feature = "rust1", since = "1.0.0")]
1021     #[inline]
1022     pub fn clear(&mut self) {
1023         self.drain();
1024     }
1025
1026     /// Returns a reference to the value corresponding to the key.
1027     ///
1028     /// The key may be any borrowed form of the map's key type, but
1029     /// `Hash` and `Eq` on the borrowed form *must* match those for
1030     /// the key type.
1031     ///
1032     /// # Examples
1033     ///
1034     /// ```
1035     /// use std::collections::HashMap;
1036     ///
1037     /// let mut map = HashMap::new();
1038     /// map.insert(1, "a");
1039     /// assert_eq!(map.get(&1), Some(&"a"));
1040     /// assert_eq!(map.get(&2), None);
1041     /// ```
1042     #[stable(feature = "rust1", since = "1.0.0")]
1043     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
1044         where K: Borrow<Q>, Q: Hash + Eq
1045     {
1046         self.search(k).into_occupied_bucket().map(|bucket| bucket.into_refs().1)
1047     }
1048
1049     /// Returns true if the map contains a value for the specified key.
1050     ///
1051     /// The key may be any borrowed form of the map's key type, but
1052     /// `Hash` and `Eq` on the borrowed form *must* match those for
1053     /// the key type.
1054     ///
1055     /// # Examples
1056     ///
1057     /// ```
1058     /// use std::collections::HashMap;
1059     ///
1060     /// let mut map = HashMap::new();
1061     /// map.insert(1, "a");
1062     /// assert_eq!(map.contains_key(&1), true);
1063     /// assert_eq!(map.contains_key(&2), false);
1064     /// ```
1065     #[stable(feature = "rust1", since = "1.0.0")]
1066     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
1067         where K: Borrow<Q>, Q: Hash + Eq
1068     {
1069         self.search(k).into_occupied_bucket().is_some()
1070     }
1071
1072     /// Returns a mutable reference to the value corresponding to the key.
1073     ///
1074     /// The key may be any borrowed form of the map's key type, but
1075     /// `Hash` and `Eq` on the borrowed form *must* match those for
1076     /// the key type.
1077     ///
1078     /// # Examples
1079     ///
1080     /// ```
1081     /// use std::collections::HashMap;
1082     ///
1083     /// let mut map = HashMap::new();
1084     /// map.insert(1, "a");
1085     /// if let Some(x) = map.get_mut(&1) {
1086     ///     *x = "b";
1087     /// }
1088     /// assert_eq!(map[&1], "b");
1089     /// ```
1090     #[stable(feature = "rust1", since = "1.0.0")]
1091     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
1092         where K: Borrow<Q>, Q: Hash + Eq
1093     {
1094         self.search_mut(k).into_occupied_bucket().map(|bucket| bucket.into_mut_refs().1)
1095     }
1096
1097     /// Inserts a key-value pair into the map.
1098     ///
1099     /// If the map did not have this key present, `None` is returned.
1100     ///
1101     /// If the map did have this key present, the value is updated, and the old
1102     /// value is returned. The key is not updated, though; this matters for
1103     /// types that can be `==` without being identical. See the [module-level
1104     /// documentation] for more.
1105     ///
1106     /// [module-level documentation]: index.html#insert-and-complex-keys
1107     ///
1108     /// # Examples
1109     ///
1110     /// ```
1111     /// use std::collections::HashMap;
1112     ///
1113     /// let mut map = HashMap::new();
1114     /// assert_eq!(map.insert(37, "a"), None);
1115     /// assert_eq!(map.is_empty(), false);
1116     ///
1117     /// map.insert(37, "b");
1118     /// assert_eq!(map.insert(37, "c"), Some("b"));
1119     /// assert_eq!(map[&37], "c");
1120     /// ```
1121     #[stable(feature = "rust1", since = "1.0.0")]
1122     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
1123         let hash = self.make_hash(&k);
1124         self.reserve(1);
1125         self.insert_hashed_nocheck(hash, k, v)
1126     }
1127
1128     /// Removes a key from the map, returning the value at the key if the key
1129     /// was previously in the map.
1130     ///
1131     /// The key may be any borrowed form of the map's key type, but
1132     /// `Hash` and `Eq` on the borrowed form *must* match those for
1133     /// the key type.
1134     ///
1135     /// # Examples
1136     ///
1137     /// ```
1138     /// use std::collections::HashMap;
1139     ///
1140     /// let mut map = HashMap::new();
1141     /// map.insert(1, "a");
1142     /// assert_eq!(map.remove(&1), Some("a"));
1143     /// assert_eq!(map.remove(&1), None);
1144     /// ```
1145     #[stable(feature = "rust1", since = "1.0.0")]
1146     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
1147         where K: Borrow<Q>, Q: Hash + Eq
1148     {
1149         if self.table.size() == 0 {
1150             return None
1151         }
1152
1153         self.search_mut(k).into_occupied_bucket().map(|bucket| pop_internal(bucket).1)
1154     }
1155 }
1156
1157 #[stable(feature = "rust1", since = "1.0.0")]
1158 impl<K, V, S> PartialEq for HashMap<K, V, S>
1159     where K: Eq + Hash, V: PartialEq, S: BuildHasher
1160 {
1161     fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1162         if self.len() != other.len() { return false; }
1163
1164         self.iter().all(|(key, value)|
1165             other.get(key).map_or(false, |v| *value == *v)
1166         )
1167     }
1168 }
1169
1170 #[stable(feature = "rust1", since = "1.0.0")]
1171 impl<K, V, S> Eq for HashMap<K, V, S>
1172     where K: Eq + Hash, V: Eq, S: BuildHasher
1173 {}
1174
1175 #[stable(feature = "rust1", since = "1.0.0")]
1176 impl<K, V, S> Debug for HashMap<K, V, S>
1177     where K: Eq + Hash + Debug, V: Debug, S: BuildHasher
1178 {
1179     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1180         f.debug_map().entries(self.iter()).finish()
1181     }
1182 }
1183
1184 #[stable(feature = "rust1", since = "1.0.0")]
1185 impl<K, V, S> Default for HashMap<K, V, S>
1186     where K: Eq + Hash,
1187           S: BuildHasher + Default,
1188 {
1189     fn default() -> HashMap<K, V, S> {
1190         HashMap::with_hasher(Default::default())
1191     }
1192 }
1193
1194 #[stable(feature = "rust1", since = "1.0.0")]
1195 impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S>
1196     where K: Eq + Hash + Borrow<Q>,
1197           Q: Eq + Hash,
1198           S: BuildHasher,
1199 {
1200     type Output = V;
1201
1202     #[inline]
1203     fn index(&self, index: &Q) -> &V {
1204         self.get(index).expect("no entry found for key")
1205     }
1206 }
1207
1208 /// HashMap iterator.
1209 #[stable(feature = "rust1", since = "1.0.0")]
1210 pub struct Iter<'a, K: 'a, V: 'a> {
1211     inner: table::Iter<'a, K, V>
1212 }
1213
1214 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1215 #[stable(feature = "rust1", since = "1.0.0")]
1216 impl<'a, K, V> Clone for Iter<'a, K, V> {
1217     fn clone(&self) -> Iter<'a, K, V> {
1218         Iter {
1219             inner: self.inner.clone()
1220         }
1221     }
1222 }
1223
1224 /// HashMap mutable values iterator.
1225 #[stable(feature = "rust1", since = "1.0.0")]
1226 pub struct IterMut<'a, K: 'a, V: 'a> {
1227     inner: table::IterMut<'a, K, V>
1228 }
1229
1230 /// HashMap move iterator.
1231 #[stable(feature = "rust1", since = "1.0.0")]
1232 pub struct IntoIter<K, V> {
1233     inner: iter::Map<table::IntoIter<K, V>, fn((SafeHash, K, V)) -> (K, V)>
1234 }
1235
1236 /// HashMap keys iterator.
1237 #[stable(feature = "rust1", since = "1.0.0")]
1238 pub struct Keys<'a, K: 'a, V: 'a> {
1239     inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
1240 }
1241
1242 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1243 #[stable(feature = "rust1", since = "1.0.0")]
1244 impl<'a, K, V> Clone for Keys<'a, K, V> {
1245     fn clone(&self) -> Keys<'a, K, V> {
1246         Keys {
1247             inner: self.inner.clone()
1248         }
1249     }
1250 }
1251
1252 /// HashMap values iterator.
1253 #[stable(feature = "rust1", since = "1.0.0")]
1254 pub struct Values<'a, K: 'a, V: 'a> {
1255     inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
1256 }
1257
1258 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1259 #[stable(feature = "rust1", since = "1.0.0")]
1260 impl<'a, K, V> Clone for Values<'a, K, V> {
1261     fn clone(&self) -> Values<'a, K, V> {
1262         Values {
1263             inner: self.inner.clone()
1264         }
1265     }
1266 }
1267
1268 /// HashMap drain iterator.
1269 #[stable(feature = "drain", since = "1.6.0")]
1270 pub struct Drain<'a, K: 'a, V: 'a> {
1271     inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)>
1272 }
1273
1274 enum InternalEntry<K, V, M> {
1275     Occupied {
1276         elem: FullBucket<K, V, M>,
1277     },
1278     Vacant {
1279         hash: SafeHash,
1280         elem: VacantEntryState<K, V, M>,
1281     },
1282     TableIsEmpty,
1283 }
1284
1285 impl<K, V, M> InternalEntry<K, V, M> {
1286     #[inline]
1287     fn into_occupied_bucket(self) -> Option<FullBucket<K, V, M>> {
1288         match self {
1289             InternalEntry::Occupied { elem } => Some(elem),
1290             _ => None,
1291         }
1292     }
1293 }
1294
1295 impl<'a, K, V> InternalEntry<K, V, &'a mut RawTable<K, V>> {
1296     #[inline]
1297     fn into_entry(self, key: K) -> Option<Entry<'a, K, V>> {
1298         match self {
1299             InternalEntry::Occupied { elem } => {
1300                 Some(Occupied(OccupiedEntry {
1301                     key: Some(key),
1302                     elem: elem
1303                 }))
1304             }
1305             InternalEntry::Vacant { hash, elem } => {
1306                 Some(Vacant(VacantEntry {
1307                     hash: hash,
1308                     key: key,
1309                     elem: elem,
1310                 }))
1311             }
1312             InternalEntry::TableIsEmpty => None
1313         }
1314     }
1315 }
1316
1317 /// A view into a single location in a map, which may be vacant or occupied.
1318 #[stable(feature = "rust1", since = "1.0.0")]
1319 pub enum Entry<'a, K: 'a, V: 'a> {
1320     /// An occupied Entry.
1321     #[stable(feature = "rust1", since = "1.0.0")]
1322     Occupied(
1323         #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>
1324     ),
1325
1326     /// A vacant Entry.
1327     #[stable(feature = "rust1", since = "1.0.0")]
1328     Vacant(
1329         #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>
1330     ),
1331 }
1332
1333 /// A view into a single occupied location in a HashMap.
1334 #[stable(feature = "rust1", since = "1.0.0")]
1335 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1336     key: Option<K>,
1337     elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
1338 }
1339
1340 /// A view into a single empty location in a HashMap.
1341 #[stable(feature = "rust1", since = "1.0.0")]
1342 pub struct VacantEntry<'a, K: 'a, V: 'a> {
1343     hash: SafeHash,
1344     key: K,
1345     elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
1346 }
1347
1348 /// Possible states of a VacantEntry.
1349 enum VacantEntryState<K, V, M> {
1350     /// The index is occupied, but the key to insert has precedence,
1351     /// and will kick the current one out on insertion.
1352     NeqElem(FullBucket<K, V, M>, usize),
1353     /// The index is genuinely vacant.
1354     NoElem(EmptyBucket<K, V, M>),
1355 }
1356
1357 #[stable(feature = "rust1", since = "1.0.0")]
1358 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>
1359     where K: Eq + Hash, S: BuildHasher
1360 {
1361     type Item = (&'a K, &'a V);
1362     type IntoIter = Iter<'a, K, V>;
1363
1364     fn into_iter(self) -> Iter<'a, K, V> {
1365         self.iter()
1366     }
1367 }
1368
1369 #[stable(feature = "rust1", since = "1.0.0")]
1370 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>
1371     where K: Eq + Hash, S: BuildHasher
1372 {
1373     type Item = (&'a K, &'a mut V);
1374     type IntoIter = IterMut<'a, K, V>;
1375
1376     fn into_iter(mut self) -> IterMut<'a, K, V> {
1377         self.iter_mut()
1378     }
1379 }
1380
1381 #[stable(feature = "rust1", since = "1.0.0")]
1382 impl<K, V, S> IntoIterator for HashMap<K, V, S>
1383     where K: Eq + Hash, S: BuildHasher
1384 {
1385     type Item = (K, V);
1386     type IntoIter = IntoIter<K, V>;
1387
1388     /// Creates a consuming iterator, that is, one that moves each key-value
1389     /// pair out of the map in arbitrary order. The map cannot be used after
1390     /// calling this.
1391     ///
1392     /// # Examples
1393     ///
1394     /// ```
1395     /// use std::collections::HashMap;
1396     ///
1397     /// let mut map = HashMap::new();
1398     /// map.insert("a", 1);
1399     /// map.insert("b", 2);
1400     /// map.insert("c", 3);
1401     ///
1402     /// // Not possible with .iter()
1403     /// let vec: Vec<(&str, isize)> = map.into_iter().collect();
1404     /// ```
1405     fn into_iter(self) -> IntoIter<K, V> {
1406         fn last_two<A, B, C>((_, b, c): (A, B, C)) -> (B, C) { (b, c) }
1407         let last_two: fn((SafeHash, K, V)) -> (K, V) = last_two;
1408
1409         IntoIter {
1410             inner: self.table.into_iter().map(last_two)
1411         }
1412     }
1413 }
1414
1415 #[stable(feature = "rust1", since = "1.0.0")]
1416 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1417     type Item = (&'a K, &'a V);
1418
1419     #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
1420     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1421 }
1422 #[stable(feature = "rust1", since = "1.0.0")]
1423 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
1424     #[inline] fn len(&self) -> usize { self.inner.len() }
1425 }
1426
1427 #[stable(feature = "rust1", since = "1.0.0")]
1428 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1429     type Item = (&'a K, &'a mut V);
1430
1431     #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
1432     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1433 }
1434 #[stable(feature = "rust1", since = "1.0.0")]
1435 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1436     #[inline] fn len(&self) -> usize { self.inner.len() }
1437 }
1438
1439 #[stable(feature = "rust1", since = "1.0.0")]
1440 impl<K, V> Iterator for IntoIter<K, V> {
1441     type Item = (K, V);
1442
1443     #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1444     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1445 }
1446 #[stable(feature = "rust1", since = "1.0.0")]
1447 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1448     #[inline] fn len(&self) -> usize { self.inner.len() }
1449 }
1450
1451 #[stable(feature = "rust1", since = "1.0.0")]
1452 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1453     type Item = &'a K;
1454
1455     #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
1456     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1457 }
1458 #[stable(feature = "rust1", since = "1.0.0")]
1459 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
1460     #[inline] fn len(&self) -> usize { self.inner.len() }
1461 }
1462
1463 #[stable(feature = "rust1", since = "1.0.0")]
1464 impl<'a, K, V> Iterator for Values<'a, K, V> {
1465     type Item = &'a V;
1466
1467     #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
1468     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1469 }
1470 #[stable(feature = "rust1", since = "1.0.0")]
1471 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
1472     #[inline] fn len(&self) -> usize { self.inner.len() }
1473 }
1474
1475 #[stable(feature = "rust1", since = "1.0.0")]
1476 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1477     type Item = (K, V);
1478
1479     #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
1480     #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
1481 }
1482 #[stable(feature = "rust1", since = "1.0.0")]
1483 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1484     #[inline] fn len(&self) -> usize { self.inner.len() }
1485 }
1486
1487 impl<'a, K, V> Entry<'a, K, V> {
1488     #[stable(feature = "rust1", since = "1.0.0")]
1489     /// Ensures a value is in the entry by inserting the default if empty, and returns
1490     /// a mutable reference to the value in the entry.
1491     pub fn or_insert(self, default: V) -> &'a mut V {
1492         match self {
1493             Occupied(entry) => entry.into_mut(),
1494             Vacant(entry) => entry.insert(default),
1495         }
1496     }
1497
1498     #[stable(feature = "rust1", since = "1.0.0")]
1499     /// Ensures a value is in the entry by inserting the result of the default function if empty,
1500     /// and returns a mutable reference to the value in the entry.
1501     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1502         match self {
1503             Occupied(entry) => entry.into_mut(),
1504             Vacant(entry) => entry.insert(default()),
1505         }
1506     }
1507 }
1508
1509 impl<'a, K, V> OccupiedEntry<'a, K, V> {
1510     /// Gets a reference to the key in the entry.
1511     #[unstable(feature = "map_entry_keys", issue = "32281")]
1512     pub fn key(&self) -> &K {
1513         self.elem.read().0
1514     }
1515
1516     /// Gets a reference to the value in the entry.
1517     #[stable(feature = "rust1", since = "1.0.0")]
1518     pub fn get(&self) -> &V {
1519         self.elem.read().1
1520     }
1521
1522     /// Gets a mutable reference to the value in the entry.
1523     #[stable(feature = "rust1", since = "1.0.0")]
1524     pub fn get_mut(&mut self) -> &mut V {
1525         self.elem.read_mut().1
1526     }
1527
1528     /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1529     /// with a lifetime bound to the map itself
1530     #[stable(feature = "rust1", since = "1.0.0")]
1531     pub fn into_mut(self) -> &'a mut V {
1532         self.elem.into_mut_refs().1
1533     }
1534
1535     /// Sets the value of the entry, and returns the entry's old value
1536     #[stable(feature = "rust1", since = "1.0.0")]
1537     pub fn insert(&mut self, mut value: V) -> V {
1538         let old_value = self.get_mut();
1539         mem::swap(&mut value, old_value);
1540         value
1541     }
1542
1543     /// Takes the value out of the entry, and returns it
1544     #[stable(feature = "rust1", since = "1.0.0")]
1545     pub fn remove(self) -> V {
1546         pop_internal(self.elem).1
1547     }
1548     /// Returns a key that was used for search.
1549     ///
1550     /// The key was retained for further use.
1551     fn take_key(&mut self) -> Option<K> {
1552         self.key.take()
1553     }
1554 }
1555
1556 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
1557     /// Gets a reference to the key that would be used when inserting a value
1558     /// through the VacantEntry.
1559     #[unstable(feature = "map_entry_keys", issue = "32281")]
1560     pub fn key(&self) -> &K {
1561         &self.key
1562     }
1563
1564     /// Sets the value of the entry with the VacantEntry's key,
1565     /// and returns a mutable reference to it
1566     #[stable(feature = "rust1", since = "1.0.0")]
1567     pub fn insert(self, value: V) -> &'a mut V {
1568         match self.elem {
1569             NeqElem(bucket, ib) => {
1570                 robin_hood(bucket, ib, self.hash, self.key, value)
1571             }
1572             NoElem(bucket) => {
1573                 bucket.put(self.hash, self.key, value).into_mut_refs().1
1574             }
1575         }
1576     }
1577 }
1578
1579 #[stable(feature = "rust1", since = "1.0.0")]
1580 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
1581     where K: Eq + Hash, S: BuildHasher + Default
1582 {
1583     fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> HashMap<K, V, S> {
1584         let iter = iterable.into_iter();
1585         let lower = iter.size_hint().0;
1586         let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
1587         map.extend(iter);
1588         map
1589     }
1590 }
1591
1592 #[stable(feature = "rust1", since = "1.0.0")]
1593 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
1594     where K: Eq + Hash, S: BuildHasher
1595 {
1596     fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
1597         for (k, v) in iter {
1598             self.insert(k, v);
1599         }
1600     }
1601 }
1602
1603 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
1604 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
1605     where K: Eq + Hash + Copy, V: Copy, S: BuildHasher
1606 {
1607     fn extend<T: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: T) {
1608         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1609     }
1610 }
1611
1612 /// `RandomState` is the default state for `HashMap` types.
1613 ///
1614 /// A particular instance `RandomState` will create the same instances of
1615 /// `Hasher`, but the hashers created by two different `RandomState`
1616 /// instances are unlikely to produce the same result for the same values.
1617 #[derive(Clone)]
1618 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1619 pub struct RandomState {
1620     k0: u64,
1621     k1: u64,
1622 }
1623
1624 impl RandomState {
1625     /// Constructs a new `RandomState` that is initialized with random keys.
1626     #[inline]
1627     #[allow(deprecated)] // rand
1628     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1629     pub fn new() -> RandomState {
1630         let mut r = rand::thread_rng();
1631         RandomState { k0: r.gen(), k1: r.gen() }
1632     }
1633 }
1634
1635 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
1636 impl BuildHasher for RandomState {
1637     type Hasher = SipHasher;
1638     #[inline]
1639     fn build_hasher(&self) -> SipHasher {
1640         SipHasher::new_with_keys(self.k0, self.k1)
1641     }
1642 }
1643
1644 #[stable(feature = "rust1", since = "1.0.0")]
1645 impl Default for RandomState {
1646     #[inline]
1647     fn default() -> RandomState {
1648         RandomState::new()
1649     }
1650 }
1651
1652 impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
1653     where K: Eq + Hash + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
1654 {
1655     type Key = K;
1656
1657     fn get(&self, key: &Q) -> Option<&K> {
1658         self.search(key).into_occupied_bucket().map(|bucket| bucket.into_refs().0)
1659     }
1660
1661     fn take(&mut self, key: &Q) -> Option<K> {
1662         if self.table.size() == 0 {
1663             return None
1664         }
1665
1666         self.search_mut(key).into_occupied_bucket().map(|bucket| pop_internal(bucket).0)
1667     }
1668
1669     fn replace(&mut self, key: K) -> Option<K> {
1670         self.reserve(1);
1671
1672         match self.entry(key) {
1673             Occupied(mut occupied) => {
1674                 let key = occupied.take_key().unwrap();
1675                 Some(mem::replace(occupied.elem.read_mut().0, key))
1676             }
1677             Vacant(vacant) => {
1678                 vacant.insert(());
1679                 None
1680             }
1681         }
1682     }
1683 }
1684
1685 #[cfg(test)]
1686 mod test_map {
1687     use prelude::v1::*;
1688
1689     use super::HashMap;
1690     use super::Entry::{Occupied, Vacant};
1691     use cell::RefCell;
1692     use rand::{thread_rng, Rng};
1693
1694     #[test]
1695     fn test_create_capacity_zero() {
1696         let mut m = HashMap::with_capacity(0);
1697
1698         assert!(m.insert(1, 1).is_none());
1699
1700         assert!(m.contains_key(&1));
1701         assert!(!m.contains_key(&0));
1702     }
1703
1704     #[test]
1705     fn test_insert() {
1706         let mut m = HashMap::new();
1707         assert_eq!(m.len(), 0);
1708         assert!(m.insert(1, 2).is_none());
1709         assert_eq!(m.len(), 1);
1710         assert!(m.insert(2, 4).is_none());
1711         assert_eq!(m.len(), 2);
1712         assert_eq!(*m.get(&1).unwrap(), 2);
1713         assert_eq!(*m.get(&2).unwrap(), 4);
1714     }
1715
1716     #[test]
1717     fn test_clone() {
1718         let mut m = HashMap::new();
1719         assert_eq!(m.len(), 0);
1720         assert!(m.insert(1, 2).is_none());
1721         assert_eq!(m.len(), 1);
1722         assert!(m.insert(2, 4).is_none());
1723         assert_eq!(m.len(), 2);
1724         let m2 = m.clone();
1725         assert_eq!(*m2.get(&1).unwrap(), 2);
1726         assert_eq!(*m2.get(&2).unwrap(), 4);
1727         assert_eq!(m2.len(), 2);
1728     }
1729
1730     thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
1731
1732     #[derive(Hash, PartialEq, Eq)]
1733     struct Dropable {
1734         k: usize
1735     }
1736
1737     impl Dropable {
1738         fn new(k: usize) -> Dropable {
1739             DROP_VECTOR.with(|slot| {
1740                 slot.borrow_mut()[k] += 1;
1741             });
1742
1743             Dropable { k: k }
1744         }
1745     }
1746
1747     impl Drop for Dropable {
1748         fn drop(&mut self) {
1749             DROP_VECTOR.with(|slot| {
1750                 slot.borrow_mut()[self.k] -= 1;
1751             });
1752         }
1753     }
1754
1755     impl Clone for Dropable {
1756         fn clone(&self) -> Dropable {
1757             Dropable::new(self.k)
1758         }
1759     }
1760
1761     #[test]
1762     fn test_drops() {
1763         DROP_VECTOR.with(|slot| {
1764             *slot.borrow_mut() = vec![0; 200];
1765         });
1766
1767         {
1768             let mut m = HashMap::new();
1769
1770             DROP_VECTOR.with(|v| {
1771                 for i in 0..200 {
1772                     assert_eq!(v.borrow()[i], 0);
1773                 }
1774             });
1775
1776             for i in 0..100 {
1777                 let d1 = Dropable::new(i);
1778                 let d2 = Dropable::new(i+100);
1779                 m.insert(d1, d2);
1780             }
1781
1782             DROP_VECTOR.with(|v| {
1783                 for i in 0..200 {
1784                     assert_eq!(v.borrow()[i], 1);
1785                 }
1786             });
1787
1788             for i in 0..50 {
1789                 let k = Dropable::new(i);
1790                 let v = m.remove(&k);
1791
1792                 assert!(v.is_some());
1793
1794                 DROP_VECTOR.with(|v| {
1795                     assert_eq!(v.borrow()[i], 1);
1796                     assert_eq!(v.borrow()[i+100], 1);
1797                 });
1798             }
1799
1800             DROP_VECTOR.with(|v| {
1801                 for i in 0..50 {
1802                     assert_eq!(v.borrow()[i], 0);
1803                     assert_eq!(v.borrow()[i+100], 0);
1804                 }
1805
1806                 for i in 50..100 {
1807                     assert_eq!(v.borrow()[i], 1);
1808                     assert_eq!(v.borrow()[i+100], 1);
1809                 }
1810             });
1811         }
1812
1813         DROP_VECTOR.with(|v| {
1814             for i in 0..200 {
1815                 assert_eq!(v.borrow()[i], 0);
1816             }
1817         });
1818     }
1819
1820     #[test]
1821     fn test_into_iter_drops() {
1822         DROP_VECTOR.with(|v| {
1823             *v.borrow_mut() = vec![0; 200];
1824         });
1825
1826         let hm = {
1827             let mut hm = HashMap::new();
1828
1829             DROP_VECTOR.with(|v| {
1830                 for i in 0..200 {
1831                     assert_eq!(v.borrow()[i], 0);
1832                 }
1833             });
1834
1835             for i in 0..100 {
1836                 let d1 = Dropable::new(i);
1837                 let d2 = Dropable::new(i+100);
1838                 hm.insert(d1, d2);
1839             }
1840
1841             DROP_VECTOR.with(|v| {
1842                 for i in 0..200 {
1843                     assert_eq!(v.borrow()[i], 1);
1844                 }
1845             });
1846
1847             hm
1848         };
1849
1850         // By the way, ensure that cloning doesn't screw up the dropping.
1851         drop(hm.clone());
1852
1853         {
1854             let mut half = hm.into_iter().take(50);
1855
1856             DROP_VECTOR.with(|v| {
1857                 for i in 0..200 {
1858                     assert_eq!(v.borrow()[i], 1);
1859                 }
1860             });
1861
1862             for _ in half.by_ref() {}
1863
1864             DROP_VECTOR.with(|v| {
1865                 let nk = (0..100).filter(|&i| {
1866                     v.borrow()[i] == 1
1867                 }).count();
1868
1869                 let nv = (0..100).filter(|&i| {
1870                     v.borrow()[i+100] == 1
1871                 }).count();
1872
1873                 assert_eq!(nk, 50);
1874                 assert_eq!(nv, 50);
1875             });
1876         };
1877
1878         DROP_VECTOR.with(|v| {
1879             for i in 0..200 {
1880                 assert_eq!(v.borrow()[i], 0);
1881             }
1882         });
1883     }
1884
1885     #[test]
1886     fn test_empty_remove() {
1887         let mut m: HashMap<isize, bool> = HashMap::new();
1888         assert_eq!(m.remove(&0), None);
1889     }
1890
1891     #[test]
1892     fn test_empty_entry() {
1893         let mut m: HashMap<isize, bool> = HashMap::new();
1894         match m.entry(0) {
1895             Occupied(_) => panic!(),
1896             Vacant(_) => {}
1897         }
1898         assert!(*m.entry(0).or_insert(true));
1899         assert_eq!(m.len(), 1);
1900     }
1901
1902     #[test]
1903     fn test_empty_iter() {
1904         let mut m: HashMap<isize, bool> = HashMap::new();
1905         assert_eq!(m.drain().next(), None);
1906         assert_eq!(m.keys().next(), None);
1907         assert_eq!(m.values().next(), None);
1908         assert_eq!(m.iter().next(), None);
1909         assert_eq!(m.iter_mut().next(), None);
1910         assert_eq!(m.len(), 0);
1911         assert!(m.is_empty());
1912         assert_eq!(m.into_iter().next(), None);
1913     }
1914
1915     #[test]
1916     fn test_lots_of_insertions() {
1917         let mut m = HashMap::new();
1918
1919         // Try this a few times to make sure we never screw up the hashmap's
1920         // internal state.
1921         for _ in 0..10 {
1922             assert!(m.is_empty());
1923
1924             for i in 1..1001 {
1925                 assert!(m.insert(i, i).is_none());
1926
1927                 for j in 1..i+1 {
1928                     let r = m.get(&j);
1929                     assert_eq!(r, Some(&j));
1930                 }
1931
1932                 for j in i+1..1001 {
1933                     let r = m.get(&j);
1934                     assert_eq!(r, None);
1935                 }
1936             }
1937
1938             for i in 1001..2001 {
1939                 assert!(!m.contains_key(&i));
1940             }
1941
1942             // remove forwards
1943             for i in 1..1001 {
1944                 assert!(m.remove(&i).is_some());
1945
1946                 for j in 1..i+1 {
1947                     assert!(!m.contains_key(&j));
1948                 }
1949
1950                 for j in i+1..1001 {
1951                     assert!(m.contains_key(&j));
1952                 }
1953             }
1954
1955             for i in 1..1001 {
1956                 assert!(!m.contains_key(&i));
1957             }
1958
1959             for i in 1..1001 {
1960                 assert!(m.insert(i, i).is_none());
1961             }
1962
1963             // remove backwards
1964             for i in (1..1001).rev() {
1965                 assert!(m.remove(&i).is_some());
1966
1967                 for j in i..1001 {
1968                     assert!(!m.contains_key(&j));
1969                 }
1970
1971                 for j in 1..i {
1972                     assert!(m.contains_key(&j));
1973                 }
1974             }
1975         }
1976     }
1977
1978     #[test]
1979     fn test_find_mut() {
1980         let mut m = HashMap::new();
1981         assert!(m.insert(1, 12).is_none());
1982         assert!(m.insert(2, 8).is_none());
1983         assert!(m.insert(5, 14).is_none());
1984         let new = 100;
1985         match m.get_mut(&5) {
1986             None => panic!(), Some(x) => *x = new
1987         }
1988         assert_eq!(m.get(&5), Some(&new));
1989     }
1990
1991     #[test]
1992     fn test_insert_overwrite() {
1993         let mut m = HashMap::new();
1994         assert!(m.insert(1, 2).is_none());
1995         assert_eq!(*m.get(&1).unwrap(), 2);
1996         assert!(!m.insert(1, 3).is_none());
1997         assert_eq!(*m.get(&1).unwrap(), 3);
1998     }
1999
2000     #[test]
2001     fn test_insert_conflicts() {
2002         let mut m = HashMap::with_capacity(4);
2003         assert!(m.insert(1, 2).is_none());
2004         assert!(m.insert(5, 3).is_none());
2005         assert!(m.insert(9, 4).is_none());
2006         assert_eq!(*m.get(&9).unwrap(), 4);
2007         assert_eq!(*m.get(&5).unwrap(), 3);
2008         assert_eq!(*m.get(&1).unwrap(), 2);
2009     }
2010
2011     #[test]
2012     fn test_conflict_remove() {
2013         let mut m = HashMap::with_capacity(4);
2014         assert!(m.insert(1, 2).is_none());
2015         assert_eq!(*m.get(&1).unwrap(), 2);
2016         assert!(m.insert(5, 3).is_none());
2017         assert_eq!(*m.get(&1).unwrap(), 2);
2018         assert_eq!(*m.get(&5).unwrap(), 3);
2019         assert!(m.insert(9, 4).is_none());
2020         assert_eq!(*m.get(&1).unwrap(), 2);
2021         assert_eq!(*m.get(&5).unwrap(), 3);
2022         assert_eq!(*m.get(&9).unwrap(), 4);
2023         assert!(m.remove(&1).is_some());
2024         assert_eq!(*m.get(&9).unwrap(), 4);
2025         assert_eq!(*m.get(&5).unwrap(), 3);
2026     }
2027
2028     #[test]
2029     fn test_is_empty() {
2030         let mut m = HashMap::with_capacity(4);
2031         assert!(m.insert(1, 2).is_none());
2032         assert!(!m.is_empty());
2033         assert!(m.remove(&1).is_some());
2034         assert!(m.is_empty());
2035     }
2036
2037     #[test]
2038     fn test_pop() {
2039         let mut m = HashMap::new();
2040         m.insert(1, 2);
2041         assert_eq!(m.remove(&1), Some(2));
2042         assert_eq!(m.remove(&1), None);
2043     }
2044
2045     #[test]
2046     fn test_iterate() {
2047         let mut m = HashMap::with_capacity(4);
2048         for i in 0..32 {
2049             assert!(m.insert(i, i*2).is_none());
2050         }
2051         assert_eq!(m.len(), 32);
2052
2053         let mut observed: u32 = 0;
2054
2055         for (k, v) in &m {
2056             assert_eq!(*v, *k * 2);
2057             observed |= 1 << *k;
2058         }
2059         assert_eq!(observed, 0xFFFF_FFFF);
2060     }
2061
2062     #[test]
2063     fn test_keys() {
2064         let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2065         let map: HashMap<_, _> = vec.into_iter().collect();
2066         let keys: Vec<_> = map.keys().cloned().collect();
2067         assert_eq!(keys.len(), 3);
2068         assert!(keys.contains(&1));
2069         assert!(keys.contains(&2));
2070         assert!(keys.contains(&3));
2071     }
2072
2073     #[test]
2074     fn test_values() {
2075         let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
2076         let map: HashMap<_, _> = vec.into_iter().collect();
2077         let values: Vec<_> = map.values().cloned().collect();
2078         assert_eq!(values.len(), 3);
2079         assert!(values.contains(&'a'));
2080         assert!(values.contains(&'b'));
2081         assert!(values.contains(&'c'));
2082     }
2083
2084     #[test]
2085     fn test_find() {
2086         let mut m = HashMap::new();
2087         assert!(m.get(&1).is_none());
2088         m.insert(1, 2);
2089         match m.get(&1) {
2090             None => panic!(),
2091             Some(v) => assert_eq!(*v, 2)
2092         }
2093     }
2094
2095     #[test]
2096     fn test_eq() {
2097         let mut m1 = HashMap::new();
2098         m1.insert(1, 2);
2099         m1.insert(2, 3);
2100         m1.insert(3, 4);
2101
2102         let mut m2 = HashMap::new();
2103         m2.insert(1, 2);
2104         m2.insert(2, 3);
2105
2106         assert!(m1 != m2);
2107
2108         m2.insert(3, 4);
2109
2110         assert_eq!(m1, m2);
2111     }
2112
2113     #[test]
2114     fn test_show() {
2115         let mut map = HashMap::new();
2116         let empty: HashMap<i32, i32> = HashMap::new();
2117
2118         map.insert(1, 2);
2119         map.insert(3, 4);
2120
2121         let map_str = format!("{:?}", map);
2122
2123         assert!(map_str == "{1: 2, 3: 4}" ||
2124                 map_str == "{3: 4, 1: 2}");
2125         assert_eq!(format!("{:?}", empty), "{}");
2126     }
2127
2128     #[test]
2129     fn test_expand() {
2130         let mut m = HashMap::new();
2131
2132         assert_eq!(m.len(), 0);
2133         assert!(m.is_empty());
2134
2135         let mut i = 0;
2136         let old_cap = m.table.capacity();
2137         while old_cap == m.table.capacity() {
2138             m.insert(i, i);
2139             i += 1;
2140         }
2141
2142         assert_eq!(m.len(), i);
2143         assert!(!m.is_empty());
2144     }
2145
2146     #[test]
2147     fn test_behavior_resize_policy() {
2148         let mut m = HashMap::new();
2149
2150         assert_eq!(m.len(), 0);
2151         assert_eq!(m.table.capacity(), 0);
2152         assert!(m.is_empty());
2153
2154         m.insert(0, 0);
2155         m.remove(&0);
2156         assert!(m.is_empty());
2157         let initial_cap = m.table.capacity();
2158         m.reserve(initial_cap);
2159         let cap = m.table.capacity();
2160
2161         assert_eq!(cap, initial_cap * 2);
2162
2163         let mut i = 0;
2164         for _ in 0..cap * 3 / 4 {
2165             m.insert(i, i);
2166             i += 1;
2167         }
2168         // three quarters full
2169
2170         assert_eq!(m.len(), i);
2171         assert_eq!(m.table.capacity(), cap);
2172
2173         for _ in 0..cap / 4 {
2174             m.insert(i, i);
2175             i += 1;
2176         }
2177         // half full
2178
2179         let new_cap = m.table.capacity();
2180         assert_eq!(new_cap, cap * 2);
2181
2182         for _ in 0..cap / 2 - 1 {
2183             i -= 1;
2184             m.remove(&i);
2185             assert_eq!(m.table.capacity(), new_cap);
2186         }
2187         // A little more than one quarter full.
2188         m.shrink_to_fit();
2189         assert_eq!(m.table.capacity(), cap);
2190         // again, a little more than half full
2191         for _ in 0..cap / 2 - 1 {
2192             i -= 1;
2193             m.remove(&i);
2194         }
2195         m.shrink_to_fit();
2196
2197         assert_eq!(m.len(), i);
2198         assert!(!m.is_empty());
2199         assert_eq!(m.table.capacity(), initial_cap);
2200     }
2201
2202     #[test]
2203     fn test_reserve_shrink_to_fit() {
2204         let mut m = HashMap::new();
2205         m.insert(0, 0);
2206         m.remove(&0);
2207         assert!(m.capacity() >= m.len());
2208         for i in 0..128 {
2209             m.insert(i, i);
2210         }
2211         m.reserve(256);
2212
2213         let usable_cap = m.capacity();
2214         for i in 128..(128 + 256) {
2215             m.insert(i, i);
2216             assert_eq!(m.capacity(), usable_cap);
2217         }
2218
2219         for i in 100..(128 + 256) {
2220             assert_eq!(m.remove(&i), Some(i));
2221         }
2222         m.shrink_to_fit();
2223
2224         assert_eq!(m.len(), 100);
2225         assert!(!m.is_empty());
2226         assert!(m.capacity() >= m.len());
2227
2228         for i in 0..100 {
2229             assert_eq!(m.remove(&i), Some(i));
2230         }
2231         m.shrink_to_fit();
2232         m.insert(0, 0);
2233
2234         assert_eq!(m.len(), 1);
2235         assert!(m.capacity() >= m.len());
2236         assert_eq!(m.remove(&0), Some(0));
2237     }
2238
2239     #[test]
2240     fn test_from_iter() {
2241         let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2242
2243         let map: HashMap<_, _> = xs.iter().cloned().collect();
2244
2245         for &(k, v) in &xs {
2246             assert_eq!(map.get(&k), Some(&v));
2247         }
2248     }
2249
2250     #[test]
2251     fn test_size_hint() {
2252         let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2253
2254         let map: HashMap<_, _>  = xs.iter().cloned().collect();
2255
2256         let mut iter = map.iter();
2257
2258         for _ in iter.by_ref().take(3) {}
2259
2260         assert_eq!(iter.size_hint(), (3, Some(3)));
2261     }
2262
2263     #[test]
2264     fn test_iter_len() {
2265         let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2266
2267         let map: HashMap<_, _>  = xs.iter().cloned().collect();
2268
2269         let mut iter = map.iter();
2270
2271         for _ in iter.by_ref().take(3) {}
2272
2273         assert_eq!(iter.len(), 3);
2274     }
2275
2276     #[test]
2277     fn test_mut_size_hint() {
2278         let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2279
2280         let mut map: HashMap<_, _>  = xs.iter().cloned().collect();
2281
2282         let mut iter = map.iter_mut();
2283
2284         for _ in iter.by_ref().take(3) {}
2285
2286         assert_eq!(iter.size_hint(), (3, Some(3)));
2287     }
2288
2289     #[test]
2290     fn test_iter_mut_len() {
2291         let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
2292
2293         let mut map: HashMap<_, _>  = xs.iter().cloned().collect();
2294
2295         let mut iter = map.iter_mut();
2296
2297         for _ in iter.by_ref().take(3) {}
2298
2299         assert_eq!(iter.len(), 3);
2300     }
2301
2302     #[test]
2303     fn test_index() {
2304         let mut map = HashMap::new();
2305
2306         map.insert(1, 2);
2307         map.insert(2, 1);
2308         map.insert(3, 4);
2309
2310         assert_eq!(map[&2], 1);
2311     }
2312
2313     #[test]
2314     #[should_panic]
2315     fn test_index_nonexistent() {
2316         let mut map = HashMap::new();
2317
2318         map.insert(1, 2);
2319         map.insert(2, 1);
2320         map.insert(3, 4);
2321
2322         map[&4];
2323     }
2324
2325     #[test]
2326     fn test_entry(){
2327         let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
2328
2329         let mut map: HashMap<_, _> = xs.iter().cloned().collect();
2330
2331         // Existing key (insert)
2332         match map.entry(1) {
2333             Vacant(_) => unreachable!(),
2334             Occupied(mut view) => {
2335                 assert_eq!(view.get(), &10);
2336                 assert_eq!(view.insert(100), 10);
2337             }
2338         }
2339         assert_eq!(map.get(&1).unwrap(), &100);
2340         assert_eq!(map.len(), 6);
2341
2342
2343         // Existing key (update)
2344         match map.entry(2) {
2345             Vacant(_) => unreachable!(),
2346             Occupied(mut view) => {
2347                 let v = view.get_mut();
2348                 let new_v = (*v) * 10;
2349                 *v = new_v;
2350             }
2351         }
2352         assert_eq!(map.get(&2).unwrap(), &200);
2353         assert_eq!(map.len(), 6);
2354
2355         // Existing key (take)
2356         match map.entry(3) {
2357             Vacant(_) => unreachable!(),
2358             Occupied(view) => {
2359                 assert_eq!(view.remove(), 30);
2360             }
2361         }
2362         assert_eq!(map.get(&3), None);
2363         assert_eq!(map.len(), 5);
2364
2365
2366         // Inexistent key (insert)
2367         match map.entry(10) {
2368             Occupied(_) => unreachable!(),
2369             Vacant(view) => {
2370                 assert_eq!(*view.insert(1000), 1000);
2371             }
2372         }
2373         assert_eq!(map.get(&10).unwrap(), &1000);
2374         assert_eq!(map.len(), 6);
2375     }
2376
2377     #[test]
2378     fn test_entry_take_doesnt_corrupt() {
2379         #![allow(deprecated)] //rand
2380         // Test for #19292
2381         fn check(m: &HashMap<isize, ()>) {
2382             for k in m.keys() {
2383                 assert!(m.contains_key(k),
2384                         "{} is in keys() but not in the map?", k);
2385             }
2386         }
2387
2388         let mut m = HashMap::new();
2389         let mut rng = thread_rng();
2390
2391         // Populate the map with some items.
2392         for _ in 0..50 {
2393             let x = rng.gen_range(-10, 10);
2394             m.insert(x, ());
2395         }
2396
2397         for i in 0..1000 {
2398             let x = rng.gen_range(-10, 10);
2399             match m.entry(x) {
2400                 Vacant(_) => {},
2401                 Occupied(e) => {
2402                     println!("{}: remove {}", i, x);
2403                     e.remove();
2404                 },
2405             }
2406
2407             check(&m);
2408         }
2409     }
2410
2411     #[test]
2412     fn test_extend_ref() {
2413         let mut a = HashMap::new();
2414         a.insert(1, "one");
2415         let mut b = HashMap::new();
2416         b.insert(2, "two");
2417         b.insert(3, "three");
2418
2419         a.extend(&b);
2420
2421         assert_eq!(a.len(), 3);
2422         assert_eq!(a[&1], "one");
2423         assert_eq!(a[&2], "two");
2424         assert_eq!(a[&3], "three");
2425     }
2426
2427     #[test]
2428     fn test_capacity_not_less_than_len() {
2429         let mut a = HashMap::new();
2430         let mut item = 0;
2431
2432         for _ in 0..116 {
2433             a.insert(item, 0);
2434             item += 1;
2435         }
2436
2437         assert!(a.capacity() > a.len());
2438
2439         let free = a.capacity() - a.len();
2440         for _ in 0..free {
2441             a.insert(item, 0);
2442             item += 1;
2443         }
2444
2445         assert_eq!(a.len(), a.capacity());
2446
2447         // Insert at capacity should cause allocation.
2448         a.insert(item, 0);
2449         assert!(a.capacity() > a.len());
2450     }
2451
2452     #[test]
2453     fn test_occupied_entry_key() {
2454         let mut a = HashMap::new();
2455         let key = "hello there";
2456         let value = "value goes here";
2457         assert!(a.is_empty());
2458         a.insert(key.clone(), value.clone());
2459         assert_eq!(a.len(), 1);
2460         assert_eq!(a[key], value);
2461
2462         match a.entry(key.clone()) {
2463             Vacant(_) => panic!(),
2464             Occupied(e) => assert_eq!(key, *e.key()),
2465         }
2466         assert_eq!(a.len(), 1);
2467         assert_eq!(a[key], value);
2468     }
2469
2470     #[test]
2471     fn test_vacant_entry_key() {
2472         let mut a = HashMap::new();
2473         let key = "hello there";
2474         let value = "value goes here";
2475
2476         assert!(a.is_empty());
2477         match a.entry(key.clone()) {
2478             Occupied(_) => panic!(),
2479             Vacant(e) => {
2480                 assert_eq!(key, *e.key());
2481                 e.insert(value.clone());
2482             },
2483         }
2484         assert_eq!(a.len(), 1);
2485         assert_eq!(a[key], value);
2486     }
2487 }