Jedną z rzeczy, które zauważyłem w Twojej metodzie hashCode() jest to, że kolejność elementów w tablicach a[] i b[] nie ma znaczenia. Tak więc (a[]={1,2,3}, b[]={99,100}) będzie hashować do tej samej wartości co (a[]={3,1,2}, b[]={100,99}). Właściwie wszystkie klucze k1 i k2 gdzie sum(k1.a)==sum(k2.a) i sum(k1.b)=sum(k2.b) spowodują kolizje. Proponuję przypisanie wagi 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, c1 i c3 są odrębnymi stałymi (w razie potrzeby możesz użyć różnych stałych dla b). To powinno trochę wyrównać. więcej.

Aby rozwinąć temat Pascala: czy rozumiesz, jak działa HashMap? Masz pewną liczbę slotów w tabeli hash. Wartość skrótu dla każdego klucza zostanie znaleziona, a następnie zmapowana do wpisu w tabeli. Jeśli dwie wartości skrótu mapują ten sam wpis -- a "hash collision" -- HashMap buduje połączoną listę.

Kolizje Hash mogą zabić wydajność mapy hash. W skrajnym przypadku, jeśli wszystkie klucze mają ten sam kod skrótu, lub jeśli mają różne kody skrótu, ale wszystkie mapują do tego samego miejsca, następnie Mapa hash zamienia się w połączoną listę.

