Haszowanie — odcisk palca tekstu

🎯 Po co Ci to?

Pobierasz duży plik, a strona podaje obok dziwny ciąg: sha256: 9f86d081…. Po co? Żebyś mógł sprawdzić — w ułamku sekundy — czy Twoje gigabajty są co do bitu identyczne z oryginałem. Porównywać bajt po bajcie z serwerem? Absurd. Zamiast tego obie strony liczą krótki „odcisk palca" i porównują odciski. Ten pomysł — zamień dowolnie długie dane na krótką liczbę, która niemal na pewno je identyfikuje — nazywa się haszowaniem i jest jednym z najbardziej wielokrotnego użytku pomysłów informatyki: przyspiesza wyszukiwanie wzorca, wykrywa uszkodzone pliki i strzeże haseł (dział 16 dopowie jak).

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • policzyć prostą funkcję haszującą tekst i wyjaśnić, czym jest kolizja;
  • zastosować haszowanie do wyszukiwania wzorca (idea porównywania odcisków);
  • wskazać zastosowania haszy: sumy kontrolne, szybkie porównania, przechowywanie haseł.

🔁 Przypomnij sobie

Z 2.5: znak ma numer; z 5.2: naiwne wyszukiwanie porównuje okno ze wzorcem znak po znaku; z 4.6: mod trzyma liczby w ryzach.

📘 Wyjaśnienie

📐 DEFINICJA — funkcja haszująca (hasz): funkcja zamieniająca dane dowolnej długości na liczbę ze stałego, niewielkiego zakresu, tak by (1) ten sam tekst zawsze dawał ten sam wynik, (2) różne teksty „prawie zawsze" dawały różne wyniki.

Po ludzku: odcisk palca: krótki, łatwy do porównania, praktycznie jednoznaczny. Czym NIE jest: szyfrem! Z odcisku nie da się odtworzyć tekstu (za mało informacji: tekstów jest nieskończenie wiele, odcisków — skończenie). Hasz gubi informację celowo.

Najprostszy hasz zbudujesz z tego, co masz: zsumuj numery znaków i weź resztę:

def hasz(tekst, M=1000):
    suma = 0
    for znak in tekst:
        suma = suma + ord(znak)
    return suma % M

hasz("kot") = $(107 + 111 + 116) \bmod 1000 = 334$. Działa… ale ma wadę, którą wykryjesz od razu: hasz("kto") = też 334. Suma nie widzi kolejności — wszystkie anagramy (5.1!) dostają wspólny odcisk. Dwa różne teksty o tym samym haszu to kolizja; tu kolizje są masowe i przewidywalne, a to dyskwalifikacja. Lepsza rodzina haszy mnoży bieżący wynik przez stałą podstawę, zanim doda kolejny znak:

def hasz(tekst, M=10**9 + 7):
    w = 0
    for znak in tekst:
        w = (w * 31 + ord(znak)) % M
    return w

Poznajesz wzorzec w = w * x + c? To schemat Hornera (4.5)! Tekst jest traktowany jak liczba zapisana w systemie o podstawie 31, redukowana mod M w locie (żeby nie puchła — sztuczka z 4.6). Teraz „kot" i „kto" dostają różne odciski, bo pozycja znaku ma wagę — kolejna cegła z poprzednich działów wskoczyła na miejsce.

Kolizje jednak nie znikają nigdy: tekstów jest nieskończenie wiele, a odcisków co najwyżej $M$ — szufladek mniej niż listów (ta sama arytmetyka, którą w 2.6 dowodziłeś, że nie ma cudownej kompresji!). Dobry hasz sprawia tylko, że kolizje są rzadkie i nieprzewidywalne. Dlatego protokół użycia zawsze brzmi: równe odciski → sprawdź naprawdę; różne odciski → na pewno różne teksty. Ta asymetria to serce wszystkich zastosowań.

Wyszukiwanie wzorca odciskami. Wróćmy do problemu z 5.2: wzorzec $m$-znakowy w tekście. Zamiast porównywać okno ze wzorcem znak po znaku — porównuj odciski: policz hasz wzorca raz, a potem hasz każdego okna; pełne porównanie rób tylko przy zgodności odcisków. Zysk? Na razie żaden — policzenie hasza okna kosztuje tyle, co porównanie. Ale tu wchodzi trik, dla którego ta idea nosi nazwisko Rabina i Karpa: hasz okna przesuniętego o jeden znak da się zaktualizować ze starego w kilku operacjach (odejmij wkład znaku, który wypadł z okna, domnóż podstawę, dodaj nowy znak — wszystko mod M). Jedno okno — kilka operacji, niezależnie od $m$. Cały tekst — koszt liniowy, a $n \cdot m$ z metody naiwnej zostaje w pobitym polu na złośliwych danych. Szczegóły aktualizacji zostawiamy bibliotekom; idea — odcisk zamiast treści, aktualizowany zamiast liczony od nowa — jest tym, co masz wynieść.

💭 Pomyśl: Serwis pobierania podaje hasz pliku. Ściągasz plik, liczysz hasz — zgadza się. Czy masz pewność, że plik jest nieuszkodzony? A czy masz pewność, że nie jest złośliwie podmieniony?

Sprawdź odpowiedź

Uszkodzenie losowe (przekłamany bit w transmisji): zgodny hasz daje pewność praktyczną — szansa, że przypadkowe uszkodzenie trafi w kolizję, jest astronomicznie mała. Podmiana złośliwa to inna liga: przeciwnik może celowo szukać pliku o tym samym haszu. Przeciw temu zwykłe hasze (jak nasz Hornerowski) są bezbronne — potrzebne są hasze kryptograficzne (rodzina SHA), projektowane tak, by znalezienie kolizji było obliczeniowo beznadziejne. I jeszcze jedno: jeśli napastnik kontroluje stronę, podmieni i plik, i opublikowany hasz — sam odcisk nie mówi, kto go złożył. Tę lukę domknie podpis elektroniczny w następnej jednostce.

⚠️ Uwaga, pułapka

„Różne hasze ⇒ różne dane" jest twierdzeniem; „równe hasze ⇒ równe dane" jest skrótem myślowym, prawdziwym tylko statystycznie. Program, który po zgodności odcisków nie robi już nic, jest szybki i subtelnie błędny — raz na wiele milionów porównań skłamie, a Ty nigdy nie dowiesz się kiedy. W zastosowaniach „szybkie porównywanie" zawsze planuj weryfikację; pomijać wolno ją tylko tam, gdzie świadomie akceptujesz ryzyko (i umiesz je oszacować).

🌍 Powiązania

