Различия

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

--- basics_of_algorithms:hash [2023/10/04 23:02]
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 слишком мал для таких чисел, потому что даже уплотненный массив все равно будет слишком большим и слишком пустым.
-Но мы не можем анализировать каждую возникающую задачу. Нам бы хотелось иметь универсальный способ, подходящий для разных случаев и позволяющий контролировать размер массива. Поэтому мы рассмотрим еще один способ.
 ===== Модульная арифметика =====
@@ Строка 565: / Строка 271: @@
 Попробуем реализовать в коде:
-<code>
+<code javascript>
 import LinkedList from './LinkedList.js';
@@ Строка 580: / Строка 286: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 from LinkedList import LinkedList
@@ Строка 595: / Строка 302: @@
     capitals[index].add({'key': year, 'value': city})
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     private LinkedList[] capitals = new LinkedList[100];
@@ Строка 612: / Строка 321: @@
 }
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 632: / Строка 343: @@
 }
 </code>
+</details>
 Мы уже разработали структуру данных ''LinkedList'', поэтому мы можем просто импортировать ее.
@@ Строка 641: / Строка 353: @@
 При поиске точно также вычисляем индекс:
-<code>
+<code javascript>
 const getCapital = (year) => {
   let index = year % capitals.length;
@@ Строка 658: / Строка 370: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def get_capital(year):
     index = year % len(capitals)
@@ Строка 673: / Строка 386: @@
     return None
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 lass App {
     private LinkedList[] capitals = new LinkedList[100];
@@ Строка 702: / Строка 417: @@
 }
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 724: / Строка 441: @@
 }
 </code>
+</details>
 Если в ячейке ничего нет, значит, мы ничего и не записывали.
@@ Строка 745: / Строка 463: @@
 При этом компьютеры умеют работать только с числами, и любые объекты в них хранятся как последовательности чисел. Каждая буква хранится как одно число, которое называют **кодом символа**:
-<code>
+<code javascript>
 const capital = 'Мадрид';
 for (let i = 0; i < capital.length; i++) {
@@ Строка 758: / Строка 476: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 capital = 'Мадрид'
@@ Строка 772: / Строка 491: @@
 # => 1076
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 var capital = "Мадрид";
 for (var i = 0; i < capital.length; i++) {
@@ Строка 787: / Строка 508: @@
 // => 1076
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 804: / Строка 527: @@
 // => 1076
 </code>
+</details>
 Слово «Мадрид» хранится как последовательность чисел 1052, 1072, 1076, 1088, 1080 и 1076. В простейшем случае мы могли бы использовать для вычисления индекса код первой буквы — в нашем примере 1052. Но это значит все города на М (Мадрид, Москва и Минск) попадут в один и тот же список. В таком случае скорость поиска будет не очень высокой.
@@ Строка 813: / Строка 537: @@
 Хороший результат в таком случае даст так называемая **полиномиальная функция**.
-Попробуем применить ее к нашей задаче с городами. Пусть коды символов строки длины   будут равны   . Возьмем число   , которое будет больше кода любого символа — скажем,   .
+Попробуем применить ее к нашей задаче с городами. Пусть коды символов строки длины //n// будут равны c0, c1..., cn-1. Возьмем число k, которое будет больше кода любого символа — скажем, k=65537.
 У нас получилось такое выражение:
-Число   достаточно большое. На каждом шаге нам приходится возводить его в возрастающую степень, поэтому выражение может оказаться просто огромным. Для слова Мадрид мы получим   .
+{{ :basics_of_algorithms:form1.png |}}
-На практике для ускорения вычислений и для удобства используют не все выражение, а только остаток от его деления на другое число —   :
+Число   достаточно большое. На каждом шаге нам приходится возводить его в возрастающую степень, поэтому выражение может оказаться просто огромным. Для слова Мадрид мы получим 13009213352423037265600321836.
-Обычно модуль   делают равным большому простому числу или большому круглому числу — например, миллиону или миллиарду. Часто в качестве модуля выбирают степень числа   — к примеру,   или   .
+На практике для ускорения вычислений и для удобства используют не все выражение, а только остаток от его деления на другое число — //m//:
-Чтобы промежуточные числа не становились слишком большими, все сложения и умножения выполняют по модулю   . Другими словами, остаток от деления вычисляется сразу после сложения или умножения:
+{{ :basics_of_algorithms:form2.png |}}
-<code>
+Обычно модуль   делают равным большому простому числу или большому круглому числу — например, миллиону или миллиарду. Часто в качестве модуля выбирают степень числа 2 — к примеру, 2<sup>.0</sup>  или 2<sup>64</sup>.
+Чтобы промежуточные числа не становились слишком большими, все сложения и умножения выполняют по модулю m. Другими словами, остаток от деления вычисляется сразу после сложения или умножения:
+<code javascript>
 const hash = (s) => {
   const k = 65537;
@@ Строка 841: / Строка 569: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 def hash(s):
     k = 65537
@@ Строка 857: / Строка 586: @@
     return result
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class App {
     private int hash(String s) {
@@ Строка 878: / Строка 609: @@
 }
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 899: / Строка 632: @@
 }
 </code>
+</details>
-Здесь в качестве модуля мы выбрали ''2%%**%%20'', то есть   . Это число равно   и часто используется программистами, потому что очень близко к миллиону. Слово мегабайт традиционно означает именно   байт, а не миллион, как можно было бы ожидать.
+Здесь в качестве модуля мы выбрали ''2%%**%%20'', то есть 2<sup>20</sup>. Это число равно 1048576 и часто используется программистами, потому что очень близко к миллиону. Слово мегабайт традиционно означает именно 1048576 байт, а не миллион, как можно было бы ожидать.
 Сейчас комитет по стандартизации мер и весов рекомендует термины «мебибайт» для 1048576 байтов и «мегабайт» для 1000000 байтов, но большинство программистов все еще не используют эту новую рекомендацию.
-Переменная   на каждом шаге цикла умножается на   . Она принимает значения   ,   ,   и так далее. В переменной ''result'' накапливается результат вычислений.
+Переменная k<sup>i</sup> на каждом шаге цикла умножается на k. Она принимает значения 1, k, k2 и так далее. В переменной ''result'' накапливается результат вычислений.
 Функция называется ''hash'', и это неслучайно. В переводе с английского слово hash означает «мелко крошить, перемешивать».
@@ Строка 910: / Строка 644: @@
 Функция перемешивает исходные данные так, чтобы получилось число, похожее на случайное:
-<code>
+<code javascript>
 hash('Мадрид') // 792876
 hash('Москва') // 399671
@@ Строка 916: / Строка 650: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 hash('Мадрид') # 792876
 hash('Москва') # 399671
 hash('Минск')  # 857356
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 App.hash("Мадрид") // 792876
 App.hash("Москва") // 399671
 App.hash("Минск")  // 857356
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 941: / Строка 680: @@
 hash('Минск')  // 857356
 </code>
+</details>
 Эту функцию так и называют — хеш-функция. В подавляющем большинстве случаев нам не приходится писать хеш-функции, потому что они уже разработаны авторами фреймворков и стандартных библиотек. Тем не менее полезно понимать принцип работы хешей.
@@ Строка 966: / Строка 706: @@
 Перепишем функцию вставки, опираясь на все новые знания. Вместе с этим реализуем хеш-таблицу в виде новой структуры данных, спрятав внутри класса массив с данными:
-<code>
+<code javascript>
 class Hash {
   let table = [];
@@ Строка 1040: / Строка 780: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 class Hash:
     table = []
@@ Строка 1109: / Строка 850: @@
         return None
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 class Hash {
@@ Строка 1186: / Строка 929: @@
 }
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1261: / Строка 1006: @@
 }
 </code>
+</details>
 Весь код из этого примера мы уже обсуждали, кроме удвоения массива. Создавая новых массив, в два раза больше текущего, мы должны скопировать все элементы, пересчитав их индексы.
@@ Строка 1266: / Строка 1012: @@
 Именно за это отвечает вложенный цикл:
-<code>
+<code javascript>
 let newTable = new Array(this.table.length * 2);
 for (let list in this.table) {
@@ Строка 1280: / Строка 1026: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
-<code>
+<code python>
 new_table = [None for _ in range(len(self.table) * 2)]
@@ Строка 1293: / Строка 1040: @@
         new_table[new_index].add(pair)
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code>
+<code java>
 LinkedList[] newTable = new LinkedList[table.length * 2];
@@ Строка 1311: / Строка 1060: @@
 }
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code>
+<code php>
 <?php
@@ Строка 1329: / Строка 1080: @@
 }
 </code>
+</details>
 В самом начале внутренний массив имеет размер 0, чтобы не тратить память, если в хеш-таблице нет ни одного элемента. При вставке первого элемента мы увеличиваем внутренний массив сразу до 128 элементов. Остальной код мы уже рассмотрели выше в этом уроке.

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

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

Различия

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