Więc jeśli widzisz problemy z wydajnością, pierwszą rzeczą, którą chciałbym sprawdzić, jest: czy otrzymuję losową dystrybucję kodów hash? Jeśli nie, potrzebujesz lepszej funkcji hash. Cóż, "lepszy" w tym przypadku może oznaczać "lepszy dla mojego konkretnego zestawu danych". Załóżmy, że pracujesz z łańcuchami i wziąłeś Długość łańcucha dla wartości hash. (Nie jak Java ' s String.hashCode działa, ale wymyślam prosty przykład.) Jeśli struny mają bardzo różne długości, od 1 do 10 000 i są dość równomiernie rozmieszczone w tym zakresie, że może to być bardzo dobra funkcja skrótu. Ale jeśli Twoje ciągi są wszystkie 1 lub 2 znaki, byłoby to bardzo zła funkcja hash.

Edit: powinienem dodać: za każdym razem, gdy dodajesz nowy wpis, HashMap sprawdza, czy jest to duplikat. Kiedy dochodzi do kolizji hash, musi porównać klucz przychodzący z każdym kluczem, który mapował do tego gniazda. Tak więc w najgorszym przypadku, gdy wszystko haszysze do pojedynczego 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 itp. Zanim dojdziesz do klucza # 1 milion, zrobiłeś ponad bilion porównań.

@Oscar: Umm, nie widzę, jak to jest "nie do końca". To bardziej jak "pozwól mi wyjaśnić". Ale tak, to prawda, że jeśli zrobisz nowy wpis z tym samym kluczem co istniejący wpis, to nadpisze on pierwszy wpis. To miałem na myśli, kiedy mówiłem o szukanie duplikatów w ostatnim akapicie: za każdym razem, gdy klucz hashuje do tego samego gniazda, HashMap musi sprawdzić, czy jest to duplikat istniejącego klucza, lub czy są one po prostu w tym samym gnieździe przez przypadek funkcji hash. Nie wiem, czy to jest "cały punkt" Hashmapy: powiedziałbym, że "cały punkt" polega na tym, że można szybko pobierać elementy według klucza.

Ale w każdym razie, to nie ma wpływu na "cały punkt", który próbowałem zrobić: kiedy masz dwa klucze -- tak, różne klucze, nie ten sam klucz pojawia się ponownie -- Ta mapa do tego samego miejsca w tabeli, HashMap buduje połączoną listę. Następnie, ponieważ musi sprawdzić każdy nowy klucz, aby sprawdzić, czy w rzeczywistości jest to duplikat istniejącego klucza, każda próba dodania nowego wpisu, który mapy do tego samego gniazda muszą gonić połączoną listę badającą każdy istniejący wpis, aby zobaczyć, czy jest to duplikat wcześniej widzianego klucza, czy jest to nowy klucz.

Aktualizacja długo po oryginalnym poście

Właśnie głosowałem nad ta ODPOWIEDŹ 6 lat po opublikowaniu, która doprowadziła mnie do ponownego przeczytania pytania.

Podana w pytaniu funkcja hash nie jest dobrym Hashem dla 26 milionów wpisów.

Dodaje razem a [0]+a [1] i b [0] + b [1]+b[2]. Podaje wartości każdego bajtu z zakresu od 0 do 51, więc daje to tylko (51*2+1)*(51*3+1)=15,862 możliwe wartości hash. Przy 26 milionach wpisów oznacza to średnio około 1639 wpisów na wartość skrótu. To jest wiele, wiele kolizji, wymagających wiele, wiele sekwencyjnych przeszukuje połączone listy.

Op mówi, że różne porządki w tablicy a i tablicy b powinny być uważane za równe, tzn. [[1,2],[3,4,5]].równe([[2,1],[5,3,4]]), i tak aby wypełnić umowę muszą mieć równe kody hash. Ok. Mimo to istnieje znacznie więcej niż 15,000 możliwych wartości. Jego druga zaproponowana funkcja hash jest znacznie lepsza, dając szerszy zakres.

Chociaż, jak ktoś inny skomentował, wydaje się niestosowne, aby funkcja hash zmieniała inne dane. Byłoby bardziej sensowne jest "znormalizowanie" obiektu podczas jego tworzenia lub działanie funkcji skrótu z kopii tablic. Również używanie pętli do obliczania stałych za każdym razem za pomocą funkcji jest nieefektywne. Ponieważ są tu 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 miał 4 stałe statyczne zdefiniowane w klasie.

Również pierwszy szkic w funkcji hash ma kilka obliczenia, które nic nie dodają do zakresu wyjść. Zauważ, że najpierw ustawia hash = 503 niż mnoży przez 5381, zanim nawet rozważy 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 funkcji hash nie jest celem. Celem jest uzyskanie szerokiego zakresu różnych wartości, a nie tylko zwiększenie złożoności złożoności.

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ść: początkową pojemność i współczynnik obciążenia. Pojemność to liczba łyżek w tabeli hash, a pojemność początkowa to po prostu pojemność w momencie tworzenia tabeli hash. Współczynnik obciążenia jest miarą tego, jak pełna jest tabela hash, zanim jej pojemność zostanie automatycznie zwiększony. Gdy liczba wpisów w tabeli hash przekroczy iloczyn współczynnika obciążenia i bieżącej pojemności, tabela hash jest ponownie odświeżana (tzn. wewnętrzne struktury danych są przebudowywane) tak, że tabela hash ma około dwukrotnie większą liczbę łyżek.

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

Proponuję podejście trójstronne:

1. Uruchom Javę z większą pamięcią: java -Xmx256M na przykład, aby uruchomić z 256 megabajtami. Użyj więcej w razie potrzeby i masz dużo pamięci RAM.

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

3. Użyj lepszego algorytmu haszującego. Ten, który napisałeś, zwróci ten sam hash, gdzie a = {0, 1}, Jak wtedy, gdy a ={1, 0}, Wszystko inne jest równe.

Wykorzystaj to, co Java daje Ci za darmo.

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

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

Wejście w szarą strefę "On / off topic", ale konieczne, aby wyeliminować zamieszanie dotyczące sugestii Oscara Reyesa, że więcej kolizji hash jest dobrą rzeczą, ponieważ zmniejsza liczbę elementów w Hashmapie. Mogę źle zrozumieć, co mówi Oscar, ale nie wydaje się być jedynym: kdgregory, delfuego, Nash0, i wszyscy wydają się dzielić to samo (mis)zrozumienie.

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

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

The pastebin.com/f20af40b9 przykład (do którego Oscar odnosi się co najmniej dwa razy), ale zmodyfikowany nieco użyć twierdzeń JUnit zamiast printlines. Ten przykład jest używany do wspierania propozycji, że te same hashcody powodują kolizje, a gdy klasy są takie same, tworzony jest tylko jeden wpis (np.]}

@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ą. Przykład pastebin pomija fakt, że zarówno s, jak i ese są równe: oba są ciągiem "ese". W ten sposób wstawianie lub pobieranie zawartości mapy za pomocą s lub ese lub "ese" ponieważ wszystkie klucze są równoważne, ponieważ s.equals(ese) && s.equals("ese").

