Function zerovec::hashmap::algorithms::compute_displacements

source · 
pub fn compute_displacements(
    key_hashes: impl ExactSizeIterator<Item = u64>,
) -> (Vec<(u32, u32)>, Vec<usize>)
Expand description

Compute displacements for the given key_hashes, which split the keys into distinct slots by a two-level hashing schema.

Returns a tuple of where the first item is the displacement array and the second item is the reverse mapping used to permute keys, values into their slots.

  1. Split the hashes into (g, f0, f1).
  2. Bucket and sort the split hash on g in descending order.
  3. In decreasing order of bucket size, try until a (d0, d1) is found that splits the keys in the bucket into distinct slots.
  4. Mark the slots for current bucket as occupied and store the reverse mapping.
  5. Repeat untill all the keys have been assigned distinct slots.

§Arguments