Миллионы пользователей Интернета создают терабайты контента каждый день, и самое удивительное: количество контента удваивается каждые шесть месяцев! Поэтому нам нужен эффективный механизм поиска или новые структуры данных для хранения и доступа к данным с таким ростом. С другой стороны, многим приложениям требуется механизм, поддерживающий только словарные операции: вставка, поиск и удаление. Например, компилятор, переводящий язык программирования, поддерживает таблицу символов, в которой ключи элементов представляют собой строки символов, соответствующие идентификаторам на языке.

Но критический вопрос: что не так с традиционными структурами данных, такими как массивы и связанные списки? Если большие данные хранятся в массиве, количество времени, необходимое для поиска элемента в массиве, равно O (log n) или O (n) в зависимости от того, отсортирован массив или нет. По крайней мере, сценарий O (n) не может быть жизнеспособным вариантом, если нам нужно обработать огромный набор данных. С другой стороны, поиск элемента в хеш-таблице в худшем случае может занять время O (n), но на практике хеширование выполняется исключительно хорошо. При разумных предположениях среднее время поиска элемента в хеш-таблице составляет O (1). Итак, пришло время глубоко погрузиться в понимание эффективной идеи хеширования и хеш-таблиц!

Таблица прямых адресов

Прямая адресация - это основная идея хеширования, которая хорошо работает, когда всех возможных ключей мало. Предположим, приложению требуется механизм хранения данных, в котором каждый элемент имеет не слишком большой ключ. Мы можем предположить, что нет двух элементов с одинаковым ключом, т.е. ключи разные, а диапазон ключей составляет от 0 до m-1. Для реализации мы можем настроить массив T [0..m-1], в котором:

  • T [i] = k, если ключ данных k = i
  • T [i] = NULL, иначе

Это таблица прямых адресов, в которой каждая операция словаря (вставка, поиск и удаление) займет O (1) раз! Но в чем тут проблема? Считать!

Ссылка на изображение: Книга CLRS

На изображении выше каждый ключ в юниверсе U = {0, 1, 2,… .9} соответствует индексу в таблице. Набор фактических ключей K = {2, 3, 5, 8} определяет слоты в таблице, которые содержат указатели на элементы. Для некоторых приложений сама таблица прямых адресов может содержать элементы в памяти: вместо того, чтобы сохранять значения ключа с указателем из слота в таблице, мы можем сэкономить пространство, сохранив значение в самом слоте. Однако у нас должен быть какой-то способ узнать, пуст слот или нет. Считать!

Идея хеш-таблицы

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

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

Таким образом, обратная сторона прямой адресации очевидна: если набор всех возможных ключей велик, хранение таблицы T размера, равного всем возможным ключам, может быть непрактичным или даже невозможным, учитывая объем памяти, доступный на типичном компьютере. Кроме того, набор сохраненных ключей K может быть настолько мал, что большая часть выделенного пространства будет потрачена впустую.

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

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

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

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

  • Предварительная обработка для вычисления ключа поиска (натурального числа) из заданных входных данных.
  • Использование хеш-функции для преобразования ключа поиска в индекс массива.
  • Вставка или доступ к желаемому значению с помощью ключа.

Математическая перспектива хеш-таблицы

Структура данных карты в математическом смысле - это связь между двумя наборами. Мы можем определить карту M как набор пар, где каждая пара находится в форме (ключ, значение), где для данного ключа мы можем найти значение, используя некоторую функцию, которая сопоставляет ключи со значениями. Проще говоря, мы можем думать о массиве как о карте, где ключ является индексом, а значение - это значение, доступное по этому индексу, то есть для данного массива A [], если i является ключом, то мы можем найти значение с помощью просто ища A [i].

Хеширование - это компромисс между временем и памятью.

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

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

Введение в хэш-функции

