====== Хэш — Основы алгоритмов и структур данных ====== Ранее в курсе мы изучили метод перебора и сталкивались с задачей про европейские столицы. Снова попробуем решить эту задачу, но выберем новый, более продуктивный способ. В задаче про европейские столицы в условиях задачи были указаны пары — город и дата основания. Зная дату, мы можем определить город. Для решения задачи используем следующую таблицу: | 881 | Вена | 1237 | Берлин | 1323 | Вильнюс | | 1614 | Тирана | 1167 | Копенгаген | 963 | Люксембург | | 1067 | Минск | 1191 | Дублин | 1275 | Амстердам | | 752 | Ватикан | 1786 | Рейкьявик | 1200 | Варшава | | 1872 | Будапешт | 856 | Мадрид | 1147 | Москва | Пары с годом и городом в таблице расположены в произвольном порядке, поэтому поиск нужной столицы требует полного перебора. Временная сложность такого алгоритма составляет , что довольно медленно. Бинарный поиск позволяет сократить это время до . На большой таблице из миллиона записей среднее количество сравнений для линейного поиска равно 500000, а для бинарного — всего 10. Но и это не предел. Если поиск нужно выполнять с максимальной скоростью, мы можем воспользоваться еще одной структурой данных. Это **хэш-таблица**, которая обеспечивает временную сложность . Хэш-таблица похожа на массив, потому что в ней тоже есть операция индексации. В JavaScript доступ к элементу массива осуществляется по индексу, записанному в квадратных скобках. В качестве индекса можно использовать последовательные целые числа. В случае с хэш-таблицей в качестве индекса можно брать любые структуры данных — строки, дату и время, массивы. В этом уроке мы разберемся, как устроены хэш-таблицы и как их реализовывать. ===== Выводы ===== В этом уроке мы изучили хэш-таблицы и научились с ними работать. Повторим основные тезисы: * **Хэш-таблица** обеспечивает временную сложность . Она похожа на массив, потому что в ней тоже есть операция индексации. В качестве индекса можно использовать практически любые структуры данных — строки, дату и время, массивы. * Массивы, в которых большая часть элементов не определена, называются **разреженными**. Чтобы сэкономить память, программисты стараются уплотнить массив, но тогда довольно трудно предсказать размер массива. * Остатки от деления любого числа на всегда находятся в диапазоне от до . Иногда вместо «остаток от деления на » говорят «модуль по основанию . В JavaScript и многих других языках программирования для вычисления модуля используют оператор ''%'' ===== Модульная арифметика ===== Предположим, мы фиксируем размер массива. Пусть у нас будет массив из ста элементов: let capitals = new Array(100);
Python capitals = [None for _ in range(100)]
Java String[] capitals = new String[100];
PHP
Мы хотим сохранить в него несколько элементов, но их индексы могут быть произвольными целыми числами. Чтобы преобразовать индекс в число от 0 до 99, мы должны вычислить остаток от деления индекса на 100. Общее правило такое: Остатки от деления любого числа на всегда находятся в диапазоне от до Это правило поможет нам работать с массивами любого размера. Иногда вместо «остаток от деления на » говорят «модуль по основанию ». В JavaScript и многих других языках программирования для вычисления модуля используют оператор ''%'': console.log(1999 % 20); // => 19
Python print(1999 % 20) # => 19
Java System.out.println(1999 % 20); // => 19
PHP 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); // Копенгаген
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) # Копенгаген
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]; } }
PHP $capitals[year % 100]; function getCity($capitals, $year) { return $capitals[$year % 100]; } $city = getCity(1167); // 'Копенгаген'
Теперь мы точно знаем, что наш массив не вырастет до больших размеров, как это может случиться с операцией деления. Но мы можем обнаружить другую проблему. Попробуем узнать, какой город основан в 1167 году. Если верить нашей таблице, это Копенгаген. Но программа говорит совсем другое: console.log(getCity(1167)); // => Минск
Python print(get_city(1167)) # => Минск
Java System.out.println(App.getCity(1167)); // => Минск
PHP Минск
Минск основан в 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 }); };
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})
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(); } capitals[index].add(new Object[] {year, city}); } }
PHP 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; };
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
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; } }
PHP
Если в ячейке ничего нет, значит, мы ничего и не записывали. Но если в ячейке что-то есть, то это список, по которому мы пробегаем и пытаемся найти пару с заданным ключом (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
Python capital = 'Мадрид' for i in range(len(capital)): print(ord(capital[i])) # => 1052 # => 1072 # => 1076 # => 1088 # => 1080 # => 1076
Java var capital = "Мадрид"; for (var i = 0; i < capital.length; i++) { System.out.println((int) capital.charAt(i)); } // => 1052 // => 1072 // => 1076 // => 1088 // => 1080 // => 1076
PHP 1052 // => 1072 // => 1076 // => 1088 // => 1080 // => 1076
Слово «Мадрид» хранится как последовательность чисел 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.0 или 264. Чтобы промежуточные числа не становились слишком большими, все сложения и умножения выполняют по модулю 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; };
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
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; } }
PHP
Здесь в качестве модуля мы выбрали ''2%%**%%20'', то есть 220. Это число равно 1048576 и часто используется программистами, потому что очень близко к миллиону. Слово мегабайт традиционно означает именно 1048576 байт, а не миллион, как можно было бы ожидать. Сейчас комитет по стандартизации мер и весов рекомендует термины «мебибайт» для 1048576 байтов и «мегабайт» для 1000000 байтов, но большинство программистов все еще не используют эту новую рекомендацию. Переменная ki на каждом шаге цикла умножается на k. Она принимает значения 1, k, k2 и так далее. В переменной ''result'' накапливается результат вычислений. Функция называется ''hash'', и это неслучайно. В переводе с английского слово hash означает «мелко крошить, перемешивать». Функция перемешивает исходные данные так, чтобы получилось число, похожее на случайное: hash('Мадрид') // 792876 hash('Москва') // 399671 hash('Минск') // 857356
Python hash('Мадрид') # 792876 hash('Москва') # 399671 hash('Минск') # 857356
Java App.hash("Мадрид") // 792876 App.hash("Москва") // 399671 App.hash("Минск") // 857356
PHP
Эту функцию так и называют — хеш-функция. В подавляющем большинстве случаев нам не приходится писать хеш-функции, потому что они уже разработаны авторами фреймворков и стандартных библиотек. Тем не менее полезно понимать принцип работы хешей. В 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; } }
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
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; } }
PHP 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); } }
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)
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); } }
PHP 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 и многих других языках программирования для вычисления модуля используют оператор ''%''