Chcę utworzyć dużą HashMap, ale put()wydajność nie jest wystarczająco dobra. Jakieś pomysły?

Inne sugestie dotyczące struktury danych są mile widziane, ale potrzebuję funkcji wyszukiwania mapy Java:

map.get(key)

W moim przypadku chcę stworzyć mapę z 26 milionami wpisów. Korzystając ze standardowej Java HashMap, szybkość sprzedaży staje się nieznośnie niska po 2-3 milionach wstawień.

Czy ktoś wie również, czy użycie różnych dystrybucji kodu skrótu dla kluczy może pomóc?

Moja metoda hashcode:

byte[] a = new byte[2];
byte[] b = new byte[3];
...

public int hashCode() {
    int hash = 503;
    hash = hash * 5381 + (a[0] + a[1]);
    hash = hash * 5381 + (b[0] + b[1] + b[2]);
    return hash;
}

Używam asocjacyjnej właściwości dodawania, aby zapewnić, że równe obiekty mają ten sam kod skrótu. Tablice są bajtami z wartościami z zakresu 0 - 51. Wartości są używane tylko raz w każdej tablicy. Obiekty są równe, jeśli tablice a zawierają te same wartości (w dowolnej kolejności) i to samo dotyczy tablicy b. Czyli a = {0,1} b = {45,12,33} i a = {1,0} b = {33,45,12} są równe.

EDYCJA, kilka uwag:

• Kilka osób skrytykowało używanie mapy skrótów lub innej struktury danych do przechowywania 26 milionów wpisów. Nie rozumiem, dlaczego wydawałoby się to dziwne. Dla mnie wygląda to na klasyczny problem struktur danych i algorytmów. Mam 26 milionów pozycji i chcę móc je szybko wstawiać i wyszukiwać ze struktury danych: podaj strukturę danych i algorytmy.

• Ustawienie początkowej pojemności domyślnej Java HashMap na 26 milionów zmniejsza wydajność.

• Niektórzy sugerowali używanie baz danych, w innych sytuacjach jest to zdecydowanie mądra opcja. Ale tak naprawdę zadaję pytanie o struktury danych i algorytmy, pełna baza danych byłaby przesadą i znacznie wolniejsza niż dobre rozwiązanie do obsługi danych (w końcu baza danych jest tylko oprogramowaniem, ale miałaby komunikację i prawdopodobnie narzut na dysku).

Jak wielu wskazywało, hashCode()winna była metoda. Generował tylko około 20 000 kodów dla 26 milionów różnych obiektów. To średnio 1300 obiektów na wiadro z mieszaniem = bardzo, bardzo źle. Jeśli jednak zamienię dwie tablice na liczbę o podstawie 52, mam gwarancję, że otrzymam unikalny kod skrótu dla każdego obiektu:

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i++) {
        result *= 52;
    }
    return result;
}

Tablice są sortowane, aby upewnić się, że te metody spełniają hashCode()kontrakt, w którym równe obiekty mają ten sam kod skrótu. Używając starej metody, średnia liczba putsów na sekundę w blokach 100 000, 100 000 do 2 000 000 wynosiła:

168350.17
109409.195
81344.91
64319.023
53780.79
45931.258
39680.29
34972.676
31354.514
28343.062
25562.371
23850.695
22299.22
20998.006
19797.799
18702.951
17702.434
16832.182
16084.52
15353.083

Użycie nowej metody daje:

337837.84
337268.12
337078.66
336983.97
313873.2
317460.3
317748.5
320000.0
309704.06
310752.03
312944.5
265780.75
275540.5
264350.44
273522.97
270910.94
279008.7
276285.5
283455.16
289603.25

O wiele lepiej. Stara metoda szybko przestała działać, podczas gdy nowa utrzymuje dobrą przepustowość.

Jedną rzeczą, którą zauważyłem w twojej hashCode()metodzie, jest to, że kolejność elementów w tablicach a[]i b[]nie ma znaczenia. W ten sposób (a[]={1,2,3}, b[]={99,100})hash będzie miał taką samą wartość jak (a[]={3,1,2}, b[]={100,99}). Właściwie wszystkie klucze k1i k2gdzie sum(k1.a)==sum(k2.a)i sum(k1.b)=sum(k2.b)spowodują kolizje. Proponuję przypisać wagę do każdej pozycji tablicy:

hash = hash * 5381 + (c0*a[0] + c1*a[1]);
hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]);

gdzie c0, c1i c3są różne stałe (można użyć różnych stałych dla bjeśli to konieczne). To powinno nieco bardziej wyrównać sytuację.

Aby rozwinąć Pascala: czy rozumiesz, jak działa HashMap? Masz pewną liczbę miejsc w swojej tabeli skrótów. Zostaje znaleziona wartość skrótu dla każdego klucza, a następnie odwzorowana na wpis w tabeli. Jeśli dwie wartości skrótu są mapowane na ten sam wpis - „kolizja hash” - HashMap tworzy połączoną listę.

