Рубрики
Без рубрики

Решение: дизайн hashmap (версия 2)

Это является частью серии объяснений решений LeetCode (индекс). Если вам понравилось это решение или fou … с меткой алгоритмы, JavaScript, Java, Python.

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

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

Проблема LeetCode #706 (легко): дизайн hashmap

Описание:

( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++

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

Чтобы быть конкретным, ваш дизайн должен включать эти функции:

  • положить (ключ, значение) : Вставьте A (ключ, значение) Пара в хэшмап. Если значение уже существует в HashMap, обновите значение.
  • получить (ключ) : Возвращает значение, на которое отображается указанный ключ, или -1 Если эта карта не содержит отображения для ключа.
  • удалить (ключ) : Удалите отображение для клавиши значения, если эта карта содержит отображение для ключа.

Примеры:

Вход: [«Myhashmap», «положить», «положить», «получить», «получить», «положить», «получить», «удалить», «получить»] [[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]
Выход: [NULL, NULL, NULL, 1, -1, NULL, 1, NULL, -1]
Объяснение: Myhashmap myhashmap (); hashmap.put (1, 1); hashmap.put (2, 2); hashmap.get (1); // возвращает 1 hashmap.get (3); // возвращает -1 (не найдено) hashmap.put (2, 1); // Обновление существующего значения hashmap.get (2); // возвращает 1 hashmap.remove (2); // Удалить отображение для 2 hashmap.get (2); // возвращает -1 (не найдено)

Ограничения:

  • Все ключи и значения будут в диапазоне [0, 1000000] Анкет
  • Количество операций будет в диапазоне [1, 10000] .
  • Пожалуйста, не используйте встроенную библиотеку HashMap.

Идея:

( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++

Hashmaps были созданы, чтобы ускорить время поиска данных, надеюсь, O (1) время . Массивы Сделайте это естественно с помощью индекса, но это становится более сложным, если вы пытаетесь найти запись каким-то другим неиндексным значением вместо этого.

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

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

В этом случае мы можем использовать функцию хэширования для преобразования ключа в целое число в пределах границ диапазона индекса нашего массива HashMap. В идеальной ситуации это позволило бы нам уменьшить размер массива HashMap до максимального количества записей, которые являются 10^4 Анкет К сожалению, однако, это всегда возможно для столкновения существовать, когда два ключа перейдут к одному и тому же целому числу с помощью функции хэширования.

Чтобы справиться с столкновениями, мы можем просто сделать каждый из элементов нашего массива HashMap A Связанный список Анкет Это позволит нам относиться к ним как к простому стеку, где мы сначала смотрим на последнее добавленное Узел а затем перейдите к следующему, пока мы не найдем правильный ключ.

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

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

Есть много, много функций хеширования, но для этой проблемы мы будем использовать очень простое Мультипликативная функция хеширования Используя Большой главный множитель а затем modulo Результат желаемого размера (также главный) нашего массива HashMap. Надеемся, что это должно привести к ровному распределению записей по всему массиву HashMap.

get () Метод довольно прост, тогда. Мы просто hash () Наш ключ , получить доступ к соответствующему ведро в нашем массиве HashMap ( data ) и перейдите через связанный список (при необходимости) и верните правильный val , или -1 Если ключ не найден.

Для put () Метод, мы должны сначала удалить () любой более ранний экземпляр этого ключ Чтобы избежать цепочки нескольких версий ключ Определение в нашем связанном списке. Тогда мы просто формируем Новый список Во главе правильного ведра Hashmap, отталкивая любого других.

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

Реализация:

Python имеет deque и у Явы LinkedList Это может выполнить работу связанного управления списками, но это составляет за счет эффективности. В этом случае это не стоит использовать за обычаем ListNode Классовая реализация.

Код JavaScript:

( Прыгните к : Описание задачи Идея решения

class ListNode {
    constructor(key, val, next) {
        this.key = key
        this.val = val
        this.next = next
    }
}
class MyHashMap {
    constructor() {
        this.size = 19997
        this.mult = 12582917
        this.data = new Array(this.size)
    }
    hash(key) {
        return key * this.mult % this.size
    }
    put(key, val) {
        this.remove(key)
        let h = this.hash(key)
        let node = new ListNode(key, val, this.data[h])
        this.data[h] = node
    }
    get(key) {
        let h = this.hash(key), node = this.data[h]
        for (; node; node = node.next)
            if (node.key === key) return node.val
        return -1
    }
    remove(key) {
        let h = this.hash(key), node = this.data[h]
        if (!node) return
        if (node.key === key) this.data[h] = node.next
        else for (; node.next; node = node.next)
            if (node.next.key === key) {
                node.next = node.next.next
                return
            }
    }
};

Код Python:

( Прыгните к : Описание задачи Идея решения

class ListNode:
    def __init__(self, key, val, nxt):
        self.key = key
        self.val = val
        self.next = nxt
class MyHashMap:
    def __init__(self):
        self.size = 19997
        self.mult = 12582917
        self.data = [None for _ in range(self.size)]
    def hash(self, key):
        return key * self.mult % self.size
    def put(self, key, val):
        self.remove(key)
        h = self.hash(key)
        node = ListNode(key, val, self.data[h])
        self.data[h] = node
    def get(self, key):
        h = self.hash(key)
        node = self.data[h]
        while node:
            if node.key == key: return node.val
            node = node.next
        return -1
    def remove(self, key: int):
        h = self.hash(key)
        node = self.data[h]
        if not node: return
        if node.key == key:
            self.data[h] = node.next
            return
        while node.next:
            if node.next.key == key:
                node.next = node.next.next
                return
            node = node.next

Код Java:

( Прыгните к : Описание задачи Идея решения

class ListNode {
    int key, val;
    ListNode next;
    public ListNode(int key, int val, ListNode next) {
        this.key = key;
        this.val = val;
        this.next = next;
    }
}
class MyHashMap {
    static final int size = 19997;
    static final int mult = 12582917;
    ListNode[] data;
    public MyHashMap() {
        this.data = new ListNode[size];
    }
    private int hash(int key) {
        return (int)((long)key * mult % size);
    }
    public void put(int key, int val) {
        remove(key);
        int h = hash(key);
        ListNode node = new ListNode(key, val, data[h]);
        data[h] = node;
    }
    public int get(int key) {
        int h = hash(key);
        ListNode node = data[h];
        for (; node != null; node = node.next)
            if (node.key == key) return node.val;
        return -1;
    }
    public void remove(int key) {
        int h = hash(key);
        ListNode node = data[h];
        if (node == null) return;
        if (node.key == key) data[h] = node.next;
        else for (; node.next != null; node = node.next)
            if (node.next.key == key) {
                node.next = node.next.next;
                return;
            }
    }
}

C ++ Код:

( Прыгните к : Описание задачи Идея решения

struct Node {
public:
    int key, val;
    Node* next;
    Node(int k, int v, Node* n) {
        key = k;
        val = v;
        next = n;
    }
};
class MyHashMap {
public:
    const static int size = 19997;
    const static int mult = 12582917;
    Node* data[size];
    int hash(int key) {
        return (int)((long)key * mult % size);
    }
    void put(int key, int val) {
        remove(key);
        int h = hash(key);
        Node* node = new Node(key, val, data[h]);
        data[h] = node;
    }    
    int get(int key) {
        int h = hash(key);
        Node* node = data[h];
        for (; node != NULL; node = node->next)
            if (node->key == key) return node->val;
        return -1;
    }    
    void remove(int key) {
        int h = hash(key);
        Node* node = data[h];
        if (node == NULL) return;
        if (node->key == key) data[h] = node->next;
        else for (; node->next != NULL; node = node->next)
            if (node->next->key == key) {
                node->next = node->next->next;
                return;
            }
    }
};

Оригинал: “https://dev.to/seanpgallivan/solution-design-hashmap-ver-2-3ihj”