prob/hash
src/prob/hash.tur
defstruct
HashPair
(defstruct HashPair [h1 : int h2 : int])
two 64-bit hash seeds for double-hashing.
Since: probabilistic-spice-plan C1
defn
prob-unsigned-shr
(prob-unsigned-shr [x : int bits : int] :)
logical (unsigned) right shift of x by n bits.
Parameters
| x | value to shift | |
| bits | number of bit positions (0..63) |
Returns
x shifted right by n bits, 0-filling high bits (logical/unsigned shift).
Since: probabilistic-spice-plan C1
defn
prob-hash-int
(prob-hash-int [n : int] :)
splitmix64 finalizer, pure Turmeric.
Parameters
| n | value to hash |
Returns
A 64-bit hash of n.
Since: probabilistic-spice-plan C1
defn
prob-hash-pair
(prob-hash-pair [key : int] :)
produce two 64-bit hash seeds from an integer key.
Parameters
| key | the integer key to hash |
Returns
A HashPair whose h1 and h2 are the seeds for double-hashing.
Example
(let [hp (prob-hash-pair 42)] ... (.h1 hp) ... (.h2 hp) ...)
Since: probabilistic-spice-plan C1
defn
prob-double-hash-index
(prob-double-hash-index [h1 : int h2 : int i : int m : int] :)
the i-th of k indices into m slots.
Parameters
| h1 | first hash seed | |
| h2 | second hash seed | |
| i | which hash index (0-based) | |
| m | number of slots (should be a power of two) |
Returns
(h1 + i * (h2 | 1)) & (m - 1), in [0, m).
Since: probabilistic-spice-plan C1
Internal definitions
__hash-step1-- x ^= x >> 30__hash-step2-- x *= 0xbf58476d1ce4e5b9__hash-step3-- x ^= x >> 27__hash-step4-- x *= 0x94d049bb133111eb__hash-step5-- x ^= x >> 31