DoxigAlpha
std › HashMapUnmanaged › rehash

rehash

Rehash the map, in-place.

Over time, due to the current tombstone-based implementation, a HashMap could become fragmented due to the buildup of tombstone entries that causes a performance degradation due to excessive probing. The kind of pattern that might cause this is a long-lived HashMap with repeated inserts and deletes.

After this function is called, there will be no tombstones in the HashMap, each of the entries is rehashed and any existing key/value pointers into the HashMap are invalidated.

Function parameters

Parameters

#
self:*Self
ctx:anytype

Type definitions in this namespace

Types

#

Functions in this namespace

Functions

#
StringHashMap
Builtin hashmap for strings as keys.
StringHashMapUnmanaged
Key memory is managed by the caller.
HashMap
General purpose hash table.
HashMapUnmanaged
A HashMap based on open addressing and linear probing.

= 80

Values

#

Source

Implementation

#
pub fn rehash(self: *Self, ctx: anytype) void {
    const mask = self.capacity() - 1;

    var metadata = self.metadata.?;
    var keys_ptr = self.keys();
    var values_ptr = self.values();
    var curr: Size = 0;

    // While we are re-hashing every slot, we will use the
    // fingerprint to mark used buckets as being used and either free
    // (needing to be rehashed) or tombstone (already rehashed).

    while (curr < self.capacity()) : (curr += 1) {
        metadata[curr].fingerprint = Metadata.free;
    }

    // Now iterate over all the buckets, rehashing them

    curr = 0;
    while (curr < self.capacity()) {
        if (!metadata[curr].isUsed()) {
            assert(metadata[curr].isFree());
            curr += 1;
            continue;
        }

        const hash = ctx.hash(keys_ptr[curr]);
        const fingerprint = Metadata.takeFingerprint(hash);
        var idx = @as(usize, @truncate(hash & mask));

        // For each bucket, rehash to an index:
        // 1) before the cursor, probed into a free slot, or
        // 2) equal to the cursor, no need to move, or
        // 3) ahead of the cursor, probing over already rehashed

        while ((idx < curr and metadata[idx].isUsed()) or
            (idx > curr and metadata[idx].fingerprint == Metadata.tombstone))
        {
            idx = (idx + 1) & mask;
        }

        if (idx < curr) {
            assert(metadata[idx].isFree());
            metadata[idx].fill(fingerprint);
            keys_ptr[idx] = keys_ptr[curr];
            values_ptr[idx] = values_ptr[curr];

            metadata[curr].used = 0;
            assert(metadata[curr].isFree());
            keys_ptr[curr] = undefined;
            values_ptr[curr] = undefined;

            curr += 1;
        } else if (idx == curr) {
            metadata[idx].fingerprint = fingerprint;
            curr += 1;
        } else {
            assert(metadata[idx].fingerprint != Metadata.tombstone);
            metadata[idx].fingerprint = Metadata.tombstone;
            if (metadata[idx].isUsed()) {
                std.mem.swap(K, &keys_ptr[curr], &keys_ptr[idx]);
                std.mem.swap(V, &values_ptr[curr], &values_ptr[idx]);
            } else {
                metadata[idx].used = 1;
                keys_ptr[idx] = keys_ptr[curr];
                values_ptr[idx] = values_ptr[curr];

                metadata[curr].fingerprint = Metadata.free;
                metadata[curr].used = 0;
                keys_ptr[curr] = undefined;
                values_ptr[curr] = undefined;

                curr += 1;
            }
        }
    }
}