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

Question

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

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

Answer 1

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

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

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

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

Если вы знаете все ключи, возможно, вы также можете рассмотреть perfect hashing? Или сопоставить с простой структурой массива?

Answer 2

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 

Answer 3

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

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

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

Answer 4

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

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

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

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

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

Оба эти фактора очень специфичны для применения.

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

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

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

Answer 5

У меня есть карта экземпляра 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); 
      }