Cuckoo Hashing — Correlated Hash Functions and Rehash Loops

package io.thecodeforge.hashing;

import java.util.Objects;

/**
 * Production-grade cuckoo hash map with cycle detection and auto-resize.
 * Two independent hash functions over two tables.
 *
 * Design constraints:
 *  - MAX_EVICTION_CHAIN bounds insertion to prevent infinite loops
 *  - LOAD_FACTOR_THRESHOLD triggers proactive resize before cycle probability climbs
 *  - hash1/hash2 use different mixing constants — verify independence before deployment
 */
public class CuckooHashMap<K, V> {

    private static final int    MAX_EVICTION_CHAIN     = 512;
    private static final double LOAD_FACTOR_THRESHOLD  = 0.45;
    private static final int    DEFAULT_INITIAL_CAPACITY = 16;

    // Package-private so CuckooResizer can read entries directly
    Entry<K, V>[] table1;
    Entry<K, V>[] table2;
    int capacity;
    private int size;

    static class Entry<K, V> {
        final K key;
        V value;

        Entry(K key, V value) {
            this.key   = key;
            this.value = value;
        }
    }

    @SuppressWarnings("unchecked")
    public CuckooHashMap(int initialCapacity) {
        this.capacity = nextPowerOfTwo(initialCapacity);
        this.table1   = new Entry[this.capacity];
        this.table2   = new Entry[this.capacity];
        this.size     = 0;
    }

    public CuckooHashMap() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    /**
     * Hash function 1 — finalizer mixing from MurmurHash3.
     * The >>> 16 XOR fold reduces slot clustering in the low bits.
     */
    private int hash1(K key) {
        int h = key.hashCode();
        h ^= (h >>> 16);
        h *= 0x85ebca6b;
        h ^= (h >>> 13);
        return h & (capacity - 1);
    }

    /**
     * Hash function 2 — different multiplier constant for independence.
     * Uses the golden-ratio-derived constant 0x9e3779b9.
     * Never derive h2 as h1 + offset — that is maximally correlated.
     */
    private int hash2(K key) {
        int h = key.hashCode() * 0x9e3779b9;
        h ^= (h >>> 16);
        h *= 0xc2b2ae35;
        h ^= (h >>> 16);
        return h & (capacity - 1);
    }

    /**
     * O(1) worst-case lookup — exactly two memory accesses.
     * Returns null if the key is absent.
     */
    public V get(K key) {
        Objects.requireNonNull(key, "null keys are not supported");
        int idx1 = hash1(key);
        if (table1[idx1] != null && table1[idx1].key.equals(key)) {
            return table1[idx1].value;
        }
        int idx2 = hash2(key);
        if (table2[idx2] != null && table2[idx2].key.equals(key)) {
            return table2[idx2].value;
        }
        return null; // key not present — checked both candidate slots
    }

    /**
     * Insert or update a key-value pair.
     *
     * Returns true on success.
     * Returns false when the eviction chain exceeds MAX_EVICTION_CHAIN —
     * the caller must trigger a resize-and-rehash before retrying.
     *
     * Never silently drops keys — false is an explicit signal, not an ignored error.
     */
    public boolean put(K key, V value) {
        Objects.requireNonNull(key, "null keys are not supported");

        // Update in place if the key already exists — avoids growing eviction chains
        int idx1 = hash1(key);
        if (table1[idx1] != null && table1[idx1].key.equals(key)) {
            table1[idx1].value = value;
            return true;
        }
        int idx2 = hash2(key);
        if (table2[idx2] != null && table2[idx2].key.equals(key)) {
            table2[idx2].value = value;
            return true;
        }

        // Begin eviction chain — alternate between T1 and T2
        Entry<K, V> toInsert  = new Entry<>(key, value);
        boolean     useTable1 = true;

        for (int i = 0; i < MAX_EVICTION_CHAIN; i++) {
            if (useTable1) {
                int idx = hash1(toInsert.key);
                if (table1[idx] == null) {
                    table1[idx] = toInsert;
                    size++;
                    return true;
                }
                // Evict occupant; it will try T2 on the next iteration
                Entry<K, V> evicted = table1[idx];
                table1[idx] = toInsert;
                toInsert    = evicted;
                useTable1   = false;
            } else {
                int idx = hash2(toInsert.key);
                if (table2[idx] == null) {
                    table2[idx] = toInsert;
                    size++;
                    return true;
                }
                Entry<K, V> evicted = table2[idx];
                table2[idx] = toInsert;
                toInsert    = evicted;
                useTable1   = true;
            }
        }

        // Chain limit exceeded — cycle detected or near-cycle.
        // Caller must call CuckooResizer.resize(this) and retry the insertion.
        return false;
    }

