basics_of_algorithms:hash []

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
====== Хэш — Основы алгоритмов и структур данных ======

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

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

| 881 | Вена | 1237 | Берлин | 1323 | Вильнюс |
| 1614 | Тирана | 1167 | Копенгаген | 963 | Люксембург |
| 1067 | Минск | 1191 | Дублин | 1275 | Амстердам |
| 752 | Ватикан | 1786 | Рейкьявик | 1200 | Варшава |
| 1872 | Будапешт | 856 | Мадрид | 1147 | Москва |

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

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

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

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

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

===== Выводы =====

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

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


===== Модульная арифметика =====

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

<code javascript>
let capitals = new Array(100);
</code>

<details>
<summary>Python</summary>

<code python>
capitals = [None for _ in range(100)]
</code>
</details>

<details>
<summary>Java</summary>

<code java>
String[] capitals = new String[100];
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$capitals = array_fill(0, 100, null);
</code>
</details>

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

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

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

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

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

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

<details>
<summary>Python</summary>

<code python>
print(1999 % 20)  # => 19
</code>
</details>

<details>
<summary>Java</summary>

<code java>
System.out.println(1999 % 20); // => 19
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

print_r(1999 % 20); // => 19
</code>
</details>
Решим нашу задачу со столицами с помощью модуля:

<code javascript>
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); // Копенгаген
</code>


<details>
<summary>Python</summary>

<code python>
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)  # Копенгаген
</code>
</details>

<details>
<summary>Java</summary>

<code java>
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];
    }
}
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?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); // 'Копенгаген'
</code>
</details>

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

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

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

<details>
<summary>Python</summary>

<code python>
print(get_city(1167))  # => Минск
</code>
</details>

<details>
<summary>Java</summary>

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

<details>
<summary>PHP</summary>

<code php>
<?php

print_r(getCity(1167)); // => Минск
</code>
</details>

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

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

===== Коллизии =====

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

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

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

<code javascript>
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 });
};
</code>

<details>
<summary>Python</summary>

<code python>
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})
</code>
</details>

<details>
<summary>Java</summary>

<code java>
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});
    }
}
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?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]);
}
</code>
</details>

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

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

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

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

<code javascript>
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;
};
</code>

<details>
<summary>Python</summary>

<code python>
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
</code>
</details>

<details>
<summary>Java</summary>

<code java>
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;
    }
}
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?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;
}
</code>
</details>

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

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

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

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

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

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

===== Хэш-функция =====

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

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

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

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

<details>
<summary>Python</summary>

<code python>
capital = 'Мадрид'

for i in range(len(capital)):
    print(ord(capital[i]))
# => 1052
# => 1072
# => 1076
# => 1088
# => 1080
# => 1076
</code>
</details>

<details>
<summary>Java</summary>

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

<details>
<summary>PHP</summary>

<code php>
<?php

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

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

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

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

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

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

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

{{ :basics_of_algorithms:form1.png |}}

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

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

{{ :basics_of_algorithms:form2.png |}}

Обычно модуль   делают равным большому простому числу или большому круглому числу — например, миллиону или миллиарду. Часто в качестве модуля выбирают степень числа 2 — к примеру, 2<sup>.0</sup>  или 2<sup>64</sup>.

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

<code javascript>
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;
};
</code>

<details>
<summary>Python</summary>

<code python>
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
</code>
</details>

<details>
<summary>Java</summary>

<code java>
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;
    }
}
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?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;
}
</code>
</details>

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

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

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

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

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

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

<details>
<summary>Python</summary>

<code python>
hash('Мадрид') # 792876
hash('Москва') # 399671
hash('Минск')  # 857356
</code>
</details>

<details>
<summary>Java</summary>

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

<details>
<summary>PHP</summary>

<code php>
<?php

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

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

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

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

===== Худший случай =====

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

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

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

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

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

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

===== Хэш-таблицы и функция вставки =====

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

<code javascript>
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;
  }
}
</code>

<details>
<summary>Python</summary>

<code python>
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
</code>
</details>

<details>
<summary>Java</summary>

<code java>
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;
    }
}
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?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;
  }
}
</code>
</details>

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

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

<code javascript>
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);
  }
}
</code>

<details>
<summary>Python</summary>

<code python>
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)
</code>
</details>

<details>
<summary>Java</summary>

<code java>
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);
    }
}
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?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);
    }
}
</code>
</details>

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

===== Выводы =====

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

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

Инструменты сайта

Инструменты страницы
