0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: python, программирование на python, словарь в python, разработка на python, хеш-таблица</p>
1
<p>Теги: python, программирование на python, словарь в python, разработка на python, хеш-таблица</p>
2
<p><strong>Словарь в Python</strong>является фундаментальным типом хотя бы потому, что используется для хранения атрибутов объектов любого класса. Внутри словарь реализован как<strong>хеш-таблица</strong>с открытой адресацией, где коллизии разрешаются методом<strong>квадратичного пробинга</strong>, таблица расширяется при заполнении более чем на ⅔.</p>
2
<p><strong>Словарь в Python</strong>является фундаментальным типом хотя бы потому, что используется для хранения атрибутов объектов любого класса. Внутри словарь реализован как<strong>хеш-таблица</strong>с открытой адресацией, где коллизии разрешаются методом<strong>квадратичного пробинга</strong>, таблица расширяется при заполнении более чем на ⅔.</p>
3
<p>Вообще,<strong>словари</strong>достаточно хорошо описаны и стоят того, чтобы взглянуть на их исходники (искать в Objects/dictobject.c). Описанное устройство словарей несёт конкретные практические последствия:</p>
3
<p>Вообще,<strong>словари</strong>достаточно хорошо описаны и стоят того, чтобы взглянуть на их исходники (искать в Objects/dictobject.c). Описанное устройство словарей несёт конкретные практические последствия:</p>
4
<p><strong>Ключ должен быть хеширумым объектом</strong>Т. е. у него должен быть определен метод __hash__, возвращающий одинаковое значение во время жизни объекта. Кстати, если у вашего типа определён метод __eq__, то обязательно должен быть и __hash__, чтобы тип корректно работал со словарями и множествами.</p>
4
<p><strong>Ключ должен быть хеширумым объектом</strong>Т. е. у него должен быть определен метод __hash__, возвращающий одинаковое значение во время жизни объекта. Кстати, если у вашего типа определён метод __eq__, то обязательно должен быть и __hash__, чтобы тип корректно работал со словарями и множествами.</p>
5
<p><strong>Словари дают повышение накладных расходов по памяти</strong>Это связано с тем, что<strong>хеш-таблица</strong>должна быть достаточно большой для эффективной работы с ней. Если есть, например, необходимость сохранить в массиве большое количество записей, то оптимальнее по памяти представить их в виде<strong>кортежей</strong>, нежели чем в виде словарей.</p>
5
<p><strong>Словари дают повышение накладных расходов по памяти</strong>Это связано с тем, что<strong>хеш-таблица</strong>должна быть достаточно большой для эффективной работы с ней. Если есть, например, необходимость сохранить в массиве большое количество записей, то оптимальнее по памяти представить их в виде<strong>кортежей</strong>, нежели чем в виде словарей.</p>
6
<p><strong>Поиск по ключу очень быстрый</strong>Здесь тот самый space-time tradeoff, алгоритмическая сложность доступа O(1).</p>
6
<p><strong>Поиск по ключу очень быстрый</strong>Здесь тот самый space-time tradeoff, алгоритмическая сложность доступа O(1).</p>
7
<p><strong>Порядок следования ключей зависит от порядка вставки в словарь</strong>Это связано с возникающими<strong>коллизиями</strong>. При этом словари с одинаковым содержимым равны при проверке через ==.</p>
7
<p><strong>Порядок следования ключей зависит от порядка вставки в словарь</strong>Это связано с возникающими<strong>коллизиями</strong>. При этом словари с одинаковым содержимым равны при проверке через ==.</p>
8
<p><strong>Модифицировать словарь, по которому итерируешься - плохая идея</strong>В определённый момент<strong>Python</strong>может решить, что пора ресайзить хеш-таблицу и тогда старые данные переедут в новую табличку с новыми коллизиями, может измениться порядок следования ключей.</p>
8
<p><strong>Модифицировать словарь, по которому итерируешься - плохая идея</strong>В определённый момент<strong>Python</strong>может решить, что пора ресайзить хеш-таблицу и тогда старые данные переедут в новую табличку с новыми коллизиями, может измениться порядок следования ключей.</p>
9
<p>Множества аналогично реализованы через<strong>хеш-таблицу</strong>, так что к ним применимы те же следствия.</p>
9
<p>Множества аналогично реализованы через<strong>хеш-таблицу</strong>, так что к ним применимы те же следствия.</p>
10
<p><em>Хотите узнать больше? Записывайтесь на курс<a>"Разработчик Python"</a>или задавайте вопросы в комментариях!</em></p>
10
<p><em>Хотите узнать больше? Записывайтесь на курс<a>"Разработчик Python"</a>или задавайте вопросы в комментариях!</em></p>
11
11