Рукописная хэш-карта? Так безжалостно, интервью было свернуто до этого уровня?

Впервые я увидел этот вопрос для интервью в статье начальника комбайна с неудобным именем:

手写HashMap,快手一面卒

Это... Я был оцепенел в то время. Мы все знаем, что структура данных HashMap представляет собой массив + связанный список + красно-черное дерево. Это ритм разрыва красно-черного дерева вручную?

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

Понимание хеш-таблиц

HashMap на самом деле является реализацией хеш-таблицы в структуре данных в Java.

Суть хеш-таблицы

Хеш-таблица также называется хеш-таблицей, давайте сначала посмотрим на определение хэш-таблицы:

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

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

Проще говоря, хеш-таблица состоит из двух элементов:桶数组и散列函数.

Bucket array: ряд рабочих станций
Хеш-функция: третий ребенок в углу

массив сегментов

Как мы знаем, существует базовый класс структур данных线性表, а линейная таблица делится на два типа,数组и链表.

В структуре данных хеш-таблицы структура данных для хранения элементов представляет собой массив, и каждую единицу в массиве можно представить как桶(Ведро).

Если несколько программистов закреплены за рабочими местами:蛋蛋,熊大,牛儿,张三, мы заметили, что эти имена более различимы, последнее слово является числом, мы можем извлечь его как关键码, как только они появятся, вы можете назначить их соответствующим пронумерованным рабочим станциям и сначала оставить неназначенные рабочие станции пустыми.

元素映射

Так какова временная сложность нашего поиска/вставки/удаления в этом случае? Очевидно, обаO(1).

Но и мы не тыквы, не можем же мы все иметь такие имена, как раз, два, три, четыре, пять, шесть и семь.南宫大牛, то как мы назначим его?

Это подводит нас ко второму ключевому элементу —散列函数.

хэш-функция

Нам нужно добавить элемент и桶数组Отношение отображения устанавливается для соответствующей позиции, и это отношение отображения散列函数, также называемая хеш-функцией.

Например, у нас есть куча случайных имен诸葛钢铁,刘华强,王司徒,张全蛋... Нам нужно использовать хэш-функцию, чтобы выяснить, какой станции должны быть присвоены эти имена.

散列函数

Построение хэш-функции

Хеш-функцию также называют哈希函数, если наш элемент данныхkeyявляется целым числом или может быть преобразовано в целое число, и отображаемый адрес может быть получен этими распространенными методами.

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

непосредственно на основеkeyДля сопоставления с соответствующей позицией массива, например, 1232 помещается в позицию нижнего индекса 1232.
цифровой анализ

Выбиратьkeyнекоторые цифры (например, десятки и сотни) в качестве местоположения отображения
квадратный метод

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

будетkeyРазделите на несколько сегментов с одинаковым количеством цифр, а затем используйте их сумму суперпозиции в качестве местоположения карты
остаточный метод

