Java/HashMap/Performance

Question

Вот мой метод реализации HashMap put(). Он работает около 1500 мс для 100 000 элементов, а Collections - HashMap работает через 8 мс.

Что делает такую ​​огромную разницу в производительности?

(Моя хэш-функция просто на основе хэш-код(), коэффициент загрузки составляет около 0,6 поэтому он должен хорошо работать)

public boolean put(K key, V value) 
{ 
    if (size > cap*LOAD_FACTOR) expand(); 

    int i; 
    for(i=hash(key);container[i] != null;i=(i+1) % cap) 
    { 
     if(container[i].key.equals(key)) 
     { 
      container[i] = new Entry<K,V>(key,value); 
      return true; 
     }    
    } 

    container[i] = new Entry<K,V>(key,value); 
    size++; 

    return true; 

Answer 1

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

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

Также обратите внимание, что;

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