Złożoność czasu hashmapu i C ++

„Złożoność czasu to względny czas wykonywania niektórych kodowania. Przed omówieniem złożoności czasowej hashmapu czytelnik musi znać rolę funkcji skrótu na mapie skrótów.

Teoretycznie funkcja skrótu konwertuje dane o dowolnym rozmiarze (dowolny duży tekst) na liczbę całkowitą, która jest większa lub równa zero. Różne duże teksty są konwertowane na różne liczby. Zainteresowanie tym artykułem nie jest konwersja dużego tekstu na liczbę całkowitą. Zainteresowanie tym artykułem jest mapowanie danych dowolnej wielkości na całkowitą liczbę. Obejmuje to możliwość mapowania (przekształcenia) pojedynczej liczby na inną liczbę.

Dane (po lewej) do zmapowania nazywane są klucze. Więc każdy klucz jest konwertowany na liczbę całkowitą, która jest równa lub większa niż zero. Wyobraź sobie, że istnieje pięć kluczy, które zostały przekonwertowane na liczby: 0, 1, 2, 3 i 4. Jeśli te klucze są indeksami tablicy o pięciu wartości tego samego typu, wówczas klawisze zostały zmapowane na pięć różnych wartości.

I co to jest hashmap (mapa skrótu)? Hashmap to struktura danych składająca się z par kluczy/wartości, w której każdy klucz został zmapowany na wartość. W rzeczywistości każdy klucz został osądzony w wielu tablicy, a odpowiednia komórka macierz. W temacie hashmap lokalizacja komórki każdego indeksu tablicy nazywana jest wiadrem."

Problem i rozdzielczość zderzenia

W praktyce różne klucze można zmapować na więcej niż jedną wartość. Rozważ przypadek dziesięciu kluczy dla szeregu długości 5, z 5 wiadrami. W takim przypadku skonstruowana byłaby struktura taka jak tablica. Każde wiadro faktycznie byłoby szeregiem długości 2. Dwa klucze miałyby to samo wiadro. W tym udostępnianiu pierwszy klucz mapowałby do pierwszego elementu tablicy dla wiadra, a drugi klucz mapowałby na drugi element tablicy dla tego samego wiadra. Ten schemat rozwiązuje problem kolizji, a dziesięć kluczy zostało zmapowanych na 10 wartości, zgodnie z oczekiwaniami.

Przez resztę tego artykułu wyobraź sobie hashmap z rozwiązaniem problemu zderzenia. Celem tego artykułu jest zapewnienie złożoności czasowej kodowania w celu wprowadzenia do hashmapu, kodowania do usunięcia do hashmapu i kodowania wyszukiwania w hashmapie. Złożoność czasu dla hashmapa jest opisana z tymi trzema cechami. W tym artykule omówiono również mapowanie skrótu dla C ++.

Pary klucza/wartości i wartość_typ

Wyobraź sobie hashmapę imion osób wbrew numerom telefonu dla katalogu telefonicznego. Nazwy użytkowników telefonu są typu danych, tekst (ciąg). Wartości numerów telefonów są typu danych i tekstu, zakładając, że przestrzenie i/lub łączniki są dozwolone w numerze telefonu. Nazwy użytkowników to klucze, a numery telefonów są wartościami. Nie zapominaj, że wewnętrznie klucze są faktycznie konwertowane na indeksy tablicy w strukturze danych. Tak więc typ kluczy jest tekst, a typ wartości to nadal tekst.

Typ wartości oznacza parę klucza/wartości jako elementu. W C ++ każdy element (para) jest wskazany przez iterator. Tak więc w C ++ jest również mapowanie iterator/pary. Para (klucz i jej wartość) jest określana jako typ wartości.

Złożoność czasu dla wstawienia hashmap

Złożoność czasu dla hashmapu nie odnosi się do czasu potrzebnego na stworzenie hashmapu. Odnosi się do czasu potrzebnego na wstawienie, usunięcie lub wyszukiwanie wartości na podstawie danego klucza. Złożoność czasu jest zwykle pisana przy użyciu notacji Big-O. Notacja Big-O składa się z O Upperce, a następnie nawiasów. W nawiasach znajdują się zmienne i liczby, które dają względny czas działania dla kawałka kodu i niekoniecznie cały program. Z hashmapem k oznacza liczbę kluczy, a n oznacza liczbę wiader. Pamiętaj, że przy niektórych hashmapach wiadro może mieć więcej niż jedną wartość dla odpowiednio różnych kluczy. W takim przypadku więcej niż jeden klucz jest osądzony w tym samym indeksie kubełkowym. Dobra hashmapa rozwiązuje tę kolizję.

Wprowadzenie

Biorąc pod uwagę nowy klucz, średnia złożoność czasu, aby mieć klucz i odpowiednią wartość włożoną do struktury danych hashmap:

O (1 + N/K)

