title: Hashmap len() not updated when element removed?
body: <p>I am somewhat tight on memory therefore I want to prevent a Hashmap I am using from reallocating space.</p>
  <p>I have:</p>
  <pre><code>const MAX_HAHSCAP: usize = 16 * 1024 * 1024;
  
  let mut posHash: HashMap&lt;usize, Vec&lt;CPos&gt;&gt; = HashMap::with_capacity(MAX_HASHCAP);
  </code></pre>
  <p>and later on I try to make sure that the HashMap never overflows. However, I keep having the condition that <code>posHash.len() &gt;= posHash.capacity()</code>. Hence I inserted some code to see what is going on:</p>
  <pre><code>assert!(posHash.contains_key(&amp;i));
  // make sure to remove the entry such that at least 1 slot remains free
  if posHash.len() &gt;= posHash.capacity() {
      match posHash.remove(&amp;i) {
         Some(_) =&gt; assert!(posHash.len() &lt; posHash.capacity()),   // &lt;-- this is violated
         None =&gt; {
            panic!(&quot;position #{} was not in the hash?&quot;, i);
         }
     };
  }
  </code></pre>
  <p>Sure enough, the assertion gets violated. (Interestingly, from logging output I know that the capacity() at this point is reported as 27487399, much more than the required 16777216.)
  What I am doing wrong here?</p>
  <p>Is it possible that the len() function is inaccurate? Is this a bug, maybe?</p>
  <p>EDIT: self contained minimal example</p>
  <pre><code>use std::collections::HashMap;
  
  pub const MAX_HASHCAP: usize = 16 * 1024 * 1024;
  
  pub fn main() {
      let mut hash: HashMap&lt;usize, Vec&lt;usize&gt;&gt; = HashMap::with_capacity(MAX_HASHCAP);
  
      println!(&quot;hash.len={} hash.capacity={}&quot;, hash.len(), hash.capacity());
  
      for u in 0usize..30_000_000 {
          assert!(hash.len() &lt; hash.capacity());
          let v = hash.entry(u).or_insert((u..u + 3).collect::&lt;Vec&lt;_&gt;&gt;());
          // let sum = v.iter().fold(0, |acc, n| acc + n);
          // v[1] = 42;
          assert!(hash.contains_key(&amp;u));
          if hash.len() &gt;= hash.capacity() {
              println!(
                  &quot;before remove: hash.len={} hash.capacity={}&quot;,
                  hash.len(),
                  hash.capacity()
              );
              hash.remove(&amp;u);
              println!(
                  &quot;after remove: hash.len={} hash.capacity={}&quot;,
                  hash.len(),
                  hash.capacity()
              );
          }
      }
  }
  </code></pre>
  <p>When run, the output will be:</p>
  <pre><code>hash.len=0 hash.capacity=29360128
  before remove: hash.len=29360128 hash.capacity=29360128
  after remove: hash.len=29360127 hash.capacity=29360127
  thread 'main' panicked at 'assertion failed: hash.len() &lt; hash.capacity()', src/main.rs:11:9
  note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
  </code></pre>
  <p>So the answer seems to be that it <strong>also</strong> reduces the capacity when removing the element that makes the hash full. This is remarkable, but as the docs say</p>
  <blockquote>
  <p>This number is a lower bound; the HashMap&lt;K, V&gt; might be able to hold
  more, but is guaranteed to be able to hold at least this many.</p>
  </blockquote>
  <p>it is probably okay. I was just not aware of the possibility that the capacity can go down anytime.</p>