4 ms·

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 reduc

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.

nowne 12y ago
The problem with that method is that it doesn't have data access locality, while linear probing does. Linear probing ends up being more efficient because it is easy on the cache.
- stormbrew 12y ago
  It seems to me this would only be true if the keys that collide are related to each other, or you have a vastly oversized table that you collide a lot in, at which point you're just accidentally synthesizing a smaller table. 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.
  - syllogism 12y ago
    Let's say you get a collision. Would you rather: 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-a-judy-array/ http://preshing.com/20130107/this-hash-table-is-faster-than-...
  - deleted 12y ago
    [deleted]
  - nowne 12y ago
    Linear probing works by initially hashing the value, call it h(x), then if there is a collision, it checks h(x)+1, h(x)+2, ..., h(x) + k, until it finds a open slot. Lookup works in the same way, and deletion is a bit more complicated. 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.
    - stormbrew 12y ago
      I do know how linear probing works, thanks. ;) 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.
- im2w1l 12y ago
  It uses quadratic probing. Notice how both h and t increase.

nowne 12y ago

The problem with that method is that it doesn't have data access locality, while linear probing does. Linear probing ends up being more efficient because it is easy on the cache.

stormbrew 12y ago
It seems to me this would only be true if the keys that collide are related to each other, or you have a vastly oversized table that you collide a lot in, at which point you're just accidentally synthesizing a smaller table. 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.
- syllogism 12y ago
  Let's say you get a collision. Would you rather: 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-a-judy-array/ http://preshing.com/20130107/this-hash-table-is-faster-than-...
- deleted 12y ago
  [deleted]
- nowne 12y ago
  Linear probing works by initially hashing the value, call it h(x), then if there is a collision, it checks h(x)+1, h(x)+2, ..., h(x) + k, until it finds a open slot. Lookup works in the same way, and deletion is a bit more complicated. 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.
  - stormbrew 12y ago
    I do know how linear probing works, thanks. ;) 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.
im2w1l 12y ago
It uses quadratic probing. Notice how both h and t increase.