Производительность для HashMap, когда ключ гарантированно уникален - PullRequest
Новая
       15

Производительность для HashMap, когда ключ гарантированно уникален

4 голосов
/ 12 июля 2011

Если ключи, которые я хочу использовать, гарантированно являются уникальными (или, по крайней мере, можно предположить, что ключи являются уникальными), использование «vanilla» ConcurrentHashMap обеспечивает наилучшую производительность, илинужно ли модифицировать хеширующую функцию или метод put, чтобы избежать ненужного хеширования?

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

Ответы [ 5 ]

7 голосов
/ 12 июля 2011

Как уже упоминалось в комментариях, если вам не нужны поточно-ориентированные аспекты, не используйте ConcurrentHashMap.

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

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

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

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

1 голос
/ 12 июля 2011

Если ключи, которые я хочу использовать, гарантированно являются уникальными (или, по крайней мере, можно предположить, что ключи уникальны), использование «vanilla» ConcurrentHashMap обеспечивает лучшую производительность,

Обычно вы используете ConcurrentHashMap, если Map является потенциальным узким местом параллелизма.Если ваше приложение однопоточное или нет конфликтов, ConcurrentHashMap медленнее, чем HashMap.

, или необходимо изменить функцию хеширования или метод put, чтобы избежать ненужного хеширования?

Хеш-функция вычисляется один раз за «зонд» хеш-таблицы;например, один раз за get или put операцию.Вы можете уменьшить стоимость хэш-функции, кэшируя результат, но это потребует дополнительных 4 байтов памяти для каждого ключевого объекта.Является ли кэширование полезной оптимизацией, зависит от:

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

Оба эти фактора сильно зависят от приложения.

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

Кроме того, имеет ли числовой ключ какое-либо преимущество в производительности по сравнению с нечисловым ключом (таким как String или POJO с правильным хешированиемfunction)?

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

1 голос
/ 12 июля 2011

ConcurrentHashMap является самой дорогой из реализаций HashMap, потому что она безопасна для потоков.

Все карты должны иметь уникальные ключи, так что это данность.

Использование чисел имеет производительностьПреимущество, если вы используете коллекцию, которая поддерживает такие примитивы, как TLongHashMap, однако вы можете намного быстрее использовать собственную хеш-карту.

С http://vanillajava.blogspot.com/2011/07/low-gc-in-java-using-primitives.html

Test                                    Performance Memory used
Use Integer wrappers and HashMap        71 - 134 (ns)   53 MB/sec
Use int primitives and HashMap          45 - 76 (ns)    36 MB/sec
Use int primitives and FastMap          58 - 93 (ns)    28 MB/sec
Use int primitives and TIntIntHashMap   18 - 28 (ns)    nonimal
Use int primitives and simple hash map   6 - 9 (ns)     nonimal
0 голосов
/ 15 июля 2011

У меня есть карта экземпляров ConcurrentHashMap, доступ к которой осуществляется с помощью multithread.seeing под фрагментом кода.как насчет этих? 

Iterator<String> it = new TreeSet<String>(map.keySet()).iterator();
            while(it.hasNext())
            {
                id = it.next();
                synchronized(map)
                {
                    msg = map.get(id);
                    if(msg != null)
                        map.remove(id);
                }
                if(msg != null)
                listener.procMessage(msg);
            }
0 голосов
/ 12 июля 2011

Хэш-карты Java в конечном итоге поддерживаются массивом Entry<K,V>, где хеш-код K используется для определения слота в массиве, в котором хранится запись.

Размер используемого массива (обычно начинается с 16) намного меньше, чем число возможных хеш-кодов (2 ^ 32 ~ = 4 миллиарда), поэтому в этом массиве обязательно будут конфликты, даже если хеш-коды уникальный.

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

...