Dlaczego implementacja HashSet w Sun Java używa HashMap jako swojego zaplecza?

Zgaduję, że nigdy nie pojawił się jako istotny problem dla prawdziwych aplikacji lub ważnych benchmarków. Po co komplikować kod bez realnych korzyści?

Zauważ również, że rozmiary obiektów są zaokrąglane w górę w wielu implementacjach JVM, więc w rzeczywistości może nie być zwiększenia rozmiaru (Nie wiem na ten przykład). Również kod HashMap może być skompilowany i w pamięci podręcznej. Inne rzeczy są równe, więcej kodu = > więcej błędów pamięci podręcznej = > niższa wydajność.

Domyślam się, że HashSet został pierwotnie zaimplementowany w kategoriach HashMap, aby zrobić to szybko i łatwo. Jeśli chodzi o linie kodu, HashSet jest ułamkiem HashMap.

Domyślam się, że powodem, dla którego wciąż nie został zoptymalizowany, jest strach przed zmianą.

Jednak marnotrawstwo jest znacznie gorsze niż myślisz. Zarówno w wersji 32-bitowej, jak i 64-bitowej HashSet jest 4x większy niż jest to konieczne, a HashMap 2x większy niż jest to konieczne. HashMap może być zaimplementowany tablicą z kluczami i wartości w nim (Plus łańcuchy dla kolizji). Oznacza to dwa wskaźniki na wpis lub 16 bajtów na 64-bitowej maszynie wirtualnej. W rzeczywistości HashMap zawiera obiekt Entry dla każdego wpisu, który dodaje 8 bajtów dla wskaźnika do wpisu i 8 bajtów dla nagłówka obiektu Entry. HashSet używa również 32 bajtów na element, ale strata wynosi 4x zamiast 2x, ponieważ wymaga tylko 8 bajtów na element.

Tak masz rację, mała ilość marnotrawstwa jest tam definitywnie. Mały, ponieważ dla każdego wpisu używa tego samego obiektu PRESENT (który jest zadeklarowany jako końcowy). Dlatego jedynym marnotrawstwem jest wartość każdego wpisu w Hashmapie.

Głównie myślę, że przyjęły takie podejście do konserwacji i ponownego użycia. (Programiści JCF pomyśleli, że i tak przetestowaliśmy HashMap, dlaczego nie użyć go ponownie.)

Spojrzałem na twoje pytanie i trochę mi zajęło przemyślenie tego, co powiedziałeś. Oto moja opinia odnośnie implementacji HashSet.

Jest konieczne, aby instancja atrapy wiedziała, czy wartość jest lub nie jest obecna w zestawie.

Spójrz na metodę dodawania

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

Abd przyjrzyjmy się teraz zwracanej wartości put

@ zwraca poprzednią wartość skojarzoną z key lub null, Jeśli dla key nie było mapowania. (Null return can zaznacz również, że mapa wcześniej powiązana z NULL Z key.)

Tak więc obiekt PRESENT jest po prostu używany do reprezentowania, że zbiór zawiera wartość e. Myślę, że zapytałeś dlaczego nie użyć null zamiast PRESENT. Ale, nie będziesz w stanie odróżnić, czy wpis był wcześniej na mapie, ponieważ map.put(key,value) zawsze zwróci null i nie będziesz miał sposobu, aby wiedzieć, czy klucz istnieje.

To powiedziawszy można argumentować, że mogli użyć implementacji like this

   public boolean add(E e) {

        if( map.containsKey(e) ) {
            return false;
        }

        map.put(e, null);

        return true;

}

Myślę, że marnują 4 bajty, aby uniknąć obliczenia hashCode, ponieważ może to być drogie, klucza dwa razy (jeśli klucz ma być dodany).

Jeśli masz pytanie, dlaczego użyli HashMap, który marnuje 8 bajtów (z powodu Map.Entry) zamiast innej struktury danych, używając podobnego wpisu tylko 4, to tak, powiedziałbym, że zrobili to z powodów, o których wspomniałeś.

Po przeszukaniu takich stron zastanawiając się, dlaczego lekko nieefektywna implementacja standardu znalazła com.carrotsearch.hppc.IntOpenHashSet

Twoje pytanie: Myślę, że marnuje to 4 bajty (na maszynach 32-bitowych) dla rozmiaru samego wpisu.

Tylko jedna zmienna obiektowa jest tworzona dla całej struktury danych hashset i dzięki temu unikniesz ponownego pisania całego kodu hashMap.

private static final Object PRESENT = new Object();

Wszystkie klucze mają jedną wartość tj. PRESENT object.