W tym samouczku dowiesz się, czym jest haszowanie.
Haszowanie to technika mapowania dużego zestawu dowolnych danych na indeksy tabelaryczne przy użyciu funkcji skrótu. Jest to metoda reprezentacji słowników dla dużych zbiorów danych.
Umożliwia wyszukiwanie, aktualizację i odzyskiwanie w stałym czasie, tj O(1).
Dlaczego haszowanie jest potrzebne?
Po zgromadzeniu dużej ilości danych musimy na tych danych wykonywać różne operacje. W przypadku zbiorów danych wyszukiwania są nieuniknione. Wyszukiwanie liniowe i wyszukiwanie binarne wykonują wyszukiwania / wyszukiwania ze złożonością czasową odpowiednio O(n)i O(log n). Wraz ze wzrostem rozmiaru zbioru danych złożoność ta również staje się znacząco wysoka, co jest niedopuszczalne.
Potrzebujemy techniki, która nie zależy od rozmiaru danych. Haszowanie umożliwia wyszukiwanie w stałym czasie, tj O(1).
Funkcja skrótu
Funkcja skrótu służy do mapowania każdego elementu zestawu danych na indeksy w tabeli.
Aby uzyskać więcej informacji na temat tablicy skrótów, technik rozwiązywania kolizji i funkcji skrótu, odwiedź stronę Hash Table.
