Резюме

Резюме

В этой главе были рассмотрены хеш-таблицы - структуры данных, которые пытаются предоставить максимально быстрый доступ к своим элементам, при этом они подпадают под категорию O(1).

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

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