Другая форма хэш-структуры — метод открытого адреса.

алгоритм

В этой статье мы обсудим основную тему структур данных: открытая адресация в хеш-структурах.

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

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

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

root = hash(key) % m   // 第一个位置，m 为数组的长度
index_i = (root + p(key, i)) % m  // 链条中的第 i 个位置

index_1 = (root + p(key, 1)) % m
index_2 = (root + p(key, 2)) % m 
...

Этой математической функцией является p в приведенном выше коде — probe sequence (зондовая последовательность). Процесс поиска пустых позиций представляет собой пошаговый процесс обнаружения. Различные ключи будут генерировать разные последовательности тестов.

При поиске, если ключ, сохраненный в первой позиции, не является целевым ключом, продолжайте поиск по пути обнаружения, пока не будет найдена или обнаружена пустая позиция.

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

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

// m = 2^n，c 必须是一个奇数
p(key, i) = c * i
index_i = root + c * i

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

public class HashTest {
    public static void main(String[] args) {
        int m = 1 << 16;
        int c = 111111;
        Set<Integer> nums = new HashSet<>();
        for (int i = 1; i < m; i++) {
            int p = c * i % m;
            if(nums.contains(p)) {
                System.out.println("duplicated");
                return;
            }
            nums.add(p);
        }
        System.out.println("no duplicate");
    }
}

------------
no duplicate

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

Чтобы не прерывать путь обнаружения, есть две реализации удаления

В удаленной позиции ставится специальная метка удаления, и при поиске можно сразу пропустить и продолжить поиск назад по пути обнаружения. Следует отметить, что эта удаленная позиция будет повторно использована при вставке последующих новых элементов. При вставке элемента он проходит путь обнаружения и сталкивается с позицией первого маркера удаления, который не может быть вставлен немедленно. Потому что возможно, что этот элемент находится во второй половине пути зондирования. Таким образом, вам нужно пройти до конца, если вы обнаружите, что элемент не существует в пути, тогда вам нужно вернуться и вставить его в первую позицию, где найден маркер удаления. Если вы удалите слишком много местоположений, это может повлиять на производительность поиска и вставки. Удалите все элементы во второй половине пути зонда и снова вставьте их. Если путь длинный, это может повлиять на производительность вставки. Вроде бы он здесь, но есть еще одна вещь, которую мы не заметили. То есть, при условии использования функции обнаружения p(key, i) = c * i, если первая позиция нескольких разных хэшей ключей одинакова, то они будут использовать один и тот же путь обнаружения. Потому что путь обнаружения полностью определяется первой позицией, независимо от ключа ввода. Затем эти связанные ключи будут сгруппированы на пути зондирования, что может привести к менее равномерному распределению данных.

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

p(key, i) = h2(key) * i

С этим покончено, читатели, у вас есть что еще добавить?

Категории