    /**
     * Deletion is clean — no tombstones required.
     * A key exists in exactly one of two known slots.
     */
    public boolean remove(K key) {
        Objects.requireNonNull(key);
        int idx1 = hash1(key);
        if (table1[idx1] != null && table1[idx1].key.equals(key)) {
            table1[idx1] = null;
            size--;
            return true;
        }
        int idx2 = hash2(key);
        if (table2[idx2] != null && table2[idx2].key.equals(key)) {
            table2[idx2] = null;
            size--;
            return true;
        }
        return false;
    }

    /** Combined load across both tables — useful for trend monitoring */
    public double loadFactor() {
        return (double) size / (2.0 * capacity);
    }

    /**
     * Per-table load factor — the metric that actually matters.
     * Returns the higher of the two individual table occupancies.
     * Alert when this exceeds 0.45; resize when it exceeds 0.50.
     */
    public double perTableLoadFactor() {
        int t1Count = 0, t2Count = 0;
        for (Entry<K, V> e : table1) if (e != null) t1Count++;
        for (Entry<K, V> e : table2) if (e != null) t2Count++;
        return Math.max(
            (double) t1Count / capacity,
            (double) t2Count / capacity
        );
    }

    /** Returns false when per-table load exceeds the production threshold */
    public boolean isHealthy() {
        return perTableLoadFactor() < LOAD_FACTOR_THRESHOLD;
    }

    public int size() { return size; }

    private static int nextPowerOfTwo(int n) {
        if (n <= 1) return 1;
        n--;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n + 1;
    }
}

package io.thecodeforge.hashing;

import java.util.HashSet;
import java.util.Set;

/**
 * Explicit cycle detection using a visited-slot fingerprint set.
 *
 * More precise than iteration count alone — terminates immediately
 * on true cycle detection rather than running to MAX_EVICTION_CHAIN.
 * Trade-off: allocates a HashSet per insertion attempt.
 *
 * Use this when key distributions are known to be adversarial
 * and early termination saves more than the allocation costs.
 * For most workloads, the iteration-count guard in CuckooHashMap
 * is sufficient and cheaper.
 */
public class CycleDetector<K> {

    private final Set<Integer> visitedSlots;
    private final int          maxChainLength;

    public CycleDetector(int maxChainLength) {
        this.maxChainLength = maxChainLength;
        this.visitedSlots   = new HashSet<>();
    }

    /**
     * Returns true if visiting this (table, slot) pair would complete a cycle.
     *
     * Encodes the pair as a single int fingerprint:
     *   - high byte = tableIndex (0 or 1)
     *   - low 24 bits = slotIndex (supports tables up to 16M slots)
     *
     * Call this before executing each eviction step.
     */
    public boolean wouldCycle(int tableIndex, int slotIndex) {
        int fingerprint = (tableIndex << 24) | (slotIndex & 0x00FFFFFF);
        return !visitedSlots.add(fingerprint); // add returns false if already present
    }

    /**
     * Returns true if the chain has exceeded the configured maximum.
     * Check this alongside wouldCycle — whichever triggers first aborts.
     */
    public boolean exceedsMaxLength(int currentLength) {
        return currentLength >= maxChainLength;
    }

    /**
     * Reset between insertion attempts.
     * Reuse the detector instance across attempts to avoid repeated allocation.
     */
    public void reset() {
        visitedSlots.clear();
    }

    /**
     * Number of unique slots visited in the current chain.
     * Useful for diagnostics — log this on insertion failure.
     */
    public int visitedCount() {
        return visitedSlots.size();
    }
}

package io.thecodeforge.hashing;

import java.util.Set;

/**
 * Two independent hash functions for cuckoo hashing.
 *
 * Both use Murmur3-style 64-bit finalizer mixing with different
 * seed constants. The seeds are chosen to be statistically independent
 * — they are not offsets of each other.
 *
 * For adversarial key environments (network-facing services), replace
 * these with SipHash using separate 128-bit key pairs per function.
 *
 * Before deploying to production, call estimateIndependence() with a
 * representative key sample and verify overlap < 2.0 / capacity.
 */
public class HashFunctions {

    // Two distinct constants derived from known low-discrepancy sequences
    // Do NOT derive SEED2 as SEED1 + offset — that introduces correlation
    private static final long SEED1 = 0x517cc1b727220a95L;
    private static final long SEED2 = 0x9e3779b97f4a7c15L;

    /** Hash function 1 — Murmur3 64-bit finalizer with SEED1 */
    public static int hash1(Object key, int capacity) {
        long h = (long) key.hashCode() ^ SEED1;
        h ^= h >>> 33;
        h *= 0xff51afd7ed558ccdL;
        h ^= h >>> 33;
        h *= 0xc4ceb9fe1a85ec53L;
        h ^= h >>> 33;
        return (int) (h & (capacity - 1));
    }