Drugi test pokazuje, że błędnym jest stwierdzenie, że identyczne hashcody na tej samej klasie są powodem, dla którego klucz -> wartość s -> 1 jest nadpisywany przez ese -> 2, gdy map.put(ese, 2) jest wywoływany w pierwszym teście. W drugim teście s i ese nadal mają ten sam hashcode (sprawdzony przez assertEquals(s.hashCode(), ese.hashCode());) i są tą samą klasą. Jednak s i ese są instancjami MyString w tym teście, a nie instancjami Javy String - z jedyną różnicą istotne dla tego testu są równe: String s equals String ese W teście pierwszym powyżej, podczas gdy MyStrings s does not equal MyString ese W 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;
    }
}

"nie bardzo. Lista jest tworzona tylko wtedy, gdy hash jest taki sam, ale klucz jest inny. Na przykład jeśli ciąg znaków daje hashcode 2345 and and Integer daje ten sam hashcode 2345, wtedy integer jest wstawiany do listy ponieważ String.equals (Integer ) jest false. Ale jeśli masz tę samą klasę ( lub przynajmniej .equals zwraca true) wtedy zostanie użyty ten sam wpis. Na przykład new String ("one") I ' new String ("one") używane jako klucze, użyją tego samego wpisu. Właściwie to jest cały sens HashMap na pierwszym miejscu! Przekonaj się sam: pastebin.com/f20af40b9 -Oscar Reyes "

"@delfuego: zobaczcie sami: pastebin.com/f20af40b9 Tak więc w tym pytaniu używa się tej samej klasy (chwila, ta sama klasa jest używana, prawda? ), Co oznacza, że gdy używany jest ten sam hash, używany jest ten sam wpis i nie ma "listy" wpisów. - Oscar Reyes "

Lub

"w rzeczywistości zwiększyłoby to wydajność. Im więcej kolizje eq mniej wpisów w Hashtable eq. mniej pracy. Czy nie hash (który wygląda dobrze ) ani hashtable (który działa świetnie ) założę się, że jest to tworzenie obiektu, gdzie wydajność jest degradująca. - Oscar Reyes "

Lub

"@kdgregory: tak, ale tylko wtedy, gdy dojdzie do kolizji z różnymi klasami, dla tej samej klasy (co ma miejsce ) zostanie użyty ten sam wpis. - Oscar Reyes "

[1] - From Effective Java, Second Edition by Joshua Bloch:

• Ilekroć jest wywoływana na tym samym obiekcie więcej niż jeden raz podczas wykonywania aplikacji, metoda hashCode musi konsekwentnie zwracać ta sama liczba całkowita, pod warunkiem, że żadne informacje nie są używane w równych s porównania na obiekt jest modyfikowany. Ta liczba całkowita nie musi pozostawać spójna od jednego wykonania aplikacji do innego wykonania tej samej aplikacji.

• Jeżeli dwa obiekty są sobie równe według metody equal s (Obj ect), to wywołanie metody hashCode na każdym z dwóch obiektów musi wytworzyć ten sam wynik całkowity.

• Nie jest wymagane, że jeżeli dwa obiekty są nierówne według metody equal s (Object), to wywołanie hashCode metoda na każdym z dwóch obiektów musi wytwarzać odrębne wyniki całkowite. Jednak programista powinien być świadomość, że generowanie odrębnych wyników całkowitych dla nierównych obiektów może poprawić wydajność tabel hashowych.

Jeśli tablice w opublikowanym hashCode są bajtami, prawdopodobnie skończysz z dużą ilością duplikatów.

A [0] + a[1] będzie zawsze pomiędzy 0 a 512. dodanie b zawsze daje liczbę z zakresu od 0 do 768. pomnóż je, a otrzymasz górną granicę 400 000 unikalnych kombinacji, zakładając, że Twoje dane są idealnie rozłożone między każdą możliwą wartość każdego bajtu. Jeśli Twoje dane są w ogóle regularne, prawdopodobnie masz 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ś Wzorzec, 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 indeksowa: 1-1, 000, 000 -> Map1 1,000,000-2,000,000 - > Map2

Więc będziesz robił dwa wyszukiwania, ale klucz zestaw będzie 1,000,000 vs 28,000,000. Można to łatwo zrobić z wzorców żądło również.

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

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

W tym 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 Hashmapy i indeksujesz ją od 0 do 25989599.

Jestem spóźniony, ale kilka komentarzy o dużych mapach:

1. Jak już wspomniano w innych postach, z dobrym hashCode (), 26m wpisów na mapie to nic wielkiego.
2. jednak potencjalnie ukrytym problemem jest wpływ GC na gigantyczne mapy.

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

