Концепция и применение от хэш-таблицы к BitMap (1)

хеш-таблица

Когда дело доходит до хеш-таблиц, вы можете думать о часто используемых коллекциях.HashMap,HashTableЖдать.

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

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

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

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

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

Далее мы будем использовать HashMap, чтобы конкретно объяснить применение хеш-таблиц и методы разрешения конфликтов.

Принцип реализации HashMap

Основой HashMap в Java является массив Entry. Запись — это основная единица HashMap, и каждая запись содержит пару ключ-значение.

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

	static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
     }

Отсюда мы видим, что Entry на самом деле является односвязным списком. Вот почему мы говорим, что HashMap разрешает коллизии хэшей путем сжатия.

Проще говоря, HashMap состоит из массива + связанный список.Массив является основной частью HashMap, а связанный список существует в основном для разрешения хеш-конфликтов.Если в расположенном массиве нет связанного списка (следующий запись текущей записи указывает на ноль), то для таких операций, как поиск и добавление, к ней нужно обращаться только один раз; если найденный массив содержит связанный список, для операции добавления временная сложность составляет O (n). ; Для операции поиска по-прежнему необходимо пройти по связанному списку, а затем передать ключевой объектequalsМетоды сравниваются и перебираются один за другим. Таким образом, с точки зрения производительности, чем меньше связанных списков в HashMap, тем выше производительность.

Алгоритм хеш-таблицы

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

прямая адресация

Возьмите линейную функцию ключа ключевого слова в качестве хеш-адреса, например Hash(key) = key или Hash(key) = A*key+B; А и В являются константами.

Например: есть демографическая таблица от 1 до 100 лет, где в качестве ключа используется возраст, а хэш-функция берет сам ключ. Но этот метод неэффективен, временная сложность O(1), а пространственная сложность O(n), где n — количество ключевых слов.

Разделить с остатком

Остаток, полученный от деления значения ключа на простое число, меньшее длины хеш-таблицы, используется в качестве хеш-адреса.Hash(key) = key % p;

Выбор p здесь очень важен. Если p выбран правильно, конфликты могут быть сведены к минимуму. Как правило, p принимает наибольшее простое число, не превышающее m.

средний китаец

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

Например, если есть следующая последовательность ключевых слов {421, 423, 436}, а результат после возведения в квадрат равен {177241, 178929, 190096}, то {72, 89, 00} можно взять в качестве хэш-адреса.

метод складывания

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

метод случайных чисел

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

H(key)=random(key) , где random — случайная функция. Этот метод обычно используется, когда длины ключевых слов не равны.

Математический анализ

Имеется N d цифр, каждая из которых может иметь r различных символов. Частота появления этих r различных символов в каждом бите не обязательно одинакова, они могут быть равномерно распределены в некоторых битах, и каждый символ имеет равные шансы появления; в некоторых битах распределение неравномерно, и только определенные виды символов часто появляются символы. В зависимости от размера хеш-таблицы в качестве хэш-адреса можно выбрать несколько битов, в которых равномерно распределены различные символы.

Например, данные о днях рождения группы людей выглядят следующим образом:

年.月.日

95.10.03
95.11.23
96.07.12
95.04.21
96.02.15
...

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

Решение конфликта

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

метод закрытого хеширования

Известный также как метод открытой адресации, существует два вида линейного обнаружения и квадратичного обнаружения.

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

Например, есть набор ключевых слов {12, 13, 25, 23, 38, 34, 6, 84, 91}, длина хеш-таблицы равна 11, а хеш-функция имеет вид address(key)=key% 11. При вставке 12(хеш(12)=1), 13(хэш(13)=2), 25(хэш(25)=3) можно вставить напрямую, а когда вставляется 23, адрес 1 занят, поэтому он проверяется по адресу 1 по очереди (размер шага обнаружения может быть определен в зависимости от ситуации, например, (хэш (23) + 1)% 11 = 2, (хэш (23) + 2)% 11 = 3, (hash(23)+3)%11=4) , пока адрес 4 не будет обнаружен и не окажется пустым, затем в него вставляется 23.
Вторичное обнаружение: это улучшение для линейного обнаружения.Значение ключа, вставленное после линейного обнаружения, слишком сконцентрировано, так что значение ключа не может быть правильно сопоставлено с адресом после прохождения через хеш-функцию.Слишком концентрированное также приведет к поиску и удалению. низкая эффективность. Поэтому через метод вторичного обнаружения берем текущий адрес и добавляем, новые адреса, которые можно получить, будут немного разбросаны.