Kolizje z skrótami mogą spowodować utratę wydajności mapy skrótów. W skrajnym przypadku, jeśli wszystkie twoje klucze mają ten sam kod skrótu lub jeśli mają różne kody skrótu, ale wszystkie są mapowane do tego samego gniazda, twoja mapa skrótów zamienia się w połączoną listę.

Więc jeśli widzisz problemy z wydajnością, pierwszą rzeczą, którą sprawdzę, jest: Czy otrzymuję losowo wyglądającą dystrybucję kodów skrótów? Jeśli nie, potrzebujesz lepszej funkcji skrótu. Cóż, „lepsze” w tym przypadku może oznaczać „lepsze dla mojego konkretnego zestawu danych”. Na przykład, załóżmy, że pracujesz z łańcuchami i wziąłeś długość ciągu dla wartości skrótu. (Nie jak działa String.hashCode w Javie, ale podam prosty przykład). Jeśli twoje łańcuchy mają bardzo różne długości, od 1 do 10 000 i są dość równomiernie rozłożone w tym zakresie, może to być bardzo dobre funkcja skrótu. Ale jeśli wszystkie twoje łańcuchy składają się z 1 lub 2 znaków, byłaby to bardzo zła funkcja skrótu.

Edycja: Powinienem dodać: Za każdym razem, gdy dodajesz nowy wpis, HashMap sprawdza, czy jest to duplikat. Kiedy dochodzi do kolizji hash, musi porównać przychodzący klucz z każdym kluczem, który jest mapowany do tego gniazda. Tak więc w najgorszym przypadku, gdy wszystko jest mieszane do jednego gniazda, drugi klucz jest porównywany z pierwszym kluczem, trzeci klucz jest porównywany z # 1 i # 2, czwarty klucz jest porównywany z # 1, # 2 i # 3 itd. Zanim dotrzesz do klucza nr 1 miliona, zrobiłeś już ponad bilion porównań.

@Oscar: Umm, nie rozumiem, dlaczego to „nie do końca”. To bardziej jak „pozwól mi wyjaśnić”. Ale tak, to prawda, że ​​jeśli utworzysz nowy wpis z tym samym kluczem, co istniejący wpis, spowoduje to nadpisanie pierwszego wpisu. To właśnie miałem na myśli, gdy mówiłem o szukaniu duplikatów w ostatnim akapicie: za każdym razem, gdy klucz jest mieszany z tym samym gniazdem, HashMap musi sprawdzić, czy jest to duplikat istniejącego klucza, czy też znajdują się w tym samym gnieździe przez przypadek funkcja skrótu. Nie wiem, czy to jest „cały punkt” HashMap: powiedziałbym, że „cały punkt” polega na tym, że możesz szybko pobierać elementy za pomocą klucza.

Ale w każdym razie nie ma to wpływu na „cały punkt”, który próbowałem zrobić: Kiedy masz dwa klucze - tak, różne klucze, a nie ten sam klucz, który pojawia się ponownie - to mapowanie do tego samego gniazda w tabeli , HashMap tworzy połączoną listę. Następnie, ponieważ musi sprawdzać każdy nowy klucz, aby zobaczyć, czy w rzeczywistości jest to duplikat istniejącego klucza, każda próba dodania nowego wpisu, który mapuje do tego samego gniazda, musi śledzić połączoną listę, badając każdy istniejący wpis, aby sprawdzić, czy to jest duplikatem wcześniej widzianego klucza lub jeśli jest to nowy klucz.

Zaktualizuj długo po oryginalnym poście

Właśnie otrzymałem pozytywny głos na tę odpowiedź 6 lat po opublikowaniu, co skłoniło mnie do ponownego przeczytania pytania.

Funkcja skrótu podana w pytaniu nie jest dobrym hashem dla 26 milionów wpisów.

Suma a [0] + a [1] i b [0] + b [1] + b [2]. Mówi, że wartości każdego bajtu mieszczą się w zakresie od 0 do 51, więc daje to tylko (51 * 2 + 1) * (51 * 3 + 1) = 15 862 możliwe wartości skrótu. Przy 26 milionach wpisów oznacza to średnio około 1639 wpisów na wartość skrótu. To wiele, wiele kolizji, które wymagają wielu, wielu sekwencyjnych wyszukiwań na połączonych listach.

OP mówi, że różne zamówienia w tablicy a i tablicy b powinny być uważane za równe, tj. [[1,2], [3,4,5]]. Równa się ([[2,1], [5,3,4] ]), więc aby zrealizować kontrakt, muszą mieć równe kody skrótu. W porządku. Mimo to istnieje dużo ponad 15 000 możliwych wartości. Jego druga proponowana funkcja skrótu jest znacznie lepsza, dając szerszy zakres.

