Хэш — Основы алгоритмов и структур данных

Ранее в курсе мы изучили метод перебора и сталкивались с задачей про европейские столицы. Снова попробуем решить эту задачу, но выберем новый, более продуктивный способ.

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

Пары с годом и городом в таблице расположены в произвольном порядке, поэтому поиск нужной столицы требует полного перебора.

Временная сложность такого алгоритма составляет , что довольно медленно. Бинарный поиск позволяет сократить это время до . На большой таблице из миллиона записей среднее количество сравнений для линейного поиска равно 500000, а для бинарного — всего 10.

Но и это не предел. Если поиск нужно выполнять с максимальной скоростью, мы можем воспользоваться еще одной структурой данных. Это хэш-таблица, которая обеспечивает временную сложность .

Хэш-таблица похожа на массив, потому что в ней тоже есть операция индексации. В JavaScript доступ к элементу массива осуществляется по индексу, записанному в квадратных скобках. В качестве индекса можно использовать последовательные целые числа. В случае с хэш-таблицей в качестве индекса можно брать любые структуры данных — строки, дату и время, массивы.

В этом уроке мы разберемся, как устроены хэш-таблицы и как их реализовывать.

В этом уроке мы изучили хэш-таблицы и научились с ними работать. Повторим основные тезисы:

• Хэш-таблица обеспечивает временную сложность . Она похожа на массив, потому что в ней тоже есть операция индексации. В качестве индекса можно использовать практически любые структуры данных — строки, дату и время, массивы.
• Массивы, в которых большая часть элементов не определена, называются разреженными. Чтобы сэкономить память, программисты стараются уплотнить массив, но тогда довольно трудно предсказать размер массива.
• Остатки от деления любого числа на всегда находятся в диапазоне от до . Иногда вместо «остаток от деления на » говорят «модуль по основанию . В JavaScript и многих других языках программирования для вычисления модуля используют оператор %

Предположим, мы фиксируем размер массива. Пусть у нас будет массив из ста элементов:

let capitals = new Array(100);

capitals = [None for _ in range(100)]

String[] capitals = new String[100];

<?php
 
$capitals = array_fill(0, 100, null);

Мы хотим сохранить в него несколько элементов, но их индексы могут быть произвольными целыми числами. Чтобы преобразовать индекс в число от 0 до 99, мы должны вычислить остаток от деления индекса на 100.

Общее правило такое:

Остатки от деления любого числа на всегда находятся в диапазоне от до

Это правило поможет нам работать с массивами любого размера.

Иногда вместо «остаток от деления на » говорят «модуль по основанию ». В JavaScript и многих других языках программирования для вычисления модуля используют оператор %:

console.log(1999 % 20); // => 19

print(1999 % 20)  # => 19

System.out.println(1999 % 20); // => 19

<?php
 
print_r(1999 % 20); // => 19

Решим нашу задачу со столицами с помощью модуля:

let capitals = new Array(100);
 
capitals[881 % 100] = 'Вена';
capitals[1237 % 100] = 'Берлин';
capitals[1323 % 100] = 'Вильнюс';
capitals[1614 % 100] = 'Тирана';
capitals[1167 % 100] = 'Копенгаген';
capitals[963 % 100] = 'Люксембург';
capitals[1067 % 100] = 'Минск';
capitals[1191 % 100] = 'Дублин';
capitals[1275 % 100] = 'Амстердам';
capitals[752 % 100] = 'Ватикан';
capitals[1786 % 100] = 'Рейкьявик';
capitals[1200 % 100] = 'Варшава';
capitals[1872 % 100] = 'Будапешт';
capitals[856 % 100] = 'Мадрид';
capitals[1147 % 100] = 'Москва';
 
const getCity = (year) => capitals[year % 100];
 
let city = getCity(1167); // Копенгаген

capitals = [None for _ in range(100)]
 
capitals[1804 % 100] = 'Вена'
capitals[1237 % 100] = 'Берлин'
capitals[1323 % 100] = 'Вильнюс'
capitals[1614 % 100] = 'Тирана'
capitals[1167 % 100] = 'Копенгаген'
capitals[963 % 100] = 'Люксембург'
capitals[1067 % 100] = 'Минск'
capitals[1191 % 100] = 'Дублин'
capitals[1275 % 100] = 'Амстердам'
capitals[752 % 100] = 'Ватикан'
capitals[1786 % 100] = 'Рейкьявик'
capitals[1200 % 100] = 'Варшава'
capitals[1872 % 100] = 'Будапешт'
capitals[856 % 100] = 'Мадрид'
capitals[1147 % 100] = 'Москва'
 
