Различия

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

--- basics_of_algorithms:hash [2023/10/04 23:20]
werwolf [Хэш-функция]
+++ basics_of_algorithms:hash [2023/10/19 12:55] (текущий)
werwolf [Разреженные массивы]
@@ Строка 21: / Строка 21: @@
 В этом уроке мы разберемся, как устроены хэш-таблицы и как их реализовывать.
-===== Разреженные массивы =====
+===== Выводы =====
-Простейший способ определить столицу по году основания — использовать массив:
+В этом уроке мы изучили хэш-таблицы и научились с ними работать. Повторим основные тезисы:
-<code javascsript>
+  * **Хэш-таблица**  обеспечивает временную сложность . Она похожа на массив, потому что в ней тоже есть операция индексации. В качестве индекса можно использовать практически любые структуры данных — строки, дату и время, массивы.
-let capitals = [];
+  * Массивы, в которых большая часть элементов не определена, называются **разреженными**. Чтобы сэкономить память, программисты стараются уплотнить массив, но тогда довольно трудно предсказать размер массива.
+  * Остатки от деления любого числа на всегда находятся в диапазоне от до . Иногда вместо «остаток от деления на » говорят «модуль по основанию . В JavaScript и многих других языках программирования для вычисления модуля используют оператор ''%''
-capitals[881] = 'Вена';
-capitals[1237] = 'Берлин';
-capitals[1323] = 'Вильнюс';
-capitals[1614] = 'Тирана';
-capitals[1167] = 'Копенгаген';
-capitals[963] = 'Люксембург';
-capitals[1067] = 'Минск';
-capitals[1191] = 'Дублин';
-capitals[1275] = 'Амстердам';
-capitals[752] = 'Ватикан';
-capitals[1786] = 'Рейкьявик';
-capitals[1200] = 'Варшава';
-capitals[1872] = 'Будапешт';
-capitals[856] = 'Мадрид';
-capitals[1147] = 'Москва';
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-capitals = [None for _ in range(1873)]
-capitals[1804] = "Вена"
-capitals[1237] = "Берлин"
-capitals[1323] = "Вильнюс"
-capitals[1614] = "Тирана"
-capitals[1167] = "Копенгаген"
-capitals[963] = "Люксембург"
-capitals[1067] = "Минск"
-capitals[1191] = "Дублин"
-capitals[1275] = "Амстердам"
-capitals[752] = "Ватикан"
-capitals[1786] = "Рейкьявик"
-capitals[1200] = "Варшава"
-capitals[1872] = "Будапешт"
-capitals[856] = "Мадрид"
-capitals[1147] = "Москва"
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code java>
-String[] capitals = new String[1873];
-capitals[881] = "Вена";
-capitals[1237] = "Берлин";
-capitals[1323] = "Вильнюс";
-capitals[1614] = "Тирана";
-capitals[1167] = "Копенгаген";
-capitals[963] = "Люксембург";
-capitals[1067] = "Минск";
-capitals[1191] = "Дублин";
-capitals[1275] = "Амстердам";
-capitals[752] = "Ватикан";
-capitals[1786] = "Рейкьявик";
-capitals[1200] = "Варшава";
-capitals[1872] = "Будапешт";
-capitals[856] = "Мадрид";
-capitals[1147] = "Москва";
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-$capitals = new SplFixedArray(1873);
-$capitals[881] = 'Вена';
-$capitals[1237] = 'Берлин';
-$capitals[1323] = 'Вильнюс';
-$capitals[1614] = 'Тирана';
-$capitals[1167] = 'Копенгаген';
-$capitals[963] = 'Люксембург';
-$capitals[1067] = 'Минск';
-$capitals[1191] = 'Дублин';
-$capitals[1275] = 'Амстердам';
-$capitals[752] = 'Ватикан';
-$capitals[1786] = 'Рейкьявик';
-$capitals[1200] = 'Варшава';
-$capitals[1872] = 'Будапешт';
-$capitals[856] = 'Мадрид';
-$capitals[1147] = 'Москва';
-</code>
-</details>
-Такой массив занимает много памяти. В нем хранится всего 15 городов, но при этом размер массива — это целых 1873 элемента:
-<code javascript>
-console.log(capitals.length); // => 1873
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-print(len(capitals))  # => 1873
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code java>
-System.out.println(capitals.length); // => 1873
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-print_r(count($capitals)); // => 1873
-</code>
-</details>
-Так получилось потому, что индексами в массиве могут быть только последовательные целые числа, начиная с 0. Если мы добавляем элемент с индексом 752, в массив добавляются и неопределенные элементы с индексами от 0 до 751. Длина массива получилась равной 1873, потому что:
-  * Наибольший год основания — 1872
-  * Первым в массиве всегда стоит элемент с индексом 0
-Если мы применим массив, доступ к элементам выполнится очень быстро — за константное время   . Но при этом мы впустую расходуем память — в нашем примере массив заполнен всего на 0,8%.
-Массивы, в которых большая часть элементов не определена, называются **разреженными**. Чтобы сэкономить память, программисты стараются уплотнить массив. Скажем, в нашем примере годы находятся достаточно далеко друг от друга — на каждые двадцать пустых элементов приходится только один элемент с данными. Мы можем уменьшить массив в двадцать раз с помощью простого трюка.
-Возьмем числа 0, 1, 2 и 3, поделим их на 20 и получим такой результат:
-  *   *   *   * Целая часть этих чисел будет равна 0, пока мы не доберемся до такой операции:
-Начиная с 20, целая часть после деления будет равна 1:
-  *   * Начиная с 40, целая часть будет равна 2.
-Получается, что после преобразования числа схлопываются:
-  * От 0 до 19 → 0
-  * От 20 до 39 → 1
-  * От 40 до 59 → 2 и так далее
-Чтобы получать целую часть, воспользуемся стандартной функцией ''Math.floor'':
-<code javascript>
-let capitals = [];
-capitals[Math.floor(881 / 20)] = 'Вена';
-capitals[Math.floor(1237 / 20)] = 'Берлин';
-capitals[Math.floor(1323 / 20)] = 'Вильнюс';
-capitals[Math.floor(1614 / 20)] = 'Тирана';
-capitals[Math.floor(1167 / 20)] = 'Копенгаген';
-capitals[Math.floor(963 / 20)] = 'Люксембург';
-capitals[Math.floor(1067 / 20)] = 'Минск';
-capitals[Math.floor(1191 / 20)] = 'Дублин';
-capitals[Math.floor(1275 / 20)] = 'Амстердам';
-capitals[Math.floor(752 / 20)] = 'Ватикан';
-capitals[Math.floor(1786 / 20)] = 'Рейкьявик';
-capitals[Math.floor(1200 / 20)] = 'Варшава';
-capitals[Math.floor(1872 / 20)] = 'Будапешт';
-capitals[Math.floor(856 / 20)] = 'Мадрид';
-capitals[Math.floor(1147 / 20)] = 'Москва';
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-# В Python для целых чисел используется целочисленное деление
-capitals = [None for _ in range(100)];
-capitals[1804 // 20] = "Вена"
-capitals[1237 // 20] = "Берлин"
-capitals[1323 // 20] = "Вильнюс"
-capitals[1614 // 20] = "Тирана"
-capitals[1167 // 20] = "Копенгаген"
-capitals[963 // 20] = "Люксембург"
-capitals[1067 // 20] = "Минск"
-capitals[1191 // 20] = "Дублин"
-capitals[1275 // 20] = "Амстердам"
-capitals[752 // 20] = "Ватикан"
-capitals[1786 // 20] = "Рейкьявик"
-capitals[1200 // 20] = "Варшава"
-capitals[1872 // 20] = "Будапешт"
-capitals[856 // 20] = "Мадрид"
-capitals[1147 // 20] = "Москва"
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code java>
-// В java для целых чисел используется целочисленное деление
-String[] capitals = new String[100];
-capitals[881 / 20] = "Вена";
-capitals[1237 / 20] = "Берлин";
-capitals[1323 / 20] = "Вильнюс";
-capitals[1614 / 20] = "Тирана";
-capitals[1167 / 20] = "Копенгаген";
-capitals[963 / 20] = "Люксембург";
-capitals[1067 / 20] = "Минск";
-capitals[1191 / 20] = "Дублин";
-capitals[1275 / 20] = "Амстердам";
-capitals[752 / 20] = "Ватикан";
-capitals[1786 / 20] = "Рейкьявик";
-capitals[1200 / 20] = "Варшава";
-capitals[1872 / 20] = "Будапешт";
-capitals[856 / 20] = "Мадрид";
-capitals[1147 / 20] = "Москва";
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-$capitals = new SplFixedArray(100);
-$capitals[round(881 / 20)] = 'Вена';
-$capitals[round(1237 / 20)] = 'Берлин';
-$capitals[round(1323 / 20)] = 'Вильнюс';
-$capitals[round(1614 / 20)] = 'Тирана';
-$capitals[round(1167 / 20)] = 'Копенгаген';
-$capitals[round(963 / 20)] = 'Люксембург';
-$capitals[round(1067 / 20)] = 'Минск';
-$capitals[round(1191 / 20)] = 'Дублин';
-$capitals[round(1275 / 20)] = 'Амстердам';
-$capitals[round(752 / 20)] = 'Ватикан';
-$capitals[round(1786 / 20)] = 'Рейкьявик';
-$capitals[round(1200 / 20)] = 'Варшава';
-$capitals[round(1872 / 20)] = 'Будапешт';
-$capitals[round(856 / 20)] = 'Мадрид';
-$capitals[round(1147 / 20)] = 'Москва';
-</code>
-</details>
-Чтобы узнать, какой город основан в 1191 году, мы проверяем элемент с индексом 1191/20:
-<code javascript>
-const getCity = (year) => capitals[Math.floor(year / 20)];
-let city = getCity(1191); // Дублин
-</code>
-<details>
-<summary>Python</summary>
-<code python>
-def get_city(year):
-    return capitals[year // 20]
-city = get_city(1191)  # Дублин
-</code>
-</details>
-<details>
-<summary>Java</summary>
-<code>
-class App {
-    public static String getCity(String[] capitals, int year) {
-        return capitals[year / 20];
-    }
-}
-</code>
-</details>
-<details>
-<summary>PHP</summary>
-<code php>
-<?php
-function getCity($year, $capitals)
-{
-    return $capitals[round($year / 20)];
-}
-</code>
-</details>
-У такого подхода есть недостаток — довольно трудно предсказать размер массива. Когда речь идет о годах основания, мы можем проанализировать данные и прикинуть, что каждые двадцать лет можно схлопнуть в один элемент.
-Для чисел 0 до 1999 нам достаточно массива из ста элементов. Последний элемент такого уплотненного массива имеет индекс 99, а ''Math.floor(1999/20)'' как раз равно 99.
-Но в другой задаче это может не сработать — например, если требуется хранить в массиве индексы, равные миллиону или миллиарду. Коэффициент 20 слишком мал для таких чисел, потому что даже уплотненный массив все равно будет слишком большим и слишком пустым.
-Но мы не можем анализировать каждую возникающую задачу. Нам бы хотелось иметь универсальный способ, подходящий для разных случаев и позволяющий контролировать размер массива. Поэтому мы рассмотрим еще один способ.
 ===== Модульная арифметика =====
@@ Строка 1000: / Строка 706: @@
 Перепишем функцию вставки, опираясь на все новые знания. Вместе с этим реализуем хеш-таблицу в виде новой структуры данных, спрятав внутри класса массив с данными:
-<code>
+<code javascript>
 class Hash {
   let table = [];
@@ Строка 1074: / Строка 780: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 class Hash:
     table = []
@@ Строка 1143: / Строка 850: @@
         return None
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class Hash {
@@ Строка 1220: / Строка 929: @@
 }
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1295: / Строка 1006: @@
 }
 </code>
+</details>
 Весь код из этого примера мы уже обсуждали, кроме удвоения массива. Создавая новых массив, в два раза больше текущего, мы должны скопировать все элементы, пересчитав их индексы.
@@ Строка 1300: / Строка 1012: @@
 Именно за это отвечает вложенный цикл:
-<code>
+<code javascript>
 let newTable = new Array(this.table.length * 2);
 for (let list in this.table) {
@@ Строка 1314: / Строка 1026: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 new_table = [None for _ in range(len(self.table) * 2)]
@@ Строка 1327: / Строка 1040: @@
         new_table[new_index].add(pair)
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 LinkedList[] newTable = new LinkedList[table.length * 2];
@@ Строка 1345: / Строка 1060: @@
 }
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1363: / Строка 1080: @@
 }
 </code>
+</details>
 В самом начале внутренний массив имеет размер 0, чтобы не тратить память, если в хеш-таблице нет ни одного элемента. При вставке первого элемента мы увеличиваем внутренний массив сразу до 128 элементов. Остальной код мы уже рассмотрели выше в этом уроке.

Инструменты пользователя

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

Различия

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