Как получить числовой хеш заданной длины?

Question

[ddddd tttt]

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

Answer 1

[Василий Дёмин]

Берите любую хэш-функцию. Например, хэш-функцию Дженкинса.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

Comments

[Руслан .]

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

[Василий Дёмин]

Руслан ., Это верно для любой хэш-функции, т.к. не существует хэш-функций без коллизий.

[ddddd tttt]

Василий Дёмин, по этой функции нельзя сортировать по алфавиту. Поэтому не подходит. аа > аб, аб < ас то есть ни в порядке убывания, ни в порядке возрастания не отсортировать.

145642639725 аб
179039592072 аа
179208876726 ас

[ddddd tttt]

Василий Дёмин, или я ошибся с юникодом

[Василий Дёмин]

ddddd tttt, Я не до конца понимаю, зачем вам нужна хэш-функция. Вы с её помощью хотите упорядочивать строки? С помощью хэш-функции это сделать вряд ли возможно, так как при её использовании коллизии неизбежны.

[Василий Дёмин]

ddddd tttt, Нет, функция работает правильно

[ddddd tttt]

Василий Дёмин, это теги и коллизий будет не много.

[Василий Дёмин]

ddddd tttt, Я нашёл соответствующую тему на stackoverflow. В ответе была дана ссылка на статью про минимальную идеальную хэш-функцию, которая преобразует множество из n ключей в целое число от 0 до n-1. Если ваши теги имеют предел в длине, то данная хэш-функция вам подойдёт.

Answer 2

[Руслан .]

Это похоже на задачу автодополнения. Может лучше вместо хэша попробовать использовать префиксное дерево?
Это неплохо описано например тут:
https://habr.com/ru/post/111874/

Comments

[ddddd tttt]

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

[Руслан .]

ddddd tttt, тогда вам нужен не обычный хеш, а такой, который не нарушает алфавитный порядок при пересчёте из строки в число. В общем случае это не так, т.е. хэш при изменении одного бита на входе может дать кардинально отличающиеся значение на выходе и строка AA может оказаться больше чем ZZ.

Когда я писал про префиксное дерево, то имел ввиду, что вы его в памяти один раз построете на основе данных БД. А дальше к БД уже не обращаетесь, а поиск по дереву ведёте, там вам уже не нужно что-то сортировать.

Но если цель именно каждай раз по БД искать, то почему вы не хотите сортировку текста сделать на стороне БД без хэшей? Можно например функцией like выбрать подходящие строки из БД (если вы ищете от начала строки и имеете индекс по текстовом полю, like хорошо работает) и результат отсортировать, а затем вернуть например первую из строк полученного датасета - это все одним Sql запросом можно сделать.

[ddddd tttt]

Руслан . , like мне кажется будет медленно работать для 1млрд строк

[Руслан .]

ddddd tttt, при наличии индекса по текстовому полю и при условии что поиск выглядит как like 'abc%', т. е. ищем от начала строки, должно быть вполне подъемно. При таких условиях оптимизатор умеет использовать вместе с like индекс.