, пока адрес 5 не будет обнаружен и не окажется пустым, то в него вставляется 23.

Перефразирование

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

Метод открытой цепи (хеш-база)

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

Когда в цепочке слишком много данных, мы можем использовать метод красно-черного дерева, чтобы уменьшить высоту, чтобы сохранить баланс и не перегружать.

BitMap

BitMap понимается как значение растрового изображения, а бит Bit используется для обозначения Value, соответствующего элементу, а Key — это элемент.

Среди всех структур данных, оптимизированных для производительности, наиболее часто используемой является хеш-таблица. Как упоминалось в предыдущем разделе, хеш-таблица имеет временной уровень O(1) для поиска местоположения. Но объем данных большой, памяти не хватает. Поскольку Bit используется для хранения данных, BitMap может значительно сэкономить место для хранения.

Идея алгоритма BitMap

На 32-битных машинах целое число, такое какint a;Он занимает в памяти 32 бита, и соответствующие 32 бита могут использоваться для соответствия десятичным числам от 0 до 31. Алгоритм BitMap использует эту идею для обработки сортировки и запроса больших объемов данных.

преимущество:

Эффективность работы высока, а сравнение и перестановка не допускаются;
Занимайте меньше памяти, например, N=10000000; нужно занимать только память, так как N/8=1250000 байт=1,25 МБ.

Недостаток: все данные не могут быть повторены. То есть невозможно отсортировать и найти повторяющиеся данные.

Например: 000000000000000000000000000010100 отмечены цифрами 2 и 4.

Для десятичных и двоичных битов требуется карта, которая отображает десятичные числа в биты. Таблица отображения карты подробно описана ниже.

таблица сопоставления карт

Если предположить, что общее количество операций сортировки или поиска равно N=10000000, то размер пространства памяти, на которое нам нужно подать заявку, равенint a[1 + N/32], из которых: a[0] занимает в памяти 32 и может соответствовать десятичным числам 0-31 и так далее, таблица BitMap такая:

a[0]--------->0-31
a[1]--------->32-63
a[2]--------->64-95
a[3]--------->96-127
...

Затем, как преобразовать десятичные числа в соответствующие биты, ниже описано, как преобразовать десятичные числа в соответствующие биты путем смещения.

Найдите индексы в массиве a, соответствующие десятичному числу 0-N: десятичное число 0-31, соответствующее a[0], сначала преобразуйте десятичное число n в остаток от 32, который можно преобразовать в соответствующие индексы в массиве a . Когда n=24, то n/32=0, тогда 24 соответствует индексу 0 в массиве a. Когда n=51, тогда n/32=1, тогда 51 соответствует индексу в массиве a как 1. Аналогично можно вычислить индекс 0-N в массиве a.
Найдите 0-N, соответствующее числу в 0-31: десятичному 0-31 соответствует 0-31, а 32-63 соответствует 0-31, то есть заданное число n можно получить по модулю 32, соответствующему 0-31. 31 числа.
Используйте сдвиг 0-31, чтобы сделать соответствующий 32-битный бит равным 1.

растровое приложение

Сортировать

Предположим, мы хотим отсортировать 5 элементов (4, 7, 2, 5, 3) в пределах 0-7 (при условии, что эти элементы здесь не повторяются), мы можем использовать метод Bit-map для достижения цели сортировки. Чтобы представить 8 чисел, нам нужно только 8 бит (1 байт).Сначала мы открываем пространство размером 1 байт и устанавливаем все биты в этих пространствах равными 0.

Пройдите через битовую область один раз и выведите номер бита, равный единице (2, 3, 4, 5, 7), чтобы цель сортировки была достигнута, а временная сложность была O (n).

быстрая дедупликация