def get_city(year):
    return capitals[year % 100]
 
city = get_city(1167)  # Копенгаген

String[] capitals = new String[100];
 
capitals[881 % 100] = "Вена";
capitals[1237 % 100] = "Берлин";
capitals[1323 % 100] = "Вильнюс";
capitals[1614 % 100] = "Тирана";
capitals[1167 % 100] = "Копенгаген";
capitals[963 % 100] = "Люксембург";
capitals[1067 % 100] = "Минск";
capitals[1191 % 100] = "Дублин";
capitals[1275 % 100] = "Амстердам";
capitals[752 % 100] = "Ватикан";
capitals[1786 % 100] = "Рейкьявик";
capitals[1200 % 100] = "Варшава";
capitals[1872 % 100] = "Будапешт";
capitals[856 % 100] = "Мадрид";
capitals[1147 % 100] = "Москва";
 
class App {
    public static String getCity(String[] capitals, int year) {
        return capitals[year % 100];
    }
}

<?php
 
$capitals = array_fill(0, 100, null);
 
$capitals[881 % 100] = 'Вена';
$capitals[1237 % 100] = 'Берлин';
$capitals[1323 % 100] = 'Вильнюс';
$capitals[1614 % 100] = 'Тирана';
$capitals[1167 % 100] = 'Копенгаген';
$capitals[963 % 100] = 'Люксембург';
$capitals[1067 % 100] = 'Минск';
$capitals[1191 % 100] = 'Дублин';
$capitals[1275 % 100] = 'Амстердам';
$capitals[752 % 100] = 'Ватикан';
$capitals[1786 % 100] = 'Рейкьявик';
$capitals[1200 % 100] = 'Варшава';
$capitals[1872 % 100] = 'Будапешт';
$capitals[856 % 100] = 'Мадрид';
$capitals[1147 % 100] = 'Москва';
 
const getCity = (year) => $capitals[year % 100];
 
function getCity($capitals, $year)
{
    return $capitals[$year % 100];
}
 
$city = getCity(1167); // 'Копенгаген'

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

Попробуем узнать, какой город основан в 1167 году. Если верить нашей таблице, это Копенгаген. Но программа говорит совсем другое:

console.log(getCity(1167)); // => Минск

print(get_city(1167))  # => Минск

System.out.println(App.getCity(1167)); // => Минск

<?php
 
print_r(getCity(1167)); // => Минск

Минск основан в 1067 году, а Копенгаген — в 1167. Годы отличаются, но у них один и тот же остаток от деления на 100, а именно 67.

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

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

• Год — это индекс, по которому мы сохраняем и извлекаем данные. Обычно его называют ключом
• Название — это значение

Попробуем реализовать в коде:

import LinkedList from './LinkedList.js';
 
let capitals = new Array(100);
 
const setCapital = (year, city) => {
  let index = year % capitals.length;
  if (typeof(capitals[index]) === 'undefined') {
    capitals[index] = new LinkedList();
  }
 
  capitals[index].add({ key: year, value: city });
};

from LinkedList import LinkedList
 
capitals = [None for _ in range(100)]
 
def set_capital(year, city):
    index = year % len(capitals)
 
    if capitals[index] is None:
        capitals[index] = LinkedList()
 
    capitals[index].add({'key': year, 'value': city})

class App {
    private LinkedList[] capitals = new LinkedList[100];
 
    public void setCapital(int year, String city) {
        var index = year % capitals.length;
        if (capitals[index] == null) {
            capitals[index] = new LinkedList<Object[]>();
        }
 
        capitals[index].add(new Object[] {year, city});
    }
}

<?php
 
use LinkedList;
 
$capitals = array_fill(0, 100, null);
 
function setCapital($year, $city, &$capitals)
{
    $index = $year % count(capitals);
    if (!isset($capitals[$index])) {
        $capitals[$index] = new LinkedList();
    }
 
    $capitals[$index]->add(['key' => $year, 'value' => $city]);
}

Мы уже разработали структуру данных LinkedList, поэтому мы можем просто импортировать ее.

Размер массива capitals всегда будет равен ста элементам.

