Почему это плохой хеш-функции?

Question

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

function hash(String_t word, Int table_size) 
    i = randomly generated number with 0<i<table_size 
    j = ASCII code of the first letter of word 

    return i * j % table_size 

Предполагая, что значение i может быть сохранена во время функциональных вызовов для достижения согласованности (например, используя ключевое слово static в C, чтобы сохранить значение i в пределах области действия), почему это плохой хеш-функции?

Answer 1

Хорошая хеш-функция должна хорошо работать для разных размеров ввода, при условии, что размер таблицы будет постоянным, большим, чем количество входов. Это не соответствует этим критериям по нескольким причинам:

1. Значение хэша определяется только первой буквой. Следовательно, общее число возможных хэш-значений ограничено числом возможных первых букв, которое мало. Выбор большого размера таблицы для большого количества входов не влияет: вы все равно получите кучи столкновений.

2. Поскольку первые буквы слов очень далеки от равномерного распределения, у вас будет много столкновений. По крайней мере, используйте все буквы этого слова при определении своей функции, но вам действительно нужно больше, чем советы, чтобы спасти эту конструкцию.

3. Определить d = gcd (i, размер стола). В некоторых случаях d будет больше 1, и в этих случаях только один из каждых d элементов таблицы будет иметь возможность заселения: остальные будут потеряны в пространстве (и, следовательно, больше столкновений). То есть, только 0, d, 2d, 3d, ... Может быть хеш-значение. По крайней мере, ограничить значения i с d = 1, чтобы предотвратить эти вырожденные случаи.

4. i, умноженное на наибольшее значение j, будет иногда меньше размера таблицы (когда я мал), подразумевая, что верхний конец таблицы никогда не будет затронут. Больше потерянного пространства.

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