    /** Hash function 2 — same finalizer structure, independent seed */
    public static int hash2(Object key, int capacity) {
        long h = (long) key.hashCode() ^ SEED2;
        h ^= h >>> 33;
        h *= 0xff51afd7ed558ccdL;
        h ^= h >>> 33;
        h *= 0xc4ceb9fe1a85ec53L;
        h ^= h >>> 33;
        return (int) (h & (capacity - 1));
    }

    /**
     * Empirical independence check.
     *
     * For a uniformly random key set, the expected fraction of keys
     * where hash1 == hash2 (after modulo) is 1/capacity.
     *
     * A result significantly above 2/capacity indicates correlation
     * and predicts premature cycle formation under load.
     *
     * Run this with at least 10,000 representative keys before
     * deploying a new hash function pair to production.
     *
     * @return overlap fraction — target < 2.0 / capacity
     */
    public static double estimateIndependence(Set<Object> keys, int capacity) {
        if (keys.isEmpty()) {
            throw new IllegalArgumentException(
                "Key sample must be non-empty — use at least 10,000 representative keys"
            );
        }
        long overlapCount = 0;
        for (Object key : keys) {
            if (hash1(key, capacity) == hash2(key, capacity)) {
                overlapCount++;
            }
        }
        return (double) overlapCount / keys.size();
    }
}

package io.thecodeforge.hashing;

/**
 * Handles table resizing and rehashing with independent hash seeds.
 *
 * Called when CuckooHashMap.put() returns false — meaning the eviction
 * chain exceeded MAX_EVICTION_CHAIN and the current table cannot
 * accommodate the key set under its current hash functions.
 *
 * Rehash strategy:
 *  1. Double capacity
 *  2. Allocate new tables (old tables become eligible for GC)
 *  3. Re-insert all entries — new hash functions break adversarial patterns
 *  4. If re-insertion fails, grow by an additional 1.5x and retry
 *  5. After MAX_REHASH_ATTEMPTS, throw — something is structurally wrong
 *
 * The caller is responsible for replacing the reference to the old map.
 * In Java, the old Entry arrays become unreachable after replacement
 * and will be collected at the next GC cycle — confirm with a heap dump
 * if memory usage does not drop as expected.
 */
public class CuckooResizer<K, V> {

    private static final double GROWTH_FACTOR        = 2.0;
    private static final double RETRY_GROWTH_FACTOR  = 1.5;
    private static final int    MAX_REHASH_ATTEMPTS  = 5;

    /**
     * Resize and rehash the given map, returning a new map at larger capacity.
     *
     * The returned map uses the same CuckooHashMap class but with a new
     * capacity. Hash seed variation is handled by the new capacity interacting
     * with the mixing constants in hash1/hash2 — for stronger independence
     * under adversarial conditions, parameterise HashFunctions with
     * externally supplied seeds and rotate them here.
     *
     * @throws IllegalStateException if rehash fails after all retry attempts
     */
    public static <K, V> CuckooHashMap<K, V> resize(CuckooHashMap<K, V> current) {
        int newCapacity = (int) (current.capacity * GROWTH_FACTOR);

        for (int attempt = 1; attempt <= MAX_REHASH_ATTEMPTS; attempt++) {
            CuckooHashMap<K, V> newMap  = new CuckooHashMap<>(newCapacity);
            boolean             success = true;

            // Re-insert from table1
            for (CuckooHashMap.Entry<K, V> entry : current.table1) {
                if (entry != null && !newMap.put(entry.key, entry.value)) {
                    success = false;
                    break;
                }
            }

            // Re-insert from table2 only if table1 succeeded
            if (success) {
                for (CuckooHashMap.Entry<K, V> entry : current.table2) {
                    if (entry != null && !newMap.put(entry.key, entry.value)) {
                        success = false;
                        break;
                    }
                }
            }

            if (success) {
                // Old map's Entry arrays are now unreachable — GC eligible
                return newMap;
            }

            // This attempt failed — grow further and try again
            // Capacity increase changes the modulo distribution, acting as
            // an implicit seed change for fixed mixing constants
            newCapacity = (int) (newCapacity * RETRY_GROWTH_FACTOR);
        }

        throw new IllegalStateException(
            String.format(
                "CuckooResizer: failed after %d rehash attempts starting at capacity %d. "
              + "Key distribution is likely adversarial. Consider SipHash with rotated seeds.",
                MAX_REHASH_ATTEMPTS,
                (int) (current.capacity * GROWTH_FACTOR)
            )
        );
    }
}