Найдите количество уникальных целых чисел среди 250 миллионов целых чисел, и места в памяти недостаточно для размещения этих 250 миллионов целых чисел. Памяти недостаточно для хранения этих 250 миллионов целых чисел, мы можем быстро связать BitMap. Ключевой вопрос ниже заключается в том, как спроектировать нашу растровую карту для представления состояния этих 250 миллионов чисел. На самом деле проблема очень проста: есть только три состояния числа: небытие, только одно и повторение. Следовательно, нам нужно всего 2 бита для хранения состояния числа.Предположим, мы устанавливаем число равным 00, если оно не существует, 01, если оно существует один раз, и 11, если оно существует дважды или более. Тогда нам, вероятно, потребуется около десятков мегабайт дискового пространства.

Следующая задача состоит в том, чтобы пройти 250 миллионов чисел один раз.Если соответствующий бит состояния равен 00, измените его на 01, если соответствующий бит состояния равен 01, измените его на 11, если он равен 11, соответствующие биты состояния хода останутся неизменными. .

Наконец, мы подсчитываем биты состояния 01, чтобы получить количество неповторяющихся чисел, а временная сложность равна O(n).

Быстрый поиск

BitMap также можно использовать для быстрого запроса, в этом случае для числа нужен только один бит, 0 означает, что оно не существует, а 1 означает, что оно существует. Предположим, что заголовок выше изменен, как быстро решить, достаточно ли числа для существования в вышеуказанном наборе из 250 миллионов номеров.

Как и прежде, сначала мы проходим все числа один раз, а затем меняем соответствующий бит перехода на 1. После завершения обхода выполняется запрос.Поскольку наш BitMap принимает непрерывное хранение (в виде целочисленного массива, один элемент массива соответствует 32 битам), мы фактически принимаем идею сегментирования. Элемент массива может хранить биты состояния 32. Разделите запрашиваемое число на 32, найдите соответствующий элемент массива (сегмент), а затем вычислите остаток (%32), чтобы найти соответствующий бит состояния. Если это 1, это означает, что число существует, в противном случае число не существует.

Фильтр Блума

Иногда одного лишь BitMap недостаточно.Если объем данных слишком велик, например 64-битных данных, следует ли использовать BitMap в данный момент? Требуемый размер хранилища:

1 ПБ = 1024 ТБ, 1 ТБ = 1024 ГБ. А ЭБ (экзабайт, эксабайт) — это единица измерения статистических данных в информатике, 1ЭБ=1024ПБ. Такой масштаб BitMap больше не доступен для человеческого оборудования. Таким образом, преимущество Bitmap в том, что сложность пространства не увеличивается с увеличением количества элементов в исходной коллекции, отсюда же вытекает и его недостаток — сложность пространства увеличивается линейно с увеличением самого большого элемента в коллекции.

Итак, далее мы собираемся представить еще одну известную промышленную реализацию — фильтр Блума. Если Bitmap отображает все возможные целочисленные значения с помощью прямой адресации, что эквивалентно использованию хэш-функции, то фильтр Блума вводит k(k>1)k(k>1). Взаимно независимая хэш-функция гарантирует, что процесс взвешивания элементов завершено под заданным пробелом и ложноположительным показателем. На рисунке ниже показан фильтр Блума при k=3.

Одним из применений фильтров Блума является кэширование лавин.

Суммировать

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

Наше требование состоит в том, чтобы каждый элемент в коллекции имел исключительное пространство и мог найти метод сопоставления с этим пространством. Эксклюзивное пространство Для нашей задачи достаточно логического значения или достаточно 1 бита, мы просто хотим знать, появился ли определенный элемент. Если для каждого возможного значения выделяется 1 бит, объем памяти, необходимый для всех возможных значений 32-битного int, составляет: $2^{32}bit=2^{29}Byte=512MB$ . Это приводит к алгоритму BitMap. Мы представили идею алгоритма BitMap и некоторых приложений, включая приложения для сортировки, дедупликации, запросов и др. BitMap очень эффективен при применении этих больших объемов данных. Фильтр Блума можно рассматривать как расширение BitMap. Алгоритм с большим объемом данных имеет определенную погрешность, чтобы судить о том, повторяется ли отображение. Что касается конкретных деталей применения фильтра Блума, есть много контента, который будет представлен в следующей статье.

Наконец, добро пожаловать на покупку новой книги автора«Продвинутая архитектура микросервисов Spring Cloud».

Ссылаться на

Хеш-таблица (закрытый хэш, метод зиппер - хэш-база)
BitMap
Обработка больших данных — растровое изображение