TypeScript реализует Map и HashMap

JavaScript
TypeScript реализует Map и HashMap

предисловие

Словарь(Map) и хэш-таблица (HashMap) — это метод, использующий [ключ (key),стоимость(value)] для хранения данных в виде структуры данных.

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

Реализовать идеи

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

Реализация словаря

Словарь хранит данные в виде пар ключ-значение, его ключ представляет собой строку, какой ключ передается вызывающей стороной, таков и ее ключ

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

  • Добавить элементы в словарь (set)

    • Метод set принимает два параметра: ключ и значение.
    • Судя по правильности параметра, добавьте элемент в словарь, когда ключ и значение не равно null | undefined, в противном случае сразу верните false
    • Когда параметр действителен, преобразуйте ключ параметра в строку
    • Используйте ключ, преобразованный в строку, в качестве ключа в словаре, поместите ключ и значение в объект и сохраните объект в ключе, преобразованном в строку.
    • Поговорив об описанных выше операциях, мы успешно добавили элемент в словарь и вернули true.

  • Определить, находится ли ключ в словаре (hasKey)

    • Метод hasKey принимает один параметр: ключ
    • Поскольку данные в словаре хранятся в виде объектов, мы можем напрямую преобразовать ключ в строку, а затем передать его объекту словаря в качестве атрибута, и определить, является ли возвращаемый результат неопределенным | null, чтобы узнать, является ли ключ находится в словаре.

  • Получить значение, хранящееся в словаре, по ключу (get)

    • Метод get принимает один параметр: ключ
    • Преобразуйте ключ в строку, пропустите ее как свойство в объект словаря и используйте переменную для получения его возврата.
    • Определить, является ли возвращаемое значение null | undefined
    • Если возвращаемое значение не равно null | undefined, вернуть значение в его объекте, в противном случае вернуть undefined.

  • Удалить элемент из словаря по ключу (remove)

    • Метод удаления принимает один параметр: ключ
    • Определить, существует ли целевой параметр в объекте словаря (вызвать метод hasKey), если нет, напрямую вернуть false
    • Если целевой элемент существует в объекте словаря, преобразуйте ключ в строку, затем передайте его объекту словаря в качестве параметра и, наконец, вызовите метод удаления объекта, чтобы удалить целевой ключ и вернуть значение true.

  • Получить все объекты, хранящиеся в словаре (keyValues)

    • Метод keyValues ​​не получает никаких параметров и возвращаемое значение представляет собой массив объектов
    • Во-первых, объявите переменную массива (valuePairs) для хранения полученного объекта.
    • Получить все ключи в объекте словаря
    • Обходя полученный ключ, ключ будет проходить через объект словаря, переданный в качестве параметра.
    • Поместите значение, возвращаемое объектом словаря, в valuePairs и верните его.

  • Получите все ключи, хранящиеся в словаре (keys) & Получает словарь всех сохраненных значений (value)

    • метод keys принимает любой параметр
    • Объявить переменную массива (ключи) для хранения полученного ключа | Объявить переменную массива (значения) для хранения полученного значения
    • Получить все объекты, хранящиеся в словаре (вызвать метод keyValues)
    • Обходим полученный массив объектов
    • Если вы хотите получить ключ, поместите значение ключа текущего пройденного элемента в массив ключей, в противном случае поместите значение значений в массив значений.
    • возвратные ключи | значения

  • Перебрать данные в словаре (forEach)

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

  • Получить размер словаря (size), вызвать метод keyValues ​​и вернуть длину его массива

  • Проверить, не пуст ли словарь (isEmpty), вызовите метод size, определите, равен ли он 0, и верните результат оценки.

  • пустой словарь (clear), напрямую инициализируйте объект словаря пустым объектом

  • Преобразовать данные в словаре в строку (toString)

    • Метод ToString не получает никаких параметров
    • Если словарь пуст, верните пустую строку напрямую.
    • Когда словарь не пуст, получить все данные в словаре.
    • Объявите переменную (objString) для хранения каждого объекта в словаре, начальное значение которого равно 0 в массиве объектов словаря.
    • Пройдите полученный объект, объединив objString с пройденными данными, и верните objString.

Реализация хеш-таблицы

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

