Хороший хеш — залог успеха

Better Living Through Better Hashing

В этой главе мы выясним: . In this chapter, you will learn:

• Как сформировать ассоциативный массив, хранящий пары вида (ключ, значение) и по известному ключу получать такую пару из него¹. . • How to store (key, value) pairs in a symbol table and retrieve values associated . with a key.1

• Как хранить пары (ключ, значение) в массиве, чтобы при этом поиск по ключу был эффективен — при условии, что размер этого массива достаточно велик по сравнению с количеством хранимых пар. • How to use an array to store (key, value) pairs for efficient search, if the size of . the array is sufficiently large, compared to the number of pairs stored.

• Как использовать массив списков для хранения и поиска пар (ключ, значение), с возможностью удаления по ключу. • How to use an array of linked lists to store (key, value) pairs to support the extra . ability to remove a key.

• Как менять размер хеш-таблицы, чтобы не потерять её производительность.

  • How to resize a symbol table to remain efficient.

• Как оценивать среднее быстродействие алгоритма, если его работа меняется по мере выполнения некоторых действий с данными (как делать амортизационный анализ). • Amortized analysis to determine the average runtime performance when the . behavior of an operation can change with successive invocations.

• Как довести оценку операции добавления в хеш-таблицу put() до амортизационной сложности O(1) в среднем путём геометрического масштабирования. • How geometric resizing reduces the frequency of the costly resize operation, . meaning that put() has amortized O(1) performance on average.

• Как свойство равномерного распределения значений хеш-функции можно использовать для эффективного размещения ключей в хеш-таблице. • How a computational hash function can uniformly distribute key values, which . ensures the efficiency of the symbol table implementation.

Переведённая сноска /* /* 1 Throughout this chapter, the notation (key, value) represents a pair of information considered as a single unit.

Соответствие значений ключам

Associating Values with Keys

Часто набор объектов, которые нужно уметь хранить в памяти, представлен не в виде последовательности, а в виде множества пар (ключ, значение), в котором каждому ключу однозначно соответствует некоторое значение. Такая структура называется ассоциативным массивом. Если наложить некоторые дополнительные требования на свойство ключа, вместо поиска пары (ключ, значение) по всему набору можно использовать гораздо более эффективный приём — хеширование. Поиск по хешу работает быстрее любого изученного нами алгоритма поиска! Ассоциативный массив сохраняет эффективность даже если разрешить при удаление ключей и значений. Порядок следования ключей в такой структуре определяется её реализацией (в словарях Python ключи идут в порядке добавления, в устаревшем Python2 определённый порядок не гарантировался вовсе; в любом случае ключи почти наверняка не будут упорядочены по возрастанию, как индексы массива). Взамен мы получаем великолепную скорость поиска и добавления пары. Instead of just storing values, you might need to store a collection of (key, value) pairs to associate values with specific keys. This is known as a symbol table data type, which lets you find the associated value given just its key. Hashing offers an efficient alternative to manually searching through a collection from start to finish just to find a (key, value) pair. It outperforms the search algorithms I covered earlier. A symbol table can be efficient even while allowing for keys (and their values) to be removed. You give up the ability to retrieve all keys in a specific order, for example, in ascend‐ ing order, but the resulting symbol table provides optimal performance for retrieving or storing the value associated with any individual key.

Скажем, мы хотим написать функцию print_month(month, year), которая будет выводить календарь на определённый месяц определённого года. С параметрами print_month('February', 2024) функция должна выводить примерно это: Let’s say you want to write a function print_month(month, year) to print a calendar for any month and year. For example, print_month('February', 2024) would out‐ put the following:

    Февраль 2024
Пн Вт Ср Чт Пт Сб Вс
          1  2  3  4
 5  6  7  8  9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29

Что нам нужно для этого знать? День недели, с которого в этом году начинается месяц (в примере это четверг), а ещё — сколько дней в феврале этого года (28, а если год високосный, как 2024-й, то 29). Для количества дней в месяце заведём числовой массив, каждый элемент которого будет соответствовать месяцу начиная с января: What information would you need? You need the weekday for the first day of that month in that year (above it is Thursday), and you need to know that February has 28 days (or 29 in a leap year, such as 2024). You might use a fixed array, month_length, with values that record the length of each month in days for the year:

   1      month_length = 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31

Итак, в январе 31 день, поэтому month_length[0] == 31, в феврале — 28, так что следующее значение —­28, и так далее до последнего 31, которое соответствует 31 дню в декабре. January, the first month, has 31 days, so month_length[0] = 31. February is the next month, with 28 days, so the next value in the list is 28. The final value in month_length is 31, since December, the last month of the year, has 31 days.

Изученные нами ранее примеры позволяют предположить, что нам понадобится также массив той же длинны с названиями месяцев — ключей, по которым мы сможем определить, в по какому индексу в month_length находится искомое количество дней. Вот такой фрагмент программы выводит количество дней в феврале: Given what I have presented in this book so far, you might choose to store a key_array of the same length and search it for the month to determine the corre‐ sponding value in month_length; the following code prints February has 28 days:

   1      key_array = ('Январь', 'Февраль', 'Март', 'Апрель', 'Май', 'Июнь', 'Июль',
   2                   'Август', 'Сентябрь', 'Октябрь', 'Ноябрь', 'Декабрь')
   3      idx = key_array.index('Февраль')
   4      print('В феврале', month_length[idx], 'дней')

Если название месяца в массиве ключей есть, этот фрагмент будет работать. Однако в худшем случае, когда нам нужен 'Декабрь', придётся просмотреть все значения. Если ключа в массиве нет, key_array.index() выдаст исключение, так что предварительно нам придется проверить наличие ключа, например, с помощью key in key_array. Это тоже худший случай, потому что будут просмотрены все строки в key_array. Следовательно, время поиска значения по ключу в изобретённой нами структуре прямо пропорционально количеству ключей. Такая скорость поиска довольно быстро станет медленной до полной неприемлемости. Несмотря на это давайте всё-таки напишем print_month(). В частности, вот возможная реализация, в которой задействованы два стандартных модуля python — datetime (для определения дня недели) и calendar (для определения високосного года). While the preceding code snippet will work, in the worst case, the key you are looking for is either the last one in the list (December) or an invalid month name, which means you have to inspect all values in the array. This means the time to locate the associated value for a key is directly proportional to the number of keys stored. If there were hundreds of thousands of (key, value) pairs, this approach would rapidly become so inefficient as to be unusable. Given this starting point, you should try to implement print_month(); for the record, Listing 3-1 contains my implementation, which uses the datetime and calendar Python modules.

   1 from datetime import date
   2 import calendar
   3 
   4 month_length = 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
   5 key_array = ('Январь', 'Февраль', 'Март', 'Апрель', 'Май', 'Июнь', 'Июль',
   6              'Август', 'Сентябрь', 'Октябрь', 'Ноябрь', 'Декабрь')
   7 
   8 def print_month(month, year):
   9   idx = key_array.index(month)              # 1
  10   wd = date(year, idx + 1, 1).weekday()     # 2
  11   days = month_length[idx]                  # 3
  12   if calendar.isleap(year) and idx == 1:    # 4
  13    days += 1
  14 
  15   print(f"{month} {year}".center(20))
  16   print("Пн Вт Ср Чт Пт Сб Вс")
  17   print('   ' * wd, end='')                 # 5
  18   for day in range(days):
  19     wd = (wd + 1) % 7                       # 6
  20     eow = " " if wd % 7 else "\n"           # 7
  21     print(f"{day+1:2}", end=eow)
  22   print()

• Пример 3-1. Вывод на экран календаря за произвольный год и месяц в удобном формате. Listing 3-1. Code to print readable calendar for any month and year

• Найдём номер месяца (целое число от 0 до 11) — индекс в month_length. Find index to use for month_length, an integer from 0 to 11.

• Вычислим первый день недели данного месяца в данном году, 0 — это понедельник. В функцию date() передаётся idx + 1, потому что месяцы в ней нумеруются с единицы, а не с нуля.

• Определим количество дней в месяце.

• В високосный год в феврале 29 дней (мы нумеруем месяцы с нуля, так что февраль — это 1). In a leap year, February (index 1 when counting from 0) has 29 days.

• Вместо дней прошедшего месяца в первой неделе выведем пробелы, тогда первый день окажется на своём месте. Add spaces in first week to start day 1 at right indentation.

• Вычислим следующий день недели. Advance day and weekday for next day.

• Вычислим, что выводить после текущей даты. Если следующий день — не понедельник, т. е. wd не делится на 7, нужно выводить пробел, а если понедельник — конец строки, потому что неделя закончилась.

Чтобы оценить производительность поиска ключа в наборе из N пар (ключ, значение), имеет смысл посчитать количество операций индексирования. Функция key_array.index() для поиска нужной строки может просматривать вплоть до N элементов, так что её сложность — O(N). For the task of finding the associated value for a given key in a collection of N (key, value) pairs, I judge efficiency by counting the number of times any array index is accessed. A function searching for a string in key_array could inspect up to N array index positions, so that function’s performance is O(N).

Тип данных list реализован в Python как динамический массив, размер которого может меняться. Для краткости его часто называют просто список. В этой главе мы будем также использовать термин массив в знак того, что наши методы применимы и к «классическим» массивам неизменяемой длины. Кроме того, если мы не собираемся менять также и сами элементы массива, в программах на Python лучше использовать кортежи (тип данных tuple), как в примерах выше.

Ассоциативные массивы, хранящие произвольные значения по ключу, реализованы в Python специальным типом данных dict (сокращённо от «dictionary» — «словарь»). Мы можем составить словарь days_in_month, хранящий целые числа — продолжительность месяцев в днях — в соответствии с ключами — названиями месяцев (с заглавной буквы) так: Python has a built-in dict type (an abbreviation of dictionary) that associates values with keys. In the following, days_in_month is a dict that associates an integer value (representing the length of that month) with a string key containing the capitalized English name:

   1 days_in_month = {'Январь':  31, 'Февраль': 28, 'Март':     31,
   2                  'Апрель':  30, 'Май':     31, 'Июнь':     30,
   3                  'Июль':    31, 'Август':  31, 'Сентябрь': 30,
   4                  'Октябрь': 31, 'Ноябрь':  30, 'Декабрь':  31 }

А вот пример вывода утверждения «в апреле 30 дней»: The following code prints April has 30 days:

print('В апреле', days_in_month['Апрель'], 'дней')

В словаре на поиск ключа в среднем уходит O(1) времени, независимо от количества хранящихся в нём пар (ключ, значение). Совершенно удивительный результат, будто фокусник только что достал кролика из шляпы! Словарями мы воспользуемся в восьмой главе, а пока попробуем сами достать этого кролика. Пример ниже предлагает интуитивное описание математического механизма, который мы изучаем в этой главе. Смысл в том, чтобы для начала преобразовать строку в число. The dict type can locate a key with an average performance of O(1), independent of the number of (key, value) pairs it stores. This is an amazing accomplishment, like a magician pulling a rabbit from a hat! In Chapter 8, I provide more details about dict. For now, let’s see how it works. The following code provides some mathematical intu‐ ition as to how this happens. The key idea is to turn a string into a number.

Будем считать, что буква «а» — это 0, буква «б» — 1 и так далее до «я» — 31. С помощью этих 32 «цифр» любое русское слово (увы, без буквы «ё»), записанное строчными буквами, соответствует некоторому числу в системе счисления с основанием 32. Например, «числе» 'июнь' четыре цифры — «и», «ю», «н» и «ь». Если начать переводить из 32-ричной системы счисления в привычную нам десятичную, получится «и»·32³+«ю»·32²+«н»·32¹+«ь»·32⁰, или, после вынесения основания за скобки, 32·(32·(32·«и»+«ю»)+«н»)+«ь». Именно так и работает функкция base32() в примере 3-2. Буква 'a' в примере — русская. Try this: consider the letter 'a' to be the value 0, 'b' to be 1, and so on through 'z' = 25. You can then consider 'June' to be a number in base 26, which represents the base 10 value j × 17,576 + u × 676 + n × 26 + e = 172,046 in base 10.2 This computa‐ tion can also be written as 26 × (26 × (26 × j + u) + n) + e, which reflects the structure of the base32() method shown in Listing 3-2.

   1 def base32(w):
   2   val = 0
   3   for ch in w.lower():                  # 1
   4     next_digit = ord(ch) - ord('а')     # 2
   5     val = 32 * val + next_digit         # 3
   6   return val

• Пример 3-2. Интерпретация слова как числа с основанием 32. Listing 3-2. Convert word to an integer assuming base 26

Эта сноска не нужна 2 Note that 263 = 17,576.

1. Преобразуем буквы строки в строчные.
2. Вычислим значение очередной цифры.
3. Припишем цифру в конец результата

В base32() используется функция ord(), которая возвращает порядковый номер буквы в таблице всех известных Python символов, Unicode². Буквы от «а» до «я» идут в алфавитном порядке³, ord('а') == 1072, ord('б') == 1073 и т. д. до ord('я') == 1103. Так что для того, чтобы вычислить значение цифры «и», достаточно выесть порядковые номера: ord('и') - ord('а') и получить 8. base32() uses the ord() function to convert a single character (such as 'a') into its integer ASCII representation.3 ASCII codes are ordered alphabetically, so ord('a') = 97, ord('e') = 101 and ord('z') = 122. To find the value associated with 'e', simply compute ord('e') – ord('a') to determine that 'e' represents the value 4.

Значение base32() очень быстро растёт с ростом длины строки. Уже base32('Июнь') возвращает 293308, а base32('Сентябрь') — так и вовсе 589940360732. When computing base32() values for a string, the resulting numbers quickly grow large: 'June' computes to the value 172,046, while 'January' computes to 2,786,534,658.

Как бы такие большие числа втиснуть в более приемлемый диапазон? Можно применить операцию «остаток от деления»: в Python, как и во многих языках программирования, это «%». Остаток сколь угодно большого целого числа (например base32(month)) можно взять относительно достаточно малого делителя. How can these numbers be cut down to a more manageable size? You might know about the modulo operator % provided by most programming languages. This opera‐ tor returns the integer remainder when dividing a large integer (i.e., the base32(month) computation) by a much smaller integer.

↓ Ниже — ещё один образчик авторского трюизма, который было очень неловко переводить. Возможно, не стоит его включать в перевод? -- FrBrGeorge 2022-01-20 07:50:40

Остатком от деления мы пользуемся в жизни постоянно, сами того не замечая. Скажем, наступило 11 утра; какое время будет на часах через 50 часов? Через 24 часа, завтра, снова наступит 11 утра, и через 48, послезавтра, — тоже. Остаётся ещё два часа, стало быть, через 50 часов буде час пополудни. Арифметика проста: 50 % 24 == 2. Другими словами, 50 не делится на 24 нацело, потому что в остатке получается 2. Остаток от деления натурального числа M на натуральное N, M % N, всегда не меньше нуля и не больше N - 1.

TODO для русского — 35.

Немного поэкспериментировав, мы можем обнаружить, что для всех названий месяцев значения base32(month) % 35 различны. Например, base32('Август') равно 2215474, а 2215474 % 35 == 9, и для каждого месяца результат будет иным. Теперь, как показано на иллюстрации 3-1, мы можем завести массив на 35 элементов, с помощью которого можно узнать количество дней в данном месяце, за одно обращение, и перебирать все пары (ключ, значение) не нужно. Вычисляем формулу для февраля, получаем 0, на нулевой позиции в day_array стоит 28 — в феврале 28 дней. Проделываем то же самое с ноябрём — получаем позицию 32 и 30 дней. With some experimentation, I discovered that base32(m) % 34 computes a different integer for each of the twelve English month names; for example, base32('August') computes to 9,258,983, and you can confirm that 9,258,983 % 34 = 1. If you create a single array containing 34 values, as shown in Figure 3-1, then independently of the number of (key, value) pairs, you can determine the number of days in a month by computing its associated index into day_array. This means that August has 31 days; a similar computation for February shows it has 28 days.

изменённое примечание 3 Originally based on the English alphabet, ASCII encodes 128 characters (typically those found on a typewriter . keyboard) into seven-bit integers. Capitalization matters! ord('A') = 65, for example, but ord('a') = 97.

Давайте ещё раз оценим, что у нас получилось. Вместо цикла по всем ключам в массиве нам нужно проделать несложное преобразование самого ключа, которое даст позицию нужного значения в массиве. Время нашего вычисления зависит от длины ключа, но не зависит от общего количества ключей — это очень большой шаг вперёд! Take a moment to reflect on what I have accomplished. Instead of iteratively search‐ ing for a key in an array, I can now perform a simple computation on the key itself to compute an index position that contains its associated value. The time it takes to per‐ form this computation is independent of the number of keys stored. This is a major step forward!

• Иллюстрация 3-1. Массив с длинами месяцев; если формула не даёт соответствующего индекса, в массиве записано -1.

Figure 3-1. Array containing month lengths interspersed with unneeded –1 values

Поработать, правда, пришлось изрядно. Во-первых — подыскать формулу однозначного преобразования имени месяца в индекс, а во-вторых — создать массив на 35 элементов, из которых имеет смысл только дюжина, а значит, больше половины этого массива потрачено впустую. В нашем примере объём хранимых данных N равен 12, а объём хранилища M — 35. But this was a lot of work. I had to (a) craft a special formula to compute unique index positions, and (b) create an array containing 34 integers, only 12 of which are relevant (meaning that more than half of the values are wasted). In this example, N equals 12, and the amount of dedicated storage, M, equals 34.

Если для некоторой строки s элемент day_array в позиции base32(s) % 35 равен -1, очевидно, эта строка — не название месяца. Этим удобно пользоваться. Может показаться, что если day_array[base32(s)%35] > 0, то любая строка s — это допустимое название месяца, но это, конечно не так. К примеру, base32("Промахнулось") выдаёт то же самое, что и base32("Февраль"); получится, что «Промахнулось» — это такой месяц, и в нём 28 дней! Это довольно неприятное свойство, и нам придётся разобраться, как его преодолеть. Given any string s, if the value in day_array at index position base32(s) % 34 is –1, you know s is an invalid month. This is a good feature. You might be tempted to con‐ firm that a given string, s, is a valid month whenever day_array[base32(s)%34] > 0, but this would be a mistake. For example, the string 'abbreviated' computes to the same index position as 'March', which might mistakenly tell you that 'abbreviated' is a valid month! This is a bad feature, but I now show how to overcome this issue.

Хеш-функции и хеш-суммы

Hash Functions and Hash Codes

Формула base32(s) % 35 — пример хеш-функции, которая отображает ключ произвольного размера в хеш-сумму (или просто хеш) в заданном диапазоне значений⁴. В нашем примере хеш не меньше нуля и не больше 34. Множество хеш-функций возвращают произвольное 32-разрядное целое (в диапазоне от -2 147 483 648 до 2 147 483 647) или произвольное 64-разрядное целое (в диапазоне от -9 223 372 036 854 775 808 до 9 223 372 036 854 775 807). Нетрудно заметить, что хеши бывают и отрицательными. base32() is an example of a hash function that maps keys of arbitrary size to a fixed- size hash code value, such as a 32-bit or 64-bit integer. A 32-bit integer is a value from –2,147,483,648 to 2,147,483,647, while a 64-bit integer is a value from –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. As you can see, a hash code can be negative.

Задача отображения структурированных данных в фиксированные целые числа, т. е. задача отыскания подходящей хеш-функции, занимает математиков последние несколько десятилетий. Программисты пользуются плодами их трудов: большинство языков программирования включают в себя вычисление хеша произвольного набора данных. В Python функция hash() для неизменяемых объектов в строена в сам язык. Mathematicians have been studying hashing for decades, developing computations to convert structured data into fixed-size integers. Programmers can take advantage of their contributions since most programming languages have built-in support for computing a hash code for arbitrary data. Python provides such a hash() method for immutable objects.

Единственное обязательное свойство хеш-функции — однозначность. Хеш, посчитанный от двух одинаковых объектов, должен совпадать; нельзя каждый раз брать первое попавшееся число. Хеш неизменямого объекта (например, string в Питоне) можно вычислять лишь единожды и потом хранить — это снизит общее количество вычислений.

Хеш-функция не обязана для каждого ключа давать уникальное число, не равное другим значениям функции (впрочем, в конце главы мы рассмотрим идеальные хеши, которые это умеют). Более того, ценой ещё большей неуникальности мы можем резко уменьшить диапазон её значений до 0 … M-1: возьмём остаток от деления на M. Hash functions do not have to compute a unique hash for each key; this is too great a computational challenge (but see the section on perfect hashing at the end of this chapter). Instead, the expression hash(key) % M uses the modulo operation to com‐ pute a value guaranteed to be an integer from 0 to M – 1.

В таблице 3-1 представлено 32-разрядное значение функции hash() для некоторых строк и соответствующий им остаток от деления на 15. Формула hash(key) % 15 обладает свойством однозначности, но если с точки зрения теории вероятности шанс на совпадение значений hash() у двух ключей исчезающе мал, то на малом диапазоне совпадение хешей вполне вероятно. В нашем примере таких совпадений два: «рифмы» — «возьми» со значением 10, и «ее» — «скорей» со значением 3. Несмотря на различие вероятностей, всегда стоит ожидать, что две разные строки могут иметь одинаковый хеш.⁵ Table 3-1 lists the 64-bit hash() value for a few string keys and the corresponding hash code modulo expressions. Mathematically, the probability that two keys have the exact same hash() value is vanishingly small.4 There are two potential hash code col‐ lisions; both smell and rose have a hash code of 6, while both name and would have a hash code of 10. You should expect that two different strings could have the exact same hash code value.

• Таблица 3-1. Пример значений функции hash() и хеш-суммы с диапазоном на 15 значений Table 3-1. Example hash() and hash code expressions for a table of size 15

Если использовать остаток от деления на M для того, чтобы вычислить хеш, hash(key) % M, стоит озаботиться тем, чтобы диапазон оказался не меньше, чем общее количество ключей. If I use hash(key) % M to compute the hash code for key, then M must be at least as large as the number of expected keys to make room to store all associated values.5

Переведённая сноска /* /* 4 Java computes 32-bit hash function values, and sometimes two string keys have the exact same hash() value; . for example, both misused and horsemints hash to 1,069,518,484.

Вот эту сноску, относящуюся к ЯП Java, предлагаю не переводить — она частично переврана, и точно только запутает читателя:↓

5 In Java, if hash(key) is negative, then the % operator will return a negative number, so the formula must be . (key.hashCode() & 0x7fffffff) % M to first convert the negative hash computation into a positive integer before computing modulo M.

-- FrBrGeorge 2022-01-21 11:14:49

Лет десять назад в Python (а в Java — до сих пор) встроенная функция hash() стабильно возвращала один и тот же конкретный хеш для каждого конкретного параметра. В современном Python в значения хешей при запуске интерпретатора подмешивается «соль» — независимое случайное значение. В течение работы одного процесса Python соль не меняется, но предсказать её значение для очередного запуска интерпретатора невозможно — это повышает безопасность приложений. Если хеш предсказуем, хакер может наполнить словарь заранее просчитанными ключами с одинаковым хешем, это нарушит равномерность их распределения в хеш-таблице, и производительность словаря упадёт до O(N). Таким способом можно организовать т. н. DoS-атаку (от «Denial of Service» — «отказ в обслуживании».

Больше информации относительно «подсоленного хеша» можно найти тут: https://oreil.ly/C4V0W и в Python-овской документации «PEP 456»; кроме того, в конце главы есть упражнение на эту тему. Currently, Java and Python 2 compute a predictable hash code for strings. In Python 3, the default hash() code values for strings are “salted” with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python as a cyberse‐ curity measure. Specifically, if a hacker can generate keys that pro‐ duce specific hash code values (thus violating the uniform distribution of keys), the performance of the hashtable defined in this chapter degrades to O(N), leading to denial-of-service attacks.6

Хеш-таблица: хранение данных по ключу

A Hashtable Structure for (Key, Value) Pairs

Для удобства работы заведём отдельный тип данных для пары (ключ, значение): The following Entry structure stores a (key, value) pair:

   1 class Entry:
   2   def __init__(self, k, v):
   3     self.key = k
   4     self.value = v

В примере 3-3 определён класс Hashtable, внутри которого в массиве table может храниться не более M объектов. Каждая из M позиций массива table — ячейка хеш-таблицы (по-английски «bucket» — «ведро» или «корзина»). Для начала сделаем так, что каждая ячейка либо пуста, либо хранит ровно одну пару (объект типа Entry). Listing 3-3 defines a Hashtable class that constructs a table array capable of storing up to M Entry objects. Each of these M index positions in the array is called a bucket. For our first attempt, either a bucket is empty or it contains a single Entry object.

   1 class Hashtable:
   2   def __init__(self, M=10):
   3     self.table = [None] * M     # 1
   4     self.M = M
   5 
   6   def get(self, k):             # 2
   7     hc = hash(k) % self.M
   8     return self.table[hc].value if self.table[hc] else None
   9 
  10   def put(self, k, v):          # 3
  11     hc = hash(k) % self.M
  12     entry = self.table[hc]
  13     if entry:
  14       if entry.key == k:
  15         entry.value = v
  16       else:                     # 4
  17         raise RuntimeError(f'Key Collision: {k} and {entry.key}')
  18     else:
  19       self.table[hc] = Entry(k, v)

• Пример 3-3. Неэффективная реализация хеш-таблицы Listing 3-3. Ineffective hashtable implementation

переведённая сноска 6 See https://oreil.ly/C4V0W to learn more and try the challenge exercise at the end of this chapter.

1. Заводим массив на M объектов. Allocate a table to hold M Entry objects.

2. Метод .get() определяет номер ячейки по ключу k, для которого вычисляется хеш, и возвращает значение, если оно есть. The get() function locates the entry associated with the hash code for k and returns its value, if present.

3. Метод .put() определяет номер ячейки по ключу k, для которого вычисляется хеш, и перезаписывает хранящееся там значение — или записывает новое, если ячейка была пуста. The put() function locates the entry associated with the hash code for k, if present, and overwrites its value; otherwise it stores a new entry.

4. Если хеш двух различных ключей приводит к одной и той же ячейке — это коллизия, происходит исключение. A collision occurs when two different keys map to the same bucket identified by its hash code value.

Вот так нашей хеш-таблицей можно пользоваться: You can use this hashtable as follows:

   1 table = Hashtable(1000)
   2 table.put('Апрель', 30)
   3 table.put('Май', 31)
   4 table.put('Сентябрь', 30)
   5 print(table.get('Август'))    # Промах: должно вывестись None
   6 print(table.get('Сентябрь'))  # Попадание: должно вывестись 30

Если всё работает как задумано, значит, в массиве на 1000 элементов нам удалось разместить три пары — объекта типа Entry. Скорость работы .put() и .get() не зависит от количества пар в таблице, так что их быстродействие можно оценить как O(1). If everything works properly, three Entry objects will be created for these three (key, value) pairs in an array that has room for 1,000 objects. The performance of put() and get() will be independent of the number of Entry objects in the array, so each action can be considered to have constant time performance, or O(1).

Если .get(key) не находит key в соответствующей хешу ячейке — это промах. Если .get(key) выбрал ячейку по хешу, и ключ находящейся там пары равен key — это попадание. В этих случаях хеш-таблица работает так, как предполагается. Чего нам пока не хватает — это поведения на случай коллизии хеша, когда два или больше ключа имеют одинаковый хеш. Если не обрабатывать коллизии, метод .put(ключ) начнёт удалять содержимое непустых ячеек, хеш ключа которых совпадает с хешем нового ключа. Смысла в Hashtable, который теряет ключи, нет. A miss occurs when get(key) fails to find an Entry in the bucket identified by the hash code for key. A hit occurs when get(key) finds an Entry whose key matches key. These are both normal behaviors. However, there is still no strategy to resolve col‐ lisions when the hash codes for two (or more) keys compute to the same bucket. If you don’t resolve collisions, then a put() could overwrite an existing Entry for a dif‐ ferent key, causing the Hashtable to lose keys—this must be prevented.

Определение коллизий и их разрешение последовательным просмотром

Detecting and Resolving Collisions with Linear Probing

Вполне может случиться, что у ключей двух пар e1 = (key1, val1) и e2 = (key2, val2) окажется одинаковый хеш, несмотря на то, что сами ключи будут разными. В таблице 3-1 и «возьми», и «скорей» имеют хеш равный 10. Допустим, e1 попал в Hashtable первым. Тогда при попытке добавить туда ещё и e2 возникнет коллизия хешей: для e2 будет вычислена та же ячейка, что и для e1, при этом ячейка будет уже занята, а её ключ, key1, не будет равен key2 из e2. Если как-то это противоречие не разрешать, в одном объекте типа Hashtable нельзя будет хранить одновременно e1 и e2. It may happen that two entries, e1 = (key1, val1) and e2 = (key2, val2), share the same hash code for their respective keys even though key1 is different from key2. In Table 3-1, both 'name' and 'would' have the same hash code of 10. Assume that e1 is put in the Hashtable first. You will encounter a hash collision later when you try to put e2 in the same Hashtable: this is because the identified bucket is nonempty with an Entry whose key, key1, is different from key2, the key for e2. If you can’t resolve these collisions, you won’t be able to store both e1 and e2 in the same Hashtable.

Справиться с этим помогает стратегия «открытой адресации»: на случай возникновении коллизии (ячейка занята, ключи не совпадают) можно предусмотреть процедуру поиска (просмотра) других незанятых ячеек в таблице. Самый простой способ — последовательный просмотр, когда .put() просто проверяет следующие за вычисленной ячейки table до тех пор, пока не найдёт свободную; если в процессе поиска массив закончится, а все ячейки заняты, .put() начнёт с его начала. Чтобы этот поиск всегда был успешным, будем проверять, что как минимум одна ячейка всё ещё свободна, а попытку записать что-то в последнюю свободную ячейку будем считать ошибкой переполнения хеш-таблицы. Open addressing resolves hash collisions by probing (or searching) through alternative locations in table when put() encounters a collision. One common approach, called linear probing, has put() incrementally check higher index positions in table for the next available empty bucket if the one designated by the hash code contains a different entry; if the end of the array is reached without finding an empty bucket, put() con‐ tinues to search through table starting from index position 0. This search is guaran‐ teed to succeed because I make sure to always keep one bucket empty; an attempt to put an entry into the last remaining empty bucket will fail with a runtime error signi‐ fying the hashtable is full.

Допустим, мы добавили пару в ячейку, индекс которой не равен хешу ключа, потому что соответствующая ячейка была занята. Чтобы убедиться в том, что так делать вообще можно, надо придумать алгоритм поиска по такому ключу. Для начала договоримся, что удалять пары из Hashtable мы не будем, будем только добавлять. понятно, что теперь чем больше пар мы добавляем в хеш-таблицу, тем длиннее становятся участки занятых ячеек в table. Тогда поиск довольно прост: по хешу ключа определяем первоначальную ячейку, а если ключи не совпадают, начинаем рассматривать все последующие непустые ячейки; если в каком-то из этих просмотров ключи совпадут, нужная ячейка найдена, а если попадётся пустая — соответствующей пары в таблице нет. Т. е. пара e1 найдется либо в ячейке с номером hash(e1.key) % M, либо в последующих непустых ячейках (с учётом перехода между концом и началом таблицы), либо не найдётся. You might wonder why this approach will even work. Since entries can be inserted into an index position different from their hash(key), how will you find them later? First, you can see that entries are never removed from Hashtable, only inserted. Sec‐ ond, as more Entry objects are inserted into buckets in the table structure, long runs of nonempty buckets appear in table. An Entry, e1, could now be in a different loca‐ tion, anywhere from hash(e1.key) or, searching to the right, until the next empty bucket is found (wrapping around as necessary).

На иллюстрации 3-2 показано, как в Hashtable размером M == 7 с помощью последовательного просмотра добавляются пять пар с коллизией ключей (показаны только ключи). Заполненные серым ячейки — пустые. Ключ 20 попадает в table[6], потому что 20 % 7 == 6, ключ 15 — в table[1], а ключ 5 — в table[5]. To demonstrate collision resolution, let’s now add five entries into a Hashtable, with M = 7 buckets in Figure 3-2 (which only shows their keys). Buckets shaded in gray are empty. Key 20 is inserted into table[6], since 20 % 7 = 6; similarly, 15 is inserted into table[1], and 5 is inserted into table[5].

Иллюстрация 3-2. Как выглядит Hashtable после добавления пяти пар (ключ, значение)

Попытка добавить пару с ключом 26 приведёт к коллизии, потому что ячейка table[5] уже занята (парой с ключом 5; на иллюстрации 3-2 просмотр занятой ячейки выделен тёмным фоном), и запускается последовательный просмотр: сначала table[6], которая тоже занята, затем придётся перевалить через конец таблицы и начать с начала, где для ключа 26 и отыщется первая свободная ячейка — table[0]. Добавление пары с ключом 19 тоже приводит к коллизии и просмотру всех непустых ячеек, вплоть до table[2], которая, наконец, оказывается свободна. Adding an entry with key 26 causes a collision since table[5] is already occupied (by an entry whose key is 5, highlighted in Figure 3-2), so linear probing next checks table[6], which is also unavailable, and so the entry is placed in the next available bucket, table[0] (because open addressing wraps around when searching for the next available empty index position). Adding an entry with key 19 similarly causes a collision with every nonempty bucket, and the entry is finally placed in table[2].

В экземпляр Hashtable с иллюстрации 3-2 можно добавить ещё только одну пару: хотя бы одна ячейка должна оставаться незанятой. Куда попадёт пара с ключом 44? Хеш ключа 44 % 7 == 2, ячейка 2 занята, а 3 свободна, так что пара попадёт в table[3]. Поскольку .get() и .put() пользуются одним и тем же алгоритмом просмотра, впоследствии эту пару можно будет найти с помощью .get(44). Using the existing Hashtable in Figure 3-2, I can put one additional entry into the table (since I need to leave one bucket empty). Where would I place an entry with a key of 44? The hash code for its key is 44 % 7 = 2, which is occupied; searching for the next available bucket places this entry in table[3]. Since get() and put() use the same search strategy, this entry will eventually be found later when invoking get(44).

Цепочкой для определённого хеша hc в таблицах с открытой адресацией, наподобие нашего Hashtable, называется последовательность ячеек в table. Эта последовательность начинается с table[hc] и продолжается вправо (с переходом из конца в начало table) вплоть до первой неиспользуемой ячейки, не включая неё. На иллюстрации 3-2 цепочка для хеша 5 состоит из пяти элементов, хотя только в трёх из них хеш ключа равен пяти. А для хеша 2 ключей вообще нет, но цепочка уже равна 1 из-за предыдущих коллизий. Длина цепочки не может превышать M-1, потому что по правилам одна ячейка должна быть незанятой.

В примере 3-4 показано, как добавить открытую адресацию в Hashtable: класс Entry не меняется, а количество сохранённых пар запоминается в счётчике N для проверки того, что всегда есть хотя бы одна свободная ячейка (при этом запоминать, где она расположена, не надо!). Правило «одной свободной ячейки» очень важно, иначе цикл поиска while в .get() и .put() может оказаться вечным. Listing 3-4 shows the modifications to Hashtable to support open addressing; the Entry class is unchanged. Hashtable keeps a running count, N, of the number of entries it stores so it can ensure there is at least one unused bucket (though it does not need to keep track of where that empty bucket is!). This is critically important to ensure the while loop in the get() and put() functions will eventually terminate.

   1 class Hashtable:
   2   def __init__(self, M=10):
   3     self.table = [None] * M
   4     self.M, self.N = M, 0
   5 
   6   def get(self, k):
   7     hc = hash(k) % self.M           # 1
   8     while self.table[hc]:
   9       if self.table[hc].key == k:   # 2
  10         return self.table[hc].value
  11       hc = (hc + 1) % self.M        # 3
  12     return None
  13 
  14   def put(self, k, v):
  15     hc = hash(k) % self.M           # 1
  16     while self.table[hc]:
  17       if self.table[hc].key == k:   # 5
  18         self.table[hc].value = v
  19         return
  20       hc = (hc + 1) % self.M        # 3
  21 
  22     if self.N >= self.M - 1:        # 6
  23        raise RuntimeError ('Table is Full.')
  24 
  25     self.table[hc] = Entry(k, v)    # 7
  26     self.N +=  1

• Пример 3-4. Реализация открытой адресации в Hashtable Listing 3-4. Open addressing implementation of Hashtable

• Начнём с первой же ячейки, в которой может быть ключ k. Start at the first bucket where an entry whose key is k could be.

• Если ключ найден, вернём соответствующее k значение. If found, return the value associated with k.

• В противном случае просмотрим следующую ячейку, при необходимости продолжая просмотр с начала таблицы. Otherwise advance to the next bucket, wrapping around to 0 as needed.

• Если table[hc] не занята, очевидно, k в table нет. If table[hc] is empty, you know k is not in table.

• Если ключ найден, обновим value соответствующей k ячейки. If found, update the value associated with the Entry for k.

• Если k нет в table, а свободная ячейка осталась одна, инициируем исключение RuntimeError. Once you’ve established that k is not in table, throw RuntimeError if hc is the last empty bucket.

• Запишем пару в свободную ячейку table[hc] и увеличим счётчик ключей N. Create new Entry in table[hc] and update N, the count of keys.

Так что, мы изобрели эффективный способ хранения? Теперь быстродействие .put() и .get() не зависит от M, размера таблицы ключей? Не тут-то было! Given this new mechanism, what is the performance of get() and put()? Is the time to perform these operations independent of N, the number of keys in the Hashtable? No!

это большая врезка отдельной страницей -- FrBrGeorge 2022-01-27 17:31:20

Связный список или динамический массив?

. The Liberating Linked List

В языках программирования с непосредственным выделением памяти часто используется динамическая структура данных под названием связный список. Для массива выделяется сразу один непрерывный блок памяти фиксированного размера, а для связного списка каждый элемент, называемый узлом, располагается в памяти отдельно, так что заведомо известен только начальный узел связного списка, в котором вместе со значением хранится ссылка (в языках такого типа она обычно называется указателем) на следующий узел, и так далее. Для поиска значения по связному списку необходимо проходить по ссылкам в узлах. The most commonly used dynamic data structure is a linked list. Instead of allocating a contiguous block of memory, as needed for an array, a linked list stores data in memory fragments called nodes that are linked together so the programmer can start at a designated first node, and follow links (also called references) to the next node in the list when searching for a desired target.

Вот этот список содержит три узла, в каждом из которых хранится своё значение. Стрелки на картинке — это ссылки на следующий узел списка (обычно для этого используется специальный тип данных, указатель, традиционное имя для такого указателя — next). Последний узел вместо ссылки содержит специальное «пустое» значение в знак того, что ссылаться больше не на что, отдельная переменная-указатель first хранит ссылку на начальный элемент списка. The following linked list consists of three nodes, each of which stores a different value. Each node has a next reference (i.e., an arrow) to the next node in the list. The next reference in the final node in a list is None.

Размер связного списка определяется количеством узлов при его просмотре от начала до конца, начиная с указателя first по всем next до тех пор, пока они не пусты. Сами узлы могут появляться в любом месте памяти и в любое время. В объектно-ориентированных языках программирования удобно моделировать тип узла классом. В языках программирования с непосредственным выделением памяти необходимо освобождать память, выделенную под узел, если он больше нигде не используется. В других, например, в Python и Java, выделением и освобождением памяти занимается сама исполняющая система языка. The size of a linked list is the number of nodes you encounter starting at first and tra‐ versing to each subsequent node using next until None is reached. The nodes are dynamically allocated memory. For object-oriented languages, nodes are objects. Both Java and Python rely on automatic memory to reclaim this memory when nodes are removed from a linked list, though other programming languages may require the programmer to manually release the memory when nodes are removed from a linked list.

Вставка в начало

Чтобы вставить узел в начало списка, надо сначала этот узел, Node0, создать, положить в него нужное значение, и сделать так, чтобы next, указатель на следующий элемент, ссылался на Node1. Кроме того, в переменной first надо переделать указатель на Node1 в указатель на Node0 (а так же во всех других местах, ссылающихся на наш список). Prepending a value You can prepend a value to the head of this list in constant time by creating a new node, Node0, to store this value and set Node0’s next reference to Node1; then set first to point to Node0.

Добавление в конец

Можно также хранить last, указатель на последний элемент связного списка. В этом случае для добавления значения в конец списка необходимо создать узел, Node4 с пустым полем next, сохранить в узел требуемое значение, сходить по ссылке из last (в нашем случае это будет узел Node3), заменить там поле next указателем на Node4, и сам last тоже переделать в указатель на Node4. Appending a value . If you maintain a reference to the last node in the list, you can append a value to the end of this list in constant time by creating a new node, Node4, to store this value; then set the next reference of last to point to Node4, and set last to Node4.

Вставка в произвольное место

Если заранее известно, что новый узел q необходимо вставить после конкретного узла p, надо создать этот новый узел q с нузным значением и полем next, которое совпадает с полем next узла p. После чего поле next узла p сделать указателем на новый узел q. Inserting a value . You can insert a value after an existing node, p, by creating a new node, q, to store this value and setting q.next to p.next, and then p.next = q.

Удаление произвольного элемента

Чтобы удалить некоторое значение из списка, необходимо найти узел, поле next которого указывает на узел, содержащий искомое значение. Тогда значение next искомого узла записывается в next узла-предшественника (где раньше была ссылка на искомый узел). Отдельно обрабатываются случаи, когда искомым оказывается первый мили последний узел; кроме того, надо соблюдать принятые в языке программирования договорённости по освобождению памяти. Deleting a value . You can delete a value from a linked list by locating its node in the linked list and adjusting next references accordingly, paying special attention if this value is the first one in the list.

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

Связные списки в Python не используются никогда — или почти никогда: вместо них следует применять динамические массивы. Гвидо ван Россум, автор языка Python, даже назвал такой тип данных list, прозрачно намекая на область его применения.

Вот таблица сравнения быстродействия различных операций над связными списками и динамическими массивами:

Как видно из таблицы, list в Python работает не хуже или даже лучше, чем связный список, за исключением случая, когда приходится модифицировать размер списка не в его конце. В самом деле, для вставки нового элемента в связный список, допустим, между вторым и третьим элементами достаточно указатель на третий записать в поле next нового элемента, а в поле next второго записать указатель на этот новый. А вот для вставки третьего элемента в динамический массив нужно добавить пустой элемент в его конец (это операция быстрая), а затем переставить все элементы, начиная с последнего, на одну позицию вперёд — N-1-й записать в позицию N, N-2-й — в позицию N-1 и так дальше до 3-го, который записывается в позицию 4, освобождая тем самым место для нового элемента в позиции 3. Эта операция, очевидно, достаточно неэффективна — порядка N.

Поначалу кажется, что такое различие быстродействия при работе с почти любым элементом списка сводит все преимущества list на нет. Однако в действительности важными являются только операции работы с началом списка. Например, эффективно реализовать абстракцию «очередь» (FIFO — «первым вошёл, первым вышел») с помощью list нельзя. Для этого в Python есть отдельный тип данных — collections.deque — в котором операции с обоих концов списка одинаково быстры (за счёт некоторых накладных расходов).

А вот эффективная работа (удаление или добавление) с элементом в произвольной позиции не даёт практически никаких преимуществ связному списку перед list. Для того, чтобы понять, что вставка или удаление должны происходить в позиции k, эту k надо сначала определить. А все операции поиска в связном списке — как по значению, так и по индексу — линейны. Таким образом, например, в операции «поиск + вставка» линейный поиск доминирует над константной вставкой, и порядок её сложности оказывается одинаков и для связных списков, и для динамических массивов (в которых, как мы видим, с поиском ещё и получше).

Не меньшую роль в выборе динамических массивов в качестве базового типа данных в Python сыграла необходимость управлять памятью, под них выделяемой. Выделение и освобождение памяти — функция ядра операционной системы, она может работать быстро, а может и долго. В языках с явным выделением памяти, таких, как Си и отчасти C++, программист сам принимает решение, как часто он может обращаться в алгоритме к системным вызовам. В языках с автоматическим учётом памяти, таких как Java и Python, этим занимается интерпретатор (или исполняющая система) — и возникает возможность реализовать работу с памятью поэффективнее. В Python для изменения размера списка используется стратегия «масштабирования», которую мы опишем ниже.

Посмотрим, что происходит в худшем случае. Поначалу Hashtable на N элементов пуст⁶, и пара добавляется в пустую ячейку — для определённости пусть в table[0]. Если теперь каждый из оставшихся N-1 запросов на добавление будет приводить к коллизии ключа, сколько всего ячеек придётся за это время просмотреть? Для первого запроса — одну, для для второго — две (из-за коллизий в первой), для третьего — три, и т. д. Очевидно, во время k-го запроса придётся просмотреть k ячеек. Значит, всего просмотров будет 1 + 2 + … + (N - 1), то есть N · (N - 1)/2. Если поделить на количество запросов, N, получится в среднем (N - 1)/2 действий на один .put(). Consider what happens in a worst case scenario. To an empty Hashtable, add an entry, and assume it is placed in table[0]. What if each of the next N – 1 requests to add an entry collides with this existing key in the table storage? What is the total number of buckets searched? For the first request, it is 1; for the second request, 2, and for the third request, 3. As you can see, there will be k buckets inspected for request number k. The total number, then, is the sum of 1 + 2 + … + (N – 1), which conveniently equals N × (N – 1)/2. The average computation is this quantity divided by N, which leaves (N – 1)/2.

Согласно классификации из второй главы, сложность (N - 1)/2 — это O(N). В самом деле, если раскрыть скобки, получится N/2 - ½. Порядок сложности определяется доминирующей составляющей — N/2. Выходит, что в худшем случае количество просмотренных ячеек прямо пропорционально N (в нашем алгоритме равно половине N).

Итак, мы рассмотрели наихудший случай, в котором среднее количество просмотров ячеек оценивается как O(N). В алгоритме мы оценивали количество просмотров ячеек, а не время работы или количество инструкций, потому что от количества просмотров производительность get() и put() зависит напрямую. I have just demonstrated that in the worst case, the average number of buckets inspected is O(N). I use algorithmic analysis here to estimate the count of buckets (not performance time or number of operations) since the runtime performance for get() and put() is directly related to the number of buckets inspected.

Похоже, мы зашли в тупик. Можно увеличить M, размер table, так, чтобы он значительно превосходил возможное количество хранимых ключей, N — тогда для случайных ключей количество коллизий (а следовательно, и время поиска) в таблице уменьшится⁷. Однако стоит ошибиться с прогнозами относительно N, то по мере приближения его к M производительность будет становиться всё ужаснее; хуже того, на N = M - 1 переполнится table, и значения вообще нельзя будет добавлять. В таблице 3-2 представлено время вставки N пар в структуру типа «Hashtable с открытой адресацией» размера M. Обратим внимание вот на что: This is a stalemate. You can increase the allocated table size, M, to be much greater than the number of keys to be inserted, N, and reduce the number of collisions and the overall time to execute. But if you don’t plan correctly—that is, if N becomes closer and closer to M—you could quickly have horrible performance: even worse, the table can still fill up, preventing more than M – 1 entries from being stored. Table 3-2 compares the performance of inserting N entries into a Hashtable of size M that uses open addressing to resolve conflicts. Observe the following:

• Для небольшого N, скажем, для 32, среднее время работы (соответствующая строка таблицы) везде примерно одинаково, независимо от M, размера Hashtable, потому что M либо само по себе мало, либо значительно превосходит N. • For a small value of N, say 32, the average cost is nearly the same (read the values . from left to right in that row) regardless of the size, M, of the Hashtable, because M is so much larger than N.

• В любой Hashtable размера M среднее время вставки N ключей постоянно растёт с ростом N — это видно в соответствующем столбце таблицы. • For any Hashtable of size M, the average time to insert N keys consistently . increases as N increases (read the numbers from top to bottom in any column).

• Любая диагональ «с северо-запада на юго-восток» в таблице содержит примерно одинаковое время работы. С учётом того, как меняются M и N в столбцах и строках таблицы, можно сказать, что для того, чтобы в Hashtable можно было вместо N ключей добавлять с той же средней скоростью 2·N ключей, нужно увеличить её размер вдвое. • If you look “diagonally southeast” in the table, you will see that the timing results . are more or less the same. In other words, if you want the average performance of inserting 2 × N keys to be the same as inserting N keys, then you need to dou‐ ble the initial size of the Hashtable.

• Таблица 3-2. Среднее время добавления N ключей в таблицу Hashtable размера M (в миллисекундах) Table 3-2. Average performance to insert N keys into a Hashtable of size M (in milliseconds)

Наша реализация типа данных «хеш-таблица» отлично работает — но только в случае, когда размер хранилища существенно больше предполагаемого количества ключей, которые мы ходим туда поместить. Если ошибиться с оценкой этого количества, быстродействие операция начинает стремительно падать, может и в сто раз уменьшиться. Что ещё неприятнее, мы не предусмотрели удаление ключа из таблицы — такой структурой данных далеко не всегда удобно пользоваться. Самый простой способ побороть эти трудности — хранить цепочки в отдельных списках. This working implementation of the symbol table data type only becomes efficient when the available storage is noticeably larger than the number of keys to be inserted. If you misjudge the total number of keys in the symbol table, then performance will be surprisingly inefficient, sometimes 100 times slower. Worse, it is not really useful since I have not yet added the capability to remove a key from the symbol table. To overcome these limitations, I need to introduce the linked list data structure.

Раздельное хранение цепочек в списках

Separate Chaining with Linked Lists Давайте перепишем Hashtable так, чтобы в таблице хранились не сами пары, а цепочки пар с совпадающими ключами. Такой способ называется хешированием с раздельными цепочками. В случае последовательного просмотра для размещения пары нам приходилось искать очередную свободную ячейку, теперь же в ячейке table[idx] будет храниться не пара, а весь список пар, хеши ключей которых совпадают с idx; если таких ключей нет, ячейка пуста: содержит пустой список. Количество ячеек для удобства оставим M. I now modify Hashtable to store an array of linked lists in a technique known as separate chaining. Where linear probing looked for an empty bucket in which to place an entry, separate chaining stores an array of linked lists where each linked list con‐ tains entries whose keys compute to the same hash code. These linked lists are formed from LinkedEntry nodes, shown in Listing 3-5.

это пример для linked list, не используется/* /* Listing 3-5. LinkedEntry node structure to support linked list of (key, value) pairs class LinkedEntry: . def init(self, k, v, rest=None): . self.key = k self.value = v self.next = rest . rest is an optional argument, which allows the newly created node to link directly to an existing list pointed to by rest.

More accurately, table[idx] refers to the first LinkedEntry node in a linked list of nodes whose keys share the same hash code value of idx. For convenience, I still refer to the M buckets, which can be empty (in which case table[idx] = None) or contain the first LinkedEntry node in a linked list.

Понятие цепочки при раздельном хранении намного очевиднее цепочки в открытой адресации: теперь длина списка в ячейке и есть длина цепочки.

Как и прежде, хеш-функцией, определяющей номер ячейки для данного ключа, у нас будет формула hash(key) % M. На иллюстрации 3-3 представлена хеш-таблица с семью ячейками; как и прежде, показаны только ключи. I continue to use hash(key) % M to compute the hash code for an entry to be inser‐ ted. All entries with the same hash code exist within the same linked list. In Figure 3-3, the table array has seven buckets, and therefore seven potential linked lists; once again, only the keys are shown.

Как выглядят цепочки Hashtable после вставки пяти пар (ключ, значение)

Figure 3-3 adds the (key, value) pairs in the same order as Figure 3-2: the first three entries with keys 20, 15, and 5 create three linked lists, one for each of the buckets associated with the hash code for these keys. Buckets shaded in gray are empty. Adding an entry whose key is 26 causes a collision in table[5], so a new entry is prepended to the beginning of this linked list, resulting in a linked list with two entries. When adding the final entry whose key is 19, it is also prepended to the linked list in table[5], resulting in a linked list with three entries. На иллюстрации 3-3 пары (ключ, значение) добавляются в том же порядке, что и на иллюстрации 3-2. Поначалу все ячейки пустые, это обозначено серым фоном. Первые три пары с ключами 20, 15 и 5 попадают в начало цепочек в соответствующих ячейках хеш-таблицы. Когда добавляется пара с ключом 26, возникает коллизия, и эта пара добавляется в конец цепочки ячейки table[5], и то же самое происходит для ключа 19, так что в результате цепочка, соответствующая хешу 5, содержит три пары.

Pay attention to how the newest entry added to a bucket becomes the first entry in that bucket’s linked list. Once put() determines that the entry’s key does not appear in the linked list, it is efficient to just prepend a new LinkedEntry node at the begin‐ ning of the linked list. When the next reference is None, that entry is the last one in the linked list. Listing 3-6 shows the modifications to Hashtable.

   1 class Hashtable:
   2     def __init__(self, M=10):
   3         self.table = [[] for i in range(M)]  # 1
   4         self.M = M
   5         self.N = 0
   6 
   7     def get(self, k):
   8         hc = hash(k) % self.M                # 2
   9         for entry in self.table[hc]:         # 3
  10             if entry.key == k:
  11                 return entry.value
  12         return None
  13 
  14     def put(self, k, v):
  15         hc = hash(k) % self.M                # 2
  16         for entry in self.table[hc]:         # 3
  17             if entry.key == k:               # 4
  18                 entry.value = v
  19                 return
  20         self.table[hc].append(Entry(k, v))   # 5
  21         self.N += 1

• Пример 3-6. Вариант хеш таблицы с раздельным хранением цепочек Listing 3-6. Separate chaining implementation of Hashtable

1. Написать self.table = [] * M значило бы создать список, все элементы которого являются одним и тем же объектом; нам же надо, чтобы это было M разных объектов (пускай они поначалу все равны []).

2. Вычисляем номер ячейки hc (остаток от деления хешированного ключа k на размер таблицы).

3. Ищем совпадение k с ключом одной из пар (быстродействие этой части пропорционально длине цепочки)

4. Если пара с данным ключом k найдена, изменим хранимое значение

5. Добавим пару с новым ключом k в конец цепочки

Методы .get() и .put() очень похожи: мы проходим по всем парам в цепочке table[hc] и сравниваем нулевой элемент пары (ключ) с k; если ключ найден — get() вернёт значение, а put() поменяет старое значение на новое, если не найден — get() вернёт None, а put() добавит пару (k, v) в конец цепочки.

"Добавить элемент в конец динамического массива типа list можно за одну операцию, так что это самый эффективный способ. Общая вычислительная сложность добавления пары в хеш-таблицу всё равно зависит от длины соответствующей цепочки: чем добавлять пару, надо убедиться, что её в этой цепочке нет."

. put(k, v) only adds a new entry to a linked list after checking that none of the existing entries in the linked list have k as its key.

Аналогично функции добавления, функция удаления пары по ключу, remove(), будет искать ключ пару с ключом k в соответствующей хешу цепочки таблицы, и удалять, если такая пара нашлась. По договорённости метод .remove() возвращает поле значение удалённой пары или None, если ключ не нашёлся.

   1 def remove(self, k):
   2     hc = hash(k) % self.M
   3     for i, entry in enumerate(self.table[hc]):  # 1
   4         if entry.key == k:
   5             del self.table[hc][i]               # 2
   6             self.N -= 1
   7             return entry.value                  # 3
   8     return None                                 # 4

1. Функция enumerate(список) возвращает последовательность пар индекс элемента, элемент; индекс нам может потребоваться для удаления

2. Динамический массив позволяет удалять любой элемент по его индексу
3. Если ключ найден, возвращаем значение из удалённой пары

4. Если удаления не было, возвращаем None

Стоит заметить, что операции над динамическим массивом (тип list), которые работают не с концом этого массива, обычно имеют линейную сложность в среднем пропорциональную длине самого массива. Это относится как к операциям поиска вида элемент in список, так и к операциям удаления вида del список[i]. Поскольку массив — это непрерывный блок элементов в памяти, для удаления из него i-го элемента на место i-го надо переписать i+1-й, на место i+1-го — i+2-й, и так далее до последнего элемента, который должен встать на место предпоследнего. Эта часть алгоритма очевидно зависит от длины списка и в среднем переставляет половину его элементов.

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

Насколько эффективны хеш-таблицы с раздельным хранением цепочек? Чтобы ответить на этот вопрос, надо посчитать и количество обращений к ячейкам таблицы, и количество просмотров пар в цепочке. Забегая вперёд скажем, что быстродействие таблиц с раздельными цепочками практически такое же, что и быстродействие таблиц с открытой адресацией; единственное важное достижение — количество пар в раздельных цепочках может быть актуально бесконечным. Тем не менее, как мы скоро увидим, когда количество хранимых пар N заметно превышает количество ячеек M, производительность значительно падает. Требования к памяти у обоих методов примерно одинаковые, однако в случае с раздельными цепочками структура данных посложнее, и и нужно дополнительно заводить M пустых списков. To evaluate the performance of this linked list structure, I need to count both the number of times a bucket is accessed as well as the number of times an entry node is inspected. It turns out that the performance of this linked list implementation is nearly identical to the open addressing implementation: the primary improvement is that there is no limit to the number of entries you can store in a linked list implemen‐ tation. However, as I will discuss later in this chapter, if the number of entries, N, far exceeds the number of buckets, M, then the performance will degrade significantly. You also must consider that the memory requirement for storing the next references in the linked lists is twice as much as for open addressing.

Это глава про удаление элемента из списка

Оценка

Evaluation

Итак, у нас есть две различных структуры, которые реализуют абстракцию «хеш-таблица» и позволяют хранить пары (ключ, значение). В варианте с раздельными цепочками мы предусмотрели операцию удаления пары. Удаление также можно было бы реализовать и в варианте с открытой адресацией: найти пару, записать на её место последнюю пару в цепочке, очистить ячейку, в которой раньше лежала последняя пара. Однако такая операция нарушает порядок добавления ключей в цепочку — свойство, которое может понадобится при использовании хеш-таблицы. В любом случае эффективность обеих структур ещё предстоит оценить. I now have two different structures that provide a symbol table data type to store (key, value) pairs. The linked list implementation has the added benefit of allowing (key, value) pairs to be removed, so you must choose that structure if you need this functionality. If you only add entries to a symbol table, however, you still need to evaluate the efficiency of these two approaches.

Сначала оценим сложность по памяти: сколько её требуется для хранения N пар (ключ, значение)? Обе структуры изначально содержат массив из M элементов (при открытой адресации это пустые ячейки, при раздельном хранении цепочек — пустые списки ячеек). Для хеш-таблицы с раздельными цепочками N может быть сколь угодно большим, для хеш-таблицы с открытой адресацией N должно быть строго меньше M — значит, это M нужно выбирать исходя из знания о максимально возможном количестве пар. В обеих структурах размер базового массива table прямо пропорционален M. Let’s first evaluate the storage requirements to store N (key, value) pairs. Both approaches create an array of size M to hold entries. However, in the linked list approach, N can grow to be as large as necessary; for open addressing, N must be strictly smaller than M, so you must be sure to choose a large enough M in advance. The size of the memory requirements for table is directly proportional to M.

Когда мы добавим хеш-таблицу все N пар, общий объём памяти при хранении с открытой адресацией не изменится, потому что базовый массив уже хранит ячейки типа Entry. При раздельном хранении цепочек каждая цепочка — это список из ячеек типа Entry, поэтому с каждой добавленной парой объём увеличивается на размер одной ячейки, и под конец размер это дополнительного пространства будет прямо пропорционален N. Ultimately, there will be N entries inserted into the symbol table. Each Entry in open addressing stores only the (key, value) pair, while the LinkedEntry for the linked list approach stores an additional next reference for each entry. Since each reference is a fixed memory size, the extra storage is directly proportional to N.

• Для открытой адресации требуется объём памяти, пропорциональный сразу и M, и N, но поскольку N < M, можно просто заметить, что сложность по памяти в данном случае — O(M). Open addressing requires storage proportional to both M and N, but since N < M, I can simply say that the storage is O(M).

• Раздельное хранение цепочек для базового массива требует память с объёмом, пропорциональным M, а для всех цепочек — память с объёмом, пропорциональным N; так что сложность по памяти стоит оценить как O(M + N). Separate chaining requires storage proportional to both M and N, but since there are no restrictions on N, the storage is O(M + N).

Теперь возьмёмся за сложность по времени. Основное действие — это обращение к ячейке таблицы, а мы будем подсчитывать количество таких обращений. Наихудший случай наступает, когда все вычисленные хеши ключей оказываются равны. В обеих структурах при этом M - 1 цепочка пуста, а оставшаяся единственная цепочка, которая соответствует этому одному на всех хешу, содержит все N пар. Для наихудшего случая предположим, что искомый элемент всегда оказывается в конце этой цепочки, так что и поиск по списку при раздельном хранении и поиск по самой таблице при открытой адресации прямо пропорционален N. Можно смело сказать, что независимо от реализации сложность худшего случая для операции get() — это O(N). To evaluate runtime performance, the key operation to count is the number of times an entry is inspected. Let’s start with the worst case, which occurs when the computed hash code for all keys is the same. In the linked list implementation, the table array contains M – 1 unused index positions, and a single linked list contains all N (key, value) pairs. The key to be searched might be the final entry in the linked list, so the get() performance in the worst case would be directly proportional to N. The situa‐ tion in open addressing is similar: there would be N consecutive entries within the M-sized array, and the one you are looking for is the last one. I can safely say that _regardless of implementation choice_, in the worst case, get() is O(N).

Казалось бы, к чему тогда все наши усилия? Если хеш-функция исследована математически, она даёт очень хороший разброс хешей на ожидаемом множестве ключей. В действительности с увеличением M вероятность коллизии уменьшается, а значит, уменьшаются и длины цепочек в наших структурах. В таблице 3-3 приведено сравнение обоих подходов: будем помещать 321129 английских слов в хеш-таблицы размера M от N/2 до 2×N. Вдобавок в первой строке приведём данные по хеш-таблицам размера M = 20 × N, а в пяти последних — малых (непригодных для открытой адресации) размеров. This might seem like a deal-breaker, but it turns out that the mathematical hash func‐ tions do a really good job of distributing the hash code values for keys; as M increa‐ ses, the probability of collisions decreases. Table 3-3 describes a head-to-head comparison of these two approaches by inserting N = 321,129 words from an English dictionary into a hashtable whose size, M, varies from N/2 to 2 × N. It also includes results for M = 20 × N (first row) and smaller values of M (the last five rows).

Таблица 3-3 показывает результаты двух измерений для каждого M, N: Table 3-3 shows two pieces of information for each (M, N) pair:

• Средний размер непустой цепочки в хеш-таблице. Этот параметр годится и для открытой адресации и для раздельнохо хранения. The average length of each nonempty chain in the Hashtable. This concept is applicable whether open addressing or linked lists are used.

• Максимальный размер цепочки в хеш-таблице. Этот параметр тоже годится для обоих структур и подсказывает ухудшение их быстродействия. Когда таблица с открытой адресацией близится к переполнению или хранимая цепочка становится чересчур длинной, быстродействие падает. The size of the maximum chain in the Hashtable. If the open addressing Hashtable becomes too congested—or linked lists become excessively long for certain hash codes—the runtime performance suffers.

• Таблица 3-3. Усреднённые показатели при добавлении 321129 ключей в хеш-таблицу размера M, по мере уменьшения M Table 3-3. Average performance when inserting N = 321,129 keys into a Hashtable of size M as M decreases in size

Все приведённые значения растут с уменьшением M⁸. Причина в том, что чем меньше хеш-таблица, тем больше случается коллизий при добавлении, и цепочки ключей становятся длиннее. Хорошо видно, что в варианте с открытой адресацией этот рост существенно выше, особенно под конец, когда в одну многотысячную цепочку начинают сливаться последовательности ключей с разными хешами. Что ещё хуже, стоит M оказаться меньше, чем N, и открытая адресация вообще становится неприменима (в таблице отмечено «звёздочками»). А вот хранение цепочек в списках себя оправдало: в разумных пределах оно нечувтствительно к этой проблеме. Когда размер таблицы M достаточно велик — скажем, в два раза больше количества хранимых элементов N — средний размер цепочки вообще близок к 1, да и длина наибольшей цепочки сравнительно невелика. Тем не менее M нужно выбирать заранее, и в случае открытой адресации у нас закончится место, как только N станет равно M - 1. The values in the table all increase as the size of M decreases; this occurs because smaller Hashtable sizes lead to more collisions, producing longer chains. As you can see, however, open addressing degrades much more quickly, especially when you con‐ sider that there are some hash codes whose chain extends to hundreds of entries to be inspected. Worse, once M is smaller than N, it becomes impossible to use open addressing (shown in the table as Fail). In contrast, the statistics for the linked list implementation appear to be almost immune from this situation. If the size, M, of a hashtable is much larger than N—for example, twice as large—then the average chain length is very close to 1, and even the maximum chain length is quite small. However, M has to be decided in advance, and if you use open addressing, you will run out of room once N = M – 1.

С раздельным хранением не всё так страшно. Таблица 3-3 показывает, что даже когда N превышает размер таблицы M более, чем десятикратно, списки растут себе и растут, и даже производительность не падает так ужасающе, как при открытой адресации c N всего лишь примерно равным M. Это можно понять по размеру максимальной цепочки в списке, который приведён в той же таблице. Things are much more promising with separate chaining. As you can see in Table 3-3, even when N is more than ten times the size of the hashtable, M, linked lists can grow to accommodate all of the entries, and the performance doesn’t suffer nearly as much as open addressing does when N became closer and closer to M. This is evident from the maximum chain length of the linked lists shown in Table 3-3.

Изучив эти показатели, мы можем изобрести для хеш-таблицы размера M простую методику оценки эффективности. Производительность хеш-таблицы зависит от того, насколько она «заполнена», от есть от отношения N к M. В экономической науке есть похожее понятие — альфа-индекс⁹, но мы будем пользоваться более очевидным термином — загруженность хеш-таблицы. These numbers provide the information to develop a strategy to ensure the efficiency of a hashtable whose initial size is M. The performance of a hashtable can be meas‐ ured by how “full” it is—which can be determined by dividing N by M. Mathemati‐ cians have even defined the term alpha to represent the ratio N/M; computer scientists refer to alpha as the load factor of a hashtable.

• При раздельном хранении цепочек показатель загруженности — это средняя длина цепочки (в отличие от данных в таблице 3-3, где приведена средняя длина только среди непустых цепочек). Этот показатель может превышать 1 и зависит только от объёма доступной памяти. . • For separate chaining, alpha represents the average number of keys in each linked . list and can be larger than 1, limited only by the available memory.

• При открытой адресации показатель загруженности — это доля занятых ячеек таблицы. Наибольшее его значение — (M - 1)/M, так что он не может превышать 1. • For open addressing, alpha is the percentage of buckets that are occupied; its highest value is (M – 1)/M, so it must be smaller than 1.

Многолетние исследования показали, что хеш-таблицы начинают стремительно терять производительность при показателе загруженности больше 0.75 — например, когда таблица с открытой адресацией заполнена на 3/4¹⁰. При раздельном хранении цепочек хеш-таблица не бывает «совсем заполнена», но принцип остаётся тот же¹¹ Years of research have identified that hashtables become increasingly inefficient once the load factor is higher than 0.75—in other words, once an open addressing hashta‐ ble is ¾ full.7 For separate chaining hashtables, the concept still applies, even though they do not “fill up” in the same way.

переведённая сноска 7 The Python dict type uses ⅔ as the threshold.

На иллюстрации 3-3 приведены средние и наибольшие длины цепочек после добавления N = 321129 слов в хеш-таблицу размера M. М меняется по оси ординат, длины отложены по оси абсцисс. Средние длины помечены ромбами, их шкала расположена слева от диаграммы, наибольшие — квадратами, их шкала — справа. Задавшись целью обеспечить определённый средний или наибольший размер цепочки для заранее известного количества ключей N, можно, по аналогии с диаграммой на иллюстрации, подобрать подходящее M. Figure 3-6 plots the average chain size (shown in diamonds using the left Y-axis) and maximum chain size (shown in squares using the right Y-axis) after inserting N = 321,129 words into a Hashtable of size M (found on the X-axis). This graph effec‐ tively shows how you can compute a suitable M value to ensure a desired average (or maximum) chain size if you know the number of keys, N, to be inserted.

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

Если бы мы могли расширять хеш-таблицу, то есть увеличивать M по необходимости, можно было бы удерживать оптимальный показатель загруженности! Как мы сейчас увидим, при известном старании такую таблицу сделать вполне реально. If the hashtable could only grow larger—that is, increase its M value—then the load factor would reduce and the hashtable would be efficient again. I next show how to accomplish this, with a little bit of effort.

Расширяемые хеш-таблицы

Growing Hashtables

В класс DynamicHashtable из примера 3-7 заведено поле load_factor, равное 0.75. Это показатель загруженности, на основании которого вычисляется пороговая загруженность threshold. The DynamicHashtable in Listing 3-8 uses a load_factor of 0.75 to set a threshold target.

   1 class DynamicHashtable:
   2     def __init__(self, M=10):
   3         self.table = [[] for i in range(M)]
   4         if M < 1:
   5             raise ValueError('Hashtable storage must be at least 1.')
   6         self.M = M
   7         self.N = 0
   8 
   9         self.load_factor = 0.75
  10         self.threshold = min(M * self.load_factor, M-1)         # 1

• Пример 3-7. Определение показателя и порога загруженности при создании динамической хеш-таблицы Listing 3-8. Determine load_factor and threshold when creating DynamicHashtable

1. Для M ⩽ 3 порог не должен превышать M - 1.

Что делать, когда хеш-таблица будет заполнена свыше порогового значения? Распространённый подход геометрического масштабирования советует сразу увеличивать таблицу вдвое. Точнее, увеличивать вдвое и ещё прибавлять к размеру единицу¹². Как только количество занятых ячеек таблицы table превысит порог (threshold), для эффективной работы понадобится таблицу увеличить. В примере 3-8 приведён доработанный метод put() для раздельно хранимых цепочек. What if I simply doubled the size of the storage array, using a resize strategy known as geometric resizing? More precisely, double the array size and add 1 when resizing.8 Once the number of (key, value) pairs is larger than or equal to threshold, the table storage array needs to grow in size to remain efficient. The revised put() method for separate chaining is shown in Listing 3-9.

   1     def put(self, k, v):
   2         hc = hash(k) % self.M
   3         for entry in self.table[hc]:
   4             if entry.key == k:
   5                 entry.value = v
   6                 return
   7         self.table[hc].append(Entry(k, v))      # 1
   8         self.N += 1
   9 
  10         if self.N >= self.threshold:            # 2
  11             self.resize(2*self.M + 1)           # 3

• Пример 3-8. Доработанный метод put(), который вызывает resize() Listing 3-9. Revised put() method initiates resize()

• Добавим новую ячейку в коней цепочки table[hc]. . Prepend new entry to the table[hc] linked list chain.

• Проверим, не превысило ли N порог. Check whether N meets or exceeds threshold for resizing.

• Увеличим размер массива ячеек вдвое (плюс ещё одна ячейка). Resize storage array into new array that is twice original size plus one.

Процедура удвоения создаёт новый массив (при открытой адресации — ячеек, при раздельном хранении — цепочек) и заново добавляет в эту новую таблицу все пары (key, value). Поскольку загруженность таблицы стала равна пороговой, но не превысила её, мы ожидаем в среднем константное время добавления одной ячейки, и следовательно, в среднем линейную сложность функции resize() по отношению к количеству ячеек, то есть, предположительно O(M). To increase storage in most programming languages, you need to allocate a new array and copy over all of the original entries from the first array into the second array, as shown in Figure 3-7. This figure shows the result after resizing the array storage for the array of linked lists as well as open addressing. Прежде, чем продвинуться дальше, попытаемся (некорректно!) упростить процедуру удвоения. Во многих языках программирования есть операции копирования части или целого массива в другой массив. Эта операция уж точно имеет сложность O(M), ибо копировать надо ровно M ячеек старого массива. Почему бы нам просто не скопировать старый массив в новый? А в случае Python — так и вовсе просто добавить M + 1 ячейку прямо в конец старого (тип данных list позволяет сделать это очень эффективно)? Не получится ли такое решение в несколько раз быстрее повторного добавления всех пар в таблицу?

Так-то оно так, вот только работать как надо эта операция не будет! После «механического» расширения хеш-таблицы с открытой адресацией некоторые её элементы нельзя будет найти, а раздельно ещё и хранимые цепочки окажутся некорректными! На иллюстрации 3-4 показано, к чему приводит «механическое» удвоение размера таблицы для обоих подходов. Попробуйте, к примеру, проследить, что произойдёт с ключами 19 и 26. You should first observe that this copy operation will take time that is directly pro‐ portional to M—the greater the size of the hashtable storage array, the more elements need to be copied—so this operation can be classified as O(M). Simply copying the entries won’t actually work, however, since some entries—such as the ones with 19 and 26 as keys—will no longer be findable.

Переведённая сноска 8 It is commonly observed that Hashtables whose number of buckets is a prime number work really well (see challenge exercise at end of this chapter); here the size is odd, which can also be helpful.

Иллюстрация 3-4. Некоторые ячейки «теряются», если таблицу просто увеличить, не меняя содержимого

Начнём искать ключ 19. Хеш этого ключа — 19 % 15 = 4, но соответствующая ячейка будет пуста в обеих структурах, то есть его там как бы нет. При старом-то размере таблицы с открытой адресацией M = 7 последовательный просмотр цепочки (с перезапуском от начала таблицы) приводил пару с ключом 19 в ячейку 2. А теперь и хеш другой, и размер, так что возврат к началу таблицы происходит после 15 ячейки, то есть алгоритм поиска не соответствует действительности. If you went to look for key 19, its hash code would now be 19 % 15 = 4, and that bucket is empty in both structures, indicating that no entry with a key of 19 exists in the hashtable. In the former open addressing Hashtable with size M = 7, key 19 had been placed in bucket 2 because linear probing wrapped around the end of the old array (of size 7) to the beginning when it was inserted. Now that the array has 15 ele‐ ments, the wraparound doesn’t happen, so this key can no longer be found.

По чистой случайности в таблице с открытой адресацией некоторые ключи всё же можно найти, но алгоритм их поиска не будет адекватен исходному. Например, ключ 20 будет найден, но не сразу (в table[5]), а последовательным просмотром, в table[6]. Точно так же и ключ 15 найдётся не в table[0], а в table[1]. И только ключ 5 остаётся на своём месте — потому что его хеш не изменился. By pure coincidence, some entries are still findable, and these are highlighted in Figure 3-7. In open addressing, the entry with key 20 is not in table[5], but linear probing will find it in table[6]; similarly, the entry with key 15 is not in table[0], but linear probing will find it in table[1]. The entry with key 5 is findable in both open addressing and separate chaining because its hash code remains the same.

Дело, конечно же, в том, что при увеличении таблицы меняется хеш-функция, так что элементы скорее всего окажутся не на своих местах. Придётся вернуться к идее повторного хеширования: создадим пустую хеш-таблицу размером 2M + 1, и заново добавим в неё все пары из исходной таблицы. В терминах примера 3-8: каждую пару (key, value) исходного массива self.table добавим в новую таблицу temp с помощью temp.put(key, value) — тогда все пары точно можно будет найти. Воспользуемся динамической природой объектов Python и подменим старый массив новым (никакого копирования ячеек при этом не происходит). В результате у нового массива окажется два имени — self.table и temp.table, а у старого — ни одного, и вскорости он будет удалён исполняющей системой Python. При выходе из функции resize() прекращает существование переменная temp, и все объекты, у которых не осталось имён также будут удалены — но новый массив никуда не денется: у него останется ещё одно имя. Этот способ подходит обеим схемам хранения цепочек. What can I do to avoid losing keys? The proper solution, shown in Listing 3-10, is to create a new temporary Hashtable with twice the original storage (technically, 2M + 1) and rehash all entries into the new Hashtable. In other words, for each of the (k, v) entries in the original Hashtable, call put(k,v) on the new temporary Hashtable. Doing so will guarantee these entries will remain findable. Then, with a nifty programming trick, the underlying storage array from temp is stolen and used as is, whether for separate chaining or for open addressing.

   1 def resize(self, new_size):
   2     temp = DynamicHashtable(new_size)                   # 1
   3     for key, value in self.table:
   4         temp.put(key, value)                            # 2
   5     self.table, self.M = temp.table, temp.M             # 3
   6     self.threshold = self.load_factor * self.M

• Пример 3-8. Динамическое масштабирование таблицы с открытой адресацией путём повторного хеширования Listing 3-10. Resize method to dynamically grow hashtable storage for separate chaining

1. Создаём временную хеш-таблицу нужного размера
2. Добавляем в неё все пары из старой таблицы

3. Обновляем массив ячеек, значение M и порог threshold

Construct temporary Hashtable of desired new size. For each node in the linked list for a given bucket, take all nodes and rehash each entry into temp. Grab the storage array from temp and use for our own. Be sure to update our M and threshold values.

При раздельном хранении цепочек процедура практически не меняется, надо только вспомнить, что элементы массива table — не сами ячейки, а их списки. This code is nearly identical for resizing with open addressing.

   1 def resize(self, new_size):
   2     temp = DynamicHashtable(new_size)                   # 1
   3     for bucket in self.table:                           # 4
   4       for key, value in bucket:                         # 5
   5           temp.put(key, value)                          # 2
   6     self.table, self.M = temp.table, temp.M             # 3
   7     self.threshold = self.load_factor * self.M

• Пример 3-7. Динамическое масштабирование таблицы с раздельным хранением цепочек путём повторного хеширования

4. Внешний цикл — по спискам ячеек
5. Внутренний цикл — по ячейкам в списке

Итак, мы определили механизм масштабирования хеш-таблицы. На иллюстрации 3-5 показано, как в действительности должны выглядеть таблица с открытой адресацией (с иллюстрации 3-2) и таблица с раздельными цепочками (с иллюстрации 3-3) после увеличения размера с 7 до 15. I now have a strategy for dynamically increasing the size of a Hashtable. Figure 3-8 contains the proper resized hashtables for the open addressing example in Figure 3-2 and the separate chaining example in Figure 3-3.

Иллюстрация 3-5. Структура хеш-таблиц после масштабирования с повторным хешированием

Насколько лучше стало с применением масштабирования? Проведём эксперимент: для каждого начального размера таблицы M предпримем 25 тестов, в которых будем измерять: How well does the resizing logic perform? Let’s conduct an experiment running 25 repeated trials using different M values to measure:

Время заполнения

Время, которое потребуется для того, чтобы добавить N = 321129 ключей в хеш-таблицу с начальным размером M и удвоением размера при превышении порога загруженности. Build time: The time it takes to add N = 321,129 keys into a Hashtable with initial size M that doubles in size when threshold is exceeded

Время доступа

Время, за которое мы найдем в получившейся таблице все N ключей. Access time: . The time to locate all N of these words once all keys are inserted.

В таблице 3-4 приведены результаты измерения времени заполнения и времени доступа для хеш-таблиц с открытой адресацией и с раздельными цепочками, причём начальный размер таблицы, M, меняется от 625 до 6400000. В последней строке приведены аналогичные данные для хеш-таблицы фиксированного размера на 428172 ячейки — этот размер соответствует пороговому заполнению таблицы 321129 элементами, потому что 428172 × 0.75 = 321129, и сравнение вполне оправдано. For separate chaining and open addressing hashtables, Table 3-4 compares the build times and access times for dynamically resizable hashtables starting with different ini‐ tial size, M, ranging from 625 to 640,000. This table also shows the performance of nongrowing hashtables with an initial size of M = 428,172. This will result in a fair comparison, since N = 321,129, or 428,172 × 0.75.

• Таблица 3-4. Сравнение масштабируемых хеш-таблиц с таблицами фиксированного размера (время в миллисекундах) Table 3-4. Comparing growing tables against fixed-size construction (time in ms)

. Linked list Linked list Open addressing Open addressing M Build time Access time Build time Access time 625 0.997 0.132 1.183 0.127 1,250 1.007 0.128 1.181 0.126 2,500 0.999 0.129 1.185 0.133 5,000 0.999 0.128 1.181 0.126 10,000 1.001 0.128 1.184 0.126 20,000 0.993 0.128 1.174 0.126 40,000 0.980 0.128 1.149 0.125 80,000 0.951 0.130 1.140 0.127 160,000 0.903 0.136 1.043 0.126 320,000 0.730 0.132 0.846 0.127 640,000 0.387 0.130 0.404 0.127 … … … … … Fixed 0.380 0.130 0.535 0.131

В последнем ряду приведён «наихудший идеальный» случай: идеальный — потому что размер таблицы заранее подобран так, чтобы показатель загруженности не превысил 0.75 (стало быть, resize() не вызывается), а наихудший — потому что под конец заполнения таблицы он подходит к пороговому значению вплотную. Разумно ожидать, что в этом случае и время заполнения, и время доступа в таблице с открытой адресацией будут несколько больше аналогичных параметров таблице с раздельными цепочками: в первом случае коллизии одного хеша в конце концов начинают неизбежно удлиннять несколько разных цепочек, а во втором — только одну, которая этому шешу соответствует. А вот для «слишком идеального» случая в предпоследней строке (с таблицей, заполненной примерно наполовину) может выиграть открытая адресация — за счёт более простой структуры, которая требует линейно меньше операций. Что более важно: время доступа к N = 321129 элементам динамической хеш-таблицы не зависит от её начального размера M, так что отпадает необходимость магически предсказывать этот размер заранее. The last row presents the ideal case, where the load factor of the Hashtable does not exceed 0.75. You should expect open addressing to require more build time, because collisions on one bucket inevitably affect other buckets, whereas separate chaining localizes all collisions within the same bucket. The other remaining rows show that you don’t have to magically predict the initial M to use, since the access time (to inspect all 321,129 keys) is essentially the same.

Оценка производительности динамических хеш-таблиц

Analyzing the Performance of Dynamic Hashtables

Мы уже говорили, что чисто теоретически хеши всех ключей могут совпасть и угодить в одну цепочку (как при открытой адресации, так и для цепочек в списках). Как следствие, время выполнения операций put() и get() будет прямо пропорционально количеству элементов в хеш-таблице N, а значит, в наихудшем случае сложность этих операций следует оценить как O(N). In the worst case, both put() and get() for Hashtable is O(N). As I have explained before, if the hash code for each key computes to exactly the same bucket (for both separate chaining and open addressing), the time to complete each operation is directly proportional to N, the number of keys in the Hashtable.

Довольно частое требование к хеш-функции — равномерное распределение хешей на всём множестве значений. Если это свойство обеспечить, любой случайный ключ будет иметь равную вероятность попасть в любую цепочку. В идеале средняя длина отдельной цепочки должна быть равна N/M, это доказывается математически. Остаётся только надеяться на то, что специалист, который разработал для Python функцию hash(), предусмотрел и равномерное распределение в ней¹³ However, under the commonly agreed-upon assumption of simple uniform hashing, hash functions will uniformly distribute keys into the buckets of the hashtable: each key has an equal probability of being placed in any bucket. From this assumption, mathematicians have proved that the average length of each chain is N/M. The take‐ away is that you can rely on the experts who have developed the Python hash() function.

Раз уж у нас таблица динамически растёт, причём N гарантированно меньше, чем M, можно уверенно утверждать, что среднее значение N/M — это константа, то есть O(1), а стало быть, оно не зависит от N. Since you can always guarantee that N < M when hashtables can grow, I can say for certain that the average quantity N/M is a constant, O(1), and is independent of N.

Если ключ есть в таблице, поиск завершается «попаданием», а если нет — «промахом». Предположим, хеш-функция равномерно распределяет значения, и оценим среднее количество обращений к ячейкам таблицы с открытой адресацией и пороговым значением alpha для обоих результатов. В случае попадания придётся просмотреть в среднем (1 + 1 / (1 - alpha))/2 ячеек, для alpha = 0.75 получается 2.5. В случае промаха результат равен 1 + 1 / (1 - alpha)²/2, то есть 8.5 при тех же условиях.

Стоит понять, во что нам обходится динамическое изменение размера таблицы — допустим, с порогом загруженности 0.75 и геометрическим масштабированием (удвоением). Возьмём для начала M = 1023, а N — гораздо большим, чем M, к примеру, используем всё тот же словарь из 321129 английских слов. Попробуем посчитать, сколько раз мы добавляем пару в таблицу — в том числе в новую, внутри функции resize(). I need to account for the extra costs of resizing the hashtable, working under the assumption that the threshold load factor is 0.75 and that the underlying storage dou‐ bles in size using geometric resizing. To start things off, let’s assume M is 1,023 and that N is much larger than M: I’ll use the 321,129-word English dictionary again. I need to count the number of times each key is inserted into a hashtable (including the temporary one in resize).

Первый раз resize() вызовется при добавлении 768-го ключа (потому что 768 ⩾ 767.25 = 0.75 × 1023), и размер таблицы M станет равен 1023 × 2 + 1, то есть 2047. В процессе масштабирования нам придётся заново добавить все 768 ключей (заново вычисляя их хеши). Заметим, что в результате показатель загруженнсти упадёт до 768 / 2047, т. е примерно 0.375. The first resize is triggered when the 768th key is added (since 768 is ≥ 767.25 = 0.75 × 1,023), which grows the hashtable to have M = 1,023 × 2 + 1, or 2,047. During this resize, 768 keys are rehashed and inserted. Note that immediately after the resize, the load factor is reduced in half to 768/2047, which is approximately 0.375.

После добавления ещё 768 ключей их количество опять подойдёт к пороговому — 1536, и все пары будут перенесены (с повторным хешированием) в новую таблицу размера M = 2047 × 2 + 1, то есть 4095. В третий раз масштабирование произойдёт после добавления ещё 1536 ключей, и придётся добавлять уже 3072 пары в таблицу размера 8191. When an additional 768 keys are inserted, all 1,536 keys are rehashed into a new hashtable of size M = 2,047 × 2 + 1, or 4,095. The hashtable is resized a third time when an additional 1,536 keys are inserted, which causes the existing 3,072 keys to be inserted into a hashtable of size M = 8,191.

Что эти числа нам говорят? Посмотрим на таблицу 3-5: там показано количество слов N, которые надо добавить в таблицу, чтобы произошло масштабирование, а ещё — каково будет после этого общее число операций добавления ключа в таблицу. После каждого перехеширования будет увеличиваться, а затем снова падать среднее количество операций добавления на один хранимый элемент; эта характеристика — отношение общего числа добавлений к N — представлена в последнем столбце. В нашем случае она никогда не превышает 3 в силу геометрической природы масштабирования — и это несмотря на то, что при каждой смене размера нужно заново добавлять все ключи из старой таблицы в новую. To make sense of these numbers, Table 3-5 shows the resizing moments when the Nth word is inserted, together with the accumulated total number of times any key is inserted into the hashtable. During resize events, the final column shows that the average number of insertions (by dividing the total number of insertions by N) converges to 3. Even though resizing forces each key to be reinserted with a geomet‐ ric resizing strategy, this table demonstrates you will never need more than three times as many insertions than without resizing.

• Таблица 3-5. На добавлении какого слова происходит изменение размера таблицы, сколько всего для этого требуется добавлений, и сколько раз в среднем добавлялось одно слово Table 3-5. Words whose addition causes a resize event, with total number of insertions and average number of times a word was inserted

Главное, что понятно из этих данных: с увеличением размера таблицы геометрическое масштабирование происходит значительно реже. В последней строке показано, как с добавлением заключительного слова среднее количество операция становится равным 2.22, и при этом масштабирование не понадобится ещё для 72087 добавлений. Если первый интервал между операциями масштабирования составлял 768 добавлений, то девятый (196608) уже в 2⁸ = 256 больше.

Если исследовать алгоритм геометрического масштабирования аналитически, картина не меняется. Для начала заметим, что ни размер таблицы, ни пороговый коэффициент загруженности на подсчёт среднего количества добавлений не влияют. В самом деле: перед очередной операцией масштабирования в таблицу размера M уже добавлено N = M·3/4 ячеек в соответствии с пороговым значением. При масштабировании размер таблицы становится 2M (забудем на время про одну дополнительную ячейку), а новое пороговое значение — 2M·3/4 = 2N. При этом на операцию масштабирования тратится ещё N добавлений, N ячеек в новой таблице оказываются заняты, и ещё 2N - N = N ячеек туда можно добавить до следующего масштабирования. В следующий раз нам потребуется уже 2N добавлений, чтобы скопировать старую таблицу, и 2N добавлений останется в запасе.

Итак, сколько добавлений проделано между этими двумя операциями масштабирования? N — для новых элементов и 2N — при повторном хешировании. Вот и весь секрет «магического» числа 3, к которому приближается среднее количество операций на элемент в хеш-таблице! После первого же масштабирования на каждое добавление нового элемента приходится дополнительно ещё две операции при копировании. Если бы начинали сразу с полупустой таблицы, это отношение было бы равно строго 3. Но поскольку мы начинаем с пустой таблицы размера M, и следовательно, имеем M/2 «неучтённых» свободных ячеек, да ещё после удвоения прибавляем дополнительную ячейку, отношение общего количества добавлений к количеству хранимых ключей в хеш-таблице с геометрическим удвоением всегда меньше 3.

The key observation is that geometric resizing ensures that resize events occur signifi‐ cantly less frequently as the size of the table grows. In Table 3-5, once the final word is inserted into the hashtable—which is not a resize event—the average has dropped to 2.22, and it will not need to be resized again until another 72,087 keys are added. As you can see, this is almost 100 times less frequently than when it started (when a resize was triggered after just 768 were added).

В частности, добавление всех N=321129 слов в нашу динамически расширяемую хеш-таблицу медленнее добавления в неизменяемую таблицу подходящего для N размера не более, чем втрое. Как мы уже договорились в главе 2, это всего лишь мультипликативная постоянная, и она не влияет на оценку сложности операции put() в среднем: даже несмотря на дополнительные затраты на масштабирование сложность остаётся O(1). The result of this last analysis is that the average cost of inserting all 321,129 entries into a dynamically resizing hashtable is no more than three times what it would cost if the hashtable had somehow been large enough to store all N keys. As you have seen in Chapter 2, this is just a multiplicative constant, which will not change the perfor‐ mance classification of the average case for put(): it remains O(1) even with extra work due to resizing.

Динамические массивы

Мы уже несколько раз указывали на то, что тип list в Python реализован как массив; строго говоря — как таблица, то есть массив ссылок на объекты. Объекты Python могут быть разного размера, а вот ссылки — всегда одинакового. Наиболее распространён интерпретатор Python, написанный на Си, т. н. CPython; в нём, как в Си, ссылки — ­это просто адреса соответствующих структур в оперативной памяти). Доступ к этим ссылкам программист почти не имеет: в том же CPython функция id(объект) вернёт число, соответствующее адресу объекта в памяти, но смысла в этом немного, ибо сделать с ним ничего нельзя, да сам этот id не обязан быть уникальным. Например, если создать произвольный объект (скажем, строку), затем удалить его, затем создать объект другого типа (скажем, кортеж), есть шанс, что оба эти объекта получат одинаковый id, потому что будут, каждый в своё время, расположены по одному и тому же адресу оперативной памяти.

О свойствах массива мы рассказывали в отдельном подразделе, заметим только, что созданием и удалением самих объектов, ссылки на которые содержит объект типа list, занимается исполняющая система Python и, в конечном итоге, операционная система. Сейчас нас будет интересовать другое очень полезное свойство типа list, которое отличает его от простого массива: его размер можно менять.

Последовательная организация оперативной памяти предполагает, что «классические» массивы могут иметь только заранее заданный размер. Скажем, в восьми идущих подряд ячейках памяти находится массив из восьми целых чисел A, а в следующих восьми — массив из четырёх вещественных чисел двойной точности B. Добавить больше восьми элементов в массив A невозможно: дальше начинается стартовый элемент массива B, и если записать в A[8] целочисленное значение, то в B[0] окажется что-то совсем невообразимое. Тем не менее в списки Python можно добавлять сколько угодно элементов, и мы указывали на то, что операция эта сравнительно дешёвая — в среднем O(1).

Ничего не напоминает? Конечно же, ситуацию с переполнением хеш-таблицы, только в упрощённой форме! Допустим, объект A типа list занимает восемь ячеек памяти и все они уже заняты: len(A) равно 8. Тогда операция A.append(объект) начнётся с масштабирования массива, причём тоже геометрического и тоже с коэффициентом 2. Опуская подробности: будет выделен фрагмент памяти на 16 ячеек, туда скопировано содержимое восьми ячеек из старого фрагмента, добавлено значение девятой ячейки (ссылка на объект), имя A начнёт указывать на это новый фрагмент, а старый — освобождён. При этом len(A) будет возвращать 9, и в A останется ещё 7 свободных мест для добавления новых объектов за константное время. Как и в случае динамической хеш-таблицы, операция добавления в динамический массив, достигший предела загруженности (здесь он просто равен 1) имеет линейную сложность. Мы уже знаем, что геометрическое масштабирование гарантирует нам O(1) в среднем, с мультипликативной постоянной 3.

Вот и весь секрет! Прежде, чем двинуться дальше, остаётся сделать два важных замечания. Во-первых, мы не рассматривали операцию удаления ключа из хеш-таблицы — потому что она сравнительно редко требуется. Однако удаление элемента из динамического массива требуется сплошь и рядом, оно имеет в среднем линейную сложность (из-за «сдвига» элементов) и в среднем константную при удалении последнего элемента, например, для A.pop(). Логично предположить, что при достижении некоторого нижнего порога загруженности (скажем, в четверть прежнего размера), нам захочется уменьшить размер массива. Это делается ровно тем же способом, геометрически масштабированием, только в меньшую сторону, и ровно по этой причине также не влияет на константность операции .pop().

Во-вторых, здесь кажется уместным ответить (или скорее не ответить) на вопрос «Как Python справляется с фрагментацией памяти?». Суть вопроса в следующем. Допустим, мы создали сто динамических массивов, и они расположились в оперативной памяти, как и полагается, подряд. Затем в каждый второй из этих массивов мы добавили столько элементов, что произошло их масштабирование. При этом, как мы договорились, для этих пятидесяти была выделена новая память, а старая «освобождена». В результате чего фрагмент памяти, в котором изначально лежали все сто массивов, приобрёл вид «массив, свободное место, массив, свободное место, массив…». Итак, вопрос: не захламляют ли такие структуры оперативную память, и кто в случае Python заведует всем этим хозяйством? Ответ: разумеется, захламляют, и заведует этим исполняющая система Python, пользуясь программным интерфейсом операционной системы.

Эффективное управление памятью — серьёзная, активно развивающаяся дисциплина IT, не имеющая ни идеального, ни даже просто устраивающего всех решения. Ей посвящены многие научные и практические труды. В нашей книге мы не станем посягать на эту тему. Чтобы оценить масштаб проблемы, которую мы не станем решать, задумаемся ещё вот над чем. Бог с ними, с массивами. Допустим, мы создали сто обычных питоновских объектов, а потом просто удалили каждый второй. Не произойдёт ли и тут фрагментации памяти, и если да, то кто и что с ней будет делать? Ведь такое происходит, считай, постоянно? Изучение этого вопроса столь же занимательно, сколь и обширно, оно может окончательно увести в сторону от главной темы. Лучше вернёмся к ней.

Идеальный хеш

Perfect Hashing

Если заранее знать, чему будут равны все наши N ключей, можно подобрать то, что называется идеальной хеш-функцией, в которой каждому ключу взаимно однозначно соответствует уникальный хеш, и стало быть, и попадание, и промах в хеш-таблице потребуют ровно одного обращения. Неожиданный, но довольно распространённый приём — по набору ключей автоматически изготовить фрагмент программы на произвольном языке программирования, в которой будет определена соответствующая хеш-функция. If you know the collection of N keys in advance, then you can use a technique known as perfect hashing to construct an optimal hashtable where the hash code for each key is a unique index location. Perfect hashing generates the Python code containing the hash function to use. This is an unexpected result, and there are perfect hash genera‐ tors for numerous programming languages.

В примере 3-8 приведён вариант такой функции perfect_hash(), сгенерированный сторонним модулем perfect-hash из файла, в котором в каждой строке расположен один ключ — слово из бессмертного пушкинского «Читатель ждёт уж рифмы розы; На, вот возьми её скорей!» (без знаков препинания и прописных букв, зато с буквами «ё»)¹⁴. Несущественную отладочную информацию и комментарии мы удалили. If you install the third-party Python library perfect-hash, it can generate a per fect_hash() function from an input file containing the desired keys.9 Listing 3-11 contains the generated code using the words “a rose by any other name would smell as sweet.”

   1 G = [0, 10, 3, 10, 10, 8, 1, 0, 3, 5, 6]
   2 S1 = [4, 10, 4, 6, 9, 7, 1, 6]
   3 S2 = [7, 1, 6, 1, 6, 8, 8, 9]
   4 
   5 def hash_f(key, T):
   6     return sum(T[i % 8] * ord(c) for i, c in enumerate(key)) % 11
   7 
   8 def perfect_hash(key):
   9     return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 11

• Пример 3-8. Идеальный хеш для десяти пушкинских слов Listing 3-11. Perfect hashtable for ten words from Shakespeare

Мы уже пользовались встроенной в Python функцией enumerate(), которая возвращает последовательность пар (индекс, элемент) для любой итерируемой последовательности. Строго говоря, исходная последовательность даже не обязана сама быть индексируемой, то есть конструкция последовательность[i] может быть синтаксически недопустимой. Но если существует возможность пройтись по ней циклом вида for элемент in последовательность, то всегда возможна конструкция вида for индекс, элемент in enumerate(последовательность). Переменная индекс при этом будет расти от 0 с шагом 1. Если при проходе циклом нужны и элементы, и их индексы, рекомендуется в любом случае использовать enumerate(), как в примере ниже.

•    1 >>> for index, character in enumerate("QWE"):
     2 ...     print(index, character)
     3 0 Q
     4 1 W
     5 2 E
     6 
  

Вспомним, как на иллюстрации 3-1 мы задали массив day_array и в дополнение к нему — функцию base32(), которая вычисляла хеш каждого из 12 месяцев. Тогда размер этого массива зависел от найденного нами числа — 35, остатки деления хешей каждого месяца на которое все оказываются различными. Тем самым мы задали идеальную для месяцев года хеш-функцию, формула которой — day_array[base32(месяц)%35]. Алгоритм из perfect-hash достигает того же эффекта, но существенно более остроумным способом. Не пытаясь описать методику создания полученных структур данных и функций¹⁵, попробуем убедиться хотя бы в том, что это именно хеш, и он идеален для наших ключей.

Итак, у нас есть массив G, размер которого (11) превосходит общее количество ключей N=10, два вспомогательных массива S1 и S2 меньшей длины (ниже мы убедимся, что эта длина растёт очень незначительно по сравнению с ростом N, вспомогательная хеш-функция hash_f() и собственно perfect_hash(), которая, поверим авторам на слово, будет выдавать идеальный хеш для заданного множества ключей. Чтобы вычислить хеш ключа «уж», необходимо сначала получить два промежуточных значения: Recall from Figure 3-1 how I defined a list, day_array, and a supporting base32() hash function that worked with twelve months? Perfect hashing pursues the same approach in a more elegant way, processing the N strings to create the lists G, S1, and S2 and a supporting hash_f() function. To compute the index location for the string 'a', you need two intermediate results; recall that ord('a') = 97:

• hash_f('уж', S1) = (S1[0] * ord('у') + S1[1] * ord('ж')) % 11, то есть (4 * 1091 + 10 * 1078) % 11 = 15144 % 11 = 8 (1091 и 1078 — порядковый номер букв «у» и «ж» в таблице Unicode). hash_f('a', S1) = sum([ S1[0] × 97 ]) % 12. Since S1[0] = 9, this is the value (9 × 97) % 12 = 873 % 12 = 9.

• hash_f('уж', S2) = (S2[0] * ord('у') + S2[1] * ord('ж')) % 11, то есть (7 * 1091 + 1 * 1078) % 11 = 8715 % 11 = 3 hash_f('a', S2) = sum([ S2[0] × 97 ]) % 12. Since S2[0] = 2, this is the value (2 . × 97) % 12 = 194 % 12 = 2.

Функция perfect_hash('уж') вычисляет (G[8] + G[3]) % 11, то есть (3 + 10) % 11 = 2. Таким образом, хеш ключа «уж» равен двум. Повторим упражнение на ключе «вот»: The value returned by perfect_hash('a') is (G[9] + G[2]) % 12 = (11 + 1) % 12 = 0. This means that the hash code for the string 'a' is 0. Repeat this computation10 for the string 'by' and you will find that:

• hash_f('вот', S1) = (4 * 1074 + 10 * 1086 + 4 * 1090) % 11 = 19516 % 11 = 2. hash_f('by', S1) = (9 × 98 + 4 × 121) % 12 = 1,366 % 12 = 10.

• hash_f('вот', S2) = (7 * 1074 + 1 * 1086 + 6 * 1090) % 11 = 15144 % 11 = 8. hash_f('by', S2) = (2 × 98 + 10 × 121) % 12 = 1,406 % 12 = 2.

• perfect_hash('вот') = (G[2] + G[8]) % 11 = (3 + 3) % 11 = 6. perfect_hash('by') is (G[10] + G[2]) % 12 = (1 + 1) % 12 = 2.

Продолжая в том же духе, получим, что хеш «уж» — это 2, хеш «вот» — 6, и вообще хеш каждого слова из «читатель ждёт уж рифмы розы на вот возьми её скорей» уникален. Математика¹⁶ временами творит настоящие чудеса! To summarize, the key 'a' hashes to index location 0, and the key 'by' hashes to index location 2. In fact, each of the words in “a rose by any other name would smell as sweet” is hashed to a different computed index location. It is sometimes truly amazing what mathematics can do!

В примере 3-9 приведена функция perfect_hash(), которую сгенерировал этот модуль для нашего тренировочного словаря из 321129 слов. На самом первом английском слове — «a» — функция возвращает 0, а на последнем, «zyzzyvas» — 321128. Сам массив G, содержащий 667596 промежуточных ключей, мы здесь, понятное дело, не приводим, а вот два массива S1 и S2 для вычисления идеального хеша всё ещё невелики. Listing 3-12 contains the perfect_hash() function for the 321,129 words in the sam‐ ple dictionary. This function computes 0 for the first English word, 'a', and 321,128 for the last English word, 'zyzzyvas'. It is supported by a large list, G, containing 667,596 values (not shown, obviously!) and two intermediate lists, S1 and S2. /*

В этом месте автор прямо обманывает читателя, ибо посчитать приводимые им числа в отсутствие G невозможно. Предлагаю вместо этого провокационного текста вставить другой (первый абзац после примера) Георгий Курячий

For the string 'by' in this larger perfect hashtable, you can confirm the following:

• hash_f('by', S1) = (394,429 × 98 + 442,829 × 121) % 667,596 = 92,236,351 % 667,596 = 108,103
• hash_f('by', S2) = (14,818 × 98 + 548,808 × 121) % 667,596 = 67,857,932 % 667,596 = 430,736

• perfect_hash('by') = (G[108,103] + G[430,736]) % 667,596 = (561,026 + 144,348) % 667,596 = 37,778

   1 S1 = [394429, 442829, 389061, 136566, 537577, 558931, 481136, 337378,
   2       395026, 636436, 558331, 393947, 181052, 350962, 657918, 442256,
   3       656403, 479021, 184627, 409466, 359189, 548390, 241079, 140332]
   4 
   5 S2 = [14818, 548808, 42870, 468503, 590735, 445137, 97305, 627438,
   6       8414, 453622, 218266, 510448, 76449, 521137, 259248, 371823,
   7       577752, 34220, 325274, 162792, 528708, 545719, 333385, 14216]
   8 
   9 def hash_f(key, T):
  10         return sum(T[i % 24] * ord(c) for i, c in enumerate(key)) % 667596
  11 
  12 def perfect_hash(key):
  13         return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 667596

• Пример 3-9. Часть текста программы с идеальным хешем для словаря английских слов /* Listing 3-12. Partial listing of perfect hash function for English dictionary

Читатель может самостоятельно изготовить полный пример: установить python-модуль perfect-hash и выполнить команду python3 -m perfect_hash --hft=2 words.english.txt, используя файл words.english.txt из репозитория с программами к данной книге. Поскольку при наполнении служебных массивов модуль использует случайный выбор, числа в получившемся примере будут другие, и длина G наверняка будет слегка отличаться.

Промежуточная функция hash_f() генерирует довольно большое число — сумму значений из S1 или S2, — далее это число обрезается с помощью остатка от деления на 667596, что даёт индекс каждой из половин хеша в большом массиве G. После того, как половины складываются и снова обрезаются до 667596, получается уникальный ключ для любого допустимого английского слова из нашего словаря в диапазоне от 0 до 667595. В действительности всё ещё интереснее: алгоритм рассчитан так, что perfect_hash(слово) возвращает индекс этого слова во входном списке, то есть число от 0  до 321128, и это значение (в отличие от содержимого S1, S2 и G) не меняется при повторной генерации текста функции. The computation in perfect_hash(key) in Listing 3-12 produces a large sum that is reduced using % 667,596 to identify a unique location from the large G list. As long as key is a valid English word from the dictionary, perfect_hash(key) uniquely identi‐ fies an index from 0 to 321,128.

Если попробовать внезапно посчитать хеш чего-то, что не является словом из исходного словаря, может возникнуть коллизия. В примере 3-9 слово «watered» и не-слово «not-a-word» получали одинаковый хеш; в только что сгенерированном примере на «not-a-word» может не быть коллизии, но она (в силу того, что всевозможных не-слов гораздо больше, чем 667595 штук) обязательно появится на каких-то других парах «слово - не-слово». Интересная задача — отыскание таких пар для конкретного варианта perfect_hash(). В этом нет никакой ошибки: за то, что нашей функции будут предъявляться только слова из исходного словаря, отвечает программист. If you inadvertently attempt to hash a key that is not an English word, a collision will occur: the word 'watered' and the nonword 'not-a-word' both hash to the index location 313,794. This is not an issue for perfect hashing, since the programmer is responsible for ensuring that only valid keys are ever hashed.

Проход таблицы циклом

Iterate Over (key, value) Pairs

Основная задача хеш-таблицы — эффективные операции get(k) и put(k, v). НО ещё было бы неплохо иметь доступ ко всем ячейкам таблицы, независимо от того, какой цепочке они принадлежат, и какой подход — открытая адресация или раздельное хранение — используется для их хранения. Hashtables are designed for efficient get(k) and put(k,v) operations. It might also be useful to retrieve all entries in a hashtable, whether it uses open addressing or sep‐ arate chaining.

Генератор, или вычислимая последовательность, — один из самых удобных инструментов Python. В современном языке программирования для последовательного просмотра некоторого набора данных не нужно задействовать отдельную память со списком этих данных. В главе 2 мы уже видели, что вычислимые последовательности range(0, 1000) и range(0, 100000) занимают одинаковый объём памяти, порождая соответствующие последовательности целых чисел. Генератор-функция — общая форма задания вычислимой последовательности в Python.

Вот такая генератор-функция изготовит и вернёт вычислимую последовательность целых неотрицательных чисел от 0 до n, в десятичном представлении которой нет заданной цифры: The following generator function produces the integers in the range from 0 to n that do not include the given digit:

•    1 def avoid_digit(n, digit):
     2     sd = str(digit)
     3     for i in range(n):
     4         if not sd in str(i):
     5             yield i
  

  • Пример 3-10. Задание генератор-функции

Анализируя синтаксис описания функции, Python обнаружит в ней оператор yield, и это будет значить, что данная это — генератор-функция, которая при вызове возвращает собственно генератор. Генератор-функцию надо вызвать один раз, получить генератор, а по генератору — пройтись циклом. Когда мы первый раз в цикле обращаемся к генератору, выполняются строки от начала функции до первого встреченного yield. В примере — от строки 2 до строки 5, при этом в цикл возвращается выражение, указанное параметром yield (в примере — i). В следующий раз выполнение продолжается непосредственно после выполненного yield и до следующего yield. В примере yield — последняя строка блока цикла, так что выполнение продолжается со строки 3 до строки 5, затем снова возвращается i, и так до тех пор, пока вычисляется цикл. Выход за пределы функции (в примере — когда i сравняется с n) означает останов цикла использующего генератор.

Посмотрим, как работает наша avoid_digit() в командной строке Python:

   1 >>> gen = avoid_digit(15, "3")                      # 1
   2 >>> gen
   3 <generator object avoid_digit at 0x7f25c6f3c200>    # 2
   4 >>> for element in gen:                             # 3
   5 ...     print(element, end=" ")
   6 ... print()
   7 0 1 2 4 5 6 7 8 9 10 11 12 14
   8 >>> for element in gen:                             # 4
   9 ...     print(element, end=" ")
  10 ... print()
  11 
  12 >>>
  13 

• Пример 3-11. Работа генератор-функции

1. Создадим генератор и назовём его gen

2. Ещё раз убедимся в том, что avoid_digit() возвращает генератор, а не, скажем, целое число

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

4. Если попробовать ещё раз пройтись циклом по тому же самому генератору, выяснится, что он уже закончился, и ни одной итерации не произойдёт¹⁷.

Если в классе Python задать специальный метод .__iter__(), сконструированный из этого класса объект станет итерируемым — его можно будет использовать в конструкции вида for элемент in объект. В примере 3-12 приведена реализация прохода циклом хеш-таблицы с открытой адресацией, а в примере 3-13 — реализация прохода циклом хеш-таблицы с раздельным хранением цепочек в списках. To give an object this same capability in Python, a class can provide an iter() method that allows the caller to use the for v in object idiom. The two iter() implementations in Listing 3-13 are designed for separate chain‐ ing and open addressing hashtables.

   1 class Hashtable:
   2     def __iter__(self):
   3         for entry in self.table:
   4             if entry:                           # 1
   5                 yield entry.key, entry.value    # 2

• Пример 3-12. Метод-итератор по всем элементам хеш-таблицы с открытой адресацией, реализованный как генератор-функция Listing 3-13. Iterate over all entries in a hashtable using Python generator function

1. Пропустим все пустые (содержащие None) ячейки

2. Вернём в yield кортеж (ключ, значение)

   1 class Hashtable:
   2     def __iter__(self):
   3         for chain in self.table:                # 1
   4             for entry in chain:                 # 2
   5                 yield entry.key, entry.value    # 3

• Пример 3-13. Метод-итератор по всем элементам хеш-таблицы с раздельным хранением цепочек

1. Цикл по цепочкам
2. Цикл по ячейкам в цепочке

3. Пара (ключ, значение) в качестве возвращаемого значения

Рассмотрим последовательности пар, порождаемые итераторами в трёх случаях: проходом по хеш-таблице размера M = 13 с открытой адресацией, по таблице размера 13 с раздельным хранением цепочек и по идеальной хеш-таблице на основе слов английского языка. После добавления в них слов из строки «a rose by any other name would smell as sweet» порядок выдачи пар при проходе циклом будет различен. В таблице 3-6 показан результат для всех трёх случаев. To demonstrate how these iterators work, construct two hashtables with M equal to 13—one using open addressing and one using separate chaining—and a third hashta‐ ble using perfect hashing. After inserting the words in the string “a rose by any other name would smell as sweet,” Table 3-6 shows the words generated by the respective hashtables.

• Таблица 3-6. Порядок слов, возвращаемых итераторами хеш-таблиц Table 3-6. Order of words returned by hashtable iterators

Порядок слов в двух наших реализациях выглядит случайным, а для идеальной хеш-функции — словарным. Конечно, никакого случайного выбора из множества ключей мы не писали: дело в алгоритме вычисления хеша, который использует Python-овскую функцию hash() с её равномерным распределением. Более того, если запустить соответствующий пример из репозитория самостоятельно, последовательность слов в этих двух случаях изменится, ибо современный hash() в Python случайно непредсказуем. The words returned for the open addressing and separate chaining hashtables appear to be in a random order; of course, this isn’t randomness but based solely on the way keys are hashed. If you execute the sample code that produces this table, your order‐ ing for open addressing and separate chaining will likely be different, because the hash() code values for strings in Python 3 are unpredictable.

Слова в выдаче третьего итератора идут в словарном порядке, потому что при формировании идеальной хеш-функции perfect_hash(ключ) исходный список слов был словарно упорядочен. Напомним одно из полезных свойств модуля perfect-hash: порождаемый этой функцией хеш — это номер слова во входном словаре. Так что если словарь был упорядочен, и ячейки в таблицу записываются в порядке значения хеша, итератор вернёт пары тоже в словарном порядке. Ещё одно важное следствие этого свойства — хеш-таблица на основе идеального хеша имеет размер, строго равный количеству элементов в исходном словаре, и не нуждается в разрешении коллизий. One nice feature of the perfect-hash library is that the index positions computed by perfect_hash(key) are based on the order of the words used when generating the per‐ fect hashing code. Simply use a list of strings that are already in sorted order, and the entries will be stored in sorted order, and the iterator will yield the pairs in the same order.

В последней, восьмой, главе мы поближе познакомимся с типом данных dict — Python-овскими ассоциативными массивами (или словарями). Всякий раз, когда в программе нужна хеш-таблица, надо использовать dict, а не наши самодельные классы, потому что dict и намного быстрее, и больше умеет. Chapter 8 contains more details of the Python dict type. Instead of implementing a symbol table from scratch, as I have done in this chapter, you should always use dict because it is a built-in type and will be significantly more efficient than the code I provide.

Заключение

Summary

В этой главе мы рассмотрели несколько важных понятий: In this chapter, I introduced several key concepts:

• . • The linked list data structure can store small collections of items efficiently, allowing for dynamic insertion and removal. это про связные списки

• Примитивным хеш-таблицам, которые хранят пары «ключ-значение» в массиве ячеек размера M, не хватает алгоритма разрешения коллизий — ситуации, когда хеш двух и более ключей приводит к одной и той же ячейке. • Symbols tables use a storage array with M buckets to store entries. There needs to be a strategy to resolve collisions when two or more keys hash to the same bucket.

• Открытая адресация ключа позволяет рассредоточить хранимые пары по всему массиву, но тогда для действительно эффективной работы нужно, чтобы размер этого массива M был как минимум вдвое больше максимального количества элементов N. Удаление элемента из такой хеш-таблицы — это целое упражнение (в тренировочных заданиях таких упражнений два). • Open addressing relies on distributing entries within an array to reduce the num‐ . ber of collisions, but this only works efficiently when the size of the storage array, M, is more than twice as large as the number of stored entries, N. See the chal‐ lenge exercises for two approaches that support removing keys.

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

  • Separate chaining uses linked lists to store entries whose keys hash to the same . bucket. This approach makes it easier to support a remove operation for keys.

• Самому придумать хеш-функцию непросто, но в Python есть встроенная функция hash(), её и стоит использовать. • Designing hash functions is hard—use the predefined ones designed by Python’s . designers.

• Геометрическое масштабирование ассоциативного массива (хеш-таблицы) позволяет сохранить среднее быстродействие операции добавления за счёт того, что «тяжёлая» процедура увеличения размера с перехешированием выполняется всё реже с ростом размера.

  • Geometric resizing ensures a symbol table remains efficient by decreasing the . frequency of future resize events.

• Python-овский тип данных list, который мы используем для списков, по сути — массив с геометрическим масштабированием при добавлении, то есть динамический массив. Это задаёт константную, O(1), сложность операциям добавления в конец списка.

• Идеальное хеширование — функция, возвращающая уникальный хеш для каждого элемента из заданного множества — возможна при условии, что это множество заранее определено. Более того, если это множество как-либо упорядочить, есть алгоритм, в котором хеш элемента совпадает с его порядковым номером. Вычислительная сложность и сложность по памяти идеальной хеш-функции чаще всего выше стандартной Python-овской hash(). • Perfect hashing can be used to construct hash functions that avoid collisions by . computing a unique bucket index location for a fixed number of keys; the hash function is often more computationally expensive than a default hash() function.

Тренировочные задания

Challenge Exercises

1. Улучшается ли работа открытой адресации, если вместо последовательного просмотра с шагом 1 и возвратом к началу избрать другую тактику разрешения коллизий? Сделайте размер массива равным степени двойки, а шаг просмотра — переменным, равным n-му элементу из последовательности т. н. треугольных чисел. После просмотра соседней ячейки (расстояние +1) исследуются ячейки на расстоянии 3, 6, 10, 15, 21 и т. д. (с учётом возврата к началу при выходе заграницы). Треугольное число № n вычисляется по формуле n · (n + 1) / 2.

   • Будет ли производительность такой таблицы лучше, чем при последовательном просмотре?
   Проведите эксперимент. Добавьте в хеш-таблицу размером 524288 половину словаря английских слов (160564 штуки — это наполнение примерно на треть), и измерьте время поиска всех 321129 слов. Сравните результаты эксперимента для хеш-таблицы с раздельным хранением, для таблицы с открытой адресацией и последовательным просмотром, и для новой таблицы с переменным шагом.

   1. Does open addressing improve if you use a different strategy for resolving colli‐ . sions? Instead of using a linear probe with a delta of 1 (wrapping around), create a hashtable whose size is a power of 2, and use a probe sequence that explores additional index positions using deltas that are triangle numbers, that is, the inte‐ gers 1, 3, 6, 10, 15, 21, and so on; you will still have to wrap around. The nth tri‐ angle number is the sum of the integers from 1 to n, represented by the formula n × (n + 1)/2. . Is the overall performance better than linear probing? Conduct an experiment where you fill a Hashtable of size 524,288 with the first 160,564 English words (for a utilization of 30%), and then measure the time it takes to search for all 321,129 words. Compare this performance against an open addressing Hashtable and the separate chaining variation.

2. Имеет ли смысл сортировать ключи в раздельно хранимых цепочках хеш-таблицы? Напишите вариант хеш-таблицы в раздельным хранением, в которой ячейка в цепочку добавляется так, чтобы (ключ, значение) оставались упорядоченными по возрастанию ключа.

   Проведите эксперимент. Создайте хеш-таблицу на 524287 элементов (524287 — простое число) и добавьте в неё первую половину словаря — 160564 английских слов (загруженность будет примерно на треть). Если добавлять слова в порядке возрастания, это сделает линейной сложность поиска нужного места для вставки пары, но константной — сложность вставки (потому что она будет фактически соответствовать добавлению в конец). Если добавлять слова в порядке убывания — наоборот. Какой из этих вариантов окажется наихудшим случаем? Сравните его производительность с производительностью хеш-таблиц того же размера с открытой адресацией и несортированными раздельными цепочками.

   Теперь измерьте время поиска первых 160564 английский слов в этой таблице. Можно ожидать, что это будет наилучший случай, потому что все эти слова уже есть в таблице. Сравните производительность с производительностью аналогичных операций на хеш-таблицах с открытой адресацией и несортированными раздельными цепочками. Затем поищите оставшиеся 160565 слов из второй половины словаря. Это должен оказаться наихудший случай, потому что поиск несуществующих слов в списке требует его полного просмотра. Снова сравните производительность с производительностью двух других типов таблиц. Насколько результаты сравнения связаны с индексом загруженности хеш-таблицы? Например, что изменится, если задать размер таблицы 214129 (загруженность 75%) или 999983 (загруженность 16%)?

   1. Is it worth sorting the keys in the linked lists of a separate chaining hashtable? . Construct a Hashtable variant that sorts the (key, value) pairs in each linked list in ascending order by key. . Conduct an experiment where you measure the time it takes to construct the ini‐ tial Hashtable of size 524,287 (a prime number) with the first 160,564 English words (for a utilization of 30%) in reverse order. As you will see, the worst case for this variation occurs when the keys are put() into the hashtable in increasing value. Compare this performance against an open addressing Hashtable and the regular separate chaining Hashtable. Now measure the time it takes to search the first 160,564 English words as keys. As you might expect, this is the best case, since all these words are in the hashta‐ ble. Compare this performance against the array-based Hashtable and the sepa‐ rate chaining variation. Next search for the remaining 160,565 words in the back half of the English dictionary. This provides a glimpse of the worst case since finding these words in a linked list will always require each linked list to be fully explored. Once again, compare this performance against the open addressing Hashtable and the regular unordered linked list variation. How sensitive are these results to the chosen initial size, 524,287? For example, compare with 214,129 (a utilization of 75%) and 999,983 (a utilization of 16%).

3. Чтобы убедиться в опасности предсказуемой хеш-функции, посмотрите на пример 3-14. Класс BadString в примере порождает объекты, схожие во всем с Python-овским типом str. Но работа встроенной функции hash() для них перегружена, потому что определён специальный метод .__hash__(). В результате hash() для таких объектов может быть равен только 0, 1, 2 или 3. To see the dangers in predictable hash codes, consider the ValueBadHash code in Listing 3-14. The objects for this Python class hash to just four different values (0 to 3). This class overrides the default behavior of hash() as well as eq(), so these objects can be used as a key when invoking put(key, v).

   •    1 class BadString(str):
        2     def __hash__(self):
        3         return hash(str(self)) % 4
     

     • Пример 3-14. Ужасная реализация хеш-функции

   Создайте хеш-таблицу с раздельно хранимыми цепочками на 50000 элементов и вызовите .put(BadString(w), 1) для первых 20000 английских слов из нашего словаря. Сделайте ещё одну такую же хеш-таблицу и добавьте туда те же слова непосредственно, без преобразования в BadString. Посчитайте: Construct a separate chaining Hashtable(50,000) and invoke put(ValueBad Hash(w), 1) for the first 20,000 English words in the dictionary. Next, create a regular separate chaining Hashtable, and invoke put(w, 1) for these same words. Generate statistics on: • The average chain length of a bucket • The maximum chain length of any bucket in Hashtable Be prepared for the code execution to take a long time! Explain these statistics.

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

4. Число ячеек в хеш-таблице, M, на практике выгодно делать простым. Если взять для примера числовой ключ и остаток от деления на M в качестве индекса в таблице, окажется, что ключ, имеющий общий делитель с M, попадает только в ячейку, индекс которой имеет тот же общий делитель с M. Скажем, пускай M = 632 = 8 · 79, а добавляем мы пару с ключом 2133 = 27 · 79 ; хеш этого ключа будет равен 2133 % 632 = 237 = 3 · 79. Видите 79? Неприятность в том, что вместо равномерного распределения по всем ячейкам, от которого зависит быстродействие хеш-таблицы, получается, что некоторые ключи будут попадать строго в ограниченный набор ячеек.

   Исследуйте влияние M на результат. По аналогии с base32() напишите функцию base26(), которая каждому слову английского словаря поставит в соответствие числовой ключ. Создайте 101 хеш-таблицу размера M, где M будет меняться от 428880 до 428890 включительно, добавьте в каждую такую таблицу все 321129 английских слова по их числовому ключу base26(), и сравните средние и наибольшие длины цепочек. Проделайте этот опыт на хеш-таблицах с открытой адресацией и на хеш-таблицах с раздельными цепочками. Нет ли среди результатов некоторой общей закономерности? Сформулируйте гипотезу и попробуйте воспользоваться ею для поиска наихудшего M среди последующих 10000 размеров (до 438890). Для этого M длина наибольшей цепочки должна быть почти вдесятеро больше. 4. Having a prime number for the number of buckets, M, is helpful in practice because every key that shares a common factor with M will be hashed to a bucket that is a multiple of this factor. For example, if M = 632 = 8 × 79 and the entry to be inserted has a key of 2,133 = 27 × 79, the hash code is 2,133 % 632 = 237 and 237 = 79 × 3. The problem is that the performance of a hashtable assumes uni‐ form distribution of keys, which is violated when some keys are predisposed to be placed in certain buckets. To demonstrate the impact of M, form a key from the base32 representation of each of the words in the 321,129-word English dictionary. In the range from 428,880 to 428,980 containing 101 potential values for M, construct fixed-size hashtables (using both open addressing and separate chaining) and produce a table showing the average and maximum chain length size. Are there any values of M in this range that are particularly bad? Can you find out what these values all have in common? Armed with this knowledge, scan the next 10,000 higher val‐ ues of M (up to 438,980) to try to find one whose maximum chain length is almost ten times as bad.

5. Из хеш-таблицы с открытой адресацией нельзя просто так удалить произвольную пару — если пометить ячейку как пустую, проходившая через неё цепочка прервётся, и последовательный просмотр не доберётся до продолжения этой цепочки. Допустим, у нас есть хеш-таблица на пять элементов, в которую мы добавили ключи 0, 5 и 10. В результате ключи в таблице разместятся так: [0, 5, 10, ×, ×], потому что с каждой коллизией просмотр будет добираться до следующей ячейки. Если сейчас спроста удалить 5, получится таблица с ключами [0, ×, 10, ×, ×], в которой внезапно образовались две цепочки, причём ключ 10 найти в ней нельзя, потому что цепочка для хеша 0 теперь состоит из всего одного элемента.

   Один из путей решения проблемы — ввести специальное логическое поле в классе Entry, в котором будет отмечено, что эта ячейка удалена, но является частью цепочки. Напишите метод .remove(ключ), удаляющий элемент по ключу. Что изменится в работе методов .get() и .put()? Не забудьте также поправить процедуру масштабирования и метод .__iter__() — они должны пропускать удалённые ячейки.

   • При таком подходе понадобится также обратное масштабирование — уменьшение размера массива ячеек в случае, когда более половины из них помечены как удалённые. Сравните быстродействие хеш-таблицы с открытой адресацией и удалением и хеш-таблицы с раздельными цепочками (в которых удаление уже реализовано).

   5. When using an open addressing hashtable, there is no easy way to support . remove(key) because removing an entry from a bucket may break an existing chain created using linear probing. Imagine you have a Hashtable with M = 5 and you hashed entries with key values of 0, 5, and then 10. The resulting table array would contain the following keys [0, 5, 10, None, None], since each collision would be resolved using linear probing. A flawed remove(5) operation would simply remove the entry with key 5 from table, resulting in an array storing [0, . Challenge Exercises | 93 . None, 10, None, None]. However, the entry with key 10 is no longer findable because the chain at index location 0 was broken. One strategy is to add a Boolean field to the Entry that records whether the entry has been deleted or not. You have to modify get() and put() accordingly. In addition, the resize event needs to be adjusted as well, since entries marked as deleted will not need to be inserted into the new hashtable. Don’t forget to update the iter() method to skip deleted entries. Consider adding logic to initiate a shrink event when more than half of the entries in the hashtable are marked for deletion. Run some trials to compare the performance of separate chaining vs. open addressing now that remove() is avail‐ able for open addressing.

6. Масштабирование хеш-таблицы весьма серьёзно понижает производительность: требуется повторно хешировать все N ключей и заполнить N ячеек новой таблицы. В поэтапном масштабировании хранятся обе таблицы — старая, размера M, и новая, размера 2M + 1. Вызов get(ключ) сначала ищет ключ в новой таблице .а если его там нет — в старой. Вызов put(ключ, значение) всегда добавляет пару в новую таблицу, после чего D раз берёт пару из старой таблицы, повторно хеширует ключ, добавляет её в новую, а из старой удаляет. Когда старая таблица опустеет, её можно удалить¹⁸.

   Реализуйте поэтапное масштабирование для хеш-таблиц с раздельным хранением цепочек и исследуйте различные значения D. В частности, каково минимальное D, при котором к следующему масштабированию старая таблица гарантированно опустеет? Постоянна ли величина D, или она зависит от M, или даже от N?

   Такой подход должен снизить максимальную сложность операции .put(). Проведите эксперимент, составив таблицу, аналогичную таблице 3-5, в которой на этот раз сравните производительность самых неэффективных операций.

6. Resizing a hashtable incurs a steep penalty since all N values need to be rehashed . into the new structure. In incremental resizing, instead, the resize event allocates a new array, newtable (with size 2M + 1), but the original hashtable remains. A get(key) request first searches for key in newtable before searching through the original table. A put(key,value) request inserts a new entry into newtable: after each insertion, delta elements from the old table are rehashed and inser‐ ted into newtable. Once all elements are removed from the original table, it can be deleted. . Implement this approach with a separate chaining hashtable, and experiment with different values of delta. In particular, what is the smallest value of delta that will ensure the old table is completely emptied before the next resize event? Is delta a constant, or is it based on M or even N? This approach will reduce the total cost incurred at any time by put(); perform empirical measurements using an example similar to Table 3-5, but now evaluat‐ ing the runtime performance cost of the most expensive operation.

7. Обратное масштабирование можно реализовать и в обычной хеш-таблице с удалением. При вызове метода .remove() надо проверить, что таблица загружена не более, чем на ¼ M, и если да — запустить масштабирование к половинному размеру. Это позволит освободить неиспользуемую память. Доработайте любой из вариантов хеш-таблицы с удалением элемента, добавив в него обратное масштабирование, и проведите несколько испытаний на предмет того, стоит ли результат затраченных усилий.

   6. Should the number of (key, value) pairs, N, in a hashtable become less than ¼ of . M, the table storage array could shrink to reduce unneeded storage space. This shrink event can be triggered by remove(). . Modify either the separate chaining or open addressing hashtable to realize this capability, and run some empirical trials to determine if it is worthwhile.

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

   Например most_duplicated([1, 2, 3, 4]) может вернуть 1, 2, 3 или 4, а вот most_duplicated([1, 2, 1, 3]) обязан вернуть 1. 1. Use a symbol table to find the element in a list that is duplicated the most num‐ . ber of times. In the case of a tie, any value that is repeated “the most number of times” can be returned. . most_duplicated([1,2,3,4]) can return 1, 2, 3, or 4, while most_duplica ted([1,2,1,3]) must return 1.

9. Ещё один способ удалить пару из хеш-таблицы с открытой адресацией — это повторно хешировать все пары (ключ, значение), которые следуют в цепочке за удаляемой парой. Добавьте в хеш-таблицу с открытой адресацией такой способ удаления и проведите несколько экспериментов, сравнивая производительность хеш-таблицы с раздельным хранением цепочек c производительностью хеш-таблицы с открытой адресацией и удалением цепочки описанным способом¹⁹. 1. An open addressing hashtable can remove entries by rehashing all remaining . (key, value) pairs in the chain after the one that is to be removed. Add this capabil‐ ity to an open addressing hashtable, and run some trials to compare the perfor‐ mance of separate chaining versus open addressing with this revised remove capability.