HashMap get/put сложность

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

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

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

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

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

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

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

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

TL; DR: с очень Большая вероятность, в худшем случае получить/поставить сложность HashMap является O(logn).

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

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

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

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

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