Когда словарь сохраняет элемент, ключ преобразуется в строку, а затем сохраняется элемент.

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

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

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

  • Добавить элемент в хеш-таблицу (put)

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

  • Вычислить хеш-значение (hashCode)

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

  • loseloseHashCodeРассчитать хэш-значение

    • Сначала мы оцениваем, является ли ключ числом, если это число, то оно не будет возвращено напрямую, и операция хеширования не будет выполнена.
    • Преобразуйте ключ в строку и объявите переменную (хэш) для хранения хеш-значения.
    • Пересекайте ключ, преобразованный в строку, вызовите функцию Charcodeat js, чтобы найти код Unicode каждого символа и добавить полученный код Unicode в хеш
    • После завершения обхода, чтобы предотвратить слишком большое значение, разделите хэш-значение на 37, чтобы получить остаток, и верните хэш.

  • djb2HashCodeРассчитать хэш-значение

    • Как и в методе lossloseHashCode, определите, является ли ключ числом, а затем преобразуйте его в строку.
    • Отличие в том, что хэш имеет начальное значение5381
    • Пройдите ключ, преобразованный в строку, получите код Unicode каждого пройденного символа, умножьте хэш-значение на 33, а затем добавьте к нему полученный код Unicode.
    • После завершения обхода разделите значение хеша на 1013, чтобы получить остаток и вернуть хеш.

  • Получить элемент в хеш-таблице по ключу (get)

    • Выполнить хэш-операцию над ключом, получить результат, передать его в качестве параметра объекту хеш-таблицы и получить элементы целевого ключа, хранящиеся в хеш-таблице.
    • Определить, является ли результат нулевым | неопределенным, если да, вернуть неопределенное значение, в противном случае вернуть его значение

  • Удалить элементы из хеш-таблицы по ключу (remove)

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

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

Обработка конфликтов хеш-значений в хеш-таблицах

Когда мы используем hashmap, если мы вызовем метод LosthashCode для расчета значения хеша, то скорость столкновения будет очень высокой. Вот два обычно используемых метода для решения проблем с хешми.

разделенная ссылка

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

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

  • Измените имя переменной таблицы приватных атрибутов.Поскольку значение метода ссылки разделения является типом связанного списка, а HashMap использует тип ValuePair, в js нет реального приватного атрибута, и тип атрибута таблицы не может быть изменен при наследовании, поэтому нам нужно изменить имя переменной (tableLink)

  • Переопределить метод put

    • Как и HashMap, определите действительность его ключа и значения.
    • Вычислите хеш-значение ключа и сохраните его в переменной (позиции)
    • Передайте position в качестве параметра tableLink, чтобы определить, является ли оно нулевым | undefined
    • Если не null | undefined, создайте связанный список в позиции tableLink
    • Добавьте объект Key & value в связанный список в позиции tableLink
    • Добавить успешно, вернуть true

  • Переопределить метод get (требуется получение элементов из связанного списка)

    • Вычислите хеш-значение ключа и сохраните его в переменной (позиции)
    • Получить элемент структуры связанного списка, хранящийся в позиции position
    • Если список lin не пуст, начните обход с заголовка цепочки до тех пор, пока ключ текущего элемента lathecoue не совпадет с ключом целевого параметра, а затем вернет соответствующее ему значение value.
    • Если связанный список пуст, вернуть undefined

  • Переопределить метод удаления (необходимо удалить элемент из связанного списка)

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

  • Переопределите метод очистки и укажите tableLink на пустой объект

  • Метод перезаписи KeyValues, HashMap хранится в связанном списке, вам нужно получить список из сохраненных объектов (valuePair)

    • Объявите переменную массива (valuePairs) для хранения полученного объекта ValuePair.
    • Получить все ключи в tableLink, преобразовать их в тип int и сохранить в переменной (keys)
    • Перемещайте ключи, получайте данные о пройденных в данный момент элементах структуры связанного списка и сохраняйте их в переменных (linkedList)
    • Если linkedList не пуст, пройдите данные в связанном списке из заголовка связанного списка, получите элементы в текущем пройденном связанном списке и сохраните их в valuePairs.
    • возвращаемое значениеPairs
Линейное зондирование

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

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

Далее рассмотрим, какие методы необходимо переписать для разрешения конфликтов с линейным зондированием.

  • Переопределить метод put

    • Как и в случае с HashMap, необходимо оценить достоверность его параметров и количество переданных параметров.
    • Вычислите хеш-значение ключа и сохраните его в переменной (позиции)
    • Определить, занята ли позиция таблицы
    • Если он не занят, создайте новый объект в положении и храните ключ и значение в нем
    • Если вы заняты, используйте переменную (индекс), чтобы получить значение позиции + 1 позиция
    • Пройдите значение позиции индекса таблицы.Если индекс не пуст, он всегда будет увеличиваться.
    • Когда обнаружена пустая позиция в таблице, создайте новый объект в индексной позиции таблицы, храните ключ и значение в нем и верните True

  • Переопределить метод получения

    • Вычислите хеш-значение ключа и сохраните его в переменной (позиции)
    • Определить, является ли элемент в позиции position таблицы нулевым | undefined, если нет, вернуть undefined
    • Определение того, равна ли позиция ключа позиции таблицы элементов целевому параметру ключа, если позиция равна прямому возвращаемому значению позиции значения
    • Если не равно, используйте переменную (индекс) для хранения значения позиции + 1 позиция
    • Обход значения позиции индекса таблицы.Если значение позиции индекса не пусто и ключ позиции индекса не равен ключу целевого параметра, индекс будет автоматически увеличиваться.
    • После завершения цикла определить, равен ли ключ элемента в позиции индекса текущей таблицы ключу целевого параметра, и если он равен, вернуть значение позиции индекса

  • Переопределить метод удаления

    • Вычислите хеш-значение ключа и сохраните его в переменной (позиции)
    • Определите, является ли позиция таблицы нулевой, если она равна нулю, верните false напрямую
    • Если ключ позиции position таблицы равен ключу целевого параметра, удалите элемент в позиции position, проверьте, не имеет ли удаление побочных эффектов, скорректируйте позицию элемента и верните true
    • Если они не равны, вам нужно объявить переменную (индекс), чтобы найти значение после позиции.Значение по умолчанию — позиция + 1
    • Перемещайтесь по элементу в позиции индекса таблицы. Если он не равен нулю и его ключ не равен целевому ключу, индекс будет автоматически увеличиваться.
    • После прохождения технологии, если элемент в позиции индекса не равен нулю, а ключ элемента в позиции индекса равен ключу целевого параметра, удалите элемент в позиции индекса в таблице, проверьте, было ли удаление имеет побочные эффекты, настроить положение элемента и вернуть true

  • Добавлен метод проверки наличия побочных эффектов у операции удаления (verifyRemoveSideEffect).Если возникает конфликт после удаления элемента, необходимо переместить конфликтующий элемент на предыдущую позицию, чтобы не образовалась пустая позиция.

    • Метод verifyRemoveSideEffect получает параметр: удаленный ключ, позиция удаленного ключа в таблице (removedPosition)
    • Вычислите хэш-значение ключа и сохраните его в переменной (хэше)
    • Используйте переменную для получения следующей позиции (индекса) позиции удаленного ключа, по умолчанию — removePosition+1.
    • Пройдите по таблице, если элемент в позиции индекса не равен нулю, получите хэш-значение ключа в текущей позиции индекса и сохраните его в переменной (posHash)
    • Если posHash меньше или равен hash или posHash меньше или равен removePosition, назначьте элемент в позиции индекса в таблице позиции removePosition.
    • Удалить элемент в позиции индекса в таблице
    • Назначить индекс для removePosition
    • Перейти к решению следующего цикла

код реализации

После анализа у нас появилась идея реализации, а затем мы сконвертируем вышеуказанные идеи в код.

Напишите интерфейс карты

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

  • Новый файл Map.TS
  • Создайте новый файл Dictionary-List-Models.ts.
  • Добавьте класс ValuePair в модели списка словарей и экспортируйте его, этот класс используется для хранения значения в словаре.
// 生成一个对象
export class ValuePair<K,V>{
    constructor(public key: K,public value: V) {}

    toString(){
        return `[#${this.key}: ${this.value}]`;
    }
}
  • Импортируйте класс ValuePair в Map, добавьте и определите методы, которые нам понадобятся позже, и укажите тип возвращаемого значения.
import {ValuePair} from "../../utils/dictionary-list-models.ts";

export default interface Map<K,V> {
    hasKey(key: K): boolean;
    set?(key: K, value: V): boolean;
    put?(key: K, value: V): boolean;
    hashCode?(key: K): number;
    remove(key: K): boolean;
    get(key: K): V|undefined;
    keyValues(): ValuePair<K, V>[];
    keys(): K[];
    values(): V[];
    forEach(callbackFn: (key: K, value: V) => any): void;
    size(): number;
    isEmpty(): boolean;
    clear():void;
    toString():string;
}

Реализовать класс словаря

  • Создайте новый файл Dictionary.ts и добавьте класс Dictionary для реализации интерфейса карты.
export default class Dictionary<K, V> implements Map<K, V> {

}
  • Объявить приватную таблицу атрибутов для хранения словаря
    private table: { [key: string]: ValuePair<K, V> };
  • Инициализируйте таблицу в конструкторе, объявите функцию преобразования значения в строку и присвойте ей значение по умолчанию.
// toStrFn用于将一个值转为字符串，可以自己来实现这部分逻辑，实例化时传进来
    constructor(private toStrFn: (key: K) => string = defaultToString) {
        this.table = {};
    }
  • Внедрить набор метод
    // 向字典中添加元素
    set(key: K, value: V) {
        if (key != null && value != null) {
            // 将key转为字符串，字典中需要的key为字符串形式
            const tableKey = this.toStrFn(key);
            this.table[tableKey] = new ValuePair(key, value);
            return true;
        }
        return false;
    }
  • Реализовать метод hasKey
    hasKey(key: K) {
        return this.table[this.toStrFn(key)] != null;
    }
  • Реализовать метод получения
    get(key: K) {
        const valuePair = this.table[this.toStrFn(key)];
        return valuePair == null ? undefined : valuePair.value;
    }
  • Реализовать метод удаления
    remove(key: K) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }
  • Реализовать метод keyValues
    keyValues(): ValuePair<K, V>[] {
        /* 使用ES2017引入的Object.values方法可以直接获取对象里存储的所有对应key的value值存进数组中 */
        const valuePairs = [];
        const keys = Object.keys(this.table);
        for (let i = 0; i < keys.length; i++){
            valuePairs.push(this.table[keys[i]])
        }
        return valuePairs;
    }
  • Реализовать метод ключей
    keys() {
        // 可以直接使用map获取对象的key
        // return this.keyValues().map(valuePair=> valuePair.key);
        const keys = [];
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            keys.push(valuePairs[i].key);
        }
        return keys;
    }
  • Реализовать метод значений
    values() {
        const values = [];
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            values.push(valuePairs[i].value);
        }
        return values;
    }
  • Реализовать метод forEach.
    forEach(callbackFn: (key: K, value: V) => any) {
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
            if (result === false) {
                break;
            }
        }
    }
  • Реализовать size, isEmpty, четкие методы
    size() {
        return this.keyValues().length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    clear() {
        this.table = {};
    }
  • Реализовать метод toString
    toString() {
        if (this.isEmpty()) {
            return '';
        }

        const valuePairs = this.keyValues();
        let objString = `${valuePairs[0].toString()}`;
        for (let i = 1; i < valuePairs.length; i++) {
            objString = `${objString},${valuePairs[i].toString()}`;
        }
        return objString;
    }

Пожалуйста, перейдите к полному коду:Dictionary.ts

написать тестовый код

Мы реализовали приведенный выше класс словаря. Теперь давайте проверим, нормально ли выполняется приведенный выше код.

const dictionary = new Dictionary();
dictionary.set("name","张三");
dictionary.set("age",20);
dictionary.set("id",198);
console.log("判断name是否在dictionary中",dictionary.hasKey("name"));
// 移除名为id的key
dictionary.remove("id");
console.log("判断id是否为dictionary中",dictionary.hasKey("id"));
console.log("将字典中存储的数据转为字符串",dictionary.toString())
// 获取dictionary中名为name的值
console.log("dictionary中名为name的值",dictionary.get("name"));
// 获取字典中所有存储的值
console.log("dictionary中所有存储的值",dictionary.keyValues());
// 获取字典中所有的键
console.log("dictionary中所有存储的键",dictionary.keys());
// 获取字典中所有的值
console.log("dictionary中所有存储的值",dictionary.values());
// 迭代字典中的每个键值对
const obj = {};
dictionary.forEach(function (key,value) {
    obj[key] = value;
})
console.log(obj)

Пожалуйста, перейдите к полному коду:DictionaryTest.js

Реализовать хеш-таблицу

  • Создайте новый класс HashMap и реализуйте интерфейс Map.
export class HashMap<K,V> implements Map<K, V>{

}
  • объявить таблицу и указать ее тип
    protected table:{ [key:number]: ValuePair<K, V> };
  • Инициализируйте таблицу в конструкторе и укажите значение в строковой функции, что позволит вызывающей стороне передать строковую функцию значения.
    constructor(protected toStrFn: (key: K) => string = defaultToString) {
        this.table = {};
    }

    // 生成哈希码
    hashCode(key: K): number {
        return this.loseloseHashCode(key);
    }

    // loselose实现哈希函数
    loseloseHashCode(key: K): number {
        if (typeof key === "number"){
            return key;
        }
        const tableKey = this.toStrFn(key);
        let hash = 0;
        for (let i = 0; i < tableKey.length; i++){
            // 获取每个字符的ASCII码将其拼接至hash中
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }

    // djb2实现哈希函数
    djb2HashCode(key: K): number {
        if (typeof key === "number"){
            return key;
        }

        // 将参数转为字符串
        const tableKey = this.toStrFn(key);
        let hash = 5381;
        for (let i = 0; i < tableKey.length; i++){
            hash = (hash * 33) + tableKey.charCodeAt(i);
        }
        return hash % 1013;
    }
  • Реализовать метод put
    put(key: K, value: V): boolean {
        if (key != null && value != null){
            const position = this.hashCode(key);
            this.table[position] = new ValuePair(key, value);
            return true;
        }
        return false;
    }
  • Реализовать метод получения
    get(key: K): V|undefined {
        const valuePair = this.table[this.hashCode(key)];
        return valuePair == null ? undefined : valuePair.value;
    }
  • Реализовать метод hasKey
    hasKey(key: K): boolean {
        return this.table[this.hashCode(key)] != null;
    }
  • Реализовать метод удаления
    remove(key: K): boolean {
        if(this.hasKey(key)){
            delete this.table[this.hashCode(key)];
            return true;
        }
        return false;
    }
  • Реализовать методы keyValues, keys, values
    keyValues(): ValuePair<K, V>[] {
        const valuePairs = [];
        // 获取对象中的所有key并将其转为int类型数组
        const keys = Object.keys(this.table).map(item => parseInt(item));
        for (let i = 0; i < keys.length; i++){
            valuePairs.push(this.table[keys[i]]);
        }
        return valuePairs;
    }

    keys(): K[] {
        const keys = [];
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++){
            keys.push(valuePairs[i].key);
        }
        return keys;
    }
    
    values(): V[] {
        const values = [];
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++){
            values.push(valuePairs[i].value);
        }
        return values;
    }
  • Реализовать методы isEmpty, size, clear
    isEmpty(): boolean {
        return this.values().length === 0;
    }
    
    size(): number {
        return this.keyValues().length;
    }
    
    clear(): void {
        this.table= {};
    }
  • Реализовать метод forEach.
    forEach(callbackFn: (key: K, value: V) => any): void {
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++){
            const result = callbackFn(valuePairs[i].key,valuePairs[i].value);
            if (result === false) {
                break;
            }
        }
    }
  • Реализовать метод toString
    toString(): string {
        if (this.isEmpty()){
            return ``
        }

        const valuePairs = this.keyValues();
        let objString = `${valuePairs[0].toString()}`;
        for (let i = 1; i < valuePairs.length; i++){
            objString = `${objString},${valuePairs[i].toString()}`;
        }
        return objString;
    }

