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

У меня возникает соблазн думать, что метод HashSet.contains (Object) выполняется в постоянное время. Он просто получает хеш-код объекта, а затем просматривает его в хеш-таблице.

Во-первых, кто-то может подтвердить, правда ли это?

Во-вторых, если это правда, существует ли риск столкновений, где два объекта могут иметь один и тот же hash-код, и, следовательно, HashSet считает, что он имеет оба, когда он имеет только один?

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

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

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

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

 final Entry getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry 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). Это связано с тем, что hashset поддерживается hash-картой и, таким образом, имеет ту же эффективность, что и поиск hashmap (т. Е. HashMap.get (…)). Фактическое отображение в hashмапе – это постоянное время (O (1)), но необходимость обработки коллизий приводит к стоимости log n. То есть, несколько элементов, hash которых имеет один и тот же индекс массива, должны храниться во вторичной структуре данных (aka bucket), и именно это ведро определяет наихудшую производительность. В Java обработка hahsmap colission осуществляется с использованием самобалансированного дерева.

Самобалансированные деревья гарантируют 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) как для вставки, так и для поиска.

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

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

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

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

  • Итерация над compilationами Java в Scala
  • Интерфейс коллекции против массивов
  • Как сортировать коллекцию?
  • Как преобразовать объект Java (bean) в пары ключ-значение (и наоборот)?
  • В чем разница между Collection.stream (). ForEach () и Collection.forEach ()?
  • C #: Разница между списком и Collection (CA1002, не выставлять общие списки)
  • Уведомлять ObservableCollection при изменении позиции
  • Различия между HashMap и Hashtable?
  • Очистите ArrayList или просто создайте новый, и пусть старый будет собран мусором?
  • Map.clear () vs new Map: Какой из них будет лучше?
  • List, IList, IEnumerable, IQueryable, ICollection, который является наиболее гибким типом возврата?
  • Interesting Posts

    Как отключить внутреннюю клавиатуру на MacBook Pro?

    Определение версии сборки во время события после сборки

    Идиоматический способ ожидания множественных обратных вызовов в Node.js

    Настройка уникального ограничения с использованием свободного API?

    Использование «системы» perl

    Белое пространство вокруг шкалы css3

    Не может быть прозрачным UIToolBar?

    Используйте вектор в качестве индекса для матрицы

    Google In-App billing, IllegalArgumentException: намерение службы должно быть явным, после перехода на Android L Dev Preview

    Проблема с Windows 7, update.packages: «невозможно переместить временную установку»?

    Объединение агрегированных значений обратно в исходный фрейм данных

    Вербальные строковые литералы v escape-последовательности

    Когда следует использовать # и = в элементах управления ASP.NET?

    Уменьшение высоты бутстрапа 3.0 navbar

    «ПРЕДУПРЕЖДЕНИЕ: предварительные заголовки отображаются» в отладчике Chrome

    Давайте будем гением компьютера.