Chociaż ktoś inny skomentował, wydaje się niewłaściwe, aby funkcja skrótu zmieniała inne dane. Bardziej sensowne byłoby „znormalizowanie” obiektu podczas jego tworzenia lub uruchomienie funkcji skrótu na podstawie kopii tablic. Ponadto używanie pętli do obliczania stałych za każdym razem przez funkcję jest nieefektywne. Ponieważ są tutaj tylko cztery wartości, napisałbym albo

return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52;

co spowodowałoby, że kompilator wykonałby obliczenia raz w czasie kompilacji; lub mieć 4 stałe statyczne zdefiniowane w klasie.

Ponadto pierwsza wersja robocza funkcji skrótu zawiera kilka obliczeń, które nie dodają nic do zakresu wyników. Zauważ, że najpierw ustawia hash = 503, a następnie mnoży przez 5381, zanim nawet rozważa wartości z klasy. Więc ... w efekcie dodaje 503 * 5381 do każdej wartości. Co to daje? Dodanie stałej do każdej wartości skrótu po prostu spala cykle procesora bez osiągnięcia niczego użytecznego. Lekcja tutaj: dodawanie złożoności do funkcji skrótu nie jest celem. Celem jest uzyskanie szerokiego zakresu różnych wartości, a nie tylko dodanie złożoności ze względu na złożoność.

Moim pierwszym pomysłem jest upewnienie się, że odpowiednio inicjalizujesz HashMap. Z JavaDocs dla HashMap :

Instancja HashMap ma dwa parametry, które wpływają na jej wydajność: pojemność początkową i współczynnik obciążenia. Pojemność to liczba segmentów w tabeli mieszania, a pojemność początkowa to po prostu pojemność w momencie tworzenia tabeli mieszania. Współczynnik obciążenia jest miarą tego, jak pełny może być tablica skrótów, zanim jej pojemność zostanie automatycznie zwiększona. Gdy liczba wpisów w tablicy skrótów przekroczy iloczyn współczynnika obciążenia i bieżącej pojemności, tablica skrótów zostanie ponownie skasowana (to znaczy, że wewnętrzne struktury danych zostaną odbudowane), tak aby tablica skrótów miała około dwukrotnie większą liczbę segmentów.

Więc jeśli zaczynasz od zbyt małej mapy HashMap, to za każdym razem, gdy trzeba zmienić rozmiar, wszystkie skróty są ponownie obliczane ... co może być tym, co czujesz, gdy dojdziesz do 2-3 milionów punktów wstawiania.

Sugerowałbym podejście trzystopniowe:

1. Uruchom Javę z większą pamięcią: java -Xmx256Mna przykład, aby działać z 256 MB. W razie potrzeby użyj więcej i masz dużo pamięci RAM.

2. Buforuj obliczone wartości skrótu zgodnie z sugestią innego plakatu, aby każdy obiekt obliczał swoją wartość skrótu tylko raz.

3. Użyj lepszego algorytmu haszującego. Ten, który opublikowałeś, zwróciłby ten sam hash, gdzie a = {0, 1}, jak w przypadku a = {1, 0}, przy czym wszystkie inne elementy są równe.

Skorzystaj z tego, co daje ci Java za darmo.

public int hashCode() {
    return 31 * Arrays.hashCode(a) + Arrays.hashCode(b);
}

Jestem prawie pewien, że ma to znacznie mniejsze szanse na konflikt niż Twoja istniejąca metoda hashCode, chociaż zależy to od dokładnej natury twoich danych.

Wchodzenie w szarą strefę „on / off topic”, ale konieczne, aby wyeliminować nieporozumienia dotyczące sugestii Oscara Reyesa, że ​​więcej zderzeń z haszowaniem jest dobrą rzeczą, ponieważ zmniejsza liczbę elementów w HashMap. Mogę źle zrozumieć, co mówi Oscar, ale nie wydaje mi się, że jestem jedyny: kdgregory, delfuego, Nash0 i wszyscy zdaje się mieć to samo (błędne) zrozumienie.

Jeśli rozumiem, co mówi Oscar o tej samej klasie z tym samym hashcode, proponuje, aby tylko jedna instancja klasy z podanym hashcode została wstawiona do HashMap. Na przykład, jeśli mam wystąpienie SomeClass z kodem skrótu 1 i drugie wystąpienie SomeClass z kodem skrótu 1, wstawiane jest tylko jedno wystąpienie SomeClass.

Przykład wklejanego kodu Java pod adresem http://pastebin.com/f20af40b9 wydaje się wskazywać, że powyższe poprawnie podsumowuje to, co proponuje Oscar.