Если у нас есть массив, который может хранить m пар ключ-значение, тогда нам нужна хеш-функция для преобразования любого заданного ключа в индекс этого массива: целое число в диапазоне [0, m - 1]. Здесь нам нужна хэш-функция, которую легко вычислить и которая равномерно распределяет ключи, т.е. для каждого ключа каждое целое число от 0 до m-1 должно быть одинаково вероятным.

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

Если функцию легко вычислить, то получить доступ к ключу также легко. Однако, поскольку все возможные ключи большие, а таблица мала, независимо от того, какую функцию мы используем, многие ключи будут отображаться в одном и том же месте в таблице. Таким образом, нам нужно иметь дело с двумя ситуациями: (1) найти хеш-функцию, которая минимизирует вероятность коллизий, и (2) обработать коллизии.

Несмотря на то, что все возможные ключи больше, чем размер таблицы, фактический набор ключей, которые мы обрабатываем, обычно не слишком велик. Конечно, никакая хеш-функция не может отобразить все возможные наборы ключей без коллизий. Если отображение единообразно, если количество ключей равно n, а размер хеш-таблицы равен m, то в каждое местоположение будет сопоставлено примерно n / m ключей.

Базовая хеш-функция

Если ключи являются действительными числами от 0 до 1, мы можем просто умножить каждый ключ на m и округлить до ближайшего целого числа, чтобы получить индекс от 0 до m-1, то есть хеш-функция равна h (k) = ⌊ км⌋

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

Метод разделения или модульное хеширование

Это наиболее часто используемый метод хеширования, который также называется модульным хешированием. В методе деления хэш-функций мы сопоставляем ключ k в один из m слотов, беря остаток от k, разделенный на m, то есть хеш-функция равна h (k) = k mod m. Например, если размер хеш-таблицы m = 12 и ключ k = 100, тогда h (k) = 4. Поскольку требуется только одна операция деления, хеширование делением выполняется довольно быстро. Но при использовании метода деления мы обычно избегаем конкретных значений m или выбираем конкретное значение m:

  1. m не должно быть степенью 2, так как если m = 2 ^ p, то h (k) - это просто p битов младшего порядка k. Если мы не знаем, что все p-битовые шаблоны низкого порядка одинаково вероятны, нам лучше разработать хеш-функцию, которая будет зависеть от всех битов ключа.
  2. Мы должны выбрать размер массива m простым и для любого положительного целочисленного ключа k. Этот подход эффективен для равномерного распределения ключей от 0 до m - 1 и минимизации конфликтов ключей. Если m не является простым, может случиться так, что не все биты ключа играют роль, и хеш-функция может не распределять значения равномерно. Простое число, не слишком близкое к точной степени двойки, часто бывает хорошим выбором для m.
  • Предположим, что если ключи представляют собой числа с основанием 10, а M равно 10 ^ k, то используются только k наименьших значащих цифр. Такой выбор может быть проблематичным!
  • Предположим, мы хотим выделить хеш-таблицу с конфликтами, разрешаемыми цепочкой, для хранения примерно n = 2000 ключей. Мы не против изучить в среднем 3 элемента при неудачном поиске, поэтому мы выделяем хеш-таблицу размером m = 701. Мы могли бы выбрать m = 701, потому что это простое число около 2000/3, но не близко к какой-либо степени двойки. Если рассматривать каждый ключ k как целое число, наша хеш-функция будет иметь вид h (k) = k mod 701.
  • Предположим, что ключи - это трехзначные телефонные коды городов и m = 100. Если средняя цифра кодов регионов равна 0 или 1, то этот выбор строго отдает предпочтение значениям меньше 20. Лучше использовать простое значение для лучше разгоняет их (простое значение, не близкое к 100, будет работать лучше). Точно так же IP-адреса, которые используются в Интернете, представляют собой двоичные числа, которые не являются случайными по тем же причинам, поэтому нам нужно использовать размер таблицы, который является простым (в частности, не степенью 2), если мы хотим использовать модульное хеширование. разогнать их.

