A small improvement could be to hash the key using a prime multiplier and successive multiplications, instead of using the key and increments of one. It'd reduce the collisions at the expense of a more computationally expensive hash function.
What am I missing here?
[edit] I guess the other situation would be if the keys are largely sequential, but then a hash table seems like an odd choice of data structure.
a) Find your correct key within the same cache-line. But, you have to check 4 more values to get there;
b) Find your correct key in the next try...But, you have to jump to another part of the array.
Once you've indexed into the array, you want to read forward from there. You don't want to jump around.
http://preshing.com/20130107/this-hash-table-is-faster-than-...
This model plays nicely with the cache, although its downside is there tend to be more "runs" of contiguous filled slots in the hash table. This method still provably takes an expected insert/lookup time of O(1) with a 5-wise independent hash function and a load factor smaller than 1.
But now I see where the confusion lies. I was taking your post to be replying more to the hash function part of the GP, but you were talking specifically about the skip distance. Yes, now I see what you mean, and I'm not actually sure how I misinterpreted so badly in the first place.