Pojęcie funkcji skrótu

5.1 Definicja funkcji skrótu i jej zastosowanie

Funkcja skrótu to funkcja, która przyjmuje dane wejściowe (lub klucz) i zwraca stały rozmiar bitów, zwykle nazywany skrótem lub wartością skrótu. Głównym celem funkcji skrótu jest efektywne rozmieszczanie danych w tabeli skrótów, zapewniając szybki dostęp do elementów.

Zastosowanie:

• Tabele skrótów: Używane do implementacji asocjacyjnych tablic (słowniki w Pythonie), zapewniającego szybki dostęp do danych po kluczu.
• Kontrola integralności danych: Funkcje skrótu stosowane są do sprawdzania integralności plików i danych (np. algorytmy MD5, SHA-1, SHA-256).
• Kryptografia: Funkcje skrótu używane są w algorytmach kryptograficznych do szyfrowania i tworzenia podpisów cyfrowych.
• Wyszukiwarki: Stosowane do indeksowania danych i szybkiego wyszukiwania informacji.
• Zarządzanie cachem: Używane do organizacji cache, aby szybko odnajdywać dane.

Przykład zastosowania funkcji skrótu w Pythonie:

# Przykład użycia funkcji skrótu w Pythonie dla tabeli skrótów (słownika)
data = {"apple": 1, "banana": 2, "cherry": 3}

# Pobranie wartości skrótu klucza
key = "banana"
hash_value = hash(key)

print(f"Wartość skrótu dla klucza '{key}': {hash_value}")

5.2 Analogii z życia codziennego

Za pomocą funkcji skrótu można podzielić dużą grupę obiektów na mniej więcej równe grupy. Co więcej, jeśli będziemy dodawać nowe obiekty, będą się one dalej równomiernie rozdzielać pomiędzy grupy.

Załóżmy, że masz 1000 osób i musisz rozdzielić je na 30 grup. Oto jak można to zrobić.

Sposób 1. Według pierwszej litery imienia.

Pierwsza grupa — to ci, których imię zaczyna się na „A”, druga grupa — to ci, których imię zaczyna się na „B”, i tak dalej. Zasada „Twoja grupa to pierwsza litera twojego imienia” — to właśnie funkcja skrótu. Jednak z taką funkcją skrótu ryzykujemy mieć wiele osób w grupie „A” i mało w „E”.

Sposób 2. Według daty urodzenia.

Urodzony pierwszego dnia miesiąca — pierwsza grupa, drugiego — druga, i tak dalej. Będzie 31 grup. W 31. grupie będzie mniej więcej dwa razy mniej osób niż w pozostałych, ale osoby w takich grupach są znacznie bardziej równomiernie rozdzielone niż w pierwszym przypadku.

Sposób 3. Numer telefonu

Idealna opcja — to uzyskać taką liczbę, która byłaby, z jednej strony, maksymalnie losowa (wtedy takie liczby będą równomiernie rozdzielone), z drugiej — musi być szybko obliczalna i zawsze taka sama.

Weźmy ostatnie 4 cyfry numeru telefonu — to będzie 10 000 wariantów. Następnie podzielimy tę liczbę przez 30. Wtedy będziemy mieć 30 możliwych reszt: 0, 1, 2, ..., 29. To będą numery naszych grup.

Przydatne! Przy okazji, prawie każda funkcja skrótu używa reszty z dzielenia — to bardzo proste i pozwala regulować liczbę grup, na które należy podzielić elementy.

5.3 Główne cechy funkcji skrótu

Główne cechy dobrej funkcji skrótu:

Deterministyczność: Ta sama funkcja skrótu zawsze powinna zwracać tę samą wartość skrótu dla tego samego wejścia.

Przykład:

key = "example"
assert hash(key) == hash(key)

Ważne! Operator assert sprawdza, czy wyrażenie po jego prawej stronie jest prawdziwe True. Jeśli wyrażenie jest fałszywe False, wyrzucane jest wyjątek.

Równomierność: Dobra funkcja skrótu powinna równomiernie rozkładać wartości w całym zakresie możliwych wartości skrótu, aby uniknąć kolizji.

Przykład z życia programisty Pythona: W słowniku (klasa dict) Pythona funkcja skrótu hash() równomiernie rozkłada klucze.

Efektywność obliczeniowa: Funkcja skrótu powinna być szybka i efektywna, aby nie spowalniać operacji wstawiania i wyszukiwania.

Przykład z życia programisty Pythona: Standardowe funkcje skrótu w Pythonie są zaimplementowane do pracy z kluczami różnych typów, takich jak ciągi znaków i liczby.

Minimalizacja kolizji: Kolizja występuje, gdy dwa różne klucze mają taką samą wartość skrótu. Dobra funkcja skrótu powinna minimalizować prawdopodobieństwo kolizji.

Przykład z życia programisty Pythona: Algorytm SHA-256 minimalizuje prawdopodobieństwo kolizji przy tworzeniu skrótu danych.

Rozkład skrótów: Dla dużych objętości danych funkcja skrótu powinna zapewnić równomierne rozkładanie wartości skrótu po całej tabeli skrótów.

Przykład z życia programisty Pythona: Standardowe funkcje skrótu w Pythonie dobrze radzą sobie z rozkładem kluczy w tabelach skrótów.

5.4 Przykłady funkcji skrótu i ich implementacja

Funkcje skrótu przyjmują na wejście dane o dowolnym rozmiarze i zwracają stały rozmiar wartości skrótu. Przyjrzyjmy się kilku przykładom funkcji skrótu i ich implementacji.

Przykład 1: Prosta funkcja skrótu dla ciągów znaków

Jedna z najprostszych funkcji skrótu dla ciągów znaków może być zrealizowana z użyciem sumy kodów znaków ciągu:

def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 1000  # Przyjmijmy, że nasza tabela ma rozmiar 1000

# Przykład użycia:
key = "example"
print(f"Wartość skrótu dla klucza '{key}': {simple_hash(key)}")

Przykład 2: Funkcja skrótu dla ciągów znaków z użyciem haszowania wielomianowego

Haszowanie wielomianowe jest bardziej skomplikowaną, ale efektywną techniką:

def polynomial_hash(key, a=33, m=1000):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * a + ord(char)) % m
    return hash_value

# Przykład użycia:
key = "example"
print(f"Wartość skrótu dla klucza '{key}': {polynomial_hash(key)}")

Przykład 3: Wbudowana funkcja skrótu w Pythonie

Python oferuje wbudowaną funkcję hash() do uzyskiwania wartości skrótu dla różnych typów danych:

key = "example"
print(f"Wartość skrótu dla klucza '{key}': {hash(key)}")

Przykład 4: Kryptograficzna funkcja skrótu (SHA-256)

Kryptograficzne funkcje skrótu, takie jak SHA-256, używane są do zapewnienia bezpieczeństwa danych:

import hashlib

def sha256_hash(key):
    return hashlib.sha256(key.encode()).hexdigest()

# Przykład użycia:
key = "example"
print(f"Wartość skrótu dla klucza '{key}': {sha256_hash(key)}")

5.5 Wprowadzenie do haszowania i jego zastosowanie

Haszowanie — to proces przekształcania danych wejściowych o dowolnym rozmiarze na stały rozmiar wartości skrótu przy użyciu funkcji skrótu. Haszowanie jest szeroko stosowane w naukach komputerowych i programowaniu do optymalizacji i zapewnienia bezpieczeństwa.

Główne zastosowania haszowania:

1. Tabele skrótów (słowniki): Tabele skrótów używają funkcji skrótu do organizacji i szybkiego dostępu do danych.

data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"Wartość skrótu dla klucza '{key}': {hash_value}")

2. Kontrola integralności danych: Funkcje skrótu służą do sprawdzania integralności plików i danych.

Przykład: Sprawdzanie integralności pliku przy użyciu SHA-256:

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

file_hash = get_file_hash('example.txt')
print(f"SHA-256 skrót pliku: {file_hash}")

3. Kryptografia i bezpieczeństwo: Funkcje skrótu stosowane są do tworzenia prymitywów kryptograficznych, takich jak podpisy cyfrowe i skróty haseł.

Przykład: Haszowanie hasła przy użyciu SHA-256:

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

password = "securepassword"
hashed_password = hash_password(password)
print(f"Skrót hasła: {hashed_password}")

4. Wyszukiwarki i indeksacja: Haszowanie stosowane jest do tworzenia indeksów i szybkiego wyszukiwania danych.

Przykład: Tworzenie indeksu do wyszukiwania tekstu:

def create_index(text):
    index = {}
    for word in text.split():
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

text = "This is an example text for indexing"
index = create_index(text)
print(f"Indeks: {index}")

5. Zarządzanie cachem: Haszowanie używane jest do organizacji cache, aby szybko odnajdywać dane.

Przykład: Prosty cache z użyciem funkcji skrótu:

cache = {}

def get_from_cache(key):
    hash_key = hash(key)
    return cache.get(hash_key, None)

def add_to_cache(key, value):
    hash_key = hash(key)
    cache[hash_key] = value

# Dodawanie i pobieranie danych z cache
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key"))  # Wyjście: test_value