По умолчанию все ячейки массива пусты, и связный список создается только при первой записи в ячейку. В каждом списке может храниться несколько элементов. Чтобы различать их, мы сохраняем не просто значение, а пару из ключа (key) и значения (value).

При поиске точно также вычисляем индекс:

const getCapital = (year) => {
  let index = year % capitals.length;
  if (typeof(capitals[index]) === 'undefined') {
    return undefined;
  }
 
  for (let pair of capitals[index]) {
    if (pair.key === year) {
      return pair.value;
    }
  }
 
  return undefined;
};

def get_capital(year):
    index = year % len(capitals)
 
    if capitals[index] is None:
        return None
 
    for pair in capitals[index]:
        if pair['key'] == year:
            return pair['value']
 
    return None

lass App {
    private LinkedList[] capitals = new LinkedList[100];
 
    public void setCapital(int year, String city) {
        // ...
    }
 
    public String getCapital(int year) {
        var index = year % capitals.length;
 
        if (capitals[index] == null) {
            return null;
        }
 
        for (var pair : capitals[index]) {
            var casted = (Object[]) pair;
            if ((int) casted[0] == year) {
                return (String) casted[1];
            }
        }
 
        return null;
    }
}

<?php
 
function getCapital($capitals, $year)
{
  $index = $year % count($capitals);
  if (!isset($capitals[$year])) {
      return null;
  }
 
  foreach($capitals[$index] as $pair) {
      if ($pair['key'] === $year) {
          return $pair['value'];
      }
  }
 
  return null;
}

Если в ячейке ничего нет, значит, мы ничего и не записывали.

Но если в ячейке что-то есть, то это список, по которому мы пробегаем и пытаемся найти пару с заданным ключом (key).

Обнаружив пару, возвращаем ее значение (value).

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

Если у нас будет случайный набор из ста чисел, он достаточно равномерно распределится по массиву: в большинстве ячеек будет храниться одно число, в некоторых — два, и в некоторых — ни одного. Алгоритмическая сложность записи и чтения в таком случае будет близка к — это один из самых быстрых возможных алгоритмов.

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

Теперь попробуем решить обратную задачу — определять год основания столицы, зная ее название. Заглянем в таблицу в начале урока и вспомним, что год основания Мадрида — 856, а Москвы — 1147.

Наша структура данных может хранить значения с любым целочисленным ключом, не только с годом. Но «Мадрид» и «Москва» — это не числа, а строки.

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

