Поскольку я глубоко погрузился в самостоятельное путешествие по структурам данных и алгоритмам, мои исследования привели меня к структуре данных хеш-таблицы. В 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 }
И у нас есть наш метод поиска для нашего хэша. Отличный и эффективный способ хранения всех наших данных, к которым нам нужен быстрый доступ.