HashMap получить / поставить сложность

Question

Мы привыкли говорить, что HashMapget/put операции O(1). Однако это зависит от реализации хэша. Хеш объекта по умолчанию фактически является внутренним адресом в куче JVM. Мы уверены, что это достаточно хорошо, чтобы утверждать, что get/put такое O(1)?

Доступная память - другая проблема. Как я понимаю из Javadocs, HashMapload factor должно быть 0,75. Что делать, если у нас недостаточно памяти в JVM и load factor превышает лимит?

Таким образом, похоже, что O (1) не гарантируется. Имеет ли это смысл или я что-то упустил?

Answer 1

Это зависит от многих вещей. Обычно это O(1) с приличным хешем, который сам по себе является постоянным временем... но у вас может быть хеш, который требует много времени для вычисления, и если в хэш-карте есть несколько элементов, которые возвращают один и тот же хеш-код, get придется перебирать их вызов equals на каждом из них найти совпадение.

В худшем случае HashMap имеет поиск O(n) из-за обхода всех записей в одном и том же хэш-сегменте (например, если все они имеют одинаковый хэш-код). К счастью, этот худший сценарий не часто встречается в реальной жизни, по моему опыту. Так что нет, O(1) определенно не гарантируется - но обычно это то, что вы должны учитывать при рассмотрении того, какие алгоритмы и структуры данных использовать.

В JDK 8 HashMap был изменен так, что если ключи можно сравнивать для упорядочения, то любое плотно заполненное ведро реализовано в виде дерева, так что даже если существует много записей с одинаковым хеш-кодом, сложность составляет O(log n). Это может вызвать проблемы, если у вас есть тип ключа, где равенство и порядок различны, конечно.

И да, если у вас недостаточно памяти для хэш-карты, у вас будут проблемы... но это будет верно для любой структуры данных, которую вы используете.

Answer 2

Уже упоминалось, что хешмапы O(n/m) в среднем, если n количество предметов и m это размер. Также было упомянуто, что в принципе все это может рухнуть в один связанный список с O(n) время запроса. (Это все предполагает, что вычисление хэша является постоянным временем).

Однако то, что не часто упоминается, это то, что, по крайней мере, с вероятностью 1-1/n (так что для 1000 предметов это вероятность 99,9%) самое большое ведро не будет заполнено больше, чем O(logn)! Отсюда соответствие средней сложности бинарных поисковых деревьев. (И константа хорошая, более жесткая граница (log n)*(m/n) + O(1)).

Все, что требуется для этой теоретической границы, это то, что вы используете достаточно хорошую хеш-функцию (см. Википедия: Универсальное хеширование. Это может быть так просто, как a*x>>m). И, конечно же, тот, кто дает вам значения для хэширования, не знает, как вы выбрали свои случайные константы.

TL; DR: с очень высокой вероятностью, сложность получения / размещения хеш-карты в худшем случае O(logn),

Answer 3

Я согласен с:

• общая амортизируемая сложность O(1)
• плохой hashCode() реализация может привести к нескольким коллизиям, что означает, что в худшем случае каждый объект отправляется в один и тот же сегмент, то есть O (N), если каждый сегмент поддерживается List,
• начиная с Java 8 HashMap Динамически заменяет узлы (связанный список), используемые в каждом сегменте, на TreeNodes (красно-черное дерево, когда список становится больше, чем 8 элементов), что приводит к худшей производительности O (logN).

Но это НЕ полная правда, если мы хотим быть на 100% точными. Реализация hashCode()тип ключа Object (неизменяемый / кэшированный или являющийся коллекцией) может также повлиять на реальную сложность в строгом смысле.

Давайте предположим следующие три случая:

1. HashMap<Integer, V>
2. HashMap<String, V>
3. HashMap<List<E>, V>

Они имеют одинаковую сложность? Что ж, амортизированная сложность 1-го, как и ожидалось, равна O(1). Но, в остальном, нам также нужно вычислить hashCode() элемента lookup, что означает, что в нашем алгоритме нам, возможно, придется обходить массивы и списки.

Предположим, что размер всех вышеперечисленных массивов / списков равен k. Затем, HashMap<String, V> а также HashMap<List<E>, V> будет иметь O(k) амортизированную сложность и, аналогично, O (k + logN) наихудший случай в Java8.

* Обратите внимание, что с помощью String ключ является более сложным случаем, потому что он неизменен, а Java кэширует результат hashCode() в приватной переменной hash, так что это вычисляется только один раз.

/** Cache the hash code for the string */
    private int hash; // Default to 0

Но вышеизложенное также имеет свой худший случай, потому что Java String.hashCode() реализация проверяет, если hash == 0 перед вычислением hashCode, Но эй, есть непустые строки, которые выводят hashcode нуля, такого как "f5a5a608", см. здесь, в этом случае запоминание может быть бесполезным.

