Словари
Словари есть во многих языках программирования и предназначены для поиска и хранения значений, связанных с некоторыми ключами. В простом случае словарь можно представить как список пар ключ-значение, но ключи уникальны.
Основная задача словаря - обеспечивать доступ по ключу, поэтому мы хотим, чтобы он делал это эффективно. Если хранить пары как обычный неупорядоченный список, для поиска придется перебирать его каждый раз, но можно сделать быстрее.
Одна из возможных реализаций словаря - использование сбалансированных деревьев поиска (обычно красно-черных). Принцип работы заключается в том, что для каждого узла дерева все что в правой ветке - больше него, а всё что в левой - меньше. Если ветки не сильно разной длины, мы можем достаточно быстро так найти нужный элемент. Единственное, что требуется от ключей - возможность их сравнивать на и =. Результат сравнения не должен меняться в процессе жизни дерева, чтобы порядок сохранялся. Примеры: std::map в C++, TreeMap в Java, SortedDictionary в C#
Более распространенный вариант - использование хэш таблиц. В этом случае мы храним элементы в списке, но имеем способы быстро найти место в списке по ключу. Для этого используется хэш функция. Примеры: dict в Python, std::unordered_map в C++, HashMap в Java
Хэш-функция - это такая функция, которая из кучи возможных данных умеет делать числа ограниченного размера. Для одинаковых данных числа должны получаться одинаковые, для разных - как получится. Так как вариантов исходных данных заведомо больше чем чисел в ограниченном диапазоне, то повторения (коллизии) неизбежны.
Таким образом, когда нам надо узнать, где находится элемент в хэш-таблице, мы ключ превращаем в число (сначала с помощью хэширования, затем обрезая до нужного размера). А так как для разных ключей числа могут повторяться, мы дальше дополнительно проверяем тот ключ нашли или нет. Чтобы обработать несколько ключей, мы либо храним их в дополнительном маленьком списке, либо специальным алгоритмом пересчитываем индекс и прыгаем дальше. Желательно, чтобы такие повторения происходили не очень часто, но сами по себе они неизбежны.
Таким образом, для работы хэш-таблицы нам нужно, чтобы:
• для каждого ключа было можно посчитать число-хэш
• хэш у одинаковых ключей был одинаков
• хэш ключа не менялся и не ломал этим логику расположения элементов
Можно попытаться упростить эти требования до того, чтобы ключи были неизменяемы, но в целом это не требуется. Как правило, нужно чтобы не менялась только та часть данных ключа, которая учитывается при расчете хэша.
В Python для многих объектов равенство определено не на основе данных, а по факту, что это один экземпляр, поэтому и хэширование для них может быть безопасно определено на основе адреса в памяти.
• Для некоторых встроенных типов, таких как function, type или генераторов, разные экземпляры никогда не равны и хэш определен тривиально.
• Если вы пишете кастомный класс, по дефолту у него есть __eq__ и __hash__ на основе "адреса". Но если вы самостоятельно определяете сравнение в своём классе, то автоматический хэш пропадает.
• Для других типов, таких как tuple и list, равенство определяется содержимым, поэтому и хэш основам на нем. А если данные могут меняться, то стабильный хэш получить для таких типов невозможно.
Дополнительные материалы:
• https://habr.com/ru/articles/830026/
• https://habr.com/ru/articles/555404/
• https://ru.wikipedia.org/wiki/Сюръекция
Словари есть во многих языках программирования и предназначены для поиска и хранения значений, связанных с некоторыми ключами. В простом случае словарь можно представить как список пар ключ-значение, но ключи уникальны.
Основная задача словаря - обеспечивать доступ по ключу, поэтому мы хотим, чтобы он делал это эффективно. Если хранить пары как обычный неупорядоченный список, для поиска придется перебирать его каждый раз, но можно сделать быстрее.
Одна из возможных реализаций словаря - использование сбалансированных деревьев поиска (обычно красно-черных). Принцип работы заключается в том, что для каждого узла дерева все что в правой ветке - больше него, а всё что в левой - меньше. Если ветки не сильно разной длины, мы можем достаточно быстро так найти нужный элемент. Единственное, что требуется от ключей - возможность их сравнивать на и =. Результат сравнения не должен меняться в процессе жизни дерева, чтобы порядок сохранялся. Примеры: std::map в C++, TreeMap в Java, SortedDictionary в C#
Более распространенный вариант - использование хэш таблиц. В этом случае мы храним элементы в списке, но имеем способы быстро найти место в списке по ключу. Для этого используется хэш функция. Примеры: dict в Python, std::unordered_map в C++, HashMap в Java
Хэш-функция - это такая функция, которая из кучи возможных данных умеет делать числа ограниченного размера. Для одинаковых данных числа должны получаться одинаковые, для разных - как получится. Так как вариантов исходных данных заведомо больше чем чисел в ограниченном диапазоне, то повторения (коллизии) неизбежны.
Таким образом, когда нам надо узнать, где находится элемент в хэш-таблице, мы ключ превращаем в число (сначала с помощью хэширования, затем обрезая до нужного размера). А так как для разных ключей числа могут повторяться, мы дальше дополнительно проверяем тот ключ нашли или нет. Чтобы обработать несколько ключей, мы либо храним их в дополнительном маленьком списке, либо специальным алгоритмом пересчитываем индекс и прыгаем дальше. Желательно, чтобы такие повторения происходили не очень часто, но сами по себе они неизбежны.
Таким образом, для работы хэш-таблицы нам нужно, чтобы:
• для каждого ключа было можно посчитать число-хэш
• хэш у одинаковых ключей был одинаков
• хэш ключа не менялся и не ломал этим логику расположения элементов
Можно попытаться упростить эти требования до того, чтобы ключи были неизменяемы, но в целом это не требуется. Как правило, нужно чтобы не менялась только та часть данных ключа, которая учитывается при расчете хэша.
В Python для многих объектов равенство определено не на основе данных, а по факту, что это один экземпляр, поэтому и хэширование для них может быть безопасно определено на основе адреса в памяти.
• Для некоторых встроенных типов, таких как function, type или генераторов, разные экземпляры никогда не равны и хэш определен тривиально.
• Если вы пишете кастомный класс, по дефолту у него есть __eq__ и __hash__ на основе "адреса". Но если вы самостоятельно определяете сравнение в своём классе, то автоматический хэш пропадает.
• Для других типов, таких как tuple и list, равенство определяется содержимым, поэтому и хэш основам на нем. А если данные могут меняться, то стабильный хэш получить для таких типов невозможно.
Дополнительные материалы:
• https://habr.com/ru/articles/830026/
• https://habr.com/ru/articles/555404/
• https://ru.wikipedia.org/wiki/Сюръекция