Поскольку я глубоко погрузился в самостоятельное путешествие по структурам данных и алгоритмам, мои исследования привели меня к структуре данных хеш-таблицы. В Ruby известен как хэш, в JS как объект, в Python как dict (ionary), в Java как HashMap и т. Д. Этот класс уже готов для большинства объектно-ориентированных языков, но многое остается за кадром.

Почему так важны хеш-таблицы?

Зачем нам хранить вещи внутри hash / obj / dict / hashmap, а не в обычном массиве? В чем разница между хранением чего-либо в массиве в JS и использованием .find () для его поиска?

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

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

Где массивы действительно превосходны, так это в поиске чего-либо по заданному индексу. Массивы индексируются, поэтому, если вы точно знаете индекс, по которому пытаетесь выполнить поиск, время поиска составит O (1). Если мы хотим искать массив arr по индексу 3, это довольно дешево. arr [3] - отличный способ.

Хеши - это массивы массивов

Хеши используют индексированный характер массивов. По своей сути они представляют собой массивы. Ну, массивы массивов. И как я это написал, массив массивов массивов.

Когда мы создаем объект, скажем

obj = {"apple" : "pie"}

а затем мы ищем obj [«яблоко»], объект на самом деле не ищет текст «яблоко». Хеш-таблица * хеширует * предоставленные ключи и преобразует их в число, которое затем используется в качестве индекса. В действительности наш вышеупомянутый объект мог бы выглядеть так:

[undefined, undefined, undefined, [["apple", "pie"]], undefined]

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

Я написал простой метод хеширования и метод настройки (на JavaScript), чтобы вы могли понять, что происходит.

class Hash {
    constructor(size=53){
        this.keyMap = new Array(size);
    }
_hash(val){
        let total = 0;
        let weirdPrime = 31;
        // I've read that if you multiply your value by a random
        // prime, the likely hood of getting a unique number is
        // increased
        for(let i = 0; i < Math.min(val.length, 100); i++){
            let char = val[i];
            let value = char.charCodeAt(0);
            total = (total * weirdPrime +  value) % 
            this.keyMap.length;
        }
        return total;
    }
set(key, val){
        let idx = this._hash(key);
        let newArr = [key, val]
        if(!this.keyMap[idx]){
            this.keyMap[idx] = [];
        }
this.keyMap[idx].push(newArr);
        return this.keyMap
    }
}

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

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

Нет сговора!

Причина, по которой мы генерируем массив и передаем наше значение, - это борьба с «сговором».

Сговор возникает, когда есть два ключа, которые после хеширования создают один и тот же индекс. Поскольку я использую метод «отдельной цепочки», если два ключа имеют одинаковый индекс, они должны совместно использовать их! Создавая массив и вставляя в него значение, он позволяет разместить несколько элементов в индексном месте.

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

Если отвлечься, предположим, что мы добавили еще один объект в наш массив, и он выглядел так:

obj = {"apple":"pie", "peach":"cobbler"}

И наш метод хеширования хеширует как «яблоко», так и «персик» и дает одно и то же число 3. Наш хеш без маски будет выглядеть так:

[undefined, undefined, undefined, [["apple", "pie"], ["peach","cobbler"]], undefined]

Searching

Если бы мы выполняли поиск объекта так - obj [«персик»], хеш-класс разбил бы «персик» на число, которое он использовал бы в качестве индекса. Затем он ищет контент по этому индексу. Если существует массив, он выполняет итерацию по этому массиву, проверяя первый элемент каждого подмассива, чтобы увидеть, соответствует ли он введенному ключу, в данном случае «персиковый». Если есть совпадение, он вернет второй элемент в этом массиве.

Ниже приведен способ сделать это:

get(key){
       let idx = this._hash(key);
       let keyMapIdx = this.keyMap[idx]
       if(!keyMapIdx){
           return undefined;
        } else if(keyMapIdx){
            for(let i = 0; i < keyMapIdx.length; i++){
                if(keyMapIdx[i][0] === key){
                    return keyMapIdx[i][1]
                }
            }
        }
        return undefined
    }

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