Mapy mieszające to indeksowane struktury danych. Mapa mieszająca wykorzystuje a funkcja skrótu do obliczenia indeksu za pomocą klucza w tablicy segmentów lub gniazd. Jego wartość jest mapowana do segmentu z odpowiednim indeksem. Klucz jest unikalny i niezmienny. Pomyśl o mapie skrótów jako o szafce z szufladami z etykietami na przechowywane w nich rzeczy. Na przykład przechowywanie informacji o użytkowniku — rozważ adres e-mail jako klucz, a wartości odpowiadające temu użytkownikowi, takie jak imię, nazwisko itp., możemy zmapować do wiadra.
Funkcja skrótu jest podstawą implementacji mapy skrótu. Pobiera klucz i tłumaczy go na indeks segmentu na liście życzeń. Idealne mieszanie powinno generować inny indeks dla każdego klucza. Mogą jednak wystąpić kolizje. Kiedy haszowanie daje istniejący indeks, możemy po prostu użyć segmentu dla wielu wartości, dołączając listę lub ponownie mieszając.
W Pythonie słowniki są przykładami map skrótów. Zobaczymy implementację mapy skrótów od podstaw, aby dowiedzieć się, jak budować i dostosowywać takie struktury danych w celu optymalizacji wyszukiwania.
Projekt mapy skrótów będzie zawierał następujące funkcje:
- set_val(klucz, wartość): Wstawia parę klucz-wartość do mapy skrótów. Jeśli wartość już istnieje na mapie skrótów, zaktualizuj ją.
- get_val(klucz): Zwraca wartość, na którą jest mapowany określony klucz, lub Nie znaleziono rekordu, jeśli ta mapa nie zawiera mapowania dla klucza.
- usuń_wartość(klucz): Usuwa mapowanie dla określonego klucza, jeśli mapa skrótu zawiera mapowanie dla klucza.
Poniżej realizacja.
Python3
po kliknięciu javascript
class> HashTable:> ># Create empty bucket list of given size> >def> __init__(>self>, size):> >self>.size>=> size> >self>.hash_table>=> self>.create_buckets()> >def> create_buckets(>self>):> >return> [[]>for> _>in> range>(>self>.size)]> ># Insert values into hash map> >def> set_val(>self>, key, val):> > ># Get the index from the key> ># using hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be inserted> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key to be inserted,> ># Update the key value> ># Otherwise append the new key-value pair to the bucket> >if> found_key:> >bucket[index]>=> (key, val)> >else>:> >bucket.append((key, val))> ># Return searched value with specific key> >def> get_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key being searched> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key being searched,> ># Return the value found> ># Otherwise indicate there was no record found> >if> found_key:> >return> record_val> >else>:> >return> 'No record found'> ># Remove a value with specific key> >def> delete_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be deleted> >if> record_key>=>=> key:> >found_key>=> True> >break> >if> found_key:> >bucket.pop(index)> >return> ># To print the items of hash map> >def> __str__(>self>):> >return> ''.join(>str>(item)>for> item>in> self>.hash_table)> hash_table>=> HashTable(>50>)> # insert some values> hash_table.set_val(>'[email protected]'>,>'some value'>)> print>(hash_table)> print>()> hash_table.set_val(>'[email protected]'>,>'some other value'>)> print>(hash_table)> print>()> # search/access a record with key> print>(hash_table.get_val(>'[email protected]'>))> print>()> # delete or remove a value> hash_table.delete_val(>'[email protected]'>)> print>(hash_table)> |
>
aryjski chan
>
Wyjście:
kliknij js
Złożoność czasowa:
Dostęp do indeksu pamięci zajmuje stały czas, a mieszanie zajmuje stały czas. Stąd złożoność wyszukiwania mapy skrótów jest również stała w czasie, czyli O(1).
Zalety HashMaps
● Szybki dostęp do pamięci losowej poprzez funkcje mieszające
● Można używać wartości ujemnych i niecałkowych, aby uzyskać dostęp do wartości.
● Klucze można przechowywać w posortowanej kolejności, dzięki czemu można łatwo przeglądać mapy.
Wady HashMaps
● Kolizje mogą powodować duże kary i mogą zwiększyć złożoność czasową do liniowej.
ile tygodni w miesiącu
● Gdy liczba kluczy jest duża, pojedyncza funkcja mieszająca często powoduje kolizje.
Zastosowania HashMaps
● Mają one zastosowanie w implementacjach pamięci podręcznej, gdzie lokalizacje pamięci są mapowane na małe zbiory.
● Służą do indeksowania krotek w systemach zarządzania bazami danych.
● Są one również wykorzystywane w algorytmach takich jak dopasowywanie wzorców Rabina Karpa