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

К примеру, в задаче Two Sum требуется найти в неупорядоченном списке L два числа, которые в сумме дадут заданное число K. Задача легко решается “в лоб”, перебором через вложенный цикл - вычислительная сложность O(n**2). Когда мне сказали, что можно решить её за O(n) - задумался, но максимум что смог - улучшить до O(n*ln(n)) - отсортировать список и искать нужную пару в нём поиском с двух сторон. Но найти пару за один проход…

Всё оказалось до смешного просто. Последовательно идём по списку, проверяем для каждого элемента x, есть ли он в словаре (проверка вхождения числа в хэш-таблицу - O(1)) и если нет, вносим туда его индекс по ключу K-x. А если элемент есть - значит мы нашли искомую пару

Примеры задач

Group Anagrams