Към съдържанието
wannacode

Как работят dict и set

Проблем

Мястото е продадено два пъти

Касата на театъра пази продадените места в речник: място → име на зрителя. Мястото е клас с ред и номер:

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number
bookings = {}
bookings[Seat(5, 12)] = "Мария"


print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Иван"
print(len(bookings))
Изход
None
1
2

Мария е купила място 5/12, но get със същото място връща None. А Иван купува същото място и речникът вече има два ключа 5/12. Защо?

Идеята

Хеш: число от ключа

Речникът не сравнява ключа с всички останали. Той смята от ключа едно цяло число и по него разбира къде да търси. Това число се казва хеш (hash code) и го връща вградената функция hash(). Тя вика метода __hash__ на обекта.

print(hash("Мария") == hash("Мария"))
print(hash("Мария") == hash("Мариа"))
print(hash("Мария") == hash("мария"))
print(hash(1004))
Изход
True
False
False
1004
  • В едно пускане един и същ текст дава едно и също число.
  • Малка промяна дава друго число: „Мария“, „Мариа“ и „мария“ са три различни хеша.
  • Хешът на цяло число е самото число.
  • Хешът се смята бързо, без значение колко ключа има в речника.

Самото число за текст тук не е отпечатано нарочно. Python смята хеша на текст различно при всяко пускане на програмата, затова при теб щеше да е друго. Сравненията излизат едни и същи всеки път.

Методът, който прави числото, се казва хеш функция.

По-точно, за любопитните
  • Защо хешът на текст се сменя? Ако е известен предварително, някой може да прати на сървъра хиляди ключове с един и същ хеш и речникът да стане бавен. Затова Python избира случайна „сол“ при всяко пускане. Може да се фиксира с променливата на средата PYTHONHASHSEED, но в програма не се разчита на самото число.
  • Изключение при цели числа: hash(-1) е -2. В картата за колизиите ще видиш защо е интересно.
  • Криптографските хеш функции като SHA-256 са друго нещо. Те дават дълъг резултат и е практически невъзможно да намериш два текста с един и същ хеш. Затова с тях се проверява дали файл не е подменен и се пазят пароли. hash() е за бързо търсене и не дава такава защита.

Виж го

Кофите

Отвътре dict е масив от кофи (buckets). Номерът на кофата за ключа е остатъкът от хеша при деление на броя на кофите. Хешът на текст се сменя при всяко пускане, затова тук ключовете са номера на поръчки: при тях хешът е самото число:

keys = [1007, 2043, 3010, 4051]
buckets = 8
for key in keys:
    h = hash(key)
    index = h % buckets
    print(f"{key} -> {h} -> кофа {index}")
Стъпка по стъпка, с думи
  1. Четири ключа (номера на поръчки) и осем празни кофи с номера от 0 до 7.
  2. hash(1007) е самото число, 1007. Остатъкът при деление на 8 е 7: това е кофата.
  3. 2043 дава кофа 3.
  4. 3010 дава кофа 2.
  5. 4051 също е в кофа 3: колизия. Тук е нарисувана като верига, както в Java. dict в CPython вместо това търси друго свободно място.
  6. Търсене на 4051: същото число, същата кофа 3. == с 2043: не. С 4051: да.
  • Записът bookings[ключ] = … смята кофата и слага двойката там. Търсенето смята същата кофа и гледа само там. Затова е бързо и при милион ключа.
  • В Python % с положителен делител никога не дава отрицателно число, дори хешът да е отрицателен: -7 % 8 е 1. Номер на кофа не може да е отрицателен.
  • 2043 и 4051 попаднаха в кофа 3. Това се казва колизия. За нея е следващата карта.
По-точно, за любопитните
  • В CPython броят на кофите в речника също е степен на двойката и началото на търсенето е хешът, от който са взети последните битове. Това е бърз остатък при деление на броя на кофите.
print(-7 % 8)
Изход
1

Пробвай

В коя кофа?

Хешът на цяло число е самото число. Номерата на поръчките отиват в речник с 4 кофи.

Какво ще отпечата програмата?

order_ids = [6, 10, 13, 21]
for order_id in order_ids:
    print(f"{order_id} -> кофа {hash(order_id) % 4}")
Отговор

Идеята

Колизия: hash намира мястото, == намира ключа

Различните ключове може да имат един и същ хеш. В Python най-известният пример е с числа:

print(hash(-1), hash(-2))