Пожалуйста, перейдите к полному коду:HashMap.ts

написать тестовый код

Давайте проверим, нормально ли выполняется приведенный выше код.

const hashMap = new HashMap();
hashMap.put("name", "张三");
hashMap.put("id", 1);
hashMap.put("class", "产品");
console.log("判断class是否存在与HashMap中", hashMap.hasKey("class"));
hashMap.remove("id");
console.log("判断id是否存在于HashMap中", hashMap.hasKey("id"))
console.log(hashMap.get("name"));
hashMap.forEach(((key, value) => {
    console.log(key +"="+ value);
}))
console.log("判断HashMap中的数据是否为空",hashMap.isEmpty());
console.log("输出HashMap中所有key对应的value",hashMap.keyValues());
console.log("获取HashMap中的所有key值",hashMap.keys());
console.log("获取HashMap中的所有Value值",hashMap.values());
console.log("获取HashMap的大小",hashMap.size());
console.log("HashMap中的数据转字符串输出",hashMap.toString());
console.log("清空HashMap中的数据");
hashMap.clear();
// 测试hash值冲突问题
hashMap.put('Ygritte', 'ygritte@email.com');
hashMap.put('Jonathan', 'jonathan@email.com');
hashMap.put('Jamie', 'jamie@email.com');
hashMap.put('Jack', 'jack@email.com');
hashMap.put('Jasmine', 'jasmine@email.com');
hashMap.put('Jake', 'jake@email.com');
hashMap.put('Nathan', 'nathan@email.com');
hashMap.put('Athelstan', 'athelstan@email.com');
hashMap.put('Sue', 'sue@email.com');
hashMap.put('Aethelwulf', 'aethelwulf@email.com');
hashMap.put('Sargeras', 'sargeras@email.com');
console.log(hashMap.toString());

