Производительность HashSet.contains

Ответ 1

Он запускается в O(1) ожидаемом времени, как и любая хеш-таблица (при условии, что функция хэша приличная). Он поддерживается HashMap, где ключ является объектом.

Два объекта могут иметь один и тот же хеш-код, но HashSet не считают, что они идентичны, если только метод equals для этих объектов не говорит о том, что они одинаковы (т.е. возвращает true).

Метод contains вызывает (косвенно) getEntry из HashMap, где ключ - это Object, для которого вы хотите узнать, находится ли он в HashSet.

Как вы можете видеть ниже, два объекта могут быть сохранены в HashMap/HashSet, даже если их ключ сопоставляется с тем же значением с помощью хэш-функции. Метод выполняет итерацию по всем ключам, которые имеют одно и то же значение хэша, и выполняет equals на каждом из них, чтобы найти соответствующий ключ.

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

Ответ 2

Производительность содержимого в худшем случае будет O (log n) для Java 8 и O (n) для Java 7, но средний случай ближе к O (1). Это связано с тем, что хэш-набор поддерживается хэш-картой и, следовательно, имеет ту же эффективность, что и поиск по хэш-карте (т.е. HashMap.get(...)). Фактическое отображение в хэш-карте - постоянное время (O (1)), но необходимость обрабатывать коллизии приводит к затратам на запись n. То есть несколько элементов, которые хэшируют к одному и тому же индексу массива, должны храниться во вторичной структуре данных (иначе говоря), и именно эта группа определяет производительность в худшем случае. В Java обработка коллизий hashmap реализована с использованием самоуравновешенного дерева.

Самоуравновешенные деревья гарантируют O (log n) для всех операций, следовательно, вставка и поиск в hashmap (и hashset) имеют общую стоимость O (1) + O (log n) = O (log n). Использование самоуравновешенного дерева для обработки коллизий было введено в Java 8 как улучшение по сравнению с цепочкой (используется до Java 7), которая использует связанный список и имеет наихудший случай O (n) для поиска и вставки (поскольку это должно пройти список). Обратите внимание, что цепочка будет иметь постоянное время для вставки (в отличие от поиска), поскольку элементы могут быть добавлены в связанный список в O (1), но свойство set (без дубликатов) накладывается на связанный список в случае hashmap, и, таким образом, он должен пройти по связанному списку и в случае вставки, чтобы убедиться, что элемент еще не существует в списке/сегменте, и в итоге мы получаем O (n) как для вставки, так и для поиска.

Рекомендации:

Этот класс реализует интерфейс Set, поддерживаемый хеш-таблицей (фактически, экземпляром HashMap). https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

Корзины, содержащие большое количество сталкивающихся ключей, будут сохранять свои записи в сбалансированном дереве вместо связанного списка после достижения определенного порога. (https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8)

Ответ 3

Рекомендуется использовать HashSet.get(object) который является null или нет, а не HashSet.contain(object), поскольку HashSet.get(object) работает быстрее.