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

Выбор размера хеш-таблицы и коллизии

Да, можно подобрать число размера хеш-таблицы менее 130000, которое даст меньше коллизий. Это один из ключевых аспектов оптимизации хеш-таблиц.

Принципы уменьшения коллизий

Коллизия наступает, когда два разных ключа получают одинаковый хеш. Вероятность коллизий зависит от нескольких факторов:

1. Простые числа как размер таблицы

Использование простых чисел критически важно:

// Плохо: составное число
const int TABLE_SIZE = 130000;  // = 2^4 * 5^4 * 13
// Высокий риск коллизий для хешей, основанных на степенях 2 и 5

// Хорошо: простое число меньше 130000
const int TABLE_SIZE = 129983;  // Простое число < 130000
// или
const int TABLE_SIZE = 131071;  // 2^17 - 1 (простое число Мерсенна)

Почему простые числа? Если размер таблицы N — простое, то для любых двух разных ключей при хеше h(k) = k mod N распределение коллизий минимально.

2. Коэффициент заполнения (Load Factor)

Критическое влияние на коллизии:

float load_factor = (float)num_elements / table_size;

// Рекомендуемые значения:
// 0.0 - 0.5  → мало коллизий, много пустого места (32KB → 64KB)
// 0.5 - 0.75 → приемлемо, хороший баланс
// 0.75+      → много коллизий, нужно увеличить таблицу

Пример расчета:

class HashTable {
private:
    vector<pair<int, int>> table;
    int size;
    int elements;
    
public:
    void resize_if_needed() {
        float load = (float)elements / size;
        if (load > 0.75) {
            // Ищем следующее простое число
            int new_size = find_next_prime(size * 2);
            rehash(new_size);
        }
    }
};

3. Выбор оптимального простого числа < 130000

Таблица рекомендуемых простых чисел:

// Начиная с меньших размеров:
const int PRIMES[] = {
    53,       // 2^6 - 11
    97,
    193,
    389,
    769,      // 2^10 - 255
    1543,
    3079,
    6151,
    12289,    // 2^14 - 255
    24593,
    49157,
    98317,
    129983    // < 130000
};

4. Функция хеширования

Хорошая функция хеширования критична:

// Плохая функция (много коллизий)
uint32_t bad_hash(const string& key) {
    return key[0];  // Только первый символ!
}

// Хорошая функция (хорошее распределение)
uint32_t good_hash(const string& key) {
    uint32_t hash = 0;
    for (char c : key) {
        hash = hash * 31 + (uint32_t)c;  // Multiplicative hashing
    }
    return hash;
}

// Отличная функция (FNV-1a для строк)
uint32_t fnv1a_hash(const string& key) {
    uint32_t hash = 2166136261u;  // FNV offset basis
    for (char c : key) {
        hash ^= (uint32_t)c;
        hash *= 16777619u;  // FNV prime
    }
    return hash;
}

// Использование:
int index = good_hash(key) % TABLE_SIZE;

5. Практический пример оптимизации

#include <vector>
#include <string>
#include <cmath>

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

int find_best_size(int max_size) {
    // Найти наибольшее простое число <= max_size
    for (int i = max_size; i >= 2; i--) {
        if (is_prime(i)) {
            return i;
        }
    }
    return 2;
}

int main() {
    int best = find_best_size(130000);
    cout << "Лучший размер < 130000: " << best << endl;  // 129983
    cout << "Это простое число: " << is_prime(best) << endl;  // true
    return 0;
}

6. Методы разрешения коллизий

При меньшем размере таблицы коллизии неизбежны, нужен способ их разрешения:

// Метод цепочек (chaining) — хорошо работает с простыми числами
struct Node {
    int key;
    int value;
    Node* next;
};

vector<Node*> table[129983];  // 129983 — простое число < 130000

void insert(int key, int value) {
    int index = hash(key) % 129983;
    // Добавляем в начало цепочки
    Node* node = new Node{key, value, table[index]};
    table[index] = node;
}

// Метод открытой адресации
struct Entry {
    int key;
    int value;
    bool empty;
};

Entry table[129983];

void insert_open_addressing(int key, int value) {
    int hash_val = hash(key) % 129983;
    // Линейное зондирование
    while (!table[hash_val].empty) {
        hash_val = (hash_val + 1) % 129983;
    }
    table[hash_val] = {key, value, false};
}

7. Когда коллизии меньше

Коллизии будут меньше, если:

• Используешь простое число вместо составного (129983 вместо 130000)
• Коэффициент заполнения < 0.75
• Функция хеширования хорошо распределяет значения
• Данные не содержат скрытых паттернов

Вывод

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