jm + hashmaps   3

Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo)
Turns out I was wrong. This is a big one. And everyone should be using it. Hash tables should not be prime number sized and they should not use an integer modulo to map hashes into slots. Fibonacci hashing is just better. Yet somehow nobody is using it and lots of big hash tables (including all the big implementations of std::unordered_map) are much slower than they should be because they don’t use Fibonacci Hashing.

Apparently this is binary multiplicative hashing, and Google's brotli, webp, and Snappy libs all use a constant derived heuristically from a compression test corpus along the same lines (see comments).

(Via Michael Fogleman)
algorithms  hashing  hash  fibonacci  golden-ratio  coding  hacks  brotli  webp  snappy  hash-tables  hashmaps  load-distribution 
27 days ago by jm
Large Java HashMap performance overview
Large HashMap overview: JDK, FastUtil, Goldman Sachs, HPPC, Koloboke, Trove – January 2015 version
java  performance  hashmap  hashmaps  optimization  fastutil  hppc  jdk  koloboke  trove  data-structures 
september 2015 by jm
OpenHFT/hftc · GitHub
This is a yet another Java collections library of primitive specializations. Java 6+. Apache 2.0 license. Currently only hash sets and hash maps are implemented.
openhft  performance  java  jvm  collections  asl  hashsets  hashmaps  data-structures 
august 2014 by jm

Copy this bookmark: