Игорь Артамонов

Неоднократно слышал о том что метод вычисления хэша, реализованный по умолчанию, для строк в Java не совсем хороший. Якобы много коллизий и пр. На замену ему можно найти в интернете несколько иных алгоритмов, но тоже непонятно какой лучший.

Поэтому проведем экперимент, сравним алгоритм по умолчанию, и пару считающихся лучшими алгоритмов. Выберем, так сказать, the best of the best среди хэширования Конкретно для меня, это равная вероятность состояний отдельных бит, в 32х битном целом. Т.е. чем ближе вероятность появления «1» в каждой из позиций к вероятности ½ тем лучше.

И так, помимо алгоритма по умолчанию решил попробовать SDBM:

public int hash(String val) {
    int hash = 0;
    for (char c: val.toCharArray()) {
	hash = c + (hash << 6) + (hash << 16) - hash;
    }
    return hash;
}

и DJB2:

public int hash(String val) {
    int hash = 0;
    for (char c: val.toCharArray()) {
	hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

и подсчитал отклонение от середины для случайно сгенеренных слов (как коротких так и длинных), на английском, русском, смешанном, смешанном+случайный регистр.

И вот график среднего отклонения, по этим четырем тестам:

По оси X — номер бита, по Y отклонение от равномерного, среднее для 4х тестов.
Видно что алгоритм по умолчанию, что DJB2 нормально работают лишь для первых 15 бит, дальше отклонения все больше и больше (на практике понижается вероятность заполнения бита по мере удаления от начала) В Java же int является 32х битным, поэтому в таком случае лучше использовать SDBM, который гораздо меньше отклоняется.

Да, кстати, для чисто русского текста результаты всегда получше чем для чисто английского и даже их смеси.

Количество коллизий я не замерял, но судя по некоторым тестам sdbm здесь тоже себя хорошо ведет.

PS: это для моих потребностей важна именно равномерность, не буду утверждать что для всех остальных случаев SDBM алгоритм лучше/быстрее/пр., но вероятно что именно так.