3. Если размер таблицы не может быть легко отрегулирован до простого числа, то можно использовать следующую хеш-функцию: h (k) = (k mod p) mod m, где p - простое число, а p ›m (p должно быть достаточно большим, чем m, чтобы быть эффективным, но оно также должно быть значительно меньше, чем количество всех возможных значений ключей). Другой факт: найти большой список простых чисел непросто. Другая возможность заключается в следующем: случайным образом выберите два числа a и b, такие, что a, b ‹p и a * 0, и пусть h (k) = (ak + b mod p) mod m. Эту функцию сложнее вычислить, чем предыдущую, но ее преимущество состоит в том, что в среднем она очень хороша для всех входных данных.

4. Как мы уже упоминали, ни одна хеш-функция не может быть подходящей для всех входных данных. Использование простых чисел, как описано, довольно безопасно, поскольку большинство данных на практике не имеют структуры, связанной с простыми числами. С другой стороны, всегда возможно (хотя и маловероятно), что в определенном приложении кто-то захочет сохранить результаты некоторых экспериментов, проведенных с целыми числами, все из которых имеют форму r + kp для константы r. Все эти числа, конечно, будут иметь одинаковые хеш-значения, если используется m = p. Мы можем пойти дальше идеи скремблирования данных с хешированием и использовать случайную процедуру для выбора хеш-функции!

5. Еще один пример! если есть 250 студентов, идентифицированных по их номеру социального страхования, мы не будем выделять массив размером 1 миллиард для хранения информации о них (существует 1 миллиард возможных номеров социального страхования). Вместо этого мы можем использовать последние три цифры чисел, и в этом случае нам понадобится только массив размером 1000. Но могут быть студенты с такими же последними тремя цифрами (на самом деле, для 250 студентов вероятность этого вполне высокий). Мы также можем использовать последние четыре цифры или последние три цифры и первую букву имени учащегося, чтобы еще больше уменьшить количество дубликатов. Однако использование большего количества цифр требует таблицы большего размера и приводит к меньшему использованию.

Простая функция хеширования для строк

Большинство хеш-функций предполагают, что ключи представляют собой набор натуральных чисел, то есть N = {0, 1, 2, 3,….}. Таким образом, если ключи не являются натуральными числами, нам нужно найти способ интерпретировать их как натуральные числа. Например, мы можем интерпретировать строку как сумму значений ASCII символов в строке. Мы также можем разработать другие методы для преобразования каждого ключа в большое натуральное число в данном приложении.

int stringHashFunction(String s[], int size, int m) 
{
    int sum = 0
    for(int i = 0; i < size; i = i + 1)
        sum = sum + s[i]
    return sum % m
}

Сворачивание строк: лучшая хеш-функция для строк

Эта функция принимает строку в качестве входных данных и обрабатывает строку по четыре байта одновременно и интерпретирует каждый из четырехбайтовых фрагментов как одно длинное целочисленное значение. Целочисленные значения для четырехбайтовых фрагментов складываются, и полученная сумма преобразуется в диапазон от 0 до m-1 с использованием оператора модуля.

int stringFolding(String s[], int size, int m) 
{
    long sum = 0
    long mul = 1
    for (int i = 0; i < size; i = i + 1) 
    {
        mul = (i % 4 == 0) ? 1 : mul * 256
        sum = sum + s[i] * mul
    }
    return (int)(sum % m)
}

Например, если дана строка «aaaabbbb», то первые четыре байта («aaaa») будут интерпретироваться как целое значение 1,633,771,873, а следующие четыре байта («bbbb») будут интерпретироваться как целое значение 1,650,614,882. Их сумма составляет 3 284 386 755 (если рассматривать как целое число без знака). Если размер таблицы равен 101, то функция модуля заставит этот ключ хешировать в слот 75 в таблице.

Метод среднего квадрата

Хорошей хеш-функцией для использования с целочисленными значениями ключа является метод среднего квадрата. Метод среднего квадрата возводит значение ключа в квадрат, а затем извлекает средние r битов результата, давая значение в диапазоне от 0 до 2 ^ r - 1. Это хорошо работает, потому что большая часть или все биты значения ключа вносят вклад в результат.