Answer 4

Я не уверен, что хеш-код по умолчанию является адресом - я читал исходный код OpenJDK для генерации хэш-кода некоторое время назад, и я помню, что он был немного сложнее. Возможно, это еще не то, что гарантирует хорошее распространение. Тем не менее, это в некоторой степени спорным, поскольку несколько классов, которые вы хотите использовать в качестве ключей в HashMap использовать хэш-код по умолчанию - они поставляют свои собственные реализации, которые должны быть хорошо.

Кроме того, что вы можете не знать (опять же, это основано на чтении источника - это не гарантировано), так это то, что HashMap перемешивает хэш перед его использованием, чтобы смешать энтропию из всего слова в нижние биты, где нужен для всех, кроме огромных хэш-карт. Это помогает бороться с хешами, которые сами этого не делают, хотя я не могу вспомнить ни одного распространенного случая, когда вы бы это увидели.

Наконец, что происходит, когда таблица перегружена, так это то, что она вырождается в набор параллельных связанных списков - производительность становится O(n). В частности, количество пройденных ссылок в среднем будет вдвое меньше коэффициента загрузки.

Answer 5

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

Теперь перейдем ко второй части вопроса о памяти, тогда да, ограничение памяти будет решено JVM.

Answer 6

На практике это O(1), но на самом деле это ужасное и математически бессмысленное упрощение. Обозначение O() говорит о том, как алгоритм ведет себя, когда размер задачи стремится к бесконечности. Hashmap get/put работает как алгоритм O (1) для ограниченного размера. Предел достаточно велик для памяти компьютера и с точки зрения адресации, но далеко от бесконечности.

Когда кто-то говорит, что hashmap get/put равен O(1), он должен действительно сказать, что время, необходимое для get / put, является более или менее постоянным и не зависит от количества элементов в hashmap настолько, насколько это может сделать hashmap. быть представленным в реальной вычислительной системе. Если проблема выходит за рамки этого размера, и нам нужны большие хэш-карты, то через некоторое время количество битов, описывающих один элемент, безусловно, также увеличится, когда у нас закончатся возможные описываемые различные элементы. Например, если мы использовали хэш-карту для хранения 32-битных чисел, а позже мы увеличили размер задачи, чтобы у нас было более 2^32-битных элементов в хеш-карте, тогда отдельные элементы будут описаны с более чем 32-битными.

Число битов, необходимых для описания отдельных элементов, равно log(N), где N - максимальное количество элементов, поэтому значения get и put действительно равны O(log N).

Если вы сравните его с древовидным набором, который равен O(log n), тогда хеш-набор равен O(long(max(n))), и мы просто чувствуем, что это O(1), потому что в определенной реализации max (n) фиксированный, не изменяется (размер хранимых нами объектов измеряется в битах), а алгоритм вычисления хеш-кода работает быстро.

Наконец, если бы найти элемент в какой-либо структуре данных был O(1), мы бы создали информацию из ничего. Имея структуру данных из n элементов, я могу выбрать один элемент n различными способами. С этим я могу закодировать информацию бита журнала (n). Если я могу закодировать это в нулевом бите (это означает, что O (1)), то я создал бесконечно сжатый алгоритм ZIP.

Answer 7

      Java HashMap time complexity
--------------------------------
get(key) & contains(key) & remove(key)          Best case   Worst case                          
HashMap before Java 8, using LinkedList buckets 1           O(n)
HashMap after Java 8, using LinkedList  buckets 1           O(n)
HashMap after Java 8, using Binary Tree buckets 1           O(log n)

 
put(key, value)                                 Best case   Worst case                          
HashMap before Java 8, using LinkedList buckets 1           1
HashMap after Java 8, using LinkedList  buckets 1           1
HashMap after Java 8, using Binary Tree buckets 1           O(log n)

Подсказки:

• Раньше используйте ведра

• ПослеJava 8,HashMapбудет использовать либоLinkedListведра илиBinary Treeведра в соответствии с размером ведра.

  если (размер корзины > TREEIFY_THRESHOLD[8]):

  treeifyBin: ведро будет сбалансированным бинарным красно-черным деревом.

  если (размер сегмента <= UNTREEIFY_THRESHOLD[6]):

  untreeify: ведро будет LinkedList (обычный режим)

Answer 8

Проще говоря, если каждое ведро содержит только один узел, то временная сложность будет O(1). Если ведро содержит более одного узла, их временная сложность будет O (размер связанного списка) . который всегда эффективнее, чем O(n).

следовательно, мы можем сказать о средней временной сложности функции put(K,V):

узлы (n) / ведра (N) = λ (лямбда)

Пример: 16/16 = 1

Временная сложность будет O(1)