Niezależnie od jakiegokolwiek zrozumienia lub nieporozumienia, dzieje się tak, że różne instancje tej samej klasy nie są wstawiane tylko raz do HashMap, jeśli mają ten sam hashcode - nie dopóki nie zostanie ustalone, czy klucze są równe, czy nie. Kontrakt z hashcode wymaga, aby równe obiekty miały ten sam hashcode; jednak nie wymaga, aby nierówne obiekty miały różne hashcodes (chociaż może to być pożądane z innych powodów) [1].

Poniżej znajduje się przykład pastebin.com/f20af40b9 (do którego Oscar odwołuje się co najmniej dwukrotnie), ale został on nieco zmodyfikowany, aby używać asercji JUnit zamiast printlines. Ten przykład służy do wspierania propozycji, że te same kody skrótów powodują kolizje, a gdy klasy są takie same, tworzony jest tylko jeden wpis (np. Tylko jeden ciąg znaków w tym konkretnym przypadku):

@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // AND equal
    assertTrue(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(2, map.size());

    assertEquals(2, map.get("ese"));
    assertEquals(3, map.get(some));

    assertTrue(s.equals(ese) && s.equals("ese"));
}

class SomeClass {
    public int hashCode() {
        return 100727;
    }
}

Jednak hashcode nie jest kompletną historią. To, czego przykład pastebin pomija, to fakt, że oba si esesą równe: oba są łańcuchem „ese”. Zatem wstawianie lub pobieranie zawartości mapy przy użyciu klucza slub eselub "ese"jako klucza jest równoważne, ponieważ s.equals(ese) && s.equals("ese").

Drugi test dowodzi, że błędem jest stwierdzić, że identyczne hashcodes na tej samej klasy jest powód klucz -> wartość s -> 1jest zastępowane przez ese -> 2kiedy map.put(ese, 2)nazywa się w jednym teście. W teście dwa, si esenadal mają taką samą hashcode (jak zweryfikowane assertEquals(s.hashCode(), ese.hashCode());) i są tej samej klasy. Jednak si esesą to MyStringinstancje w tym teście, a nie Stringinstancje Javy - jedyną różnicą istotną dla tego testu jest równość: String s equals String esew teście pierwszym powyżej, podczas gdy MyStrings s does not equal MyString esew teście drugim:

@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // BUT not equal
    assertFalse(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(3, map.size());

    assertEquals(1, map.get(s));
    assertEquals(2, map.get(ese));
    assertEquals(3, map.get(some));
}