Например, рассмотрим записи, ключи которых представляют собой 4-значные числа в базе 10. Цель состоит в том, чтобы хэшировать эти ключевые значения в таблицу размером 100, то есть в диапазоне от 0 до 99. Этот диапазон эквивалентен двум цифрам в базе 10, поэтому r = 2. Если введено число 4567, возведение в квадрат дает 8-значное число 20857489.

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

Метод умножения

Метод умножения для создания хеш-функций работает в два этапа. Сначала мы умножаем ключ k на константу A в диапазоне 0 ‹A‹ 1 и извлекаем дробную часть kA. Затем мы умножаем это значение на m и получаем результат. Короче говоря, хеш-функция равна h (k) = ⌊m (kA mod 1) ⌋, где «kA mod 1» означает дробную часть kA, то есть kA - ⌊kA⌋.

Преимущество метода умножения в том, что значение m не критично. Обычно мы выбираем степень двойки (m = 2 ^ p для некоторого целого числа p), поскольку мы можем легко реализовать эту функцию на большинстве компьютеров. Предположим, что размер слова машины равен w битов и что k умещается в одно слово. Мы ограничиваем A дробью вида s = 2w, где s - целое число в диапазоне 0 ‹s‹ 2w.

Сначала мы умножаем k на w-битовое целое число s = A * 2 ^ w. Результатом является 2w-битное значение r12 ^ w + r0, где r1 - старшее слово продукта, а r0 - младшее слово продукта. Желаемое p-битовое хеш-значение состоит из p наиболее значимых битов r0. Хотя этот метод работает с любым значением константы A, с некоторыми значениями он работает лучше, чем с другими. Оптимальный выбор зависит от характеристик хешируемых данных. Считать!

Специальное примечание о хэш-функциях

  • Хеш-функции должны равномерно преобразовывать набор ключей в набор случайных местоположений в диапазоне от 1 до m. Равномерность и случайность - суть хеширования. Например, вместо трех последних цифр номера социального страхования можно взять последние три цифры года рождения студента. Понятно, что это второстепенная хеш-функция, поскольку гораздо более вероятно, что многие студенты родились в один год, чем то, что многие студенты имеют одни и те же последние три цифры номера социального страхования.
  • Хорошая хеш-функция генерирует хеш-значения из ключей независимо от каких-либо шаблонов, которые могут существовать в данных. Например, модульное хеширование часто дает хорошие результаты, предполагая, что мы выбираем m как простое число, не связанное с какими-либо шаблонами в распределении ключей.
  • Конечно, одна и та же хеш-функция должна использоваться для всех обращений к одной и той же таблице. Однако во многих случаях существует потребность во многих независимых таблицах или таблицах, которые часто создаются и уничтожаются. В этих случаях при создании новой таблицы можно использовать другую хеш-функцию. Описанные выше случайные хеш-функции обладают некоторыми другими желательными свойствами.
  • Информация о распределении ключей может помочь нам разработать эффективную хеш-функцию. Например, предположим, что ключи - это строки, представляющие имя человека, тогда часто могут встречаться близкие по счету имена, такие как «Мохан», «Сохан», «Рохан». Здесь хорошая хеш-функция свела бы к минимуму вероятность того, что такие имена хешируются в один и тот же слот в хеш-таблице. Другими словами, для некоторых приложений хеш-функций могут потребоваться более сильные свойства, чем условие простого равномерного хеширования. Например, нам могут понадобиться «близкие» ключи, чтобы получить хеш-значения, которые находятся далеко друг от друга.

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

использованная литература

  • Книга: Алгоритмы CLRS
  • Книга: Алгоритмы Роберта Седжвика
  • Лекции Введение в алгоритмы от MIT OpenCourseWare
  • Книга: Руководство по разработке алгоритмов Стивена Скиены