Чтобы найти слово w, нам нужно осуществить последовательный поиск в списке, на который указывает поле таблицы с номером h (w).
В следующей схеме используется таблица гораздо большего размера. При п = 23 в большинстве клеток, скорее всего, окажется не более одного элемента (рис. 13.5). В этом примере h (а) = 13 и h (list) « 5.
—————I——————————————————
LjJ 111 111 III LJ LL
list words a of five
Рис. 13.5. Хэш-таблица для случая h (а) = 13 и h (list) = 5
В программе ispell n = 227 (около 134 миллионов), и почти все непустые списки состоят из одного элемента.
Следующим ходом Макилрой рискнул: вместо связанного списка в каждое поле таблицы он поместил единственный бит. При этом объем используемой памяти значительно сокращается, но возникают ошибки. На рис. 13.6 используется та же функция хэширования, что и в предыдущем примере, а нулевым битам соответствуют пустые ячейки:
Опубликовал vovan666
April 17 2013 00:03:55 ·
0 Комментариев ·
2685 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.