Różnica między mieszaniem dynamicznym i statycznym

W strukturze danych Hashing jest techniką mapowania dużej liczby elementów danych na mniejsze tabele przy użyciu specjalnej funkcji o nazwie Funkcja HASH dla szybszego dostępu. Czasami struktura danych jest tak ogromna, że ​​przeszukanie wszystkich wartości indeksu na wszystkich poziomach, aby uzyskać dostęp do końcowego bloku danych. Tutaj pojawia się Hashing. To, co robi, to bezpośrednie obliczenie lokalizacji rekordu danych na dysku bez użycia struktury indeksu. Adres każdego rekordu jest określany przy użyciu algorytmu mieszania, który przekształca wartość klucza podstawowego na adres rekordu. Tak więc istnieją dwie kategorie indeksowania dostępnych za pomocą funkcji skrótu - dynamiczne mieszanie i haszowanie statyczne.

Co to jest haszowanie statyczne?

Haszowanie statyczne to metoda mieszania, w której ustalona liczba wiader jest przydzielana do pliku do przechowywania rekordów. Liczba wiader jest wstępnie allokowana, więc po podaniu wartości klucza wyszukiwania funkcja skrótu zawsze oblicza ten sam adres. Strona pliku można wyświetlić jako zbiór wiader, z jedną stroną podstawową i dodatkowymi stronami przepełnienia. W przypadku haszu statycznego mechanizm lokalizacji jest funkcją skrótu i ​​nie są zaangażowane żadne struktury danych. Tutaj wpisy indeksu są losowo losowo w sposób, w jaki liczba wpisów indeksu w każdym wiadrze jest mniej więcej taka sama. Istnieją jednak również pewne wady tego programu. Jeśli początkowa liczba wiader jest zbyt mała, a plik rośnie, wydajność degraduje się z powodu przepełnienia wiadra. Z drugiej strony, jeśli jest zbyt duży, wiele przestrzeni jest przydzielane do przewidywanego wzrostu, a znaczna ilość przestrzeni przechodzi.

Co to jest dynamiczne mieszanie?

Z drugiej strony dynamiczne mieszanie jest techniką stosowaną w celu przezwyciężenia ograniczeń w haszku statycznym jak przepełnienie wiadra. W przeciwieństwie do haszu statycznego, pozwala dynamicznie różnić się liczbą wiader. Umożliwia modyfikowanie funkcji skrótu na żądanie, co jest dobre dla baz danych, które rosną i kurczą się. W miarę dodawania i usuwania wierszy zmienia odpowiednio liczbę wiader w celu zminimalizowania przepełnienia wiader. Osadza dynamicznie obsługę rejestrów przepełnienia w głównej przestrzeni adresowej, aby uniknąć zarządzania wiadrami przepełnienia. Dwie powszechnie stosowane formy dynamicznego mieszania to haszowanie liniowe i rozszerzalne. Exterible Hashing to popularna technika, która obsługuje przepełnienie wiadra, dzieląc wiadro na dwa, dystrybuując rekordy między starymi i nowymi wiadrami. Haszowanie liniowe to kolejna popularna forma dynamicznego mieszania, która pozwala dynamiczne rosnąć lub kurczyć się pliku skrótu poprzez przydzielenie nowych wiader.

Różnica między mieszaniem dynamicznym i statycznym

Technika

- Haszowanie statyczne to metoda mieszania, w której ustalona liczba wiader jest przydzielana do pliku do przechowywania rekordów, co oznacza, że ​​używa funkcji skrót. Tutaj wpisy indeksu są losowo losowo w sposób, w jaki liczba wpisów indeksu w każdym wiadrze jest mniej więcej taka sama. Z drugiej strony dynamiczne mieszanie umożliwia dynamicznie liczbę wiader.

Wydajność

- Jeśli początkowa liczba wiader jest zbyt mała, a plik rośnie, wydajność degraduje się z powodu przepełnienia wiadra. Z drugiej strony, jeśli jest zbyt duży, wiele przestrzeni jest przydzielane do przewidywanego wzrostu, a znaczna ilość przestrzeni przechodzi. Z drugiej strony dynamiczne mieszanie umożliwia dynamiczne modyfikowanie funkcji skrótu, co jest dobre dla baz danych, które rosną i kurczą się. W miarę dodawania i usuwania wierszy zmienia odpowiednio liczbę wiader w celu zminimalizowania przepełnienia wiader.

Realizacja

- Hashowanie statyczne używa stałej funkcji skrótu do podziału zestawu wszystkich możliwych wartości wyszukiwania na podzbiór, a następnie mapuje każdy podzbiór na wiadro. Z drugiej strony dynamiczne mieszanie używa drugiego etapu mapowania w celu ustalenia wiadra powiązanego z pewną wartością wyszukiwania. Haszowanie rozszerzalne i liniowe to mapowanie zupełnie inaczej.

Dynamiczny vs. Haszowanie statyczne: wykres porównawczy

Streszczenie

Liczba wiader jest ustalona w statycznym mieszaniu i rekordach o różnych wartościach wyszukiwania wskazuje na ten sam wiadro, w którym to przypadku może wystąpić zderzenie. Jeśli chcesz zlokalizować konkretny rekord w wiadrze z wieloma klawiszami, musisz przeszukać całe wiadro sekwencyjne. Czasami wiadro ma więcej rekordów niż może zawierać. W tym przypadku należy wywołać niektóre techniki obsługi przepełnienia. W takim przypadku stosuje się dynamiczne mieszanie, które wykorzystuje dynamicznie zmieniającą się funkcję, która umożliwia wzrost liczby przydzielonych wiader. Już wyraźnie obsługuje przepełnienie wiader poprzez dynamicznie osadzanie rejestrów przepełnienia w głównym adresie.