Пожалуйста, перейдите к полному коду:HashMapTest.js

Разделение метода связанного списка для решения проблемы коллизии хэшей

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

Давайте посмотрим, как объединить связанные списки для решения проблемы конфликта.

  • Создайте новый файл HashMapSeparateChaining.ts и добавьте класс HashMapSeparateChaining, наследуемый от HashMap.
export default class HashMapSeparateChaining<K,V> extends HashMap<K, V> {

}
  • Объявите личную собственность Tablink и определите его тип для хранения таблицы.
    private tableLink:{ [key: number]: LinkedList<ValuePair<K, V>> };
  • Объявите метод toStrFn в конструкторе, чтобы задать значения по умолчанию, инициализируйте родительский класс и tableLink.
    constructor(protected toStrFn: (key: K) => string = defaultToString) {
        super(toStrFn);
        this.tableLink = {};
    }
  • Переопределить метод put
    put(key: K, value: V): boolean {
        if (key != null && value != null) {
            const position = this.hashCode(key);
            if (this.tableLink[position] == null){
                // 如果当前要添加元素的位置为空则创建一个链表
                this.tableLink[position] = new LinkedList<ValuePair<K, V>>();
            }
            // 往当前要添加元素的链表中添加当前当前元素
            this.tableLink[position].push(new ValuePair(key,value));
            return true;
        }
        return false;
    }
  • Переопределить метод получения
    get(key: K): V | undefined {
        // 获取参数的hash值
        const position = this.hashCode(key);
        // 获取目标元素位置存储的链表结构元素
        const linkedList = this.tableLink[position];
        if (linkedList !=null && !linkedList.isEmpty()){
            // 获取链表头部数据
            let current = linkedList.getHead();
            while (current != null){
                // 遍历链表，找到链表中与目标参数相同的数据
                if (current.element.key === key){
                    // 返回目标key对应的value值
                    return current.element.value;
                }
                current = current.next;
            }
        }
        return undefined;
    }
  • Переопределить метод удаления
    remove(key: K): boolean {
        const position = this.hashCode(key);
        // 获取目标元素位置存储的链表结构元素
        const linkedList = this.tableLink[position];
        if (linkedList != null && !linkedList.isEmpty()){
            // 获取链表头部元素
            let current = linkedList.getHead();
            while (current != null){
                // 遍历链表，找到与目标元素相同的数据
                if (current.element.key === key){
                    // 将当前链表中的元素从链表中移除
                    linkedList.remove(current.element);
                    if (linkedList.isEmpty()){
                        // 链表为空，删除目标位置元素
                        delete this.tableLink[position];
                    }
                    return true;
                }
                current = current.next;
            }
        }
        return false;
    }
  • Переопределить метод очистки
    clear() {
        this.tableLink = {};
    }
  • Переопределить метод keyValues
    keyValues(): ValuePair<K, V>[] {
        const valuePairs = [];
        // 获取tableLink中的所有key并转为int类型
        const keys = Object.keys(this.tableLink).map(item=>parseInt(item));
        for (let i = 0; i < keys.length; i++){
            const linkedList = this.tableLink[keys[i]];
            if (linkedList != null && !linkedList.isEmpty()){
                // 遍历链表中的数据，将链表中的数据放进valuePairs中
                let current = linkedList.getHead();
                while (current != null){
                    valuePairs.push(current.element);
                    current = current.next;
                }
            }
        }
        return valuePairs;
    }

