use quadratic probing in OpenHashMap #9789
Labels
Milestone
Comments
|
Imported From: https://issues.scala-lang.org/browse/SI-9789?orig=1
|
|
Mike (mike) said: |
|
Mike (mike) said: def hashOf(key: Int) = {
var h = key
h ^= ((h >>> 20) ^ (h >>> 12))
h ^ (h >>> 7) ^ (h >>> 4)
}
def check(key: Int) = {
val hash = hashOf(key)
val arr = new Array[Boolean](64)
val mask = arr.length - 1
var j = hash
var index = hash & mask
var perturb = index
(0 to arr.length * 2).foreach( i => {
arr(index) = true
j = 5 * j + 1 + perturb
perturb >>= 5
index = j & mask
})
val falses = arr.filterNot(i => i).length
if (falses >= arr.length / 2)
println( key, falses, arr.mkString(",") )
}
(0 to 100000000).foreach( check(_) )Still, I've seen no theoretical justification for why this "exponential probing" should work, nor have I seen this technique used elsewhere, and it adds unnecessary computation compared to linear or quadratic probing, while having the poor locality of reference of double hashing but none of its non-clustering guarantees. So I still think it should be replaced on performance grounds. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The original (and still current) probe implementation in
OpenHashMapis based on the algorithm used in Python. It is exponential (in the long run), with sequence (h+¼)·5 ^i^ - ¼ modulo the table size, where i is the sequence index and h is the hash of the key. (Actually, the start of the sequence is modified by adding in a "perturbation" at each step, but this value becomes 0 or -1 after the 8th step.)Using these probe intervals leads to poor memory locality, as the sequence jumps around the table.
This ticket replaces the probe algorithm with a more sensible and well-studied quadratic probe with small step size.
The text was updated successfully, but these errors were encountered: