Я хочу создать большую HashMap, но put() производительность недостаточна. Любые идеи?

Приветствуются другие предложения по структуре данных, но мне нужна функция поиска Java Map:

map.get(key)

В моем случае я хочу создать карту с 26 миллионами записей. При использовании стандартной Java HashMap скорость вставки становится невыносимо медленной после 2-3 миллионов вставок.

Кроме того, кто-нибудь знает, может ли помочь использование разных распределений хэш-кода для ключей?

Мой метод хэш-кода:

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;
}

Я использую ассоциативное свойство сложения, чтобы гарантировать, что одинаковые объекты имеют одинаковый хэш-код. Массивы представляют собой байты со значениями в диапазоне от 0 до 51. Значения используются только один раз в любом массиве. Объекты равны, если массивы a содержат одинаковые значения (в любом порядке) и то же самое относится к массиву b. Значит, a = {0,1} b = {45,12,33} и a = {1,0} b = {33,45,12} равны.

РЕДАКТИРОВАТЬ, некоторые примечания:

• Некоторые люди критиковали использование хэш-карты или другой структуры данных для хранения 26 миллионов записей. Я не понимаю, почему это может показаться странным. Мне это кажется классической проблемой структур данных и алгоритмов. У меня 26 миллионов элементов, и я хочу иметь возможность быстро вставлять их и искать их в структуре данных: дайте мне структуру данных и алгоритмы.

• Установка начальной емкости Java HashMap по умолчанию на 26 миллионов снижает производительность.

• Некоторые люди предлагают использовать базы данных, в некоторых других ситуациях это определенно разумный вариант. Но я действительно задаю вопрос о структурах данных и алгоритмах, полная база данных была бы излишней и намного медленнее, чем хорошее решение для структуры данных (в конце концов, база данных - это просто программное обеспечение, но будет иметь связь и, возможно, накладные расходы на диск).

Как отмечали многие, hashCode()виноват метод. Он генерировал всего около 20 000 кодов для 26 миллионов различных объектов. Это в среднем 1300 объектов на хеш-ведро = очень-очень плохо. Однако, если я превращу два массива в число в базе 52, я гарантированно получу уникальный хэш-код для каждого объекта:

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;
}

Массивы сортируются, чтобы гарантировать, что эти методы выполняют hashCode()контракт о том, что одинаковые объекты имеют одинаковый хэш-код. При использовании старого метода среднее количество пут в секунду по блокам из 100000 пут, от 100000 до 2000000 было:

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

Использование нового метода дает:

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

Намного лучше. Старый метод сработал очень быстро, в то время как новый сохранил хорошую пропускную способность.

Одна вещь , которую я замечаю в вашем hashCode()методе является то , что порядок элементов в массивах a[]и b[]не имеют значения. Таким образом (a[]={1,2,3}, b[]={99,100}), хеш будет иметь то же значение, что и (a[]={3,1,2}, b[]={100,99}). Собственно все ключи k1и k2где sum(k1.a)==sum(k2.a)и sum(k1.b)=sum(k2.b)приведут к коллизиям. Предлагаю присвоить вес каждой позиции массива:

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

где, c0, c1и c3являются различными константами (вы можете использовать различные константы , bесли это необходимо). Это должно немного выровнять ситуацию.

Чтобы подробнее рассказать о Паскале: вы понимаете, как работает HashMap? У вас есть некоторое количество слотов в вашей хеш-таблице. Хеш-значение для каждого ключа находится и затем сопоставляется с записью в таблице. Если два значения хэша соответствуют одной и той же записи - «конфликт хешей» - HashMap создает связанный список.

Коллизии хэшей могут убить производительность хэш-карты. В крайнем случае, если все ваши ключи имеют один и тот же хэш-код или если у них разные хэш-коды, но все они соответствуют одному и тому же слоту, ваша хеш-карта превращается в связанный список.

Итак, если вы видите проблемы с производительностью, первое, что я проверю, это: получаю ли я случайное распределение хэш-кодов? Если нет, вам нужна лучшая хеш-функция. Что ж, «лучше» в этом случае может означать «лучше для моего конкретного набора данных». Например, предположим, что вы работали со строками и взяли длину строки в качестве хеш-значения. (Не так, как работает Java String.hashCode, но я просто привожу простой пример.) Если ваши строки имеют очень разную длину, от 1 до 10 000, и довольно равномерно распределены в этом диапазоне, это может быть очень хорошим хеш-функция. Но если все ваши строки состоят из 1 или 2 символов, это будет очень плохая хеш-функция.

Изменить: я должен добавить: каждый раз, когда вы добавляете новую запись, HashMap проверяет, не является ли это дубликатом. Когда возникает конфликт хешей, он должен сравнивать входящий ключ с каждым ключом, сопоставленным с этим слотом. Таким образом, в худшем случае, когда все хешируется в один слот, второй ключ сравнивается с первым ключом, третий ключ сравнивается с # 1 и # 2, четвертый ключ сравнивается с # 1, # 2 и # 3. и т. д. К тому времени, когда вы дойдете до ключевого №1 миллиона, вы сделали более триллиона сравнений.

@Oscar: Умм, я не понимаю, почему это «не совсем так». Это больше похоже на «позвольте мне уточнить». Но да, это правда, что если вы сделаете новую запись с тем же ключом, что и существующая запись, это перезапишет первую запись. Это то, что я имел в виду, когда говорил о поиске дубликатов в последнем абзаце: всякий раз, когда ключ хэшируется в один и тот же слот, HashMap должен проверять, является ли он дубликатом существующего ключа, или они находятся только в том же слоте по совпадению хеш-функция. Я не знаю, что в этом «весь смысл» HashMap: я бы сказал, что «весь смысл» в том, что вы можете быстро извлекать элементы по ключу.

Но в любом случае это не влияет на «всю мысль», которую я пытался сформулировать: когда у вас есть два ключа - да, разные ключи, а не один и тот же ключ снова появляется - эта карта соответствует одному и тому же слоту в таблице. , HashMap создает связанный список. Затем, поскольку он должен проверять каждый новый ключ, чтобы увидеть, действительно ли он является дубликатом существующего ключа, каждая попытка добавить новую запись, которая сопоставляется с этим же слотом, должна преследовать связанный список, проверяя каждую существующую запись, чтобы убедиться, что это является дубликатом ранее увиденного ключа, или если это новый ключ.

Обновление спустя много времени после исходного сообщения

Я только что проголосовал за этот ответ через 6 лет после публикации, что заставило меня перечитать вопрос.

Хэш-функция, указанная в вопросе, не подходит для 26 миллионов записей.

Он складывает вместе a [0] + a [1] и b [0] + b [1] + b [2]. Он говорит, что значения каждого байта находятся в диапазоне от 0 до 51, что дает только (51 * 2 + 1) * (51 * 3 + 1) = 15 862 возможных хеш-значения. При 26 миллионах записей это означает в среднем около 1639 записей на одно значение хеш-функции. Это много-много коллизий, требующих много-много последовательных поисков через связанные списки.

OP говорит, что разные порядки в массиве a и массиве b следует считать равными, то есть [[1,2], [3,4,5]]. Equals ([[2,1], [5,3,4] ]), поэтому для выполнения контракта они должны иметь одинаковые хэш-коды. Ладно. Тем не менее, существует более 15 000 возможных значений. Его вторая предложенная хеш-функция намного лучше, дает более широкий диапазон.

Хотя, как заметил кто-то другой, для хэш-функции кажется неуместным изменять другие данные. Было бы разумнее «нормализовать» объект при его создании или заставить хеш-функцию работать с копиями массивов. Кроме того, использование цикла для вычисления констант каждый раз через функцию неэффективно. Поскольку здесь всего четыре значения, я бы написал

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

что заставит компилятор выполнить вычисление один раз во время компиляции; или иметь 4 статические константы, определенные в классе.

Кроме того, в первом черновике хэш-функции есть несколько вычислений, которые ничего не делают для увеличения диапазона выходных данных. Обратите внимание, что он сначала устанавливает hash = 503, а затем умножает его на 5381, прежде чем даже рассматривать значения из класса. Итак ... фактически он добавляет 503 * 5381 к каждому значению. Что это дает? Добавление константы к каждому значению хэша просто сжигает циклы процессора, не выполняя ничего полезного. Урок здесь: усложнение хеш-функции - не цель. Цель состоит в том, чтобы получить широкий диапазон различных значений, а не просто добавить сложности ради сложности.

Моя первая идея - убедиться, что вы правильно инициализируете свою HashMap. Из JavaDocs для HashMap :

Экземпляр HashMap имеет два параметра, которые влияют на его производительность: начальная емкость и коэффициент загрузки. Емкость - это количество сегментов в хеш-таблице, а начальная емкость - это просто емкость на момент создания хеш-таблицы. Коэффициент загрузки - это мера того, насколько может быть заполнена хеш-таблица до того, как ее емкость автоматически увеличится. Когда количество записей в хэш-таблице превышает произведение коэффициента загрузки и текущей емкости, хеш-таблица перестраивается (то есть перестраиваются внутренние структуры данных), так что хеш-таблица имеет примерно вдвое больше сегментов.

Итак, если вы начинаете со слишком маленьким HashMap, то каждый раз, когда ему нужно изменить размер, все хэши пересчитываются ... что может быть тем, что вы чувствуете, когда добираетесь до точки вставки 2-3 миллионов.

Я бы предложил трехсторонний подход:

1. Запустите Java с большим объемом памяти: java -Xmx256Mнапример, для запуска с 256 мегабайтами. Если нужно, используйте больше, и у вас много оперативной памяти.

2. Кэшируйте свои рассчитанные хеш-значения, как это было предложено другим автором, чтобы каждый объект вычислял свое хеш-значение только один раз.

3. Используйте лучший алгоритм хеширования. Тот, который вы опубликовали, вернет тот же хеш, где a = {0, 1}, как и где a = {1, 0}, при прочих равных.

Используйте то, что Java дает вам бесплатно.

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

Я почти уверен, что у него гораздо меньше шансов столкнуться, чем у вашего существующего метода hashCode, хотя это зависит от точного характера ваших данных.

Попадание в серую область «вкл. / Выкл. По теме», но это необходимо для устранения путаницы в отношении предположения Оскара Рейеса о том, что большее количество хеш-коллизий - это хорошо, потому что это уменьшает количество элементов в HashMap. Я могу неправильно понять то, что говорит Оскар, но, похоже, я не единственный: kdgregory, delfuego, Nash0, и я, кажется, все разделяем одно (неправильное) понимание.

Если я понимаю, что Оскар говорит об одном и том же классе с тем же хэш-кодом, он предлагает, чтобы только один экземпляр класса с данным хэш-кодом был вставлен в HashMap. Например, если у меня есть экземпляр SomeClass с хэш-кодом 1 и второй экземпляр SomeClass с хэш-кодом 1, вставляется только один экземпляр SomeClass.

Пример Java pastebin на http://pastebin.com/f20af40b9, кажется, указывает, что вышеизложенное правильно резюмирует то, что предлагает Оскар.

Независимо от какого-либо понимания или недопонимания, происходит то, что разные экземпляры одного и того же класса не вставляются только один раз в HashMap, если они имеют одинаковый хэш-код - пока не будет определено, равны ли ключи или нет. Контракт хэш-кода требует, чтобы одинаковые объекты имели одинаковый хэш-код; однако не требуется, чтобы у неравных объектов были разные хэш-коды (хотя это может быть желательно по другим причинам) [1].

Пример pastebin.com/f20af40b9 (на который Оскар ссылается по крайней мере дважды) следует, но немного изменен для использования утверждений JUnit, а не строк печати. Этот пример используется для поддержки предложения о том, что одни и те же хэш-коды вызывают коллизии и когда классы одинаковы, создается только одна запись (например, только одна строка в этом конкретном случае):

@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;
    }
}

Однако хэш-код - это еще не все. Пример pastebin игнорирует тот факт, что sиese равны: они оба являются строкой «ese». Таким образом, вставка или получение содержимого карты с использованием sили eseили "ese"в качестве ключа эквивалентны, потому чтоs.equals(ese) && s.equals("ese") .

Второй тест демонстрирует, что ошибочный вывод о том, что идентичные хэш-коды в одном и том же классе являются причиной s -> 1перезаписи ключа -> значение ese -> 2при map.put(ese, 2)вызове в первом тесте. Во втором тесте sи eseвсе еще имеют тот же хэш-код (как проверено assertEquals(s.hashCode(), ese.hashCode());) И они одного класса. Тем не менее, sи eseявляются MyStringэкземплярами в этом тесте, а не Stringэкземплярами Java - единственная разница, имеющая отношение к этому тесту, заключается в том, что:String s equals String ese в первом тесте выше, тогда как MyStrings s does not equal MyString eseво втором тесте:

@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;
    }
}

Основываясь на более позднем комментарии, Оскар, кажется, переворачивает то, что он сказал ранее, и признает важность равных. Тем не менее, все еще кажется неясным идея, что значение имеет равенство, а не «тот же класс» (выделено мной):

"Не совсем. Список создается только в том случае, если хеш-код такой же, но ключ другой. Например, если String дает хэш-код 2345, а Integer дает тот же хэш-код 2345, тогда целое число вставляется в список, потому что String. equals (Integer) имеет значение false. Но если у вас тот же класс (или, по крайней мере, .equals возвращает true), то используется та же запись. Например, new String ("one") и `new String (" one ") используются как ключи, будут использовать одну и ту же запись. На самом деле это ВСЯ точка HashMap в первую очередь! Убедитесь сами: pastebin.com/f20af40b9 - Oscar Reyes "

по сравнению с более ранними комментариями, в которых явно говорится о важности идентичного класса и одного и того же хэш-кода, без упоминания равенства:

"@delfuego: Убедитесь сами: pastebin.com/f20af40b9 Итак, в этом вопросе используется один и тот же класс (подождите, тот же класс используется правильно?) Это означает, что при использовании одного и того же хеша одна и та же запись используется, и нет «списка» записей. - Оскар Рейес »

или

"На самом деле это повысило бы производительность. Чем больше столкновений, тем меньше записей в уравнении хэш-таблицы. Меньше работы, которую нужно сделать. Это не хеш (который выглядит нормально), ни хеш-таблица (которая отлично работает), я уверен, что это на объекте создание, где производительность ухудшается. - Оскар Рейес "

или

«@kdgregory: Да, но только если столкновение происходит с разными классами, для одного и того же класса (что имеет место) используется одна и та же запись. - Оскар Рейес»

Опять же, я могу неправильно понять, что на самом деле пытался сказать Оскар. Однако его первоначальные комментарии вызвали достаточно путаницы, поэтому кажется разумным все прояснить с помощью некоторых явных тестов, чтобы не оставалось никаких сомнений.

[1] - Из « Эффективной Java», второе издание , Джошуа Блох:

• Каждый раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения, метод hashCode должен последовательно возвращать одно и то же целое число, при условии, что информация, используемая в равных сравнениях с объектом, не изменяется. Это целое число не обязательно должно оставаться непротиворечивым от одного выполнения приложения к другому выполнению того же самого приложения.

• Если два объекта равны в соответствии с методом equal s (Obj ect), то вызов метода hashCode для каждого из двух объектов должен давать одинаковый целочисленный результат.

• Не требуется, чтобы, если два объекта не равны в соответствии с методом equal s (Object), тогда вызов метода hashCode для каждого из двух объектов должен давать различные целочисленные результаты. Однако программист должен знать, что получение различных целочисленных результатов для неравных объектов может улучшить производительность хеш-таблиц.

Если массивы в вашем опубликованном хэш-коде являются байтами, то у вас, скорее всего, будет много дубликатов.

a [0] + a [1] всегда будет между 0 и 512. добавление b всегда приведет к числу от 0 до 768. умножьте их, и вы получите верхний предел в 400 000 уникальных комбинаций, при условии, что ваши данные идеально распределены среди всех возможных значений каждого байта. Если ваши данные вообще регулярны, у вас, вероятно, будет гораздо меньше уникальных результатов этого метода.

HashMap имеет начальную емкость, а производительность HashMap очень сильно зависит от hashCode, который создает базовые объекты.

Попробуйте настроить оба.

Если ключи имеют какой-либо шаблон, вы можете разделить карту на более мелкие карты и получить карту индекса.

Пример: Ключи: 1,2,3, .... n 28 карт по 1 миллиону каждая. Индексная карта: 1-1,000,000 -> Map1 1,000,000-2,000,000 -> Map2

Таким образом, вы выполните два поиска, но набор ключей будет равен 1 000 000 против 28 000 000. Вы также можете легко сделать это с помощью шаблонов укусов.

Если ключи полностью случайны, это не сработает.

Если два байтовых массива, которые вы упомянули, представляют собой весь ваш ключ, значения находятся в диапазоне от 0 до 51, уникальны, а порядок в массивах a и b незначителен, мои математические вычисления говорят мне, что существует только около 26 миллионов возможных перестановок и что вы, вероятно, пытаетесь заполнить карту значениями для всех возможных ключей.

В этом случае и заполнение, и получение значений из вашего хранилища данных, конечно, будет намного быстрее, если вы будете использовать массив вместо HashMap и проиндексировать его от 0 до 25989599.

Я здесь опоздал, но пара комментариев по поводу больших карт:

1. Как подробно обсуждается в других сообщениях, с хорошим hashCode () 26M записей на карте не имеют большого значения.
2. Однако потенциально скрытой проблемой здесь является влияние гигантских карт на сборщик мусора.

Я предполагаю, что эти карты долговечные. т.е. вы заполняете их, и они остаются на время работы приложения. Я также предполагаю, что само приложение долгоживущее - вроде какого-то сервера.

Каждая запись в Java HashMap требует трех объектов: ключа, значения и записи, которая связывает их вместе. Таким образом, 26M записей на карте означает 26M * 3 == 78M объектов. Это нормально, пока вы не достигнете полного GC. Тогда у вас есть проблема паузы в мире. Сборщик мусора просмотрит каждый из 78 миллионов объектов и определит, что все они живы. 78M + объектов - это просто множество объектов, на которые стоит смотреть. Если ваше приложение может выдерживать периодические длительные (возможно, несколько секунд) паузы, проблем нет. Если вы пытаетесь добиться каких-либо гарантий задержки, у вас может быть серьезная проблема (конечно, если вам нужны гарантии задержки, Java - не та платформа, которую следует выбирать :)) Если значения на ваших картах быстро меняются, вы можете в конечном итоге часто получать полные сборы что сильно усугубляет проблему.

Я не знаю отличного решения этой проблемы. Идеи:

• Иногда можно настроить сборщик мусора и размеры кучи, чтобы «в основном» не допустить полных сборщиков мусора.
• Если содержимое вашей карты сильно меняется, вы можете попробовать FastMap от Javolution - он может объединять объекты Entry, что может снизить частоту полных сборов.
• Вы можете создать свою собственную карту impl и явно управлять памятью на byte [] (то есть заменить процессор на более предсказуемую задержку, сериализуя миллионы объектов в один байт [] - тьфу!)
• Не используйте Java для этой части - поговорите с какой-то предсказуемой БД в памяти через сокет
• Надеюсь, что новый коллектор G1 поможет (в основном относится к случаю высокого оттока)

Просто некоторые мысли от того, кто много времени провел с гигантскими картами на Java.

В моем случае я хочу создать карту с 26 миллионами записей. При использовании стандартной Java HashMap скорость вставки становится невыносимо медленной после 2-3 миллионов вставок.

Из моего эксперимента (студенческий проект 2009 г.):

• Я построил Red Black Tree для 100000 узлов от 1 до 100000. На это ушло 785,68 секунды (13 минут). И мне не удалось создать RBTree для 1 миллиона узлов (как ваши результаты с HashMap).
• Используя "Prime Tree", мой алгоритм структуры данных. Я мог построить дерево / карту для 10 миллионов узлов за 21,29 секунды (RAM: 1,97 ГБ). Стоимость пары "ключ-значение" для поиска - O (1).

Примечание: «Prime Tree» лучше всего работает с «непрерывными ключами» от 1 до 10 миллионов. Для работы с такими ключами, как HashMap, нам понадобится небольшая корректировка.

Итак, что такое #PrimeTree? Короче говоря, это древовидная структура данных, такая как двоичное дерево, где номера ветвей являются простыми числами (вместо двоичного числа "2").

Вы можете попробовать использовать базу данных в памяти, такую ​​как HSQLDB .

SQLite позволяет использовать его в памяти.

Думали ли вы об использовании встроенной базы данных для этого? Посмотрите на Berkeley DB . Это открытый исходный код, сейчас принадлежит Oracle.

Он хранит все как пару Key-> Value, это НЕ СУБД. и он стремится быть быстрым.

Сначала вы должны убедиться, что вы правильно используете Map, хороший метод hashCode () для ключей, начальную емкость для Map, правильную реализацию Map и т.д., как описано во многих других ответах.

Затем я бы предложил использовать профилировщик, чтобы увидеть, что на самом деле происходит и на что уходит время выполнения. Например, выполняется ли метод hashCode () миллиарды раз?

Если это не поможет, как насчет использования чего-то вроде EHCache или memcached? ? Да, это продукты для кэширования, но вы можете настроить их так, чтобы они имели достаточную емкость и никогда не вытесняли какие-либо значения из хранилища кешей.

Другой вариант - какой-нибудь механизм базы данных, который легче, чем полная СУБД SQL. Что-то вроде Berkeley DBМожет быть, что- .

Обратите внимание, что лично у меня нет опыта работы с этими продуктами, но попробовать их стоит.

Вы можете попытаться кэшировать вычисленный хэш-код в ключевой объект.

Что-то вроде этого:

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;
}

Конечно, вы должны быть осторожны, чтобы не изменить содержимое ключа после того, как хэш-код был вычислен в первый раз.

Изменить: кажется, что кеширование значений кода не имеет смысла, когда вы добавляете каждый ключ только один раз на карту. В другой ситуации это может быть полезно.

Другой плакат уже указал, что ваша реализация хэш-кода приведет к множеству коллизий из-за того, как вы складываете значения вместе. Я согласен с тем, что если вы посмотрите на объект HashMap в отладчике, вы обнаружите, что у вас может быть 200 различных значений хеш-функции с чрезвычайно длинными цепочками сегментов.

Если у вас всегда есть значения в диапазоне 0..51, для представления каждого из этих значений потребуется 6 бит. Если у вас всегда есть 5 значений, вы можете создать 30-битный хэш-код со сдвигом влево и дополнениями:

    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;

Сдвиг влево выполняется быстро, но в результате вы получите хэш-коды, которые распределены неравномерно (поскольку 6 бит подразумевают диапазон 0..63). Альтернативный вариант - умножить хэш на 51 и сложить каждое значение. Это все еще не будет идеально распределено (например, {2,0} и {1,52} будут сталкиваться) и будет медленнее, чем сдвиг.

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

Как уже отмечалось, ваша реализация хэш-кода имеет слишком много конфликтов, и их исправление должно привести к достойной производительности. Более того, поможет кеширование хэш-кодов и эффективное использование равенства.

Если вам нужно еще больше оптимизировать:

Судя по вашему описанию, всего (52 * 51/2) * (52 * 51 * 50/6) = 29304600 разных ключей (из них 26000000, т.е. около 90%, будут присутствовать). Следовательно, вы можете разработать хэш-функцию без каких-либо коллизий и использовать простой массив, а не хэш-карту для хранения ваших данных, уменьшая потребление памяти и увеличивая скорость поиска:

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

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

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

