Hash Table

Last updated Oct 14, 2023 Edit Source

• Алгоритмы

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

Для решения этой проблемы часто используется система кэширования. При запросе пользователем страницы с перечнем товаров, система первым делом проверяет наличие запрошенной страницы в кэше. Для быстродействия кэширование реализовано в виде хэш-таблицы, где URL страницы служит ключом (key), а список товаров - значением(value).

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

Когда у нас есть индекс для URL, мы можем обратиться к массиву по этому индексу и получить значение или установить новое. Таким образом, вместо поиска нужной страницы и связанного с ней списка товаров, что занимает время O(n), мы получаем доступ к списку товаров за O(1).

К хэш функции предъявляются следующие требования:

1. одинаковые входные данные должны давать один и тот же индекс (в примере page1 всегда соотвествует 5)

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

Пример хэш-функции для строк, созданная в 1991 году Daniel J. Berstein:

1
2
3
4
5
6

def hash_djb2(s):                                       
    hash = 5381
    for x in s:
        # ord(x) simply returns the unicode represitation
        hash = (( hash << 5) + hash) + ord(x)
    return hash & 0xFFFFFFFF

Коллизии - это явление в хэшировании, когда разные входные данные дают одинаковое значение хэша.

Чтобы решить проблему коллизий, существуют разные методы, включая открытое хэширование (Open Hashing значение массива становится списком, в нашем примере index 5 -> [список товаров page1, список товаров page7]) и закрытое хэширование (Closed Hashing). Открытое хэширование позволяет хранить несколько значений по одному индексу, в то время как закрытое хэширование пытается найти новый индекс для данных, вызывающих коллизию.

Hовый индекс Closed Hashing может быть получен следующим способом:

• линейным(Linear Probing),

• квадратичным(Quadratic Probing),

• двойным хэшированием (Double hashing)

Python предоставляет реализацию хэш-таблицы в виде словаря (dict), который хранит пары key-value. Чтобы объект мог быть использован в качестве key в словаре, он должен поддерживать хэш-функцию (через метод __hash__), а также операцию сравнения на равенство (через методы __eq__ или __cmp__). Важно отметить, что метод __eq__ используется при разрешении коллизий для нахождения правильного значения.

Одной из частых ошибок среди новичков является попытка использования list в качестве key. Однако стоит помнить, что list может менять количество элементов и их значения. В результате, создание надежных функций __hash__ и __eq__ для list затруднительно.

Код ниже вернет ошибку: TypeError: unhashable type: ’list'

1

my_dict[[1, 2]] = 'foo'

• https://theartincode.stanis.me/008-djb2/