Haszowanie jest popularną techniką stosowaną do możliwie najszybszego przechowywania i odzyskiwania danych. Głównym powodem używania skrótu jest to, że wykonuje on wstawianie, usuwanie, wyszukiwanie i inne operacje
Dlaczego warto używać hashowania?
Podczas mieszania wszystkie operacje, takie jak wstawianie, wyszukiwanie i usuwanie, można wykonywać w O(1), tj. Stałym czasie. W najgorszym przypadku złożoność czasowa dla mieszania pozostaje O(n), ale średnia złożoność czasowa przypadku wynosi O(1).
Tabela Hash
Używane w celu utworzenia nowej tablicy mieszającej.
Składnia:
// function to delete a key from the hashtable delete (key) { const index = this._setKey(key); if (this.table[index]) { this.table[index] = []; this.size--; return true; } else { return false; } }> Podstawowe operacje ze składnią
Dostawać:
Służy do wyszukiwania klucza w tabeli skrótów i zwracania wartości powiązanej z tym kluczem.
Składnia:
// function inside hashtable class to // access a value using its key get(key) { const target = this._setKey(key); return this.table[target]; }> Wstawić:
Służy do wstawiania nowej pary klucz-wartość wewnątrz tabeli mieszającej.
Składnia:
// function to insert a value in the // hash table using setKey function insert(value) { const index = this._setKey(value); this.table[index] = value; this.size++; }> Szukaj:
Służy do wyszukiwania wartości.
Składnia:
// search a value (by getting its // key using setKey function) search(value){ const index = this._setKey(value); if(this.table[index]==value) console.log('The value is found at index : ',index); else console.log('Not found'); }> Usuwać:
Używane w celu usunięcia określonej pary klucz-wartość z tabeli mieszającej.
Składnia:
// function to delete a key from the hashtable delete (key) { const index = this._setKey(key); if (this.table[index]) { this.table[index] = []; this.size--; return true; } else { return false; } }> Składniki hashowania w JavaScript
1. Tabela mieszająca: Tabela mieszająca jest uogólnieniem tablicy. Daje funkcjonalność polegającą na przechowywaniu zbioru danych w taki sposób, aby w razie potrzeby łatwo było je później odnaleźć. Dzięki temu wyszukiwanie elementu jest bardzo efektywne.
jak wyłączyć tryb programisty
2. Funkcja skrótu: Funkcja skrótu służy do przekształcenia danego klucza w określony indeks szczeliny. służy do mapowania każdego możliwego klucza na unikalny indeks szczeliny. Jeśli każdy klucz jest odwzorowany na unikalny indeks szczeliny, wówczas funkcja mieszająca jest znana jako doskonała funkcja mieszająca. Stworzenie idealnej funkcji mieszającej jest bardzo trudne, ale naszym zadaniem jako programisty jest stworzenie takiej funkcji mieszającej, przy pomocy której liczba kolizji będzie jak najmniejsza.
Dobra funkcja skrótu powinna mieć następujące właściwości:
zmienne Nginxa
- Wydajnie obliczalne.
- Należy równomiernie rozmieścić klucze (każda pozycja na stole jest jednakowo prawdopodobna dla każdego).
- Powinien minimalizować kolizje.
- Powinien mieć niski współczynnik obciążenia (liczba pozycji w tabeli podzielona przez rozmiar tabeli).
3. Postępowanie w przypadku kolizji: Ponieważ funkcja skrótu daje nam małą liczbę dla dużego klucza, istnieje możliwość, że dwa klucze dadzą tę samą wartość. Sytuacja, w której nowo wstawiony klucz jest mapowany na już zajęte miejsce w tablicy skrótów, nazywana jest kolizją i należy ją rozwiązać za pomocą pewnej techniki obsługi kolizji. Oto sposoby radzenia sobie z kolizjami:
- Łańcuch: Pomysł polega na tym, aby każda komórka tabeli mieszającej wskazywała połączoną listę rekordów, które mają tę samą wartość funkcji mieszającej. Łańcuch jest prosty, ale wymaga dodatkowej pamięci poza stołem.
- Otwarte adresowanie: W adresowaniu otwartym wszystkie elementy są przechowywane w samej tablicy mieszającej. Każdy wpis w tabeli zawiera rekord lub NIL. Szukając elementu, przeglądamy kolejno miejsca w tabeli, aż znajdziemy żądany element lub okaże się, że elementu nie ma w tabeli.
Implementacja z przykładem:
Krok 1: Utwórz klasę HashTable z początkowymi właściwościami tabeli i rozmiaru.
Krok 2: Dodaj prywatną funkcję setKey(key) do przekształcania kluczy w indeksy.
Krok 3: Dodaj funkcje wstawek() i get() umożliwiające dodawanie par klucz-wartość i uzyskiwanie do nich dostępu z tabeli.
Krok 4: Dodaj funkcję usuwania (), aby usunąć klucz z tabeli skrótów.
Przykład 1: Załóżmy, że musimy przechowywać 5 liczb 100,87,86,12,25 i 9 w tablicy mieszającej. W tym przypadku utworzymy funkcję setKey, w której przyjmiemy wartość jako argument i przekonwertujemy ją na indeks tablicy mieszającej. Poniżej realizacja.
JavaScript
// HashTable Implementation> class HashTable {> >constructor() {> >this>.table =>new> Array(10);> >this>.size = 0;> >}> >// private function to convert key to index> >// _ shows that the function is private> >_setKey(key) {> >return> key % 10;> >}> >// insert value in the hashtable> >insert(value) {> >const index =>this>._setKey(value);> >this>.table[index] = value;> >this>.size++;> >}> >get(key) {> >const target =>this>._setKey(key);> >return> this>.table[target];> >}> >search(value) {> >const index =>this>._setKey(value);> >if> (>this>.table[index] == value)> >console.log(>'The value is found at index : '>, index);> >else> >console.log(>'Not found'>);> >}> >delete>(key) {> >const index =>this>._setKey(key);> >if> (>this>.table[index]) {> >this>.table[index] = [];> >this>.size--;> >return> true>;> >}>else> {> >return> false>;> >}> >}> }> const hashExample =>new> HashTable();> // insert> hashExample.insert(100);> hashExample.insert(87);> hashExample.insert(86);> hashExample.insert(12);> hashExample.insert(9);> console.log(hashExample.table);>// ->pokazuje tablicę mieszającą> // search> hashExample.search(87);>// found> hashExample.search(10);>// not found> // delete> hashExample.>delete>(12);> // showing table after deletion> console.log(hashExample.table);> |
numpy odchylenie standardowe
>
>
Wyjście:
w łańcuchu w Javie
[ 100, , 12, , 86, 87, , 9 ] The value is found at index : 7 Not found [ 100, , [], , 86, 87, , 9 ]>
Na wyjściu lub pokazuje, że tabela zawiera 1 lub 3 kolejne puste spacje/indeksy.
Przykład 2: Załóżmy, że chcemy przechowywać numery kontaktowe pięcioosobowej rodziny w tabeli mieszającej. W tym celu utworzymy tabelę skrótów o rozmiarze 10 i zapiszemy dane kontaktowe. Indeks zostanie ustawiony za pomocą prywatnej funkcji setKey, która przekonwertuje ostatnią cyfrę numeru kontaktowego na indeks tablicy mieszającej.
JavaScript
// HashTable Implementation> class HashTable {> >constructor() {> >this>.table =>new> Array(10);> >this>.size = 0;> >}> >// private function to convert key to index> >// _ shows that the function is private> >_setKey(key) {> >const lastDigit = key % 10;> >return> lastDigit;> >}> >// insert value in the hashtable> >insert(value) {> >const index =>this>._setKey(value);> >this>.table[index] = value;> >this>.size++;> >}> >get(key) {> >const target =>this>._setKey(key);> >return> this>.table[target];> >}> >search(value) {> >const index =>this>._setKey(value);> >if> (>this>.table[index] == value)> >console.log(>'The contact number is found at index : '>, index);> >else> >console.log(>'Contact Number not found'>);> >}> >delete>(key) {> >const index =>this>._setKey(key);> >if> (>this>.table[index]) {> >this>.table[index] = [];> >this>.size--;> >return> true>;> >}>else> {> >return> false>;> >}> >}> }> const hashExample =>new> HashTable();> // insert> hashExample.insert(98754525);> hashExample.insert(98747512);> hashExample.insert(94755523);> hashExample.insert(92752521);> hashExample.insert(98556529);> console.log(hashExample.table);>// ->pokazuje tablicę mieszającą> // search> hashExample.search(92752521);>// found> hashExample.search(92755784);>// not found> // delete> hashExample.>delete>(92752521);> // showing table after deletion> console.log(hashExample.table);> |
>
>
Wyjście:
przeczytaj plik Excela w Javie
[ , 92752521, 98747512, 94755523, , 98754525, , 98556529 ] The contact number is found at index : 1 Contact Number not found [ , [], 98747512, 94755523, , 98754525, , 98556529 ]>
Na wyjściu lub pokazuje, że tabela zawiera 1 lub 3 kolejne puste spacje/indeksy.