Пожалуйста, перейдите к полному коду:HashMapSeparateChaining.ts

написать тестовый код

Давайте проверим, могут ли вышеуказанные методы нормально выполняться.

const hashMapSC = new HashMapSeparateChaining();
hashMapSC.put("name","张三");
hashMapSC.put("id",11);
hashMapSC.put("age",22);
hashMapSC.put("phone","09871588");
hashMapSC.remove("id");
console.log(hashMapSC.get("name"));
console.log("判断hashMap中的数据是否为空", hashMapSC.isEmpty());
console.log(hashMapSC.toString());
console.log("使用forEach遍历hashMap中的数据");
hashMapSC.forEach((key,value)=>{
    console.log(`${key} = ${value}`);
})
console.log("获取hashMap中存储的所有key",hashMapSC.keys());
console.log("获取hashMap中存储的所有value",hashMapSC.values());
console.log("判断id是否在hashMap中",hashMapSC.hasKey("id"));
console.log("清空HashMap中的数据");
hashMapSC.clear();
console.log("判断HashMap中的数据是否为空", hashMapSC.isEmpty());
console.log("冲突测试")
hashMapSC.put('Ygritte', 'ygritte@email.com');
hashMapSC.put('Jonathan', 'jonathan@email.com');
hashMapSC.put('Jamie', 'jamie@email.com');
hashMapSC.put('Jack', 'jack@email.com');
hashMapSC.put('Jasmine', 'jasmine@email.com');
hashMapSC.put('Jake', 'jake@email.com');
hashMapSC.put('Nathan', 'nathan@email.com');
hashMapSC.put('Athelstan', 'athelstan@email.com');
hashMapSC.put('Sue', 'sue@email.com');
hashMapSC.put('Aethelwulf', 'aethelwulf@email.com');
hashMapSC.put('Sargeras', 'sargeras@email.com');
console.log(hashMapSC.toString());

Пожалуйста, перейдите к полному коду:HashMapSeparateChainingTest.js

Линейное зондирование для решения проблем с коллизией хэшей

  • Создайте новый файл HashMapLinearProbing.ts и добавьте класс HashMapLinearProbing, наследуемый от HashMap.
