Innovation in hash tables

Andrew Krapivin, a young computer scientist, along with colleagues Martín Farach-Colton and William Kuszmaul, has disproved a long-standing conjecture by Andrew Yao regarding hash tables. Their January 2025^[1] paper introduces a new hash table design that performs queries and insertions faster than previously believed possible, with times proportional to (log x)² instead of x.

Additionally, they discovered that non-greedy hash tables can achieve a constant average query time, independent of the table's fullness. This breakthrough challenges conventional wisdom and opens new avenues for understanding and optimizing data structures. Experts hail the work for its elegance and potential future impact on data structure efficiency.

Implementing the strategies described in the paper, such as elastic hashing and funnel hashing, in Java involves creating a custom hash table structure that adheres to the principles outlined. Below is a simplified example of how you might implement a basic version of these strategies in Java. Note that this is a conceptual implementation and may need further optimization and testing for production use.

Elastic Hashing

Elastic hashing involves dynamically adjusting the probe sequence to achieve better performance. Here's a basic outline:

import java.util.Random;

public class ElasticHashTable<K, V> {
    private Entry<K, V>[] table;
    private int size;
    private double loadFactor;
    private Random random;

    public ElasticHashTable(int capacity, double loadFactor) {
        this.size = 0;
        this.loadFactor = loadFactor;
        this.table = new Entry[capacity];
        this.random = new Random();
    }

    public boolean insert(K key, V value) {
        int initialPosition = hash(key);
        int probeLength = calculateProbeLength(key);

        for (int i = 0; i < probeLength; i++) {
            int position = (initialPosition + probeSequence(i)) % table.length;
            if (table[position] == null) {
                table[position] = new Entry<>(key, value);
                size++;
                return true;
            }
        }
        return false;
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }

    private int calculateProbeLength(K key) {
        // Implement the logic to calculate probe length based on load factor
        return (int) (Math.log(1 / loadFactor) + 1);
    }

    private int probeSequence(int i) {
        // Implement the logic for the probe sequence
        return random.nextInt(table.length);
    }

    public V get(K key) {
        int initialPosition = hash(key);
        int probeLength = calculateProbeLength(key);

        for (int i = 0; i < probeLength; i++) {
            int position = (initialPosition + probeSequence(i)) % table.length;
            if (table[position] != null && table[position].key.equals(key)) {
                return table[position].value;
            }
        }
        return null;
    }

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

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

Funnel Hashing

import java.util.Arrays;

public class FunnelHashTable<K, V> {
    private Entry<K, V>[][] levels;
    private int size;
    private double loadFactor;

    public FunnelHashTable(int capacity, double loadFactor) {
        this.size = 0;
        this.loadFactor = loadFactor;
        int levelsCount = (int) Math.ceil(Math.log(1 / loadFactor) / Math.log(2));
        this.levels = new Entry[levelsCount][];
        for (int i = 0; i < levelsCount; i++) {
            levels[i] = new Entry[(int) (capacity / Math.pow(2, i))];
        }
    }

    public boolean insert(K key, V value) {
        for (Entry<K, V>[] level : levels) {
            int position = hash(key, level.length);
            if (level[position] == null) {
                level[position] = new Entry<>(key, value);
                size++;
                return true;
            }
        }
        return false;
    }

    private int hash(K key, int levelSize) {
        return Math.abs(key.hashCode()) % levelSize;
    }

    public V get(K key) {
        for (Entry<K, V>[] level : levels) {
            int position = hash(key, level.length);
            if (level[position] != null && level[position].key.equals(key)) {
                return level[position].value;
            }
        }
        return null;
    }

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

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

Notes

Probe Sequence: The probe sequence logic should be implemented according to the specifics of elastic hashing or funnel hashing as described in the paper.

Load Factor: The load factor is used to determine the probe length and manage the table's capacity.

Optimization: This code is a simplified version and may require additional optimizations, especially for handling collisions and ensuring efficient memory usage.