Должен ли вывод хеш-функции быть ограничен меньшим количеством сегментов?

Я читал об интервью этого человека "в известной поисковой компании".

http://asserttrue.blogspot.com/2009/05/one-of-toughest-job-interview-questions.html

Ему задали вопрос, который привел его к реализации хеш-таблицы. Он сказал следующее:

HASH = INITIAL_VALUE;
FOR EACH ( CHAR IN WORD ) {
HASH *= MAGIC_NUMBER
HASH ^= CHAR
HASH %= BOUNDS
}
RETURN HASH

Я объяснил, что длина массива хэш-таблицы должна быть простой, а число BOUNDS меньше длины таблицы, но взаимно просто с длиной таблицы.

Почему число BOUNDS должно быть меньше количества ведер? Что делает взаимно простое с длиной таблицы? Разве это не должно быть взаимно простым с ГРАНИЦАМИ?


algorithm hash hashtable
person Unknown    schedule 13.05.2009    source источник

Ответы (3)


arrow_upward
4
arrow_downward

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

Кроме того, ограничение вывода количеством сегментов должно быть ВНЕ хеш-функции. Это деталь реализации этой конкретной хеш-таблицы. У вас может быть очень большая таблица с большим количеством сегментов, а другая — с несколькими. Оба должны использовать одну и ту же функцию string-> hash

Кроме того, если вы читаете страницу, на которую вы ссылаетесь, это довольно интересно. Я бы реализовал его хеш-таблицу как что-то вроде 10 000 ведер. Для тех, кто ее не читал, в статье предлагается ~ 4 000 000 000 ведер для хранения примерно 1 000 000 возможных слов. Для коллизий каждое ведро имеет вектор структур слов, каждое из которых содержит количество, строку открытого текста и хэш (уникальный в пределах ведра). Это будет использовать гораздо меньше памяти и лучше работать с современными кэшами, поскольку ваш рабочий набор будет намного меньше.

Чтобы еще больше сократить использование памяти, вы можете поэкспериментировать с отбраковкой слов из хэша на этапе ввода, которые выглядят так, как будто они находятся ниже первых 100 000 на основе текущего подсчета.

person Tom Leys    schedule 13.05.2009
comment
Спасибо за вклад, Том. У меня было ощущение, что он неправ, но мне пришлось попросить StackOverflow убедиться, что не мне не хватает знаний. - person Unknown; 13.05.2009
comment
BOUNDS должно быть числом ведер, иначе последние несколько ведер будут недоиспользованы, как вы думаете, может быть, это какой-то особый трюк, когда нужно изменить размер хеш-таблицы? - person Unknown; 13.05.2009
comment
Я полностью согласен с тем, что %BOUNDS совершенно неуместен. Хэш данного ввода должен быть независим от того, для чего этот хэш используется. Вы можете использовать его как ключ к таблице, вы можете связать его бантиком, вы можете передать его \dev\null. Хеш-функция должна быть в блаженном неведении. - person leoger; 14.05.2009
comment
@Unknown - Нет, это ограничение. Хэш-функция устанавливает верхний предел размера вашей карты. Кроме того, если ваша карта не кратна хэш-границам, первая часть (границы карты % хэш-границы) вашей карты будет использоваться чрезмерно. Чем шире диапазон вывода хэш-функции, тем она лучше в общем случае. Равномерное распределение выходных хэшей в этом диапазоне еще более важно. Однако я не специалист в этой области. - person Tom Leys; 15.05.2009

arrow_upward
0
arrow_downward

Однажды я проходил собеседование на работу в известную поисковую компанию. У меня точно такой же вопрос. Я попытался решить эту проблему с помощью хеш-таблицы.

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

person Community    schedule 13.05.2009

arrow_upward
0
arrow_downward

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

Я думаю, что парень в статье перехитрил самого себя.

person patros    schedule 19.05.2009