10.1 Wprowadzenie do funkcji hashujących i tablic mieszających
Przypomnijmy sobie i pogłębmy nasze zrozumienie funkcji hashujących i tablic mieszających. Funkcja hashująca to algorytm, który przekształca dane wejściowe o dowolnej długości w ciąg o stałej długości. Główne właściwości funkcji hashujących:
- Deterministyczność: takie same dane wejściowe zawsze dają taki sam wynik.
- Szybkie obliczanie: hash powinien być obliczany wystarczająco szybko.
- Nieodwracalność (dla kryptograficznych funkcji hashujących): z hasha nie można (lub jest to ekstremalnie trudne) odzyskać danych wejściowych.
- Równomierne rozłożenie: niewielkie zmiany w danych wejściowych prowadzą do znacznych zmian w hashach.
W uproszczeniu, ta funkcja u identycznych obiektów zawsze się zgadza, ale jeśli dwie funkcje hashujące dla obiektów są takie same, to te obiekty nie muszą być równe. W matematyce nazywa się to warunkiem koniecznym, ale niewystarczającym.
Tablica mieszająca to struktura danych, która używa funkcji hashującej do efektywnego przechowywania i wyszukiwania informacji. Składa się z:
- Tablicy "koszyków" do przechowywania danych.
- Funkcji hashującej, która określa, do którego koszyka umieścić dane.
Tablice mieszające zapewniają szybki dostęp do danych, zazwyczaj z złożonością O(1) w przypadku średnim.
Zastosowanie funkcji hashujących w rzeczywistości
Przykład: Technologie blockchain
W blockchainie funkcje hashujące są używane do tworzenia unikalnych identyfikatorów bloków i zapewnienia integralności danych. Każdy blok zawiera hash poprzedniego bloku, co tworzy łańcuch i czyni system odpornym na zmiany.
import hashlib
import time
class Block:
def __init__(self, data, previous_hash):
self.timestamp = time.time()
self.data = data
self.previous_hash = previous_hash
self.hash = self.calculate_hash()
def calculate_hash(self):
hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
return hashlib.sha256(hash_string.encode()).hexdigest()
# Przykład użycia
block1 = Block("Transakcja 1", "0")
block2 = Block("Transakcja 2", block1.hash)
print(f"Hash bloku 1: {block1.hash}")
print(f"Hash bloku 2: {block2.hash}")
Porównanie wydajności
Rozważmy zadanie wyszukiwania duplikatów w tablicy. Porównajmy rozwiązanie z użyciem tablicy mieszającej i bez niej:
import time
def find_duplicates_with_hash(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
def find_duplicates_without_hash(arr):
duplicates = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j] and arr[i] not in duplicates:
duplicates.append(arr[i])
return duplicates
# Test wydajności
arr = list(range(10000)) + list(range(5000)) # Tablica z duplikatami
start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Czas wykonania z tablicą mieszającą: {end - start} sekund")
start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Czas wykonania bez tablicy mieszającej: {end - start} sekund")
Uruchom program i przekonaj się, jak bardzo użycie tablicy mieszającej przyspiesza wyszukiwanie duplikatów. Zwłaszcza w dużych zbiorach danych.
10.2 Przykłady zastosowania funkcji hashujących w rzeczywistych zadaniach
1. Hashowanie haseł
Funkcje hashujące są używane do bezpiecznego przechowywania haseł. Zamiast przechowywać hasła w postaci jawnej, systemy przechowują ich hashe. Podczas wprowadzania hasła przez użytkownika system hashuje wprowadzone hasło i porównuje je z hashem przechowywanym w bazie danych.
Przykład implementacji:
import hashlib
def hash_password(password):
return hashlib.sha256(password.encode()).hexdigest()
# Przykład użycia:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash hasła: {hashed_password}")
2. Kontrola integralności danych
Funkcje hashujące są używane do sprawdzania integralności plików i danych. Na przykład, aby sprawdzić, czy plik nie został zmieniony lub uszkodzony podczas przesyłania.
Przykład implementacji:
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()
# Przykład użycia:
file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash pliku: {file_hash}")
3. Wyszukiwarki i indeksowanie
Wyszukiwarki używają funkcji hashujących do tworzenia indeksów i szybkiego wyszukiwania informacji. Każdy dokument jest indeksowany według słów kluczowych, a funkcje hashujące pomagają szybko znajdować dokumenty zawierające określone słowa.
Przykład implementacji:
def create_index(text):
index = {}
words = text.split()
for word in words:
word_hash = hash(word)
if word_hash not in index:
index[word_hash] = []
index[word_hash].append(word)
return index
# Przykład użycia:
text = "This is an example text for indexing"
index = create_index(text)
print(f"Indeks: {index}")
10.3 Optymalizacja wyszukiwania z użyciem funkcji hashujących
1. Użycie tablic mieszających do wyszukiwania duplikatów
Tablice mieszające pozwalają szybko znajdować duplikaty w tablicy, porównując wartości hash elementów.
Przykład implementacji:
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Przykład użycia:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Output: [2, 4]
2. Optymalizacja wyszukiwania par z określoną sumą
Tablice mieszające pozwalają efektywnie znajdować pary liczb w tablicy, których suma jest równa danej wartości.
Przykład implementacji:
def find_pairs_with_sum(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
# Przykład użycia:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Output: [(4, 2), (8, -2)]
10.4 Przykłady użycia funkcji hashujących w różnych algorytmach
1. Liczenie liczby słów w tekście
Użyj tablicy mieszającej do liczenia liczby wystąpień każdego słowa w tekście.
Przykład implementacji:
def count_words(text):
word_count = {}
words = text.split()
for word in words:
if word in word_count:
word_count[word] += 1
else:
word_count[word] = 1
return word_count
# Przykład użycia:
text = "this is a test this is only a test"
print(count_words(text)) # Output: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}
2. Sprawdzanie przecięcia dwóch tablic
Sprawdź, czy dwie tablice się przecinają (czy mają co najmniej jeden wspólny element).
Przykład implementacji:
def has_intersection(arr1, arr2):
set1 = set(arr1)
for item in arr2:
if item in set1:
return True
return False
# Przykład użycia:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2)) # Output: True
print(has_intersection(arr1, arr3)) # Output: False
3. Sprawdzanie unikalności elementów w tablicy
Sprawdź, czy w tablicy znajdują się tylko unikalne elementy.
Przykład implementacji:
def all_unique(arr):
seen = set()
for item in arr:
if item in seen:
return False
seen.add(item)
return True
# Przykład użycia:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1)) # Output: True
print(all_unique(arr2)) # Output: False
GO TO FULL VERSION