Всем привет, это десятая часть серии блогов о структурах данных и алгоритмах в JavaScript. В этом блоге я расскажу о структуре данных словаря.

Что такое словарь?

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

Список доступных операций

  • set: вставить в словарь новую пару "ключ-значение".
  • получить: вернуть значение, если ключ присутствует.
  • удалить: удалить пару ключ-значение из словаря, если она присутствует.
  • hasKey: проверьте, существует ли ключ, если нет.
  • keys: возвращает все ключи в словаре.
  • значения: возвращает все значения в словаре.
  • keyValues : возвращает массив, содержащий все пары.
  • forEach: принимает функцию обратного вызова для выполнения операции над каждой парой.

Словарь также известен как карта, таблица символов и ассоциативный массив.

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

Начнем с определения класса Dictionary со свойством table.
Таблица свойств будет объектом javascript, который будет содержать элементы в нем. .
В словаре идеально было бы хранить ключи строкового типа и значения любого типа (от примитивных типов, таких как числа, строки, до сложных объектов). Однако, поскольку JavaScript не является строго типизированным, мы не можем гарантировать, что ключ будет строкой, т.е.

Сначала мы преобразуем ключ любого объекта, передаваемого в качестве ключа, в строку, чтобы упростить поиск и извлечение значений из класса Dictionary.

Значения будут храниться как table[stringify(Key)] = new KeyValues(key,value);

class Dictionary {
    constructor(toStrFn = toStringFunc) {
        this.table = {};
        this.toStrFn = toStrFn;
        }
    }

Функция преобразования строк по умолчанию

function toStringFunc(key) {
    if (key == null) {
        return 'NULL'
    }
    if (key == undefined) {
        return 'UNDEFINED'
    }
    if ((typeof key == "string") || key instanceof String) {
        return `${key}`;
    }
    return key.toString();
}

Набор

При вставке пары ключ-значение мы проверим, не является ли ключ и значение нулевым.

Еще :

  • Строковать ключ, используя строковый метод по умолчанию.
  • Создайте новый экземпляр KeyPair.
  • Добавьте строковое значение в качестве ключа и значение в качестве экземпляра Keypair.

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

set(key, value) {
        if (key != null & value != null) {
            const stringKey = this.toStrFn(key);
            this.table[stringKey] = new KeyValue(key, value);
            return true;
        }
        return false;
    }

Класс ключевого значения

class KeyValue{
     constructor(key, value){
         this.key = key;
         this.value = value;
     }
     toString(){
         return `[#${this.key} , ${this.value}]`
     }
 }

ХасКей

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

hasKey(key) {
        return this.table[this.toStrFn(key)] !== null;
    }

Удалять

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

remove(key) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }

получить

Если существует пара ключ-значение с ключом, то возвращается значение или null.
Поскольку мы знаем, что сначала мы преобразуем ключ в строку и устанавливаем его как ключ объекта, а значение — как экземпляр KeyValue. т.е.

  • Строковать ключ.
  • Возвращает значение KeyValue ключа stringify.
get(key) {
        const keyValuesPair = this.table[this.toStrFn(key)];
        return keyValuesPair != null ? keyValuesPair.value : null;
    }

Ключевые значения

Этот метод вернет всю сохраненную пару ключ-значение в классе словаря,

  • Инициализировать массив keyValuePairs
  • Итерировать свойство table, если ключ существует, затем отправить в массив keyValuePairs
  • Верните keyValuePairs.
keyValues() {
        const keyValuePairs = [];
        for (const key in this.table) {
            if (this.table.hasOwnProperty(key)) {
                keyValuePairs.push(this.table[key])
            }
        }
        return keyValuePairs;
    }

Ключи

Этот метод возвращает все ключи пар ключ-значение. Мы будем вызывать KeyValues, извлекать ключи, используя Array.prototype.map. Альтернативное использование также может сделать то же самое, используя цикл for.

keys() {
        return this.keyValues().map(element => element.key);
    }

Ценности

Этот метод возвращает все значения пар ключ-значение. Мы будем вызывать KeyValues, извлекать значения, используя Array.prototype.map.

values() {
        return this.keyValues().map(element => element.value);
    }

Для каждого

ForEach — это функция итератора, которая позволяет нам зацикливать все пары ключ-значение, присутствующие в классе Dictionary. Но то же самое можно применить и к другим структурам данных.

  • Мы вызываем KeyValues ​​и получаем все пары ключ-значение.
  • Мы будем перебирать отдельные пары и выполнять обратный вызов до тех пор, пока условие не станет истинным.
forEach(callback) {
        let keyValuePairs = this.keyValues();
        for (let index = 0; index < keyValuePairs.length; index++) {
            const result = callback(keyValuePairs[index].key, keyValuePairs[index].value);
            if (result == false) {
                break;
            }
        }
    }

вы получаете полный источник здесь

Карта ES6, аналогична словарю.

Вывод :

Итак, следите за обновлениями в следующем блоге, в котором я расскажу о другой хеш-таблице DS.