H(key)=key%p(pЭто наиболее широко используемый конструктор хеш-функций..

散列函数构造

В Java класс Object предоставляет метод hashCode() по умолчанию, который возвращает 32-битное целое число, которое на самом деле является адресом хранения объекта в памяти.

Однако это целое число должно быть обработано.В приведенных выше методах直接定址法Можно исключить, потому что мы не можем построить такой большой массив корзин.

И хеш-адрес, который мы наконец вычислили, должен максимально соответствовать длине массива сегментов, поэтому мы выбираем除留取余法.

хэш-коллизия

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

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

哈希冲突

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

метод цепного адреса

Этот метод также называется методом застежки-молнии. Он выглядит как извлечение связанного списка из массива сегментов и помещение элементов с хэш-коллизиями в связанный список. При поиске просматривайте связанный список спереди назад, чтобы найти соответствующийkeyВот и все.

链地址法

закон об открытых адресах

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

Есть много способов найти свободное место:

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

...

开放地址法

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

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

Создайте общую область переполнения

Устанавливается общая область переполнения, и конфликтующие элементы данных сохраняются в общей области переполнения.

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

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

Реализация HashMap

Простой HashMap, который мы реализовали, называетсяThirdHashMap, сначала определите общий дизайн:

Хеш-функция: hashCode() + метод деления и остатка
Разрешение конфликтов: метод цепных адресов

Общая структура выглядит следующим образом:

自定义HashMap整体结构

класс внутреннего узла

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

    /**
     * 节点类
     *
     * @param <K>
     * @param <V>
     */
    class Node<K, V> {
        //键值对
        private K key;
        private V value;

        //链表，后继
        private Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

Переменные-члены

В основном есть четыре переменных-члена, из которых массив Bucket используется как структура для загрузки элементов данных:

    //默认容量
    final int DEFAULT_CAPACITY = 16;
    //负载因子
    final float LOAD_FACTOR = 0.75f;
    //HashMap的大小
    private int size;
    //桶数组
    Node<K, V>[] buckets;

Метод строительства

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

    /**
     * 无参构造器，设置桶数组默认容量
     */
    public ThirdHashMap() {
        buckets = new Node[DEFAULT_CAPACITY];
        size = 0;
    }

    /**
     * 有参构造器，指定桶数组容量
     *
     * @param capacity
     */
    public ThirdHashMap(int capacity) {
        buckets = new Node[capacity];
        size = 0;
    }

хэш-функция

Хеш-функция — это оставшаяся часть функции hashCode(), о которой мы упоминали ранее, и длина массива.

    /**
     * 哈希函数，获取地址
     *
     * @param key
     * @return
     */
    private int getIndex(K key, int length) {
        //获取hash code
        int hashCode = key.hashCode();
        //和桶数组长度取余
        int index = hashCode % length;
        return Math.abs(index);
    }

положить метод

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

Приблизительная логика:

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

    /**
     * put方法
     *
     * @param key
     * @param value
     * @return
     */
    public void put(K key, V value) {
        //判断是否需要进行扩容
        if (size >= buckets.length * LOAD_FACTOR) resize();
        putVal(key, value, buckets);
    }

    /**
     * 将元素存入指定的node数组
     *
     * @param key
     * @param value
     * @param table
     */
    private void putVal(K key, V value, Node<K, V>[] table) {
        //获取位置
        int index = getIndex(key, table.length);
        Node node = table[index];
        //插入的位置为空
        if (node == null) {
            table[index] = new Node<>(key, value);
            size++;
            return;
        }
        //插入位置不为空，说明发生冲突，使用链地址法,遍历链表
        while (node != null) {
            //如果key相同，就覆盖掉
            if ((node.key.hashCode() == key.hashCode())
                    && (node.key == key || node.key.equals(key))) {
                node.value = value;
                return;
            }
            node = node.next;
        }
        //当前key不在链表中，插入链表头部
        Node newNode = new Node(key, value, table[index]);
        table[index] = newNode;
        size++;
    }

Метод расширения

Примерный процесс расширения:

Создайте новый массив с удвоенной емкостью
Перефразирует элементы текущего массива сегментов в новый массив.
Новый массив устанавливается в массив ведра карты

    /**
     * 扩容
     */
    private void resize() {
        //创建一个两倍容量的桶数组
        Node<K, V>[] newBuckets = new Node[buckets.length * 2];
        //将当前元素重新散列到新的桶数组
        rehash(newBuckets);
        buckets = newBuckets;
    }

    /**
     * 重新散列当前元素
     *
     * @param newBuckets
     */
    private void rehash(Node<K, V>[] newBuckets) {
        //map大小重新计算
        size = 0;
        //将旧的桶数组的元素全部刷到新的桶数组里
        for (int i = 0; i < buckets.length; i++) {
            //为空，跳过
            if (buckets[i] == null) {
                continue;
            }
            Node<K, V> node = buckets[i];
            while (node != null) {
                //将元素放入新数组
                putVal(node.key, node.value, newBuckets);
                node = node.next;
            }
        }
    }

получить метод

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

    /**
     * 获取元素
     *
     * @param key
     * @return
     */
    public V get(K key) {
        //获取key对应的地址
        int index = getIndex(key, buckets.length);
        if (buckets[index] == null) return null;
        Node<K, V> node = buckets[index];
        //查找链表
        while (node != null) {
            if ((node.key.hashCode() == key.hashCode())
                    && (node.key == key || node.key.equals(key))) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

Полный код:

完整代码

контрольная работа

Код теста выглядит следующим образом:

    @Test
    void test0() {
        ThirdHashMap map = new ThirdHashMap();
        for (int i = 0; i < 100; i++) {
            map.put("刘华强" + i, "你这瓜保熟吗？" + i);
        }
        System.out.println(map.size());
        for (int i = 0; i < 100; i++) {
            System.out.println(map.get("刘华强" + i));
        }
    }

    @Test
    void test1() {
        ThirdHashMap map = new ThirdHashMap();
        map.put("刘华强1","哥们，你这瓜保熟吗？");
        map.put("刘华强1","你这瓜熟我肯定要啊！");
        System.out.println(map.get("刘华强1"));
    }

Вы можете запустить его для себя, чтобы увидеть результаты.

Суммировать

Ну вот, мы реализовали простой HashMap, теперь Kuaishou больше не боится написанного от руки HashMap.

Куайшоу Интервьюер: Правда? Не верю. Я хочу, чтобы вы вручную написали версию красно-черного дерева...

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

Однако на самом деле нам не нужно так много думать, потому что г-н Ли уже написал это за нас, и нам нужно только позвонить.

В следующей статье я расскажу о HashMap, которым управляет г-н Ли, в виде интервью!

как,обрати внимание наНе теряйтесь, увидимся в следующий раз!

Ссылаться на:

[1] «Структуры данных и алгоритмы».

[2].Построить метод хеш-функции

[3].Золотые медалисты ACM объясняют алгоритм LeetCode «Хэш»

Первый личный публичный аккаунт статьи:трехконечное зло, добро пожаловать, обратите внимание!