Почему HashMap содержит ключ медленнее, чем в Sun JDK? (ВС-JDK-1.6.0.17)

Question

Почему вызов containsKey в HashMap медленнее, чем get?

Тест: http://ideone.com/QsWXF (разница> 15%, работает на sun-jdk-1.6.0.17)

Answer 1

Поскольку он [очень немного] выполняет больше работы, см. источник OpenJDK 7 .

---

Обратите внимание, что containsKey вызывает getEntry, а get напрямую "делает волшебный поиск ". Я не знаю, почему это было сделано таким образом, и я еще больше озадачен использованием / неиспользованием getForNullKey: См. Комментарии Джона Б. и Теда Хоппса о том, почему это сделано.

get имеет раннее разделение кода для нулевого ключа (обратите внимание, что get вернет null, если запись не существует или существует с сохраненным нулевым значением):

315           if (key == null)
316               return getForNullKey();
...
322               if (e.hash == hash &&
                      ((k = e.key) == key || key.equals(k)))
323                   return e.value;

Хотя getEntry, вызванный из containsKey, не разделяется на getForNullKey, здесь есть дополнительная работа для проверки случая нулевого ключа (для каждой записи, отсканированной в цепочке):

366               if (e.hash == hash &&
367                   ((k = e.key) == key || (key != null && key.equals(k))))
368                   return e;

Кроме того, containsKey имеет дополнительный условный вызов и вызов метода (обратите внимание, что getEntry вернет объект Entry, если указанный ключ существует, даже если сохраненное значение равно null):

352           return getEntry(key) != null;

Полагаю, можно утверждать, что containsKey выиграет - с точки зрения "производительности" - от наличия специализированной формы (за счет кода с меньшим количеством СУХОГО), или что getEntry может последовать примеру getс ранней проверкой нулевого ключа .. с другой стороны, можно утверждать, что get должно бытьнаписано в виде getEntry; -)

Удачного кодирования.

Answer 2

Тестирование хэш-карт разных размеров, если есть смещение в производительности, оно очень мало.

Запуск на Java 7 с обновлением 1 на 4,6 ГГц i7 2600K.

public class HashMapPerfMain {
    public static void main(String... args) {
        Integer[] keys = generateKeys(2 * 1000 * 1000);

        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for (int j = 0; j < keys.length; j += 2)
            map.put(keys[j], true);

        for (int t = 0; t < 5; t++) {
            long start = System.nanoTime();
            int count = countContainsKey(map, keys);
            long time = System.nanoTime() - start;
            assert count == keys.length / 2;

            long start2 = System.nanoTime();
            int count2 = countGetIsNull(map, keys);
            long time2 = System.nanoTime() - start2;
            assert count2 == keys.length / 2;
            System.out.printf("Map.containsKey avg %.1f ns, ", (double) time / keys.length);
            System.out.printf("Map.get() == null avg %.1f ns, ", (double) time2 / keys.length);
            System.out.printf("Ratio was %.2f%n", (double) time2/ time);
        }
    }

    private static int countContainsKey(Map<Integer, Boolean> map, Integer[] keys) {
        int count = 0;
        for (Integer i : keys) {
            if (map.containsKey(i)) count++;
        }
        return count;
    }

    private static int countGetIsNull(Map<Integer, Boolean> map, Integer[] keys) {
        int count = 0;
        for (Integer i : keys) {
            if (map.get(i) == null) count++;
        }
        return count;
    }

    private static Integer[] generateKeys(int size) {
        Integer[] keys = new Integer[size];
        Random random = new Random();
        for (int i = 0; i < keys.length; i++)
            keys[i] = random.nextInt();
        return keys;
    }
}

отпечатков для полумиллиона ключей

Map.containsKey avg 27.1 ns, Map.get() == null avg 26.4 ns, Ratio was 0.97
Map.containsKey avg 19.6 ns, Map.get() == null avg 19.6 ns, Ratio was 1.00
Map.containsKey avg 18.3 ns, Map.get() == null avg 19.0 ns, Ratio was 1.04
Map.containsKey avg 18.2 ns, Map.get() == null avg 19.1 ns, Ratio was 1.05
Map.containsKey avg 18.3 ns, Map.get() == null avg 19.0 ns, Ratio was 1.04

отпечатков на миллион ключей

Map.containsKey avg 30.9 ns, Map.get() == null avg 30.9 ns, Ratio was 1.00
Map.containsKey avg 26.0 ns, Map.get() == null avg 25.5 ns, Ratio was 0.98
Map.containsKey avg 25.0 ns, Map.get() == null avg 24.9 ns, Ratio was 1.00
Map.containsKey avg 25.0 ns, Map.get() == null avg 24.9 ns, Ratio was 1.00
Map.containsKey avg 24.8 ns, Map.get() == null avg 25.0 ns, Ratio was 1.01

однако для двух миллионов ключей

Map.containsKey avg 36.5 ns, Map.get() == null avg 36.7 ns, Ratio was 1.00
Map.containsKey avg 34.3 ns, Map.get() == null avg 35.1 ns, Ratio was 1.02
Map.containsKey avg 36.7 ns, Map.get() == null avg 35.1 ns, Ratio was 0.96
Map.containsKey avg 36.3 ns, Map.get() == null avg 35.1 ns, Ratio was 0.97
Map.containsKey avg 36.7 ns, Map.get() == null avg 35.2 ns, Ratio was 0.96

для пяти миллионов ключей

Map.containsKey avg 40.1 ns, Map.get() == null avg 40.9 ns, Ratio was 1.02
Map.containsKey avg 38.6 ns, Map.get() == null avg 40.4 ns, Ratio was 1.04
Map.containsKey avg 39.3 ns, Map.get() == null avg 38.3 ns, Ratio was 0.97
Map.containsKey avg 39.3 ns, Map.get() == null avg 38.3 ns, Ratio was 0.98
Map.containsKey avg 39.3 ns, Map.get() == null avg 38.8 ns, Ratio was 0.99

Кстати: сложность времени для get () и containsKey равна O (1) (на идеализированной машине), но вы можете видеть, что для реальной машины стоимость увеличивается с размером карты.

Answer 3

Давайте посмотрим на исходный код:

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}


public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

Может быть, это из-за дополнительного вызова метода или из-за повторной проверки для key != null?

Answer 4

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