(Как правило, невозможно разработать эффективную хэш-функцию без коллизий, которая хорошо кластеризуется, поэтому HashMap допускает коллизии, что влечет за собой некоторые накладные расходы)

Предполагая, что aи bсортируются, вы можете использовать следующую хеш-функцию:

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;  

Думаю, это без столкновений. Доказательство этого оставлено в качестве упражнения для математически склонного читателя.

В Effective Java: Руководство по языку программирования (серия Java)

В главе 3 вы можете найти хорошие правила, которым нужно следовать при вычислении hashCode ().

Специально:

Если поле является массивом, относитесь к нему так, как если бы каждый элемент был отдельным полем. То есть вычислить хэш-код для каждого значимого элемента, рекурсивно применяя эти правила, и объединить эти значения на шаге 2.b. Если каждый элемент в поле массива имеет значение, вы можете использовать один из методов Arrays.hashCode, добавленных в версии 1.5.

Вначале разместите большую карту. Если вы знаете, что в нем будет 26 миллионов записей и у вас есть для этого достаточно памяти, выполнитеnew HashMap(30000000) .

Вы уверены, что у вас достаточно памяти для 26 миллионов записей с 26 миллионами ключей и значений? Для меня это звучит как много воспоминаний. Вы уверены, что сборка мусора все еще работает на вашей отметке в 2–3 миллиона? Я мог представить это как узкое место.

Вы можете попробовать две вещи:

Эти два действия значительно сократят объем перефразирования структуры, и я думаю, что их довольно легко протестировать.

Если это не сработает, рассмотрите возможность использования другого хранилища, такого как СУБД.

РЕДАКТИРОВАТЬ

Странно, что установка начальной емкости снижает производительность в вашем случае.

Смотрите из javadocs :

Если начальная емкость превышает максимальное количество записей, разделенное на коэффициент загрузки, никакие операции повторного хеширования никогда не будут выполняться.

Я сделал микропляж (который никоим образом не является окончательным, но, по крайней мере, доказывает это)

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

Таким образом, использование начальной емкости снижается с 21 до 16 из-за перефазировки. Это оставляет нам ваш hashCodeметод как «область возможностей»;)

РЕДАКТИРОВАТЬ

Это не HashMap

Согласно вашему последнему изданию.

Я думаю, вам действительно следует профилировать свое приложение и посмотреть, где он потребляет память / процессор.

Я создал класс, реализующий ваши hashCode

Этот хэш-код дает миллионы коллизий, после чего количество записей в HashMap резко сокращается.

Я перехожу с 21 до 16 в моем предыдущем тесте на 10 и 8. Причина в том, что hashCode вызывает большое количество столкновений, и вы храните не 26 миллионов объектов, которые, как вы думаете, а гораздо более низкое число (около 20 тысяч, я бы сказал) Итак:

Проблема НЕ В ХЭШ-КАРТЕ находится где-то еще в вашем коде.

Пора обзавестись профайлером и узнать где. Я бы подумал, что это связано с созданием элемента, или, возможно, вы пишете на диск или получаете данные из сети.

Вот моя реализация вашего класса.

нота я не использовал диапазон 0-51, как вы, но от -126 до 127 для моих значений и допускает повторение, потому что я провел этот тест до того, как вы обновили свой вопрос

Единственное отличие состоит в том, что у вашего класса будет больше столкновений, следовательно, на карте будет храниться меньше элементов.

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 );
    }
}

Использование этого класса имеет ключ для предыдущей программы

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

дает мне:

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


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

Может быть, попробуйте использовать, если вам нужно синхронизировать

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

Некоторое время назад я провел небольшой тест со списком и хэш-картой, забавно было перебирать список и поиск объекта занимал такое же количество времени в миллисекундах, что и использование функции получения хэш-карты ... просто к сведению. О да, память - большая проблема при работе с хэш-картами такого размера.

Используемые популярные методы хеширования на самом деле не очень хороши для больших наборов, и, как указывалось выше, используемый хеш особенно плох. Лучше использовать алгоритм хеширования с высоким уровнем смешивания и покрытия, такой как BuzHash (пример реализации на http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )