Грокаем а Иллюстрированное пособие для программистов и любопытствующих

КОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ - V,
Новая таблица имеет коэффициент заполнения ³/₈. Гораздо лучше! С мень­шим коэффициентом загрузки число коллизий уменьшается, и ваша табли­ца начинает работать более эффективно. Хорошее приближенное правило:
изменяйте размер хеш-таблицы, когда коэффициент заполнения превышает 0,7. Но ведь на изменение размеров уходит много времени, скажете вы, и будете абсолютно правы! Да, изменение размеров требует значитель­ных затрат ресурсов, поэтому оно не должно происходить слишком часто. В среднем хеш-таблицы работают за время 0(1) даже с изменением раз­меров.
Хорошая хеш-функция
Хорошая хеш-функция должна обеспечивать равномерное распределение значений в массиве.
П
12

лохая хеш-функция создает скопления и порождает множество коллизий.



Какую хеш-функцию считать хорошей? К счастью, вам об этом никогда не придется беспокоиться — пусть об этом беспокоятся пожилые бородатые умники, сидящие в полутемных комнатах. Если вам интересна эта тема, поищите информацию об алгоритме SHA (короткое описание приведено в последней главе). Вы можете использовать этот алгоритм в своей хеш- функции.
Упражнения
Очень важно, чтобы хеш-функции обеспечивали хорошее распределение.
Они должны распределять значения как можно шире. Худший случай —
хеш-функция, которая отображает все значения на одну позицию в хеш-
таблице.
Предположим, имеются четыре хеш-функции, которые получают строки:

1. 
   Первая функция возвращает «1» для любого входного значения.
   
2. 
   Вторая функция возвращает длину строки в качестве индекса.
   
3. 
   Третья функция возвращает первый символ строки в качестве индекса. Таким образом, все строки, начинающиеся с «а», хешируются в одну позицию, все строки, начинающиеся с «Ь» — в другую и т. д.
   
4. 
   Четвертая функция ставит в соответствие каждой букве простое число:
   

а = 2, b = 3, с = 5, d = 7, е = 11 и т. д. Для строки хеш-функцией становит­ся остаток от деления суммы всех значений на размер хеша. Например, если размер хеша равен 10, то для строки «bag» будет вычислен индекс 3+2+17/610 = 22% 10 = 2. ‘
В каком из этих примеров хеш-функции будут обеспечивать хорошее распределение? Считайте, что хеш-таблица содержит 10 элементов.

5. 
   Телефонная книга, в которой ключами являются имена, а значения­ми - номера телефонов. Задан следующий список имен: Esther, Ben, Bob, Dan.
   
6. 
   Связь размера батарейки с напряжением. Размеры батареек: А, АА, AAA, АААА.
   
7. 
   Связь названий книг с именами авторов. Названия книг: «Maus», «Fun Ноте», «Watchmen».
   

Шпаргалка
Вам почти никогда не придется реализовать хеш-таблицу самостоятельно. Язык программирования, который вы используете, должен предоставить необходимую реализацию. Вы можете пользоваться хеш-таблицами Python, и при этом вам будет обеспечена производительность среднего случая: по­стоянное время.
Хеш-таблицы чрезвычайно полезны, потому что они обеспечивают высокую скорость операций и позволяют по-разному моделировать данные. Воз­можно, вскоре выяснится, что вы постоянно используете их в своей работе.

• 
  Хеш-таблица создается объединением хеш-функции с массивом.
  
• 
  Коллизии нежелательны. Хеш-функция должна свести количество кол­лизий к минимуму.
  
• 
  Хеш-таблицы обеспечивают очень быстрое выполнение поиска, вставки и удаления.
  
• 
  Хеш-таблицы хорошо подходят для моделирования отношений между объектами.
  
• 
  Как только коэффициент заполнения превышает 0,7, пора изменять раз­мер хеш-таблицы.
  
• 
  Хеш-таблицы используются для кэширования данных (например, на веб-серверах).
  
• 
  Х
  ю ОКТЯБРЯ
  
  а апреля
  
  
  13 МАРТА
  
  еш-таблицы хорошо подходят для обнаружения дубликатов.