Każdy wpis w Hashmapie Java wymaga trzech obiektów: klucza, wartości i wpisu, który je łączy. Zatem 26m wpisów na mapie oznacza 26m * 3 == 78m obiektów. To jest w porządku, dopóki nie osiągniesz pełnego GC. Więc masz problem z pauzą. GC sprawdzi każdy z 78m obiektów i stwierdzi, że wszyscy żyją. Obiekty 78M+ to po prostu dużo 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ąć wszelkie gwarancje latencji możesz mieć poważny problem (oczywiście jeśli chcesz gwarancji latencji, Java nie jest platformą do wyboru:)) jeśli wartości w Mapach szybko znikną, możesz skończyć z częstymi pełnymi zbiorami, które znacznie wiążą problem.

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

• czasami można dostroić rozmiary GC i sterty, aby "głównie" zapobiec pełnemu GCs.
• Jeśli zawartość twojej mapy jest zbyt duża, możesz spróbować Javolution ' s FastMap -- może łączyć Obiekty wejściowe, co może obniżyć częstotliwość pełnych zbiorów
• możesz stworzyć własne impl map i zarządzać pamięcią na bajcie [] (tzn. wymienić cpu na bardziej przewidywalne opóźnienia, serializując miliony obiektów w jeden bajt [] -- ugh!)
• nie używaj Javy do tej części -- rozmawiaj z jakimś przewidywalnym w pamięci DB przez gniazdo
• Mam nadzieję, że nowy G1 collector pomoże (dotyczy głównie wysokiego case)

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

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

W moim przypadku chcę stworzyć mapę z 26 milionami wpisów. Używając standardowej Java HashMap szybkość put staje się nieznośnie powolna po 2-3 milionach wstawek.

Z mojego eksperymentu (Projekt studencki w 2009 roku):

Zbudowałem czerwone czarne drzewo dla 100.000 węzłów z 1 do 100.000. Trwał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 Prime", moje dane algorytmu struktura. Mógłbym zbudować drzewo / mapę dla 10 milionów węzłów w ciągu 21,29 sekund (RAM: 1,97 Gb). Klucz wyszukiwania-wartość koszt jest O (1).

Uwaga: "drzewo Prime" działa najlepiej na "klawiszach ciągłych"od 1 do 10 milionów. Aby pracować z kluczami takimi jak HashMap potrzebujemy pewnych poprawek.

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

Czy rozważałeś użycie osadzonej bazy danych w tym celu? Spójrz na Berkeley DB . Jest to open-source, którego właścicielem jest Oracle now.

Przechowuje wszystko jako parę Key - > Value, nie jest to RDBMS. i ma być szybki.

Najpierw należy sprawdzić, czy poprawnie używasz Map, dobrej metody hashCode () dla kluczy, początkowej pojemności Mapy, właściwej implementacji Map itp. jak wiele innych odpowiedzi opisują.

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

Jeśli to nie pomoże, Co powiesz na użycie czegoś w rodzaju EHCache lubmemcached ? Tak, są produkty do buforowania, ale można je skonfigurować tak, że będą miały wystarczającą pojemność i nigdy nie będzie eksmitować żadnych wartości z pamięci podręcznej.

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

Zauważ, że osobiście nie mam doświadczenia z wydajnością tych produktów, ale mogą być warte spróbowania.

Możesz spróbować buforować obliczony kod hash do obiektu key.

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 należy uważać, aby nie zmieniać zawartości klucza po pierwszym obliczeniu hashCode.

Edit: wydaje się, ż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 już wskazał, że implementacja hashcode spowoduje wiele kolizji ze względu na sposób dodawania wartości razem. Jeśli spojrzysz na obiekt HashMap w debuggerze, przekonasz się, że masz może 200 różnych wartości skrótu, z bardzo długimi łańcuchami kubełkowymi.

Jeśli zawsze masz wartości z zakresu 0..51, każda z tych wartości zajmie 6 bitów do reprezentowania. Jeśli zawsze masz 5 wartości, możesz utworzyć 30-bitowy hashcode z lewymi przesunięciami 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 pozostawia hashcodes, które nie są równomiernie rozłożone (ponieważ 6 bitów oznacza zakres 0..63). Alternatywą jest pomnożyć hash przez 51 i dodać każdą wartość. 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 jej naprawienie powinno skutkować przyzwoitą wydajnością. Co więcej, pomocne będzie buforowanie hashcodów i efektywne implementowanie równych.

Jeśli potrzebujesz jeszcze bardziej zoptymalizować:

Według Twojego opisu, są tylko (52 * 51 / 2) * (52 * 51 * 50 / 6) = 29304600 różne klucze (z czego 26000000, czyli ok.90%). Dlatego można zaprojektować funkcję hash bez żadnych kolizji i użyć prostego Tablica zamiast hashmapy 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()];
}

(Ogólnie rzecz biorąc, nie jest możliwe zaprojektowanie wydajnej, bezkolizyjnej funkcji skrótu, która dobrze się klastruje, dlatego HashMap toleruje kolizje, które wiążą się z pewnymi kosztami)

Zakładając, że a i b są posortowane, możesz użyć następującej funkcji hash:

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;  

In Effective Java: Programming Language Guide (Java Series)

Rozdział 3 Możesz znaleźć dobre zasady, których należy przestrzegać przy obliczaniu hashCode().

Specjalnie:

Jeśli pole jest tablicą, traktuj je tak, jakby każdy element był osobnym polem. Oznacza to, że Oblicz kod hash dla każdego znaczącego elementu, stosując reguły te rekurencyjnie i łączą te wartości na krok 2.b. jeśli każdy element w polu tablicy jest znaczący, można użyć jednego z Tablice.hashCode metody dodane w wersji 1.5.

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

Jesteś pewien, że masz wystarczająco dużo pamięci na 26 milionów wpisów z 26 milionami kluczy i wartości? To brzmi jak dużo pamięci dla mnie. Czy jesteś pewien, że wywóz śmieci jest nadal w porządku za Twoje 2-3 miliony? Wyobrażam sobie to jako wąskie gardło.

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

• Spraw, aby twoja metoda hashCode zwróciła coś prostszego i skuteczniejszego, na przykład kolejny int

• Zainicjalizuj mapę jako:

  Map map = new HashMap( 30000000, .95f );
  

Te dwa działania znacznie zmniejszą ilość ponownego przerobu struktury i są dość łatwe do przetestowania, jak sądzę.

Jeśli to nie zadziała, rozważ użycie innego magazynu, takiego RDBMS.

EDIT

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, nigdy nie zostaną wykonane żadne operacje ponownego ładowania.

$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
$

Więc, używając początkowa pojemność spada z 21 do 16 z powodu ponownego ładowania. To pozostawia nam Twoją metodę hashCode jako "obszar możliwości";)

EDIT

Nie jest HashMap

Zgodnie z twoim ostatnim wydaniem.

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

I have created a class implementing your same hashCode

Że kod hash daje miliony kolizji, wtedy wpisy w HashMap jest znacznie zmniejszona.

Zdaję z 21s, 16s w poprzednim teście na 10s i 8s. powodem jest to, że hashCode prowokuje dużą liczbę kolizji i nie przechowujesz obiektów 26M, które myślisz, ale znacznie mniejszą liczbę (powiedziałbym, że o 20K), więc: {]}

Problem nie jest HASHMAP jest gdzie indziej w Twoim kodzie.

Najwyższy czas, aby znaleźć profilera i dowiedzieć się, gdzie. Myślę, że chodzi o stworzenie przedmiotu lub prawdopodobnie zapisujesz na dysk lub odbierasz dane z sieci.

Oto moja implementacja twojej klasy.

Uwaga nie używałem zakresu 0-51, jak ty, ale -126 do 127 dla moich wartości i przyznaje się powtarzane, to dlatego, że zrobiłem ten test, zanim zaktualizowałeś swoje pytanie

Jedyna różnica polega na tym, że twoja klasa będzie miała więcej kolizji, a więc 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 zsynchronizować

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

Jakiś czas temu zrobiłem mały test z listą vs hashmapą, zabawną rzeczą było iterowanie listy i znalezienie obiektu zajęło tyle samo czasu w milisekundach, co Korzystanie z funkcji get hashmaps... tak dla twojej wiadomości. Oh yeah pamięć jest dużym problemem podczas pracy z hashmapami o takim rozmiarze.

Popularne metody hashowania nie są zbyt dobre dla dużych zestawów i, jak wspomniano powyżej, używany hash jest szczególnie zły. Lepiej jest użyć algorytmu hash o wysokim mieszaniu i zasięgu, takiego jak BuzHash (przykładowa implementacja w http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm)