В программировании нам часто приходится брать набор данных и проходить его, чтобы найти заданное значение или выполнить действие. Нам, новичкам, первое, что обычно приходит на ум, — это использование цикла; мы просматриваем каждый элемент наших данных, пока не получим решение, соответствующее нашим условиям. Это отлично работает для большинства мелкомасштабных поисков и базовых вычислений, но когда набор данных становится слишком большим или нам нужно вернуться к значениям, которые мы уже передали в нашем цикле, мы можем увидеть некоторые недостатки традиционного цикла.
Если вы изучали программирование, вы, скорее всего, когда-то видели или слышали о хеш-картах, они повсюду. Когда я впервые начал изучать, я был сбит с толку тем, что такое хэш-карта, как будто это был какой-то мистический тип данных, который я еще не открыл, или что-то, что существует только в определенных языках. Я был смущен этим и, казалось, не нуждался в этом, поэтому я просто продолжал работать. Я написал еще один пост здесь о построении структуры данных двоичного дерева и о том, как мы можем использовать ее для управления большими наборами данных; оказывается, бинарное дерево — это реализация хеш-карты!
Так что же такое хэш-карта? Короче говоря, это структура данных, которая использует пары ключ-значение для отслеживания значений, которые были переданы в нашей итерации. Вот простой пример, чтобы показать концепцию.
const arrayToMap = [3,6,4,12,1,23,8,10,26]
//I am manually entering the elements here for the hash map
//the key will be the valueand the value is the index
const hashMap = {3:0, 6:1, 4:2, 12:3, 1:4, 23:5, 8:6, 10:7, 26:8}
Выше у нас есть неупорядоченный массив и хеш-карта значений массива. Мы можем видеть значение, за которым следует соответствующий индекс из исходного массива. Теперь мы можем упорядочить хеш-карту по значениям и при этом сохранить позицию в исходном массиве. Это избавляет нас от необходимости управлять тем, как добавлять новые значения в нужное место. Мы просто помещаем их в массив и можем управлять положением в хэше. Ниже приведен тот же хеш, но упорядоченный по значению, а не по индексу.
const hashMap = {1:4, 3:0, 4:2, 6:1, 8:6, 12:3, 10:7, 23:5, 26:8}
Это может быть действительно мощно! Теперь у нас есть исходные данные в массиве, полностью нетронутые, и вся информация, необходимая нам для выполнения наших действий, И, поскольку мы сохранили исходные индексы в качестве ключей в нашем хэше, мы МОЖЕМ очень легко манипулировать исходным массивом. Нам просто нужно найти значение в нашем хеше и использовать его ключ для доступа к этому значению в исходном массиве.
arrayToMap[0] //this returns 3 since our value at index 0 is 3 arrayToMap[0] = 20 //changes the value from 3 to 20
Довольно просто, верно!?
Теперь мы можем использовать эту структуру, чтобы попытаться решить проблему. Давайте рассмотрим проблему TwoSums. В этой задаче нам предлагается взять массив чисел и найти ДВА значения, которые в сумме дают заданное целевое число. Когда я посмотрел на эту проблему, я сразу же начал использовать циклы и настроил решение методом грубой силы.
const twoSum = (array, target) => {
let indexes = []
for(let i = 0; i < array.length; i++){
for(let j = i + 1; j < array.length; j++){
if (array[i] + array[j] === target) {
indexes.push(i);
indexes.push(j);
}
}
}
return indexes;
}Это берет первое значение массива и добавляет его ко всем остальным значениям в массиве, а затем проверяет, равно ли оно целевому числу. Это прекрасное решение, и оно хорошо работает, если набор данных не слишком велик, но есть способ получше. Ниже мы реализуем хеш-карту для отслеживания уже переданных значений, и я объясню, почему это важно, после того, как мы рассмотрим функцию.
const twoSum = (array, target) => {
const hashMap = {}
for (let i = 0; i < array.length; i++) {
hashMap[array[i]] = i;
}
for (let i = 0; i < array.length; i++) {
let diff = target - array[i]
if (hashMap[diff] !== undefined && hashMap[diff] !== i) {
return [hashMap[diff], i]
}
}
}
В этой функции мы сначала создаем нашу хеш-карту, перебирая массив и назначая пары ключ-значение переменной hashMap. Поскольку у нас есть ВСЕ наши значения внутри этой хеш-карты, мы можем легко просто проверить число, которое нам нужно. Мы определяем необходимое число, вычитая текущее значение из целевого числа, затем проверяем, есть ли это значение в нашей хеш-карте. Мы можем искать значение в хеш-карте, используя тот же синтаксис, что и для доступа к индексу массива, и нам не нужно перебирать каждый элемент, чтобы найти его.
hashMap[x] //x = the number you are searching for
Мы можем сделать это, так как мы установили все ключи в фактические значения, а значение в индекс!
Внедряя метод хеширования, мы значительно сокращаем наши накладные расходы. Теперь вместо того, чтобы сравнивать каждый элемент массива с одним числом за раз и проверять, соответствует ли оно нашему условию, вместо этого мы просто выясняем, какое число необходимо для выполнения условия, и проверяем, есть ли это число в нашем наборе данных с помощью хэш-карты. . Это означает гораздо меньше итераций, но все же очень читаемый код. Понимание различных структур данных может дать нам больше возможностей для эффективного управления нашими данными, и многие структуры основаны на этой концепции хэш-карты, теперь нам просто нужно попрактиковаться в ее использовании.
