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

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

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

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

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

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

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

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

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

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

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