codes = {}
codes[-1] = "минус едно"
codes[-2] = "минус две"
print(codes[-1], codes[-2])
Изход
-2 -2
минус едно минус две

Двата ключа имат един и същ хеш, но речникът не ги бърка. В CPython кофата не пази списък от двойки: ако мястото е заето от друг ключ, речникът пробва друго място по формула, докато не намери ключа или празно място. На всяко място сравнява ключовете с ==.

Така работят и двете стъпки:

  1. hash() казва откъде да търси.
  2. == казва кой от ключовете е търсеният.

Сега е ясно какво стана с мястото в театъра. Seat няма нито __eq__, нито __hash__, затова ползва тези по подразбиране от object. Там == е същото като is, а хешът е различен за всеки обект. Двата Seat(5, 12) са два различни обекта, затова са и два различни ключа.

Идеята

Договорът: __eq__ и __hash__ заедно

Seat трябва да каже кога две места са едно и също място (__eq__) и да даде еднакъв хеш на еднаквите (__hash__):

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number


    def __eq__(self, other):
        if not isinstance(other, Seat):
            return NotImplemented
        return self.row == other.row and self.number == other.number


    def __hash__(self):
        return hash((self.row, self.number))

Със същата програма като в първата карта:

bookings = {}
bookings[Seat(5, 12)] = "Мария"


print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Иван"
print(len(bookings))
Изход
Мария
1
1

Правилата, които Python очаква:

  • Ако a == b, тогава hash(a) == hash(b). Винаги.
  • Ако хешовете са равни, обектите може да са различни. Това е колизия.
  • Напишеш ли __eq__, напиши и __hash__, по същите атрибути.

Ако напишеш само __eq__, Python не те оставя да сбъркаш тихо. Той маха хеша на класа и такъв обект не може да е ключ:

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number


    def __eq__(self, other):
        if not isinstance(other, Seat):
            return NotImplemented
        return self.row == other.row and self.number == other.number
Грешка
TypeError: unhashable type: 'Seat'

bookings[Seat(5, 12)] = "Мария" спира с тази грешка: „unhashable“ значи „няма хеш“.

По-точно, за любопитните
  • hash((self.row, self.number)) е хешът на кортежа от атрибутите. Това е обичайният начин: кортежът смята хеш от всички елементи и от реда им, затова 5/12 и 12/5 имат различни хешове. Може и с формула, като в Java:
def __hash__(self):
    return 31 * self.row + self.number
  • isinstance проверява дали другият изобщо е Seat. Ако не е, NotImplemented казва на Python „не знам как да се сравня с това“, и тогава Seat(5, 12) == "5/12" е False.
  • За ключ от няколко стойности често не ти трябва клас: кортежът (5, 12) вече има == и хеш.
bookings = {}
bookings[(5, 12)] = "Мария"
print(bookings.get((5, 12)))
print(hash((5, 12)) == hash((12, 5)))
Изход
Мария
False

Пробвай

Намери грешката

Каталогът пази продуктите в set. Два продукта с един и същ код са един и същ продукт, дори цената да се е сменила. Но in с новата цена дава False:
catalog = set()
catalog.add(Product("A-100", 25.0))
# Цената е намалена, но продуктът е същият.
print(Product("A-100", 19.9) in catalog)
Изход
False

На кой ред в класа е грешката?

Избери реда с грешката.

Идеята

Кофите се пълнят

Когато двойките станат много, кофите стават дълги и търсенето се забавя. Затова dict расте:

  • В CPython малкият речник има 8 места.
  • Когато двойките станат повече от 2/3 от местата, той прави по-голяма таблица и преразпределя всички ключове. Мястото зависи от размера на таблицата, затова всеки ключ се смята наново. Ето кога расте, по паметта, която речникът заема:
import sys


prices = {}
size = sys.getsizeof(prices)
for i in range(1, 12):
    prices[f"продукт {i}"] = i
    if sys.getsizeof(prices) != size:
        size = sys.getsizeof(prices)
        print("Расте при", i, "двойки")
Изход
Расте при 1 двойки
Расте при 6 двойки
Расте при 11 двойки
  • Първият път е, когато се появи таблицата с 8 места. После расте при 6-ата двойка (5 са 2/3 от 8) и при 11-ата (10 са 2/3 от 16).
  • Затова средно записът и търсенето са бързи, а понякога един запис отнема повече време.

Има и капан. Ключът не бива да се променя, докато е в речника или в множеството:

seat = Seat(5, 12)
sold = set()
sold.add(seat)


