W strukturze danych, haszowanie jest techniką mapowania dużej liczby elementów danych do mniejszych tabel za pomocą specjalnej funkcji zwanej funkcją Hash dla szybszego dostępu. Czasami struktura danych jest tak ogromna, że staje się prawie niemożliwe, aby przeszukać wszystkie wartości indeksu przez wszystkie poziomy, aby uzyskać dostęp do końcowego bloku danych. To jest miejsce, w którym hashowanie przychodzi w prawo. To, co robi, to oblicza lokalizację rekordu danych na dysku bezpośrednio bez użycia struktury indeksu. Adres każdego rekordu jest określany za pomocą algorytmu haszującego, który przekształca wartość klucza głównego w adres rekordu. Istnieją więc dwie kategorie indeksowania dostępne przy użyciu funkcji haszujących – haszowanie dynamiczne i haszowanie statyczne.
Czym jest haszowanie statyczne?
Statyczne haszowanie jest metodą haszowania, w której stała liczba wiaderek jest przypisana do pliku w celu przechowywania rekordów. Liczba wiaderek jest wstępnie przydzielona, więc gdy dostarczana jest wartość klucza wyszukiwania, funkcja haszująca zawsze oblicza ten sam adres. Strona pliku może być postrzegana jako kolekcja wiaderek, z jedną stroną główną i dodatkowymi stronami przepełnienia. W przypadku statycznego haszowania mechanizmem lokalizacji jest funkcja haszująca i nie są zaangażowane żadne struktury danych. Tutaj wpisy indeksu są randomizowane w taki sposób, że liczba wpisów indeksu w każdym wiadrze jest mniej więcej taka sama. Istnieją jednak pewne minusy tego schematu również. Jeśli początkowa liczba kubełków jest zbyt mała i plik rośnie, wydajność ulega pogorszeniu z powodu przepełnienia kubełków. Z drugiej strony, jeśli jest zbyt duża, dużo miejsca jest przydzielane na przewidywany wzrost i znaczna ilość miejsca idzie na marne.
Co to jest Dynamic Hashing?
Dynamiczne hashowanie, z drugiej strony, jest techniką używaną do pokonania ograniczeń w statycznym hashowaniu, takich jak przepełnienie wiadra. W przeciwieństwie do statycznego haszowania, pozwala na dynamiczne zmiany liczby wiaderek, aby dostosować się do wzrostu lub kurczenia się plików bazy danych. Pozwala to na modyfikację funkcji haszującej na żądanie, co jest dobre dla baz danych, które rosną i kurczą się w rozmiarze. W miarę dodawania i usuwania wierszy zmienia odpowiednio liczbę wiader, aby zminimalizować przepełnienie wiader. Osadza obsługę rekordów przepełnienia w swojej podstawowej przestrzeni adresowej dynamicznie, aby uniknąć zarządzania obsługą wiaderek przepełnienia. Dwie powszechnie stosowane formy dynamicznego haszowania to liniowe haszowanie i rozszerzalne haszowanie. Rozszerzalne hashowanie jest popularną techniką, która obsługuje przepełnienie wiadra poprzez podział wiadra na dwa, dystrybuując rekordy pomiędzy starym i nowym wiadrem. Haszowanie liniowe to kolejna popularna forma dynamicznego haszowania, która pozwala na dynamiczny wzrost lub kurczenie się pliku haszującego poprzez przydzielanie nowych wiaderek.
Różnica między dynamicznym i statycznym Hashingiem
Technika
– Hashing statyczny jest metodą haszowania, w której stała liczba wiaderek jest przypisana do pliku w celu przechowywania rekordów, co oznacza, że używa funkcji haszującej, w której liczba adresów wiaderek jest stała. Tutaj wpisy indeksowe są randomizowane w taki sposób, że liczba wpisów indeksowych w każdym wiadrze jest mniej więcej taka sama. Z kolei Dynamic Hashing pozwala na dynamiczną zmianę liczby kubełków w celu dostosowania do wzrostu lub kurczenia się plików bazy danych.
Wydajność
– Jeśli początkowa liczba kubełków jest zbyt mała, a plik rośnie, wydajność spada z powodu przepełnienia kubełków. Z drugiej strony, jeśli jest zbyt duża, dużo miejsca jest przydzielane do przewidywanego wzrostu i znaczna ilość miejsca idzie na marne. Dynamiczne haszowanie, z drugiej strony, pozwala na dynamiczne modyfikowanie funkcji haszującej, co jest dobre dla baz danych, które rosną i kurczą się w rozmiarze. W miarę dodawania i usuwania wierszy odpowiednio zmienia liczbę wiaderek, aby zminimalizować przepełnienie wiaderek.
Implementacja
– Statyczne haszowanie używa stałej funkcji haszującej do partycjonowania zbioru wszystkich możliwych wartości klucza wyszukiwania na podzbiory, a następnie mapuje każdy podzbiór do kubła. Dynamiczne haszowanie, z drugiej strony, używa drugiego etapu mapowania, aby określić kubełek związany z pewną wartością klucza wyszukiwania. Rozszerzalne i liniowe haszowanie wykonuje to mapowanie bardzo różnie.
Podsumowanie
W statycznym hashowaniu liczba wiaderek jest stała, a rekordy o różnych wartościach klucza wyszukiwania wskazują na to samo wiaderko, w którym to przypadku może dojść do kolizji. Jeśli trzeba zlokalizować konkretny rekord w wiadrze z wieloma kluczami, trzeba sekwencyjnie przeszukać całe wiadro. Czasami wiadro ma więcej rekordów niż może zawierać. Tak więc, w tym przypadku, niektóre techniki obsługi przepełnienia muszą zostać wywołane. W takim przypadku stosuje się dynamiczne haszowanie, które wykorzystuje dynamicznie zmieniającą się funkcję, która pozwala, aby liczba przydzielonych wiaderek rosła i zmniejszała się w miarę dodawania i usuwania wierszy. Wyraźnie obsługuje przepełnienie wiaderek, osadzając dynamicznie rekordy przepełnienia w swoim adresie głównym.