Нужно ли выводить хеш-функцию меньше, чем количество сегментов?

Question

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

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 должно быть меньше количества сегментов? Что делает быть взаимно простым с длиной таблицы? Разве это не должно быть взаимно простым для СОВЕЩАНИЙ?

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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