seat.number = 13
print(seat in sold)
print(Seat(5, 12) in sold)
print(len(sold))
Изход
False
False
1
Мястото е сложено на мястото на 5/12. После номерът му стана 13 и хешът се смени. seat in sold търси на мястото на 5/13 и не го намира. Seat(5, 12) in sold търси на правилното място, но там обектът вече не е равен на 5/12. Елементът е вътре (размерът е 1), но не може да бъде намерен. В Python няма final: че атрибутите на ключа не се променят, е споразумение. Ключ, който наистина не може да се промени, е кортежът.
По-точно, за любопитните
  • sys.getsizeof дава колко байта заема самият речник. Тук служи само да се види кога таблицата се сменя.
  • set работи по същия начин, но пази само ключове.

Упражнение

Свои хешове

Реши задачите в редактора си.

1. Хеш на човек. Клас Person с име, фамилия и възраст. Напиши __eq__ и __hash__ по трите атрибута, с кортеж. Създай Иван Петров на 30 два пъти и веднъж на 31. Отпечатай дали хешовете на първите двама са равни, дали на първия и третия са равни, и колко различни хора остават в множество. Самите хешове не печатай: при текст те се сменят при всяко пускане.

Изход
True
False
Различни хора: 2

2. Роботът в склада. Роботът тръгва от клетка (0, 0) и изпълнява ходове NNEESWWN: N е нагоре (y + 1), S надолу, E надясно (x + 1), W наляво. Колко различни клетки е посетил, заедно с началната? Пази ги в множество от Point. С този клас програмата казва 9, а трябва да каже 7. Поправи го:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
Изход
Ходове: 8
Различни клетки: 7

3. Хеш на файл. Функция hash_file_content(file_path) чете файла и връща хеша на съдържанието му като шестнайсетичен текст. hash() тук не става: при следващото пускане същият файл ще има друг хеш. Ползвай SHA-256 от вградения модул hashlib: hashlib.sha256(content.encode("utf-8")).hexdigest(). Запиши три отчета: a.txt и b.txt с „Отчет за октомври: 1250 €“, c.txt с „Отчет за октомври: 1260 €“. Сравни хешовете им. Различни хешове значат различни файлове, а еднакви SHA-256 на практика значат еднакви файлове.

Изход
a.txt: 690871a6fdd1b9ecdd0ee92ba8da848997bc137f5712cbe02c9c3bcbc1c63a11
b.txt: 690871a6fdd1b9ecdd0ee92ba8da848997bc137f5712cbe02c9c3bcbc1c63a11
c.txt: 1d9642f8c4031aa37d607ee81164a672c1b3a76b70212a6da967d54fa5339247
a и b: еднакви
a и c: различни

Още задачи

  • Своя хеш таблица. Продължение на таблицата с потребители от миналия урок, този път без dict. Направи списък от 8 кофи, всяка е списък от двойки потребител–имейл. Хеш функцията е сумата от кодовете на символите в името (ord). Напиши add, get и метод, който печата колко двойки има във всяка кофа.
  • Идентификатор от имейл. generate_user_id(email) връща "U" и първите 8 знака от SHA-256 на имейла с малки букви. Еднакъв ли е идентификаторът за Ivan@Example.com и ivan@example.com? Защо тук не става с hash()? Може ли два различни имейла да получат един и същ идентификатор? Как ще го откриеш?
  • Броене на колизии. Сметни мястото на ключовете user1 … user1000 с hash(ключ) % n при 16, 64 и 1024 кофи и преброй колко ключа попадат в кофа, в която вече има ключ. Пусни програмата два пъти: броят се мени малко, защото хешът на текст се сменя.
  • Кутията за обувки. Клас Box с ширина, височина и дълбочина. Две кутии са еднакви, ако размерите им са еднакви в същия ред. Напиши __eq__ и __hash__ с кортеж и провери кутиите 30×20×10 и 10×20×30 в множество.

Тест

Провери се

1. Какво прави dict с хеша на ключа?
2. Два различни ключа имат един и същ хеш. Какво става?
3. a == b е True. Какво трябва да е вярно за хешовете им?
4. Слагаш свой клас Seat като ключ, без __eq__ и __hash__. Какво връща bookings.get(Seat(5, 12))?
5. Seat има __eq__, но няма __hash__. Какво става при bookings[Seat(5, 12)] = "Мария"?
6. Кой атрибут е безопасно да е част от __hash__ на ключ?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·