Dlaczego drzewo map Java Java nie pozwala na początkowy rozmiar?

Question

Ładowanie 1 000 000 liczb zajmuje 2 sekundy, aby załadować do drzewa treemap (drzewa wyszukiwania binarnego), ale zajmuje milisekundy, aby załadować do mapy mieszającej (w java).
Jedyna różnica między tymi dwoma to to, że widzę, że mogę ustawić początkowy rozmiar wahhapy, więc nie musi ciągle zmieniać rozmiaru.

Czy nie mam racji zakładając, że początkowy rozmiar macierzy TreeMap powinien być możliwy do ustawienia? Czy jest inny powód, że jest tak powolny?
Czy istnieje logiczny powód, dlaczego nie można ustawić TreeMap's, lub dowolnego drzewa ogólnego rozmiaru drzewa binarnego, rozmiaru lub czy jest to błędne?

Answer 1

W przeciwieństwie do HashMap, które ponownie przypisują swoje elementy wewnętrzne, gdy wstawiane są nowe, TreeMap zwykle nie przydziela nowych węzłów podczas dodawania nowych. Różnicę można bardzo luźno zilustrować jako różnicę między ArrayList i LinkedList: pierwsza ponownie alokuje do zmiany rozmiaru, podczas gdy druga nie. Dlatego ustawienie początkowego rozmiaru TreeMap jest mniej więcej tak samo ważne, jak próba ustawienia początkowego rozmiaru LinkedList.

różnica Prędkość wynika z różnej złożoności czasie dwóch pojemników: wstawiania N węzłów w HashMap jest O(n), podczas gdy dla TreeMap to O(N*LogN), które dla 1000000 węzłów jest około 20 razy asymptotyczna różnica. Chociaż różnica w asymptotycznej złożoności nie przekłada się bezpośrednio na różnicę czasową z powodu różnych stałych dyktowanych przez poszczególne algorytmy, służy ona jako dobry sposób na ustalenie, który algorytm będzie szybszy przy bardzo dużych wejściach.

Answer 2

Treemap jest zawsze zrównoważony. Za każdym razem, gdy dodajesz węzeł do drzewa, musi upewnić się, że wszystkie węzły są uporządkowane według dostarczonego komparatora. Nie masz określonego rozmiaru, ponieważ treemap jest zaprojektowany dla gładko posortowanej grupy węzłów i łatwo przechodzić przez węzły.

Hashmap musi mieć odpowiednią ilość wolnego miejsca na rzeczy, które w nim przechowujesz. Mój profesor zawsze mi powtarzał, że potrzebuje 5 razy więcej miejsca niż przedmioty lub cokolwiek, co przechowujesz w tej nieszczęści. Zatem określenie rozmiaru od początkowego utworzenia Hashmap poprawia szybkość twojej hashmap. W przeciwnym razie, jeśli masz więcej obiektów wchodzących w nieszczęściu, niż planowałeś, hashmap musi "powiększyć".

(edytowany przez pisowni)

Answer 3

jestem niesłusznie zakładają TreeMap za tablicowej, która początkowa wielkość powinna móc być ustawiony?

Tak. A TreeMap nie ma tablicy. A TreeMap używa binarnych węzłów z 2 dziećmi.

Jeśli sugerujesz, że liczba dzieci w węźle drzewa powinna być parametrem, musisz dowiedzieć się, jak wpływa to na czas wyszukiwania. I myślę, że zmienia on czas wyszukiwania z O(log2N) na O(log2M * log2(N/M)), gdzie N to elementy liczbowe, a M to średnia liczba węzłów potomnych. (I robię pewne optymistyczne założenia ...) To nie jest "wygrana".

Czy istnieje inny powód, że jest tak powolny?

Tak. Powód, dla którego (duży) TreeMap jest powolny względem (dużego) HashMap w optymalnych warunkach jest taki, że wyszukiwanie przy użyciu zrównoważonego drzewa binarnego wymaga spojrzenia na węzły drzewa. W przeciwieństwie do tego, w optymalnym HashMap (dobry współczynnik obciążenia i brak punktów szczególnych kolizji) wyszukiwanie obejmuje 1 obliczenie hashcode i przeglądanie węzłów hashchain O(1).

Uwagi:

1. TreeMap używa binarny organizację drzewo, które daje wyważone drzewa, tak O(log2N) jest najgorszy czas wyszukiwania.
2. 2 wydajność zależy od szybkości kolizji funkcji mieszania i przestrzeni kluczy. W najgorszym przypadku, gdy wszystkie klucze kończą się na tym samym łańcuchu haszowania, wyszukiwanie HashMap ma wartość O(N).

Answer 4

Czy jestem w błędzie zakładając, że początkowy rozmiar macierzy TreeMap powinien być możliwy do ustawienia?

Tak. Nie ma ona tablic. Ma drzewo.