Gdzie n jest liczbą wiader, a k to liczba kluczy. Na przykład, może 10, a może 5. W tej konkretnej sytuacji niektóre wiadra są puste (nie mają wartości). Tak więc liczba operacji byłaby, 1 + 10/5 = 1 + 2 = 3. Oznacza to, że byłyby 3 operacje kodowania w celu wstawienia elementu pary klucza/wartości (biorąc pod uwagę klucz). Biorąc pod uwagę nowy klucz i wartość, najgorsze złożoność czasu, aby mieć klucz i odpowiednią wartość wstawioną do struktury danych hashmap:

NA)

Gdzie n jest liczbą wiader dla operacji N, jeśli hashmap przyjmuje więcej niż jedną wartość na wiadro dla więcej niż jednego klucza, wówczas każdy dodatkowy czas na włożenie kolejnej wartości w tym samym wiadrze jest znikome i zaniedbane.

Usunięcie

Biorąc pod uwagę klucz już w strukturze danych hashmap, usunięcie usuwa element pary klucza/wartości. Średnia złożoność czasu do usunięcia wynosi:

O (1 + N/K)

Gdzie n jest liczbą wiader, a k to liczba kluczy. Na przykład, może 10, a może 5. W tej konkretnej sytuacji niektóre wiadra są puste (nie mają wartości). Tak więc liczba operacji dla kodu usuwania, wynosi by 1 + 10/5 = 1 + 2 = 3. Więc tutaj byłyby 3 operacje kodowania, aby usunąć element pary klucza/wartości, biorąc pod uwagę klucz.

Najgorsze złożoność czasu do usunięcia, biorąc pod uwagę klucz, to:

NA)

Gdzie n jest liczbą wiader, więc jeśli istnieją n wiadra dla struktury danych hashmap, na limicie wymagałoby 10 operacji, aby usunąć element pary klucza/wartości w hashmapie.

Badawczy

Wyszukiwanie oznacza znalezienie elementu pary klucza/wartości, który ma dany klucz, który powinien już znajdować się w hashmapie. Średnia złożoność czasu na to jest:

O (1 + N/K)

Z argumentami o tych samych znaczeniach jak powyżej. Najgorsze złożoność czasu na to jest:

NA)

Z argumentem o tym samym znaczeniu co powyżej.

C ++ 20

Czy C ++ 20 ma klasę hashmap? - Cóż, tak, ale nie z nazwą, hashmap. C ++ 20 ma cztery nieoporządkowane pojemniki asocjacyjne, które są różnymi formami klas hashmap. Kontenery to: UNOPORDED_MAP, UNOPOREDRED_MULTIMAP, UNOPORDED_SET i UNOORDED_MULTISET. Te asocjacyjne pojemniki znajdują się w standardowej bibliotece C ++ 20. Kontener asocjacyjny do rozważenia w tym artykule jest UNOPORDED_MAP. UNOPORDED_MAP używa domyślnej funkcji skrótu dostarczonej przez standardową bibliotekę C ++.

Aby włączyć nagłówek Unordered_Map do programu, użyj dyrektywy,

#włączać

Nie używaj #Include, który będzie zawierał zamówienie_map. C ++ nie przyjmuje #include . Nagłówek UNOPOREDED_MAP wprowadza klasę UNOPORED_MAP do programu C ++.

Wstaw z c++

Poniższy segment kodu w funkcji głównej C ++ wstawuje element pary klucza/wartości (nazwa i numer telefonu) do obiektu Unorderred_Map, UMP:

#włączać
UNOPORDED_MAP UMP;
Ump.insert („John Rambo”, „555-5555”);

Usuń z c++

Składnia do usunięcia elementu pary klucza/wartości z obiektu nie uporządkowanego_map, biorąc pod uwagę klucz, k, to:

A.usuń (k)

Gdzie „A” jest obiektem UNOPORED_MAP (np. UMP powyżej), a Erase () to funkcja członka UNOPOREDED_MAP.

Badawczy

Składnia do wyszukiwania elementu pary klucza/wartości w obiekcie UNOPOREDED_MAP, biorąc pod uwagę klawisz K, który powinien być już w UNOPOREDED_MAP, to:

B.Znajdź (k)

Gdzie B jest obiektem UNOPORED_MAP (np. UMP powyżej), a Find () to funkcja członka UNOPOREDED_MAP.

Wniosek

Złożoność czasu oznacza względny czas działania dla jakiegoś kodu. Chociaż złożoność czasu w tworzeniu hashmapy można określić, w przypadku skrótów, złożoność czasu dotyczy wkładania, usuwania i wyszukiwania zadań. Średnia i gorsza złożoność czasu dla dobrze zdefiniowanej wkładki hashmap to:

O (1 + N/K)
NA)

Średnia i gorsza złożoność czasu dla dobrze zdefiniowanego usunięcia hashmap to:

O (1 + N/K)
NA)

Średnia i gorsza złożoność czasu dla dobrze zdefiniowanego wyszukiwania hashmap to:

O (1 + N/K)
NA)