Haszowanie odnosi się do procesu generowania wyniku o stałym rozmiarze z danych wejściowych o zmiennym rozmiarze przy użyciu wzorów matematycznych znanych jako funkcje mieszające. Technika ta określa indeks lub lokalizację przechowywania elementu w strukturze danych.
Potrzeba struktury danych Hash
Ilość danych w Internecie rośnie wykładniczo z każdym dniem, co utrudnia ich efektywne przechowywanie. W codziennym programowaniu ta ilość danych może nie być aż tak duża, ale mimo to należy ją przechowywać, uzyskiwać do niej dostęp oraz przetwarzać ją łatwo i wydajnie. Bardzo popularną strukturą danych wykorzystywaną w tym celu jest struktura danych Array.
Teraz pojawia się pytanie, czy Array już tam był, jaka była potrzeba nowej struktury danych! Odpowiedź na to pytanie kryje się w słowie efektywność. Chociaż przechowywanie w Array zajmuje O(1) czasu, szukanie w nim zajmuje przynajmniej O(log n) czas. Czas ten wydaje się niewielki, jednak w przypadku dużego zbioru danych może przysporzyć sporo problemów, a to z kolei powoduje, że struktura danych Array jest nieefektywna.
Zatem teraz szukamy struktury danych, która będzie w stanie przechowywać dane i wyszukiwać w nich dane w czasie stałym, tj O(1) czas. W ten sposób w grę wchodzi struktura danych Hash. Dzięki wprowadzeniu struktury danych Hash możliwe jest teraz łatwe przechowywanie danych w stałym czasie i ich odzyskiwanie również w stałym czasie.
Składniki haszowania
Istnieją trzy główne elementy mieszania:
Java równa się metoda
- Klucz: A Klucz może być dowolnym ciągiem znaków lub liczbą całkowitą podawaną jako dane wejściowe funkcji skrótu. Jest to technika określająca indeks lub lokalizację przechowywania elementu w strukturze danych.
- Funkcja skrótu: The funkcja skrótu otrzymuje klucz wejściowy i zwraca indeks elementu w tablicy zwanej tablicą mieszającą. Indeks jest tzw indeks skrótu .
- Tabela mieszająca: Tabela mieszająca to struktura danych, która odwzorowuje klucze na wartości za pomocą specjalnej funkcji zwanej funkcją mieszającą. Hash przechowuje dane w sposób asocjacyjny w tablicy, w której każda wartość danych ma swój własny, unikalny indeks.
Składniki haszowania
Co to jest kolizja?
Proces mieszania generuje małą liczbę dla dużego klucza, więc istnieje możliwość, że dwa klucze mogą dać tę samą wartość. Sytuacja, w której nowo wstawiony klawisz jest mapowany na już zajęty i należy go obsłużyć za pomocą technologii obsługi kolizji.
Kolizja w hashowaniu
Zalety haszowania w strukturach danych
- Obsługa klucz-wartość: Haszowanie idealnie nadaje się do implementowania struktur danych typu klucz-wartość.
- Szybkie odzyskiwanie danych: Haszowanie pozwala na szybki dostęp do elementów o stałej złożoności czasowej.
- Efektywność: Operacje wstawiania, usuwania i wyszukiwania są bardzo wydajne.
- Redukcja zużycia pamięci: Haszowanie wymaga mniej pamięci, ponieważ przydziela stałą przestrzeń do przechowywania elementów.
- Skalowalność: Haszowanie dobrze radzi sobie z dużymi zbiorami danych, zachowując stały czas dostępu.
- Bezpieczeństwo i szyfrowanie: Haszowanie jest niezbędne do bezpiecznego przechowywania danych i weryfikacji integralności.
Aby dowiedzieć się więcej na temat haszowania, zapoznaj się z Wprowadzenie do haszowania – samouczki dotyczące struktury danych i algorytmów