Можно ли подобрать число меньше 130000, при котором коллизий в хеш-таблице будет меньше?

Да, можно. Количество коллизий в хеш-таблице с методом цепочек или открытой адресацией сильно зависит от двух факторов: качества хеш-функции и размера таблицы (количества бакетов).

1. Выбор размера таблицы:

• Простое число: Если хеш-функция основана на делении по модулю (hash(key) = key % table_size), то для уменьшения коллизий размер таблицы должен быть простым числом. Это помогает избежать кластеризации, когда ключи с определенными закономерностями попадают в одни и те же бакеты.

• Число, не являющееся степенью двойки: Для мультипликативных хеш-функций часто используют размер, равный степени двойки (для быстрого взятия модуля через битовую маску). Однако это может увеличить коллизии, если хеш-функция не дисперсна. Простое число — более надежный выбор.

  Для числа меньше 130000 (которое само не является простым) хорошими кандидатами будут близкие простые числа:

• 129983
• 129989
• 130001 (чуть больше, но часто допустимо)

2. Пример реализации на C++:

#include <iostream>
#include <vector>
#include <list>
#include <cmath>

bool isPrime(size_t n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (size_t i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

size_t findGoodPrime(size_t target) {
    size_t candidate = target;
    while (!isPrime(candidate)) {
        --candidate;
    }
    return candidate; // Например, 129983 для target=130000
}

class HashTable {
private:
    std::vector<std::list<std::pair<int, std::string>>> table;
    size_t tableSize;

    // Простая хеш-функция с делением по модулю
    size_t hashFunction(int key) const {
        return static_cast<size_t>(key) % tableSize;
    }

public:
    // Конструктор принимает желаемый размер и находит ближайшее простое число
    HashTable(size_t desiredSize) {
        tableSize = findGoodPrime(desiredSize);
        table.resize(tableSize);
        std::cout << "Table size set to prime: " << tableSize << 'n';
    }

    void insert(int key, const std::string& value) {
        size_t index = hashFunction(key);
        // Вставка в цепочку (разрешение коллизий методом цепочек)
        table[index].emplace_back(key, value);
    }
    // ... другие методы (поиск, удаление)
};

int main() {
    // Создаем таблицу с размером, близким к 130000, но простым
    HashTable ht(130000); // Внутри будет использован размер 129983
    ht.insert(12345, "data1");
    ht.insert(12345 + 129983, "data2"); // Это вызовет коллизию с data1
    // Но благодаря большому простому размеру, общее распределение будет лучше.
    return 0;
}

3. Дополнительные методы уменьшения коллизий:

• Качественная хеш-функция: Для целых чисел подходит мультипликативный метод. Для строк — например, DJB2 или CRC32.
• Двойное хеширование: Используется в открытой адресации, когда при коллизии вычисляется второй хеш для поиска следующего свободного слота.
• Метод цепочек: Как в примере выше, когда коллизии разрешаются путем хранения списка элементов в одном бакете.

Вывод: Подбор простого числа в качестве размера таблицы (например, 129983 вместо 130000) при использовании хеш-функции с делением по модулю — это простой и эффективный способ уменьшить количество коллизий для произвольного набора ключей.