export default class HashMapLinearProbing<K,V> extends HashMap<K, V>{

}
  • Конструктор инициализирует родительский класс
    constructor() {
        super();
    }
  • Переопределить метод put
    put(key: K, value: V): boolean {
        if (key != null && value!= null){
            const position = this.hashCode(key);
            // 判断当前要插入的位置在表中是否被占据
            if (this.table[position] == null){
                // 当前位置没有被占据，将Key & value放进ValuePair中赋值给当前表中要插入位置的元素
                this.table[position] = new ValuePair(key,value);
            } else{
                // 位置被占据，递增index直至找到没有被占据的位置
                let index = position + 1;
                while (this.table[index] != null){
                    index++;
                }
                // 找到没有被占据的位置，将Key & value放进ValuePair中赋值给当前表中要插入位置的元素
                this.table[index] = new ValuePair(key,value);
            }
            return true;
        }
        return false;
    }
  • Переопределить метод получения
    get(key: K): V | undefined {
        const position = this.hashCode(key);
        if(this.table[position] != null) {
            // 如果当前位置元素的key等于目标元素的key直接返回当前位置元素的value
            if (this.table[position].key === key){
                return this.table[position].value;
            }
            // 位置递增直至找到我们要找的元素或者找到一个空位置
            let index = position + 1;
            while (this.table[index] != null && this.table[index].key !== key){
                index++;
            }
            // 递增结束后，判断当前表中index的key是否等于目标key
            if (this.table[index] != null && this.table[index].key === key){
                return this.table[index].value;
            }
        }
        return undefined;
    }
  • Переопределить метод удаления
    remove(key: K): boolean {
        const position = this.hashCode(key);
        if (this.table[position] != null){
            if (this.table[position].key === key){
                delete this.table[position];
                // 删除后，验证本次删除是否有副作用，调整元素位置
                this.verifyRemoveSideEffect(key,position);
                return true;
            }
            let index = position + 1;
            while (this.table[index] != null && this.table[index].key !== key){
                index++;
            }
            if (this.table[index] != null && this.table[index].key === key){
                delete this.table[index];
                this.verifyRemoveSideEffect(key,index);
                return true;
            }
        }
        return false;
    }
  • Реализуйте метод verifyRemoveSideEffect.
    // 验证删除操作是否有副作用
    private verifyRemoveSideEffect(key: K,removedPosition: number){
        // 计算被删除key的哈希值
        const hash = this.hashCode(key);
        // 从被删除元素位置的下一个开始遍历表直至找到一个空位置
        // 当找到一个空位置后即表示元素在合适的位置上不需要移动
        let index = removedPosition + 1;
        while (this.table[index] != null){
            // 计算当前遍历到的元素key的hash值
            const posHash = this.hashCode(this.table[index].key);
            console.log(`当前遍历到的元素的hash= ${posHash} , 上一个被移除key的hash = ${removedPosition}`)
            if (posHash <= hash || posHash <= removedPosition){
                // 如果当前遍历到的元素的哈希值小于等于被删除元素的哈希值或者小于等于上一个被移除key的哈希值(removedPosition)
                // 需要将当前元素移动至removedPosition位置
                this.table[removedPosition] = this.table[index];
                // 移动完成后，删除当前index位置的元素
                delete this.table[index];
                // 更新removedPosition的值为index
                removedPosition = index;
            }
            index++;
        }
    }

Пожалуйста, перейдите к полному коду:HashMapLinearProbing.ts

написать тестовый код

Проверьте, выполняются ли вышеуказанные методы нормально

const hashMapLP = new HashMapLinearProbing();
console.log("冲突元素删除测试");
hashMapLP.put('Ygritte', 'ygritte@email.com');
hashMapLP.put('Jonathan', 'jonathan@email.com');
hashMapLP.put('Jamie', 'jamie@email.com');
hashMapLP.put('Jack', 'jack@email.com');
hashMapLP.put('Jasmine', 'jasmine@email.com');
hashMapLP.put('Jake', 'jake@email.com');
hashMapLP.put('Nathan', 'nathan@email.com');
hashMapLP.put('Athelstan', 'athelstan@email.com');
hashMapLP.put('Sue', 'sue@email.com');
hashMapLP.put('Aethelwulf', 'aethelwulf@email.com');
hashMapLP.put('Sargeras', 'sargeras@email.com');
// hashMapLP.remove("Ygritte");
hashMapLP.remove("Jonathan");
console.log(hashMapLP.toString());

Пожалуйста, перейдите к полному коду:HashMapLinearProbing.ts

лучшая хэш-функция

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

Мы реализовали метод djb2HashCode в приведенном выше коде. Вероятность того, что этот метод будет генерировать повторяющиеся хэш-значения, очень мала, поэтому мы должны использовать этот метод для их генерации. Далее мы изменим метод, используемый hashCode, на djb2HashCode для проверки результат выполнения HashMap.

    hashCode(key: K): number {
        return this.djb2HashCode(key);
    }
❝

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

напиши в конце

  • Если в статье есть ошибки, исправьте их в комментариях, если статья вам поможет, ставьте лайк и подписывайтесь 😊
  • Эта статья была впервые опубликована на Наггетс, перепечатка без разрешения запрещена 💌
Категории