Как сделать неэффективное заполнение хэш-таблицы за O(n^2)?

Как уже сказали в комментариях, нужно просто сделать так, чтобы у объектов было разное значение, но одинаковый хэш-код, тогда хэш-таблица должна будет как-то решать коллизии, а для этого обычно нужно проходить по всем уже имеющимся в таблице элементам в поисках элемента совпадающего по значению (или чтобы убедиться в отсутствии такого элемента).

Проверим эту мысль кодом:

• Берём класс с нормальным хэшем
• Берём класс с вырожденным хэшем
• Создаём по 1000 экземпляров каждого класса
• Делаем из этих экземпляров множество (а это как-раз хэш-таблица)
• Меряем время создания множества (для стабильности - усредняем за 100 прогонов)
• Сравниваем

import timeit

class Test:
    
    def __init__(self, x):
        self.x = x
        
    def __hash__(self):
        return hash(self.x)
    
    def __eq__(self, other):
        if not isinstance(other, Test):
            return NotImplemented  # Or raise TypeError, depending on desired behavior
        return self.x == other.x
    
class TestDegenerate(Test):
    
    def __hash__(self):
        return 1

t1 = timeit.timeit('set(map(Test, range(1_000)))', number=100, globals=globals())
t2 = timeit.timeit('set(map(TestDegenerate, range(1_000)))', number=100, globals=globals())
print(t1, t2, t2/t1, sep='\n')

Вывод:

0.025643200031481683
6.845358700025827
266.9463519226113

Деградация произошла не совсем в n раз (n = 1000 в данном случае), но по порядку близко к тому. И это видимо правильно, потому что n² - это "оценка сверху". Ведь в хэш-таблице не сразу уже n элементов, они туда постепенно добавляются.

P.S. Добавил во второй класс вызов подсчёта хэша без его использования _ = hash(self.x), чтобы скорость подсчёта хэша обоих классов была схожая - результат чуть поменялся, но не сильно.

P.S. Fun fact: в Питоне hash натурального числа совпадает с самим числом вплоть до числа 2_305_843_009_213_693_950 (0x1ffffffffffffffe), после которого хэш опять начинается с 0.

Пример деградации хэш-таблицы в Питоне. Само по себе падение производительности не означает, что сложность стала квадратичной, но намекает.

$ time -p python -c 'set(i * 2 ** 61 for i in range(40000))'
real 0.01
user 0.01
sys 0.00

$ time -p python -c 'set(i * (2 ** 61 - 1) for i in range(40000))'
real 5.07
user 5.06
sys 0.00

Подробности

Хэш небольшого целого числа в Питоне совпадает с ним самим. Более того, можно установить что для неотрицательных чисел хэши вычисляются как величина числа по некоторому модулю. Функция hash_loop отыскивает этот модуль. На моей машине он равен 2⁶¹ - 1.

Если построить любую прогрессию неотрицательных целых чисел с шагом 2⁶¹ - 1, все числа в ней получат одинаковое значение хэша.

Функция main строит прогрессии увеличивающейся длины и вызывает построение множества от них. Печатается длина прогрессии и время, которое было потрачено на построение множества.

import time


def bsearch(low, high, pred):
    if low >= high or pred(low):
        return low
    while low < high - 1:
        mid = (low + high) // 2
        if pred(mid):
            high = mid
        else:
            low = mid
    return high


def hash_loop():
    n = 1
    while hash(n) == n:
        n *= 2
    return bsearch(n // 2, n, lambda n: hash(n) != n)


def elapsed(f):
    start = time.perf_counter()
    r = f()
    finish = time.perf_counter()
    return finish - start, r


def main():
    n = hash_loop()
    p = 1
    while True:
        for k in range(10 ** p, 10 ** (p + 1), 10 ** p):
            r = range(0, k * n, n)
            t, _ = elapsed(lambda: set(r))
            print(len(r), f'{t:.2f}')
        p += 1


main()

Запустите и дождитесь пока времена работы будут сравнимы с секундами. У меня получается такое:

$ python benchmark.py
...
10000 0.30
20000 1.42
30000 3.10
40000 5.69
50000 9.11
60000 13.73
70000 19.04
80000 27.44
90000 35.25
100000 42.29
....

Отношение времён для разных длин прогрессий:

Для всех отношений длин, отношения времён превышают квадрат.

Что и требовалось доказать.

График времён и парабола:

В современной Java сделать n² не получится. Но можно сделать n log n.

Если в одной корзине таблицы накапливается более восьми элементов, корзина из списка превращается в сортированное дерево (TREEIFY_THRESHOLD).
Для сортировки используется порядок на ключах, если он доступен (comparableClassFor).
А если порядка нет, ключи сортируются по адресам (tieBreakOrder).

Операции с сортированным деревом занимают log n. Если поместить все элементы в одну корзину, получим дополнительный логарифмический множитель в сложность.

По исходному коду Long.hashCode можно предсказать, что все числа типа long кратные 2³² + 1 буду иметь нулевой хэш.

Benchmark.java читает шаг из командной строки, печатает хэши для первых десяти шагов (нужно для проверки) и начинает измерять времена построения HashSet:

import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.HashSet;

class Benchmark {
    public static void main (String[] args) {
        long step = Long.valueOf(args[0]);
        for (int i = 0; i < 10; ++i) {
            System.out.print(" " + Long.valueOf(i * step).hashCode());
        }
        System.out.println();
        for (int t = 1; ; t *= 10) {
            for (int s = t; s < 10 * t; s += t) {
                System.out.format("%d %.3f\n", s, elapsed(step, s));
            }
        }
    }

    private static double elapsed(long step, int n) {
        Long[] a = new Long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = i * step;
        }
        List<Long> aa = Arrays.asList(a);

        System.gc();

        long start = System.nanoTime();
        Set<Long> s = new HashSet<>(aa);
        long finish = System.nanoTime();
        return (finish - start) / 1e9;
    }
}

Я запускал её два раза, для шагов 4294967297 (все хэши нулевые) и 4294967296 (хэши – последовательные числа). Результат в таблице:

На картинке синие точки (нулевой хэш) наложены на график n log n, а зелёные на линейный график. К сожалению, на таких масштабах прогиб, вызванный логарифмическим множителем почти не заметен.