Haszowanie spotkasz jeszcze w tej książce dwa razy: w dziale 12 (bazy danych błyskawicznie znajdują rekord, bo hasz klucza wskazuje szufladkę — to tzw. tablice haszujące, najczęściej używana struktura danych świata) i w dziale 16 (serwisy nie przechowują Twojego hasła, lecz jego hasz — dlatego „przypomnienie hasła" to zawsze reset, nigdy odesłanie). A sumy kontrolne haszopodobne siedzą w numerze PESEL, kodach kreskowych i numerach kont bankowych — ostatnia cyfra to strażnik literówek.

🛠️ Teraz Ty

Z komputerem: zaimplementuj oba hasze; znajdź eksperymentalnie kolizję hasza sumacyjnego (podpowiedź: anagramy masz z 5.1), a potem sprawdź, czy Hornerowski ją rozbija. Bez komputera: policz hasz Hornerowski słowa „ab" ($M = 100$, podstawa 31, kody: a = 97, b = 98) i słowa „ba" — różne?

📐 Definicje tej lekcji

  • Hasz / kolizja — krótki odcisk danych; dwa różne teksty o wspólnym odcisku.
  • Hasz Hornerowski — w = (w * podstawa + kod_znaku) % M; pozycyjny, rozbija anagramy.
  • Protokół odcisków — różne hasze: na pewno różne dane; równe hasze: zweryfikuj naprawdę.

📌 Najważniejsze w pigułce

  • Hasz gubi informację celowo — dlatego jest krótki i dlatego kolizje są nieuniknione; sztuką jest ich rzadkość.
  • Suma znaków to zły hasz (anagramy!); mnożenie przez podstawę daje pozycji wagę — Horner po raz trzeci.
  • Odciski przyspieszają porównywanie i wyszukiwanie; przy zgodności — weryfikuj; przeciw złośliwym kolizjom — hasze kryptograficzne.

🎒 Zadania

  1. Policz ręcznie hasz sumacyjny ($M = 100$) słów: „lis", „sil", „los". Które kolidują i dlaczego? Zaproponuj czwarte słowo kolidujące z „los" niebędące jego anagramem.
Wskazówka i odpowiedź

lis: $108+105+115 = 328 \to 28$; sil: te same litery → 28 (kolizja anagramowa); los: $108+111+115 = 334 \to 34$. Czwarte słowo: potrzebna suma kodów $\equiv 34 \pmod{100}$ — np. „mit" ($109+105+116 = 330 \to 30$, nie)… szukaj: „lot" = $108+111+116 = 335 \to 35$, blisko; „kos" = $107+111+115 = 333 \to 33$; „kot" = $107+111+116 = 334 \to 34$ ✓ — „kot" koliduje z „los" bez żadnego pokrewieństwa. Kolizje sumacyjne są tak gęste, że znajduje się je ręcznie w minutę — właśnie dlatego ten hasz nadaje się tylko do nauki.

  1. W tablicy haszującej o $M = 1000$ szufladek umieszczono 2000 tekstów. Czy kolizje są możliwe, pewne, czy prawdopodobne? A przy 500 tekstach?
Wskazówka i odpowiedź

2000 listów, 1000 szufladek: kolizje pewne (zasada szufladkowa — co najmniej jedna szufladka ma ≥2 listy). Przy 500 tekstach: możliwe i wcale prawdopodobne — to słynny „paradoks dnia urodzin": już przy ~$\sqrt{M} \approx 38$ tekstach szansa jakiejkolwiek kolizji przekracza 50%! Dlatego praktyczne $M$ liczy się w miliardach, a projektant zawsze zakłada, że kolizje będą, i pisze obsługę (np. lista tekstów w szufladce).

  1. Zaprojektuj (opisowo) system sprawdzania, czy dwa duże pliki na dwóch końcach świata są identyczne, przesyłając jak najmniej danych. Uwzględnij: co przesyłasz, co porównujesz, co robisz przy zgodności i niezgodności, oraz słabe punkty.
Wskazówka i odpowiedź

Obie strony liczą hasz (kryptograficzny) swojego pliku; przesyłasz sam odcisk (dziesiątki bajtów). Różne → pliki na pewno różne, koniec (ewentualnie: potnij plik na bloki, haszuj bloki i binarnie szukaj różnicy — tak działają narzędzia synchronizacji). Równe → praktycznie identyczne; jeśli stawka jest najwyższa (prawo, finanse), można dodatkowo porównać rozmiary i drugi, niezależny hasz. Słabe punkty: zaufanie do kanału (kto przysłał odcisk? — podpis!), no i kolizje celowe przy słabym haszu. Właśnie opisałeś szkielet działania kopii zapasowych i kontroli wersji.

🔍 Sprawdź, czy umiesz

  • Policzyć hasz Hornerowski krótkiego słowa na kartce.
  • Wyjaśnić nieuchronność kolizji zasadą szufladkową i podać protokół postępowania.
  • Opisać, jak odciski przyspieszają wyszukiwanie wzorca i porównywanie plików.

Ucz się tej jednostki z asystentem