В хэш-таблицах для хранения данных используются пары ключ-значение. Из-за их скорости и полезности почти каждый язык программирования поставляется с той или иной реализацией хеш-таблицы. Хеш-таблицы в Javascript называются объектами, в Python - словарями, а в Java, Go и Scala - картами. Хеш-таблицы появились потому, что люди думают не только числами.

Массивы - это прекрасно, но моделировать все данные на основе индексов - это кошмар. Итак, хеш-таблицы существуют, потому что возможность моделировать ваши данные таким образом passwords["gmail"] намного лучше, чем моделировать их таким образом passwords[0].

Но задумывались ли вы, как эта структура данных реализована под капотом? Компьютеры не понимают интуитивно понятные для человека строки как ключи, так как же они могут хранить значения, связанные с ключами?

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

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

  1. Это быстро (постоянное время Big O)
  2. Он не группирует результаты по конкретным индексам, а распределяет их равномерно.
  3. Он детерминирован: одни и те же входные данные дают одинаковые результаты.

Кроме того, оказывается, что простые числа очень важны для хэш-функций. Создав массив, имеющий длину простого числа, и включив простые числа в вычисления хеширования, вы можете значительно улучшить равномерное распределение данных и избежать множества коллизий. Я не могу полностью объяснить, почему это так, но этот парень пытается: https://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Столкновения

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

При раздельной цепочке используется другой массив или связанный список для хранения нескольких значений в одном индексе. Взгляните на изображение ниже. Оба ключа darkblue и salmon привели к созданию одного и того же индекса. Вместо того, чтобы перезаписывать значение индекса 4, мы сохраняем оба значения в массиве.

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

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

Приведенный ниже код является доказательством концепции и очень упрощен. Используемая функция хеширования работает только со строками. Он перебирает каждый символ, находит его в кодировке UTF 8, а затем вычитает 96, что дает его алфавитный порядок. Затем мы умножаем значение на простое число и добавляем его к нашему промежуточному итогу. После того, как все символы в строке вычислены, мы находим остаток от общего числа, деленный на длину нашего массива хранения. Таким образом, мы можем сохранить наши выходные данные для каждого индекса, который находится за пределами нашего массива.

class HashTable {
    constructor(size=53){
        this.keyMap = new Array(size)
    }
    _hash(key){
        let total = 0
        let WEIRD_PRIME = 31
        for (let i=0; i < Math.min(key.length, 100); i++){
            let char = key[i]
            let value = char.charCodeAt(0) - 96
            total = (total * WEIRD_PRIME + value) %    this.keyMap.length
        }
        return total;
    }
    set(key, value){
        let hashedKey = this._hash(key)
        if (!this.keyMap[hashedKey]) this.keyMap[hashedKey] = []
        this.keyMap[hashedKey].push([key, value])
        return this;
    }
    get(key){
        let hashedKey = this._hash(key)
        if (this.keyMap[hashedKey]) {
            let found = this.keyMap[hashedKey].map((value) => {
                if (value[0] === key) {
                    return value[1]
                }
            })
            return found[0]
        } else {
            return undefined
        }
    }
    keys(){
        let keys = []
        for (let i=0; i < this.keyMap.length; i++){
            if (this.keyMap[i]){
                for (let j=0; j < this.keyMap[i].length; j++){
                    if (!keys.includes(this.keyMap[i][j][0])){
                        keys.push(this.keyMap[i][j][0])    
                    }
                }
            }
        }
        return keys
    }
    values(){
        let values = []
        for (let i=0; i < this.keyMap.length; i++){
            if (this.keyMap[i]){
                for (let j=0; j < this.keyMap[i].length; j++){
                    if (!values.includes(this.keyMap[i][j][1])) {
                        values.push(this.keyMap[i][j][1])    
                    }
                }
            }
        }
        return values
    }
}