jaka jest różnica między mapą a hashmapem w STL [duplikat]

Hash_map używa tabeli hash. W teorii jest to czas "stały". Większość implementacji używa tabeli hash "collision". To, co dzieje się w rzeczywistości, to:

• tworzy dużą tabelę
• masz funkcję "hash" dla swojego obiektu, która generuje losowe miejsce w tabeli (losowo wyglądające, ale funkcja hash zawsze zwróci tę samą wartość dla Twojego obiektu) i zwykle jest to mod rzeczywistej 32-bitowej (lub 64-bitowej) wartości hash o rozmiarze tabeli.
• tabela wygląda, aby zobaczyć, czy miejsce jest dostępne. Jeśli tak, to umieszcza element w tabeli. Jeśli nie, sprawdza, czy element jest Tym, który próbujesz wstawić. Jeśli tak to jest duplikat więc nie wstawić. Jeśli nie, nazywa się to "kolizją" i używa pewnej formuły, aby znaleźć inną komórkę, a to trwa, dopóki nie znajdzie duplikatu lub pustej komórki.
• gdy tabela jest zbyt wypełniona, zmienia rozmiar. Efektywna (w czasie) implementacja będzie przechowywać wszystkie oryginalne wartości hash razem z elementami, więc nie będzie musiał ponownie obliczać hashów, gdy to zrobi. Ponadto porównywanie skrótów jest zwykle szybsze niż porównywanie elementów, więc może to zrobić podczas wyszukiwania, aby wyeliminować większość kolizji jako etap wstępny.
• Jeśli nigdy niczego nie usuniesz, jest to proste. Jednak usuwanie elementów dodaje dodatkowej złożoności. Komórka, która miała w sobie element, który został usunięty, jest w innym stanie niż ten, który był pusty przez cały czas, jak być może miałeś kolizji i jeśli po prostu go opróżnisz, te elementy nie zostaną znalezione. Więc zwykle jest jakiś "znak". Oczywiście teraz, gdy chcemy ponownie użyć komórki, nadal musimy rekurencyjnie w przypadku, gdy istnieje duplikat w dół (w którym to przypadku nie możemy wstawić do tej komórki), a następnie pamiętaj, aby ponownie użyć usuniętej komórki.
• zwyczajowym ograniczeniem jest to, że Twoje obiekty muszą być zaimplementowane, aby sprawdzić równość, ale Dinkumware (lub był to SGI) zaimplementowane z operatorem

Teoria jest taka, że jeśli masz wystarczająco dużą tabelę, operacje są w czasie stałym, tzn. nie zależy od liczby rzeczywistych elementów, które masz. W praktyce, oczywiście, im więcej elementów masz, tym więcej kolizji występuje.

Std::map używa drzewa binarnego. Nie ma potrzeby definiowania funkcji hash dla obiekt, tylko ściśle uporządkowane porównanie. Po wstawieniu rekursuje się w dół drzewa, aby znaleźć punkt wstawiania (i czy są jakieś duplikaty) i dodaje węzeł, i może być konieczne Zrównoważenie drzewa, aby głębokość liści nigdy nie była większa niż 1 od siebie. Czas równoważenia jest również zależny od głębokości drzewa, więc wszystkie te operacje są O (log N), gdzie N jest liczbą elementów.

Zaletą hasha jest złożoność Zalety drzewa to:

• całkowicie skalowalne. Używa tylko tego, czego potrzebuje, nie ma potrzeby posiadania ogromnej tabeli ani wyprzedzania rozmiaru tabeli, chociaż hash może wymagać mniej "bagażu" na element niż drzewo.
• nie trzeba najpierw hashować, co dla dobrej funkcji może trwać dłużej niż porównania, jeśli zestaw danych nie jest duży.

Innym problemem z std::map jest to, że używa pojedynczej ściśle uporządkowanej funkcji porównawczej, podczas gdy funkcja "Porównaj", która zwraca -1, 0 LUB 1, byłaby o wiele bardziej efektywna, szczególnie w przypadku najczęściej używanego typu klucza, std:: string, który ma już zaimplementowaną tę funkcję (jest to char_traits::compare). (Ta nieefektywność opiera się na założeniu, że aby to sprawdzić x==y, sprawdzasz x<y i y<x, więc robisz dwa porównania. Można to zrobić tylko raz na wyszukiwanie).

map jest czerwono-czarnym drzewem, O(log(n)) Czas dostępu. hash_map (który nie jest standardem, jednak unordered_map stanie się standardem) używa (koncepcyjnie) skrótu klucza jako indeksu w tablicy połączonych list i dlatego ma najlepszy czas dostępu O(1) i najgorszy przypadek O(n).

Zobacz http://en.wikipedia.org/wiki/Red-black_tree

Główną różnicą jest czas wyszukiwania.

Dla kilku danych jest lepsza Mapa

Dla wielu danych jest lepsza hashmap

W każdym razie podane wcześniej odpowiedzi są poprawne.