Теоретический прорыв может увеличить объем хранилища данных

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

Предположим, например, что база данных предназначена для хранения номеров социального страхования 10 000 человек, – предлагает Кузмаул. «Мы берем ваш номер социального страхования x, а затем вычисляем хеш-функцию x, h (x), которая дает вам случайное число от единицы до 10 000». Следующий шаг – взять это случайное число h (x), перейти в эту позицию в массиве и поместить в это место x, номер социального страхования.

Если что-то уже занимает это место, говорит Кушмаул, «вы просто переходите к следующей свободной позиции и кладете ее туда. Отсюда и термин «линейное зондирование», когда вы продолжаете линейно двигаться вперед, пока не найдете открытое место ». Чтобы позже получить этот номер социального страхования, x, вы просто переходите в указанное место h (x), а если его там нет, вы двигаетесь вперед, пока не найдете x или не перейдете в свободное положение и не придете к выводу, что x равен нет в вашей базе данных.

Существует несколько иной протокол для удаления элемента, например номер социального страхования. Если вы просто оставили пустое место в хеш-таблице после удаления информации, это может вызвать путаницу, когда вы позже попытаетесь найти что-то еще, так как свободное место может ошибочно указывать на то, что элемент, который вы ищете, нигде не может быть найден. база данных. Чтобы избежать этой проблемы, объясняет Кушмауль, «вы можете перейти к месту, где элемент был удален, и поставить там небольшой маркер, называемый« надгробие », который означает, что раньше здесь был элемент, но теперь его нет».

Эта общая процедура соблюдается более полувека. Но за все это время почти все, кто использовал хеш-таблицы с линейным зондированием, предполагали, что если вы позволите им заполниться, длинные участки занятых мест будут объединяться, образуя «кластеры». В результате время, необходимое для поиска свободного места, резко возрастет – по сути, квадратично – до такой степени, что это будет непрактично. Следовательно, люди были обучены работать с хэш-таблицами при низкой емкости – практика, которая может нанести экономический ущерб, влияя на количество оборудования, которое компания должна покупать и поддерживать.

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

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

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

Кузмаул вместе с Бендером и Кузмаулем изложил эти выводы в опубликованной ранее в этом году статье, которая будет представлена ​​в феврале на симпозиуме по основам компьютерных наук (FOCS) в Боулдере, штат Колорадо.

Кузмауля. Научный руководитель, профессор информатики Массачусетского технологического института Чарльз Лейзерсон (который не участвовал в этом исследовании), согласен с этой оценкой. «Эти новые и удивительные результаты опровергают одно из самых старых традиционных представлений о поведении хеш-таблиц», – говорит Лейзерсон. «Уроки будут звучать в течение многих лет как среди теоретиков, так и среди практиков».

Что касается претворения их результатов в жизнь, отмечает Кушмауль, «при построении хеш-таблицы необходимо учитывать множество факторов. Хотя мы значительно продвинулись в этой истории с теоретической точки зрения, мы только начинаем исследовать экспериментальную сторону вещей ».