Leapfrog Probing for open addressing hash tables
preshing.com
preshing.com
Also, I can see that if your first delta hits another probe chain's beginning, then you'll end up with the same chain. This is slightly solved by quadratic probing, where your first and second multipliers have differing effects on the output so two chains that meet once aren't forever locked together. Maybe if you incorporated some of the quadratic effect into Leapfrog this issue might be alleviated.
This is a link to a very technical article hash table implementation a pretty popular data structure. Right at the top it tells you that's what it's about. Also, if you bother to check the side of the article when it list recent article or go look at the other blog post you'll see it's a follow up on a previous article on lock-free hash tables that use this method. That's more then plenty of context if you just give it more then 5 seconds.
> Although some ideas seem pretty clever, I've too often seen code implementing this in a haphazard way (buggy, no comments). This leaves the next programmer scratching their head and wondering ... why? Unless you have very specific performance and memory constraints, I do not see the need for such structures in most every programmers daily business.
Again, right in the article... the guy tells you that the common implementation of using a linked list for buckets in hash table is performance unfriendly (cache unfriendly) on modern machines.
Just because you don't see a need for it in your daily business, doesn't mean others do not there are plenty of cases where linear probing hash tables make sense. This includes any kind of GPU computing, databases, or anywhere your bottle neck is a particular lookup data structure. And yeah, those are all niche use cases, but they numerous and important enough where somebody might learn something.
See the conclusion of "Space efficient hash tables with worst case constant access time" (http://www.itu.dk/people/pagh/papers/d-cuckoo.pdf); it starts:
> From a practical point of view, d-ary Cuckoo Hashing seems a very advantageous approach to space efficient hash tables with worst case constant access time. Both worst case access time and average insertion time are very good.