const capital = 'Мадрид';
for (let i = 0; i < capital.length; i++) {
  console.log(capital.charCodeAt(i));
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

capital = 'Мадрид'
 
for i in range(len(capital)):
    print(ord(capital[i]))
# => 1052
# => 1072
# => 1076
# => 1088
# => 1080
# => 1076

var capital = "Мадрид";
for (var i = 0; i < capital.length; i++) {
    System.out.println((int) capital.charAt(i));
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

<?php
 
$capital = 'Мадрид';
for ($i = 0; $i < count($capital); i += 1) {
  print_r(mb_ord($capital[$i]));
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

Слово «Мадрид» хранится как последовательность чисел 1052, 1072, 1076, 1088, 1080 и 1076. В простейшем случае мы могли бы использовать для вычисления индекса код первой буквы — в нашем примере 1052. Но это значит все города на М (Мадрид, Москва и Минск) попадут в один и тот же список. В таком случае скорость поиска будет не очень высокой.

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

Однако сложение и умножение — слишком простые операции. Все слова, состоящие из одних и тех же букв (ведро, вроде и древо), будут иметь один и тот же ключ — сумму или произведение кодов символов.

Хороший результат в таком случае даст так называемая полиномиальная функция.

Попробуем применить ее к нашей задаче с городами. Пусть коды символов строки длины n будут равны c0, c1…, cn-1. Возьмем число k, которое будет больше кода любого символа — скажем, k=65537.

У нас получилось такое выражение:

Число достаточно большое. На каждом шаге нам приходится возводить его в возрастающую степень, поэтому выражение может оказаться просто огромным. Для слова Мадрид мы получим 13009213352423037265600321836.

На практике для ускорения вычислений и для удобства используют не все выражение, а только остаток от его деления на другое число — m:

Обычно модуль делают равным большому простому числу или большому круглому числу — например, миллиону или миллиарду. Часто в качестве модуля выбирают степень числа 2 — к примеру, 2^.0 или 2⁶⁴.

Чтобы промежуточные числа не становились слишком большими, все сложения и умножения выполняют по модулю m. Другими словами, остаток от деления вычисляется сразу после сложения или умножения:

const hash = (s) => {
  const k = 65537;
  const m = 2**20;
 
  let result = 0;
  let k_i = 1;
  for (let i = 0; i < s.length; i++) {
    result = (result + k_i * s.charCodeAt(i)) % m;
    k_i = (k_i * k) % m;
  }
 
  return result;
};

def hash(s):
    k = 65537
    m = 2**20
 
    result = 0
    k_i = 1
 
    for i in range(len(s)):
        result = (result + k_i * ord(s[i])) % m
        k_i = (k_i * k) % m
 
    return result

class App {
    private int hash(String s) {
        var k = 65537;
        var m = (int) Math.pow(2, 20);
 
        var result = 0;
        var k_i = 1;
 
        for (var i = 0; i < s.length(); i++) {
            result = (result + k_i * s.charAt(i)) % m;
            k_i = (k_i * k) % m;
        }
 
        return result;
    }
}

<?php
 
function hash($s)
{
    $k = 65537;
    $m = 2 ** 20;
 
    $result = 0;
    $k_i = 1;
    for ($i = 0; $i < mb_strlen($s); $i += 1) {
        $result = ($result + $k_i * mb_ord($s[$i])) % $m;
        $k_i = ($k_i * $k) % $m;
    }
 
    return $result;
}

Здесь в качестве модуля мы выбрали 2**20, то есть 2²⁰. Это число равно 1048576 и часто используется программистами, потому что очень близко к миллиону. Слово мегабайт традиционно означает именно 1048576 байт, а не миллион, как можно было бы ожидать.

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

Переменная kⁱ на каждом шаге цикла умножается на k. Она принимает значения 1, k, k2 и так далее. В переменной result накапливается результат вычислений.

Функция называется hash, и это неслучайно. В переводе с английского слово hash означает «мелко крошить, перемешивать».

Функция перемешивает исходные данные так, чтобы получилось число, похожее на случайное:

hash('Мадрид') // 792876
hash('Москва') // 399671
hash('Минск')  // 857356

hash('Мадрид') # 792876
hash('Москва') # 399671
hash('Минск')  # 857356

App.hash("Мадрид") // 792876
App.hash("Москва") // 399671
App.hash("Минск")  // 857356

<?php
 
hash('Мадрид') // 792876
hash('Москва') // 399671
hash('Минск')  // 857356

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

В Python для вычисления хешей можно использовать функцию hash(), в Java — метод hashCode(), в C# — метод GetHashCode(). В JavaScript нет готовой хеш-функции — считается, что все нужное уже есть в языке.

Название функции дало название всей структуре данных. Обычно ее называют хеш-таблицей (hash table или hashmap). Очень часто это название сокращают до просто до хеша. Другие распространенные названия — словарь (dictionary) и ассоциативный массив (associative array).

Выше мы говорили, что обычно вставка и поиск в хеш-таблице выполняются за время . Но если хеш-функция выбрана неудачно, все значения могут оказаться в одном связном списке во внутреннем массиве.

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

Есть еще одна возможная сложность. В массиве, который мы использовали в примерах выше, мы резервировали сто элементов, потому что рассчитывали, что данные будут распределены равномерно. Однако если мы поместим в такой массив 10000 элементов, то даже при идеальном распределении в каждом связном списке окажется сто элементов. Это значит, что поиск и вставка все-таки будут медленными.

Чтобы справиться с этой проблемой, надо расширять хеш-таблицу — увеличивать внутренний массив по мере того, как в нее добавляются элементы. Конечно, это накладно делать при каждой вставке.

Обычно подсчитывают коэффициент заполнения хеш-таблицы (load factor) — это частное от деления количества вставленных элементов на размер внутреннего массива. Если он достигает заранее выбранного порога в 60–80%, внутренний массив увеличивают вдвое, а индексы всех элементов пересчитывают.

Точно также, если коэффициент заполнения становится слишком маленьким, 20–25%, массив уменьшают вдвое. У массива есть нижняя граница в 128 или 256 элементов, чтобы не перестраивать его слишком часто, пока он маленький.

Перепишем функцию вставки, опираясь на все новые знания. Вместе с этим реализуем хеш-таблицу в виде новой структуры данных, спрятав внутри класса массив с данными:

class Hash {
  let table = [];
  let count = 0;
 
  hash(s) {
    const k = 65537;
    const m = 2**20;
 
    let result = 0, power = 1;
    for (let i = 0; i < s.length; i++) {
      result = (result + power * s.charCodeAt(i)) % m;
      power = (power * k) % m;
    }
 
    return result;
  }
 
  calculateIndex(table, key) {
    return this.hash(String(key)) % table.length;
  }
 
  rebuildTableIfNeed() {
    if (this.table.length == 0) {
      this.table.length = 128;
    } else {
      const loadFactor = this.count/this.table.length;
      if (loadFactor >= 0.8) {
        let newTable = new Array(this.table.length * 2);
        for (let list in this.table) {
          for (let pair of list) {
            const newIndex = this.calculateIndex(newTable, pair.key)
            if (typeof(newTable[newIndex]) === 'undefined') {
              newTable[newIndex] = new LinkedList();
            }
 
            newTable[newIndex].add(pair);
          }
        }
 
        this.table = newTable;
      }
    }
  }
 
  set(key, value) {
    this.rebuildTableIfNeed();
 
    const index = this.calculateIndex(this.table, key);
    if (typeof(this.table[index]) === 'undefined') {
      this.table[index] = new LinkedList();
    }
 
    this.table[index].add({ key: key, value: value });
    this.count += 1;
  }
 
  get(key) {
    const index = this.calculateIndex(this.table, key);
    if (typeof(this.table[index]) === 'undefined') {
      return undefined;
    }
 
    for (let pair of this.table[index]) {
      if (pair.key === key) {
        return pair.value;
      }
    }
 
    return undefined;
  }
}

class Hash:
    table = []
    count = 0
 
    def hash(self, s):
        k = 65537
        m = 2**20
 
        result = 0
        power = 1
 
        for i in range(len(s)):
            result = (result + power * ord(s[i])) % m
            power = (power * k) % m
 
        return result
 
    def calculate_index(self, table, key):
        try:
            return self.hash(str(key)) % len(table)
        except ZeroDivisionError:
            return self.hash(str(key))
 
    def rebuild_table_if_need(self):
        if len(self.table) == 0:
            table = [None for _ in range(128)]
        else:
            load_factor = self.count / len(self.table)
 
            if load_factor >= 0.8:
                new_table = [None for _ in range(len(self.table) * 2)]
 
                for list_ in self.table:
                    for pair in list_:
                        new_index = self.calculate_index(new_table, pair['key'])
                        if new_table[new_index] is None:
                            new_table[new_index] = LinkedList()
 
                        new_table[new_index].add(pair)
 
                self.table = new_table
 
    def set(self, key, value):
        self.rebuild_table_if_need()
        index = self.calculate_index(self.table, key)
 
        if self.table[index] is None:
            self.table[index] = LinkedList()
 
        self.table[index].add(
            {'key': key, 'value': value}
        )
        self.count += 1
 
    def get(self, key):
        index = self.calculate_index(self.table, key)
 
        if self.table[index] is None:
            return None
 
        for pair in self.table[index]:
            if pair['key'] == key:
                return pair['value']
 
        return None

class Hash {
 
    private LinkedList[] table = new LinkedList[128];
    int count = 0;
 
    private int hash(String s) {
        var k = 65537;
        var m = (int) Math.pow(2, 20);
 
        var result = 0;
        var k_i = 1;
 
        for (var i = 0; i < s.length(); i++) {
            result = (result + k_i * s.charAt(i)) % m;
            k_i = (k_i * k) % m;
        }
 
        return result;
    }
 
    private int calculateIndex(LinkedList[] table, String key) {
        return hash(key) % table.length;
    }
 
    private void rubuildTableIfNeed() {
        var loadFactor = (double) count / table.length;
        if (loadFactor >= 0.8) {
            LinkedList[] newTable = new LinkedList[table.length * 2];
            for (LinkedList list : table) {
                for (var pair : list) {
                    Object[] casted = (Object[]) pair;
                    var newIndex = calculateIndex(newTable, (String) casted[0]);
                    if (newTable[newIndex] == null) {
                        newTable[newIndex] = new LinkedList();
                    }
 
                    newTable[newIndex].add(pair);
                }
            }
 
            table = newTable;
        }
    }
 
    public void set(String key, Object value) {
        this.rubuildTableIfNeed();
        var index = calculateIndex(table, key);
 
        if (table[index] == null) {
            table[index] = new LinkedList();
        }
 
        table[index].add(new Object[] {key, value});
        count++;
    }
 
    public Object get(String key) {
        var index = calculateIndex(table, key);
        if (table[index] == null) {
            return null;
        }
 
        for (var pair : table[index]) {
            var casted = (Object[]) pair;
            if (casted[0].equals(key)) {
                return casted[1];
            }
        }
 
        return null;
    }
}

<?php
 
class Hash {
  public $table = [];
  public $count = 0;
 
  public function hash($s) {
      $k = 65537;
      $m = 2 ** 20;
 
      $result = 0;
      $power = 1;
      for ($i = 0; $i < mb_strlen($s); $i += 1) {
          $result = ($result + $power * mb_ord($s[$i])) % $m;
          $power = ($power * $k) % $m;
      }
 
      return $result;
  }
 
  public function calculateIndex($table, $key) {
      return $this->hash((string) $key) % count($table);
  }
 
  public function rebuildTableIfNeed() {
      $loadFactor = $this->count/count($this->table);
      if ($loadFactor >= 0.8) {
          $newTable = array_fill(0, count($this->table) * 2, null);
          foreach ($this->table as $list) {
              foreach ($list as $pair) {
                  $newIndex = $this->calculateIndex($newTable, $pair['key'])
                  if (!isset($newTable[$newIndex])) {
                      $newTable[$newIndex] = new LinkedList();
                  }
 
                $newTable[$newIndex]->add($pair);
              }
          }
 
          $this->table = $newTable;
      }
  }
 
  public function set($key, $value) {
      $this->rebuildTableIfNeed();
 
      $index = $this->calculateIndex($this->table, $key);
      if (!isset($this->table[$index])) {
          $this->table[$index] = new LinkedList();
      }
 
      $this->table[$index]->add(['key' => $key, 'value' => $value ]);
      $this->count += 1;
  }
 
  public function get($key) {
      $index = $this->calculateIndex($this->table, $key);
      if (!isset($this->table[$index])) {
          return null;
      }
 
      foreach ($this->table[$index] as $pair) {
          if ($pair['key'] === $key) {
              return $pair['value'];
          }
      }
 
      return null;
  }
}

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

Именно за это отвечает вложенный цикл:

let newTable = new Array(this.table.length * 2);
for (let list in this.table) {
  for (let pair of list) {
    const newIndex = this.calculateIndex(newTable, pair.key)
    if (typeof(newTable[newIndex]) === 'undefined') {
      newTable[newIndex] = new LinkedList();
    }
 
    newTable[newIndex].add(pair);
  }
}

new_table = [None for _ in range(len(self.table) * 2)]
 
for list_ in self.table:
    for pair in list_:
        new_index = self.calculate_index(new_table, pair['key'])
        if new_table[new_index] is None:
            new_table[new_index] = LinkedList()
 
        new_table[new_index].add(pair)

LinkedList[] newTable = new LinkedList[table.length * 2];
 
for (LinkedList list : table) {
    for (var pair : list) {
        Object[] casted = (Object[]) pair;
        var newIndex = calculateIndex(newTable, (String) casted[0]);
        if (newTable[newIndex] == null) {
            newTable[newIndex] = new LinkedList();
        }
 
        newTable[newIndex].add(pair);
    }
}

<?php
 
$newTable = array_fill(0, count($this->table) * 2, null);
foreach ($this->table as $list) {
    foreach ($list as $pair) {
        $newIndex = $this->calculateIndex($newTable, $pair['key'])
        if (!isset($newTable[$newIndex])) {
            $newTable[$newIndex] = new LinkedList();
        }
 
      $newTable[$newIndex]->add($pair);
    }
}

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

В этом уроке мы изучили хэш-таблицы и научились с ними работать. Повторим основные тезисы:

• Хэш-таблица обеспечивает временную сложность . Она похожа на массив, потому что в ней тоже есть операция индексации. В качестве индекса можно использовать практически любые структуры данных — строки, дату и время, массивы.
• Массивы, в которых большая часть элементов не определена, называются разреженными. Чтобы сэкономить память, программисты стараются уплотнить массив, но тогда довольно трудно предсказать размер массива.
• Остатки от деления любого числа на всегда находятся в диапазоне от до . Иногда вместо «остаток от деления на » говорят «модуль по основанию . В JavaScript и многих других языках программирования для вычисления модуля используют оператор %