title: Faster HashMap for sequential keys
body: <p>Initially I was very surprised to find out Rust's <code>HashMap</code>, even with the <code>FNV</code> hasher, was considerably slower than the equivalents in Java, .NET, PHP. I am talking about optimized <strong>Release</strong> mode, not Debug mode. I did some calculations and realized the timings in Java/.NET/PHP were suspiciously low. Then it hit me - even though I was testing with a big hash table (millions of entries), I was reading mostly sequential <em>key</em> values (like <code>14, 15, 16, ...</code>), which apparently resulted in <em>lots of</em> CPU cache hits, due to the way the standard hash tables (and hash-code functions for integers and short strings) in those languages are implementated, so that entries with nearby keys are usually located in nearby memory locations.</p>
  <p>Rust's <code>HashMap</code>, on the other hand, uses the so called <code>SwissTable</code> implementation, which apparently distributes values differently. When I tested reading by random keys, everything fell into place - the &quot;competitors&quot; scored behind Rust.</p>
  <p>So if we are in a situation where we need to perform lots of gets sequentially, for example iterating some DB IDs that are ordered and mostly sequential (with not too many gaps), is there a good Rust hash map implementation that can compete with Java's <code>HashMap</code> or .NET's <code>Dictionary</code>?</p>
  <hr />
  <p>P.S. As requested in the comments, I paste an example here. I ran lots of tests, but here is a simple example that takes 75 ms in Rust (release mode) and 20 ms in Java:</p>
  <p>In Rust:</p>
  <pre><code>let hm: FnvHashMap&lt;i32, i32&gt; = ...;  
  // Start timer here
  let mut sum: i64 = 0;
  for i in 0..1_000_000 {
      if let Some(x) = hm.get(&amp;i) {
          sum += *x as i64;
      }
  }
  println!(&quot;The sum is: {}&quot;, sum);
  </code></pre>
  <p>In Java:</p>
  <pre><code>Map&lt;Integer, Integer&gt; hm = ...;
  // Start timer here
  long sum = 0;
  for (int i = 0; i &lt; 1_000_000; i++) {
      sum += hm.get(i);
  }
  </code></pre>
  <p>With <code>HashMap&lt;i32, i32&gt;</code> and its default <a href="https://doc.rust-lang.org/std/hash/struct.SipHasher.html" rel="noreferrer"><code>SipHash</code></a> hasher it took 190 ms. I know <em>why</em> it's slower than <code>FnvHashMap</code>. I'm just mentioning that for completeness.</p>