/**
 * NOTE: equals is not overridden so the default implementation is used
 * which means objects are only equal if they're the same instance, whereas
 * the actual Java String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return 100727;
    }
}

Opierając się na późniejszym komentarzu, Oscar wydaje się odwracać to, co powiedział wcześniej, i uznaje znaczenie równości. Jednak nadal wydaje się, że to, co się liczy, a nie „ta sama klasa”, jest równe, jest niejasne (wyróżnienie moje):

"Niezupełnie. Lista jest tworzona tylko wtedy, gdy hash jest taki sam, ale klucz jest inny. Na przykład, jeśli String daje hashcode 2345, a Integer daje ten sam hashcode 2345, to liczba całkowita jest wstawiana do listy, ponieważ String. equals (Integer) jest fałszem. Ale jeśli masz tę samą klasę (lub przynajmniej .equals zwraca true), to używany jest ten sam wpis. Na przykład new String („one”) i „new String („ one ”) używane jako keys, użyją tego samego wpisu. Właściwie jest to CAŁY punkt HashMap na pierwszym miejscu! Przekonaj się sam: pastebin.com/f20af40b9 - Oscar Reyes "

w porównaniu z wcześniejszymi komentarzami, które wyraźnie odnoszą się do znaczenia identycznej klasy i tego samego kodu skrótu, bez wzmianki o równych:

"@delfuego: Przekonaj się sam: pastebin.com/f20af40b9 Więc w tym pytaniu używana jest ta sama klasa (poczekaj chwilę, ta sama klasa jest używana, prawda?) Co oznacza, że ​​gdy ten sam hash jest używany ten sam wpis jest używany i nie ma "listy" wpisów. - Oscar Reyes "

lub

"Właściwie to zwiększyłoby wydajność. Im więcej kolizji równa się mniej wpisów w równaniu z hashtagiem. Mniej pracy do wykonania. Czy hash (który wygląda dobrze) ani hashtable (który działa świetnie), założę się, że jest na obiekcie) kreacja, w której wydajność jest degradująca. - Oscar Reyes ”

lub

„@kdgregory: Tak, ale tylko wtedy, gdy kolizja występuje z różnymi klasami, dla tej samej klasy (co ma miejsce) używany jest ten sam wpis. - Oscar Reyes”

Ponownie, mogę źle zrozumieć, co właściwie próbował powiedzieć Oscar. Jednak jego oryginalne komentarze spowodowały tyle zamieszania, że ​​rozsądne wydaje się wyjaśnienie wszystkiego za pomocą kilku wyraźnych testów, więc nie ma żadnych wątpliwości.

[1] - Z Effective Java, Second Edition autorstwa Joshua Blocha:

• Za każdym razem, gdy jest wywoływana na tym samym obiekcie więcej niż jeden raz podczas wykonywania aplikacji, metoda hashCode musi konsekwentnie zwracać tę samą liczbę całkowitą, pod warunkiem, że nie zostaną zmodyfikowane żadne informacje użyte w porównaniach równych na obiekcie. Ta liczba całkowita nie musi pozostawać spójna od jednego wykonania aplikacji do innego wykonania tej samej aplikacji.

• Jeśli dwa obiekty są równe zgodnie z metodą equal s (Obj ect), to wywołanie metody hashCode na każdym z dwóch obiektów musi dać ten sam wynik w postaci liczby całkowitej.

• Nie jest wymagane, aby jeśli dwa obiekty były nierówne zgodnie z metodą equal s (Object), to wywołanie metody hashCode na każdym z dwóch obiektów musi dać różne wyniki w postaci liczb całkowitych. Jednak programista powinien mieć świadomość, że tworzenie różnych wyników całkowitych dla nierównych obiektów może poprawić wydajność tablic mieszających.

Jeśli tablice w Twoim wysłanym hashCode są bajtami, prawdopodobnie otrzymasz wiele duplikatów.

a [0] + a [1] zawsze będzie mieścić się w przedziale od 0 do 512. dodanie b zawsze da liczbę z przedziału od 0 do 768. pomnóż je, a uzyskasz górny limit 400 000 unikalnych kombinacji, zakładając, że dane są doskonale rozmieszczone wśród wszystkich możliwych wartości każdego bajtu. Jeśli twoje dane są w ogóle regularne, prawdopodobnie uzyskasz znacznie mniej unikalnych wyników tej metody.

HashMap ma początkową pojemność, a wydajność HashMap bardzo zależy od hashCode, który tworzy podstawowe obiekty.

Spróbuj poprawić oba.

Jeśli klucze mają jakiś wzór, możesz podzielić mapę na mniejsze mapy i mieć mapę indeksową.

Przykład: Klucze: 1, 2, 3, ... n 28 map po 1 milion każda. Mapa indeksu: 1 000 000 -> Mapa 1 1 000 000 - 2 000 000 -> Mapa 2

Będziesz więc przeprowadzać dwa wyszukiwania, ale zestaw kluczy będzie wynosić 1 000 000 w porównaniu do 28 000 000. Możesz to łatwo zrobić również za pomocą wzorów żądeł.

Jeśli klucze są całkowicie losowe, to nie zadziała

Jeśli dwie tablice bajtowe, o których wspomniałeś, to cały klucz, wartości mieszczą się w zakresie 0-51, są unikalne, a kolejność w tablicach a i b jest nieistotna, moja matematyka mówi mi, że jest tylko około 26 milionów możliwych permutacji i że prawdopodobnie próbujesz wypełnić mapę wartościami dla wszystkich możliwych kluczy.

W takim przypadku zarówno wypełnianie, jak i pobieranie wartości z magazynu danych byłoby oczywiście znacznie szybsze, jeśli użyjesz tablicy zamiast HashMap i zindeksujesz ją od 0 do 25989599.

Jestem spóźniony, ale kilka komentarzy na temat dużych map:

1. Jak omówiono szczegółowo w innych postach, z dobrym hashCode (), 26M wpisów w Mapie to nic wielkiego.
2. Jednak potencjalnie ukrytym problemem jest tutaj wpływ GC gigantycznych map.

Zakładam, że te mapy są długowieczne. tj. wypełniasz je i pozostają one przez cały czas trwania aplikacji. Zakładam również, że sama aplikacja jest długowieczna - jak jakiś serwer.

Każdy wpis w Java HashMap wymaga trzech obiektów: klucza, wartości i wpisu, który je łączy. Zatem 26 mln wpisów na mapie oznacza 26 mln * 3 == 78 mln obiektów. To jest w porządku, dopóki nie osiągniesz pełnego GC. W takim razie masz problem z zatrzymaniem świata. GC przyjrzy się każdemu z 78M obiektów i ustali, że wszystkie żyją. Ponad 78 milionów obiektów to po prostu wiele obiektów do obejrzenia. Jeśli Twoja aplikacja toleruje sporadyczne długie (być może wielosekundowe) przerwy, nie ma problemu. Jeśli próbujesz osiągnąć jakiekolwiek gwarancje opóźnienia, możesz mieć poważny problem (oczywiście jeśli chcesz zagwarantować opóźnienia, Java nie jest platformą do wyboru :)) Jeśli wartości w twoich mapach szybko się zmieniają, możesz skończyć z częstymi pełnymi kolekcjami co znacznie potęguje problem.

Nie znam dobrego rozwiązania tego problemu. Pomysły:

• Czasami można dostroić GC i rozmiary sterty, aby „głównie” uniemożliwić pełne GC.
• Jeśli zawartość mapy bardzo się zmienia, możesz wypróbować FastMap Javolution - może łączyć obiekty Entry, co może obniżyć częstotliwość pełnych zbierań
• Możesz stworzyć własną mapę impl i jawnie zarządzać pamięcią na bajcie [] (tj. Wymień procesor na bardziej przewidywalne opóźnienie poprzez serializację milionów obiektów w jeden bajt [] - ugh!)
• Nie używaj Javy do tej części - porozmawiaj z jakąś przewidywalną bazą danych w pamięci przez gniazdo
• Mam nadzieję, że nowy kolektor G1 pomoże (dotyczy głównie przypadku dużej liczby zmian)

Tylko kilka myśli od kogoś, kto spędził dużo czasu z gigantycznymi mapami w Javie.

W moim przypadku chcę stworzyć mapę z 26 milionami wpisów. Korzystając ze standardowej Java HashMap, szybkość sprzedaży staje się nieznośnie niska po 2-3 milionach wstawień.

Z mojego eksperymentu (projekt studencki w 2009):

• Zbudowałem Red Black Tree dla 100 000 węzłów od 1 do 100 000. Zajęło to 785,68 sekund (13 minut). I nie udało mi się zbudować RBTree dla 1 miliona węzłów (jak twoje wyniki z HashMap).
• Używając „drzewa pierwszego”, struktury danych mojego algorytmu. Mogłem zbudować drzewo / mapę dla 10 milionów węzłów w ciągu 21,29 sekund (RAM: 1,97 Gb). Koszt wyszukiwania pary klucz-wartość to O (1).

Uwaga: „Drzewo Prime” działa najlepiej z „ciągłymi kluczami” od 1 do 10 milionów. Aby pracować z kluczami takimi jak HashMap, potrzebujemy pewnych korekt dla nieletnich.

Więc co to jest #PrimeTree? Krótko mówiąc, jest to struktura danych drzewa, taka jak Drzewo binarne, z numerami gałęzi są liczbami pierwszymi (zamiast „2” -binarnych).

Możesz spróbować użyć bazy danych w pamięci, takiej jak HSQLDB .

SQLite pozwala używać go w pamięci.

Czy rozważałeś użycie do tego osadzonej bazy danych? Spójrz na Berkeley DB . Jest to oprogramowanie typu open source, obecnie należące do Oracle.

Przechowuje wszystko jako parę klucz-> wartość, NIE jest systemem RDBMS. i ma być szybki.

Najpierw powinieneś sprawdzić, czy używasz Map poprawnie, dobra metoda hashCode () dla kluczy, początkowa pojemność dla Map, prawidłowa implementacja mapy itp., Jak wiele innych odpowiedzi opisuje.

Następnie zasugerowałbym użycie profilera, aby zobaczyć, co faktycznie się dzieje i gdzie spędza się czas wykonania. Czy na przykład metoda hashCode () jest wykonywana miliardy razy?

Jeśli to nie pomoże, co powiesz na użycie czegoś takiego jak EHCache lub memcached ? Tak, są to produkty do buforowania, ale można je skonfigurować tak, aby miały wystarczającą pojemność i nigdy nie wykluczały żadnych wartości z pamięci podręcznej.

Inną opcją byłby silnik bazy danych, który jest lżejszy niż pełny SQL RDBMS. Może coś w rodzaju Berkeley DB .

Zwróć uwagę, że osobiście nie mam doświadczenia z wydajnością tych produktów, ale warto spróbować.

Możesz spróbować buforować obliczony kod skrótu do obiektu klucza.

Coś takiego:

public int hashCode() {
  if(this.hashCode == null) {
     this.hashCode = computeHashCode();
  }
  return this.hashCode;
}

private int computeHashCode() {
   int hash = 503;
   hash = hash * 5381 + (a[0] + a[1]);
   hash = hash * 5381 + (b[0] + b[1] + b[2]);
   return hash;
}

Oczywiście musisz uważać, aby nie zmienić zawartości klucza po pierwszym obliczeniu hashCode.

Edycja: Wygląda na to, że buforowanie ma wartości kodu nie jest opłacalne, gdy dodajesz każdy klucz tylko raz do mapy. W innej sytuacji może się to przydać.

Inny plakat wskazywał już, że implementacja hashcode spowoduje wiele kolizji ze względu na sposób, w jaki dodajesz wartości. Jestem skłonny tak być, jeśli spojrzysz na obiekt HashMap w debugerze, zobaczysz, że masz może 200 różnych wartości mieszania z bardzo długimi łańcuchami wiader.

Jeśli zawsze masz wartości z zakresu 0..51, każda z tych wartości będzie reprezentować 6 bitów. Jeśli zawsze masz 5 wartości, możesz utworzyć 30-bitowy kod skrótu z przesunięciami w lewo i dodatkami:

    int code = a[0];
    code = (code << 6) + a[1];
    code = (code << 6) + b[0];
    code = (code << 6) + b[1];
    code = (code << 6) + b[2];
    return code;

Przesunięcie w lewo jest szybkie, ale pozostawi cię z hashcodes, które nie są równomiernie rozłożone (ponieważ 6 bitów implikuje zakres 0..63). Alternatywą jest pomnożenie skrótu przez 51 i dodanie każdej wartości. To nadal nie będzie idealnie rozłożone (np. {2,0} i {1,52} zderzą się) i będzie wolniejsze niż przesunięcie.

    int code = a[0];
    code *= 51 + a[1];
    code *= 51 + b[0];
    code *= 51 + b[1];
    code *= 51 + b[2];
    return code;

Jak wspomniano, Twoja implementacja hashcode ma zbyt wiele kolizji, a ich naprawienie powinno zapewnić przyzwoitą wydajność. Ponadto pomocne będzie buforowanie hashCodes i efektywne implementowanie equals.

Jeśli chcesz jeszcze bardziej zoptymalizować:

Według twojego opisu istnieje tylko (52 * 51/2) * (52 * 51 * 50/6) = 29304600 różnych kluczy (z których 26000000, czyli około 90%, będzie obecnych). Dlatego możesz zaprojektować funkcję skrótu bez żadnych kolizji i użyć prostej tablicy zamiast tablicy mieszającej do przechowywania danych, zmniejszając zużycie pamięci i zwiększając szybkość wyszukiwania:

T[] array = new T[Key.maxHashCode];

void put(Key k, T value) {
    array[k.hashCode()] = value;

T get(Key k) {
    return array[k.hashCode()];
}

(Generalnie niemożliwe jest zaprojektowanie wydajnej, bezkolizyjnej funkcji skrótu, która dobrze się grupuje, dlatego HashMap będzie tolerować kolizje, co wiąże się z pewnym narzutem)

Zakładając ai bsą posortowane, możesz użyć następującej funkcji skrótu:

public int hashCode() {
    assert a[0] < a[1]; 
    int ahash = a[1] * a[1] / 2 
              + a[0];

    assert b[0] < b[1] && b[1] < b[2];

    int bhash = b[2] * b[2] * b[2] / 6
              + b[1] * b[1] / 2
              + b[0];
    return bhash * 52 * 52 / 2 + ahash;
}

static final int maxHashCode = 52 * 52 / 2 * 52 * 52 * 52 / 6;  

Myślę, że to jest bezkolizyjne. Dowodzenie tego pozostawiono jako ćwiczenie dla czytelnika ze skłonnościami matematycznymi.

In Effective Java: Podręcznik języka programowania (seria Java)

W rozdziale 3 można znaleźć dobre zasady, których należy przestrzegać podczas obliczania funkcji hashCode ().

Specjalnie:

Jeśli pole jest tablicą, traktuj je tak, jakby każdy element był oddzielnym polem. Oznacza to, że należy obliczyć kod skrótu dla każdego znaczącego elementu, stosując te reguły rekurencyjnie i połączyć te wartości w kroku 2.b. Jeśli każdy element w polu tablicy jest istotny, można użyć jednej z metod Arrays.hashCode dodanych w wersji 1.5.

Na początku przydziel dużą mapę. Jeśli wiesz, że będzie miał 26 milionów wpisów i masz na to pamięć, zrób new HashMap(30000000).

Czy na pewno masz wystarczająco dużo pamięci na 26 milionów wpisów z 26 milionami kluczy i wartości? To brzmi dla mnie jak dużo pamięci. Czy jesteś pewien, że odśmiecanie nadal działa dobrze przy twoim 2 do 3 milionach punktów? Mogę to sobie wyobrazić jako wąskie gardło.

Możesz spróbować dwóch rzeczy:

Te dwie czynności ogromnie zmniejszą ilość ponownego haszowania struktury i myślę, że są dość łatwe do przetestowania.

Jeśli to nie zadziała, rozważ użycie innej pamięci, takiej jak RDBMS.

EDYTOWAĆ

To dziwne, że ustawienie początkowej pojemności zmniejsza wydajność w twoim przypadku.

Zobacz z javadocs :

Jeśli początkowa pojemność jest większa niż maksymalna liczba wpisów podzielona przez współczynnik obciążenia, żadne operacje ponownego mieszania nie będą nigdy wykonywane.

Zrobiłem mikro-znak (który nie jest w żaden sposób ostateczny, ale przynajmniej dowodzi tego)

$cat Huge*java
import java.util.*;
public class Huge {
    public static void main( String [] args ) {
        Map map = new HashMap( 30000000 , 0.95f );
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
import java.util.*;
public class Huge2 {
    public static void main( String [] args ) {
        Map map = new HashMap();
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
$time java -Xms2g -Xmx2g Huge

real    0m16.207s
user    0m14.761s
sys 0m1.377s
$time java -Xms2g -Xmx2g Huge2

real    0m21.781s
user    0m20.045s
sys 0m1.656s
$

Tak więc, użycie początkowej pojemności spada z 21 do 16 sekund z powodu ponownego dopasowania. To pozostawia nam Twoją hashCodemetodę jako „obszar możliwości”;)

EDYTOWAĆ

To nie jest HashMap

Zgodnie z Twoim ostatnim wydaniem.

Myślę, że naprawdę powinieneś sprofilować swoją aplikację i zobaczyć, gdzie jest zużyta pamięć / procesor.

Stworzyłem klasę implementującą twoje to samo hashCode

Ten kod skrótu daje miliony kolizji, a następnie wpisy w HashMap są znacznie zmniejszone.

Przechodzę z 21, 16 w moim poprzednim teście do 10 i 8. Powodem jest to, że hashCode wywołuje dużą liczbę kolizji, a Ty nie przechowujesz 26 milionów obiektów, o których myślisz, ale znacznie niższą liczbę (powiedziałbym, że około 20 000).

Problem NIE JEST HASHMAPĄ, znajduje się w innym miejscu twojego kodu.

Najwyższy czas zdobyć profilera i dowiedzieć się, gdzie. Wydaje mi się, że chodzi o tworzenie elementu lub prawdopodobnie piszesz na dysk lub odbierasz dane z sieci.

Oto moja implementacja twojej klasy.

uwaga , nie użyłem zakresu 0-51 tak jak ty, ale -126 do 127 dla moich wartości i przyznaje się, że powtórzyłem, to dlatego, że zrobiłem ten test, zanim zaktualizowałeś swoje pytanie

Jedyną różnicą jest to, że twoja klasa będzie miała więcej kolizji, a tym samym mniej przedmiotów przechowywanych na mapie.

import java.util.*;
public class Item {

    private static byte w = Byte.MIN_VALUE;
    private static byte x = Byte.MIN_VALUE;
    private static byte y = Byte.MIN_VALUE;
    private static byte z = Byte.MIN_VALUE;

    // Just to avoid typing :) 
    private static final byte M = Byte.MAX_VALUE;
    private static final byte m = Byte.MIN_VALUE;


    private byte [] a = new byte[2];
    private byte [] b = new byte[3];

    public Item () {
        // make a different value for the bytes
        increment();
        a[0] = z;        a[1] = y;    
        b[0] = x;        b[1] = w;   b[2] = z;
    }

    private static void increment() {
        z++;
        if( z == M ) {
            z = m;
            y++;
        }
        if( y == M ) {
            y = m;
            x++;
        }
        if( x == M ) {
            x = m;
            w++;
        }
    }
    public String toString() {
        return "" + this.hashCode();
    }



    public int hashCode() {
        int hash = 503;
        hash = hash * 5381 + (a[0] + a[1]);
        hash = hash * 5381 + (b[0] + b[1] + b[2]);
        return hash;
    }
    // I don't realy care about this right now. 
    public boolean equals( Object other ) {
        return this.hashCode() == other.hashCode();
    }

    // print how many collisions do we have in 26M items.
    public static void main( String [] args ) {
        Set set = new HashSet();
        int collisions = 0;
        for ( int i = 0 ; i < 26000000 ; i++ ) {
            if( ! set.add( new Item() ) ) {
                collisions++;
            }
        }
        System.out.println( collisions );
    }
}

Użycie tej klasy ma klucz do poprzedniego programu

 map.put( new Item() , i );

daje mi:

real     0m11.188s
user     0m10.784s
sys 0m0.261s


real     0m9.348s
user     0m9.071s
sys  0m0.161s

Może spróbuj użyć, jeśli potrzebujesz go do synchronizacji

http://commons.apache.org/collections/api/org/apache/commons/collections/FastHashMap.html

Jakiś czas temu zrobiłem mały test z listą vs hashem, zabawną rzeczą było iterowanie listy i znalezienie obiektu zajęło tyle samo czasu w milisekundach, co użycie funkcji hashmaps get ... po prostu fyi. O tak, pamięć jest dużym problemem podczas pracy z hashmapami tego rozmiaru.

Popularne metody haszowania nie są zbyt dobre w przypadku dużych zestawów i, jak wskazano powyżej, używany hash jest szczególnie zły. Lepiej jest użyć algorytmu wyznaczania wartości skrótu o wysokim stopniu mieszania i pokrycia, takiego jak BuzHash (przykładowa implementacja pod adresem http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )