Junior
Czym jest tablica haszująca?
sobes.tech AI
Odpowiedź od AI
Tablica haszowa to struktura danych, która implementuje tablicę asocjacyjną (słownik). Przechowuje pary "klucz-wartość", gdzie klucze są unikalne.
Podstawowe zasady:
- Funkcja haszująca: Zamienia klucz na liczbę (kod haszujący lub indeks). Ten indeks wskazuje miejsce przechowywania wartości w tablicy (koszu).
- Tablica (kosze): Rzeczywiste przechowywanie par "klucz-wartość".
- Kolizje: Sytuacja, gdy różne klucze generują ten sam kod haszujący.
Rozwiązanie kolizji:
- Metoda łańcuchowa (separate chaining): W każdym koszu przechowywana jest lista (lub inna struktura danych) elementów z tym samym kodem haszującym.
- Adresowanie otwarte (open addressing): W przypadku kolizji, poszukiwanie wolnego kosza odbywa się z użyciem różnych strategii (sondowanie liniowe, kwadratowe, podwójne haszowanie).
Charakterystyka:
- Szybki dostęp: W idealnym przypadku O(1) dla operacji wstawiania, wyszukiwania i usuwania.
- Zależność od funkcji haszującej: Jakość funkcji haszującej i strategia rozwiązywania kolizji mają duży wpływ na wydajność.
- Zużycie pamięci: Wymaga dodatkowej pamięci na tablicę koszy.
Zastosowanie w QA:
- Przechowywanie danych testowych (klucz - nazwa parametru, wartość - oczekiwana lub faktyczna wartość).
- Sprawdzanie unikalności elementów (np. ID użytkowników).
- Implementacja pamięci podręcznych.