282    Объекты и типы

СЛОВАРИ

Словари — быстрый и гибкий способ сопоставления. Они используются разработчиками для хранения и сопоставления данных, а также объектами Python для хранения свойств и методов.

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

Хеширование

Все неизменяемые встроенные типы предоставляют функцию хеширования. Эта функция определяется в слоте типа tp_hash или (для пользовательских типов) при помощи специального метода __hash__(). Хеш имеет такой же размер, как указатель (64 бита для 64-разрядных систем, 32 бита для 32-раз- рядных систем), но он не представляет адреса своего значения в памяти.

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

>>> "hello".__hash__() == ("hel" + "lo").__hash__() True

Коллизии хешей недопустимы. Два объекта с разными значениями не должны иметь одинаковые хеши.

Некоторые хеши очень просты, например, у типа Python long:

>>> (401).__hash__() 401

Для более длинных значений хеши усложняются:

>>> (401123124389798989898).__hash__() 2212283795829936375

Многие встроенные типы используют модуль Python pyhash.c, который предоставляет следующие вспомогательные функции хеширования:

Книги для программистов: https://t.me/booksforits

Словари    283

zz Байты: _Py_HashBytes(const void*, Py_ssize_t) zz Double: _Py_HashDouble(double)

zz Указатели: _Py_HashPointer(void*)

Например, строки Юникода используют _Py_HashBytes() для хеширования байтовых данных строки:

>>> ("hello").__hash__() 4894421526362833592

Пользовательские классы могут определять функцию хеширования, реализуя __hash__(). Вместо того чтобы писать специальную реализацию хеш-функции, добавьте в класс уникальное свойство. Позаботьтесь о том, чтобы свойство было неизменяемым, сделав его доступным только для чтения, а затем хешируйте его встроенной функцией hash():

class User:

def __init__(self, id: int, name: str, address: str): self._id = id

def __hash__(self): return hash(self._id)

@property def id(self):

return self._id

Теперь экземпляры этого класса могут хешироваться:

>>>bob = User(123884, "Bob Smith", "Townsville, QLD")

>>>hash(bob)

123884

Экземпляр может использоваться в качестве ключа словаря:

>>>sally = User(123823, "Sally Smith", "Cairns, QLD")

>>>near_reef = {bob: False, sally: True}

>>>near_reef[bob]

False

Множества удаляют дублирующиеся хеши этого экземпляра:

>>> {bob, bob}

{<__main__.User object at 0x10df244b0>}

Книги для программистов: https://t.me/booksforits

284    Объекты и типы

Исходные файлы

Ниже перечислены исходные файлы, относящиеся к словарям.

Структура словаря

Объект словаря PyDictObject состоит из следующих элементов:

1.Свойства объекта словаря: размер, метка версии, ключи и значения.

2.Объект таблицы ключей словаря PyDictKeysObject, содержащий ключи и хеши всех элементов.

(PyObject*)

(PyObject *)

-

Книги для программистов: https://t.me/booksforits

Словари    285

Объект PyDictObject содержит следующие свойства.

ПРИМЕЧАНИЕ

Словари могут находиться в одном из двух состояний: разделенном или объединенном.В объединенном словаре указатели на значения словаря хранятся в таблице ключей.

В разделенном словаре значения хранятся в дополнительном свойстве ma_values в виде таблицы значений PyObject*.

Таблица ключей словаря PyDictKeysObject содержит следующие свойства.

Книги для программистов: https://t.me/booksforits

286    Объекты и типы

Запись ключа словаря PyDictKeyEntry содержит следующие свойства.

Поиск

Для заданного объекта ключа существует обобщенная функция поиска lookdict().

Поиск в словаре должен обеспечивать обработку трех возможных ситуаций:

1.В таблице ключей существует адрес ключа в памяти.

2.В таблице ключей существует хеш объекта.

3.Ключ не существует в словаре.

СМ. ТАКЖЕ

ФункцияпоискаосновананаматериалахзнаменитойкнигиДональдаКну­ та«Искусство программирования»(«TheArt of Computer Programming»).

Хеширование рассматривается в 4-м разделе 6-й главы.

Функция поиска работает по следующей схеме:

1.Получить хеш ob.

2.Найти хеш ob в ключах словаря и получить индекс ix.

3.Если значение ix пусто, вернуть DKIX_EMPTY (не найдено).

4.Получить запись ключа ep для заданного индекса.

5.Если значения ключей совпадают, то ob указывает на то же значение ключа. Вернуть результат.

6.Если хеши ключей совпадают, потому что объект ob разрешает то же значение хеша, что и ep->me_mash, вернуть результат.

Книги для программистов: https://t.me/booksforits