Мне кажется, что метод HashSet.contains(Object) выполняется в постоянное время. Он просто получает хеш-код объекта, а затем просматривает его в хеш-таблице.
Во-первых, кто-нибудь может подтвердить, правда ли это?
Во-вторых, если это правда, существует ли риск столкновений, где два объекта могут иметь один и тот же хэш-код, и, следовательно, HashSet считает, что он имеет оба, когда он имеет только один?
Он запускается в 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;
}
Производительность содержимого в худшем случае будет 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)
Рекомендуется использовать HashSet.get(object) который является null или нет, а не HashSet.contain(object), поскольку HashSet.get(object) работает быстрее.