как создать коллекцию со сложностью O (1)

Question

Я хотел бы создать структуру данных или коллекцию, которая будет иметь сложность O (1) при добавлении, удалении и расчете no. элементов. Как я должен начать?

Я подумал о решении: я буду использовать Hashtable, и для каждой вставленной пары ключ / значение у меня будет только один хеш-код, то есть: мой алгоритм хеш-кода будет генерировать уникальное хеш-значение каждый раз, поэтому Индекс, в котором хранится значение, будет уникальным (т.е. без коллизий).

Это даст мне O (1) сложность?

Answer 1

Да, это будет работать, но, как вы упомянули, ваша функция хеширования должна быть уникальной на 100%. Любые дубликаты приведут к тому, что вам придется использовать какое-то разрешение конфликта. Я бы порекомендовал линейную цепочку.

edit: Hashmap.size () разрешает O (1) доступ

edit 2: В связи с путаницей, вызванной Ларри = P

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

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

Дело в том, что уникальность хеша является необходимым условием для O (1) времени выполнения.

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

Основная идея состоит в том, что операция в наихудшем случае может изменить состояние таким образом, что наихудший случай не может возникнуть снова в течение длительного времени, что приведет к амортизации его стоимости.

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

Надеюсь, это все прояснит.

Answer 2

Добавление, удаление и размер (при условии, что он отслеживается отдельно, с помощью простого счетчика) может быть предоставлен связанным списком. Если вам не нужно удалить определенный элемент. Вы должны быть более конкретными о ваших требованиях.

Answer 3

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

Например, скажем, у меня есть три объекта A (хэш: 2), B (хэш: 18), C (хэш: 66) Все уникально.Скажем, вы положили их в HashMap емкостью 16 (по умолчанию).Если они были сопоставлены с сегментом% 16 (на самом деле более сложным, чем этот) после уменьшения хеш-кодов, у нас теперь есть A (хэш: 2% 16 = 2), B (хэш: 18% 16 = 2), C (hash: 66% 16 = 2)

HashMap, вероятно, будет быстрее, чем Hashtable, если вам не нужна безопасность потоков.(В этом случае я предлагаю вам использовать CopncurrentHashMap) ИМХО, Hashtable был унаследованной коллекцией в течение 12 лет, и я бы посоветовал вам использовать ее только в случае необходимости.

Answer 4

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

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

¹ Конечно, равенство должно подразумевать равные хэш-коды.

Answer 5

Удивительно, но ваша идея сработает, если вы знаете все ключи, которые вы хотите поместить в коллекцию заранее. Идея состоит в том, чтобы генерировать a специальную хеш-функцию , которая отображает каждую клавишу на уникальное значение в диапазоне (1, n). Тогда наша «хеш-таблица» представляет собой простой массив (+ целое число для кэширования количества элементов)

Реализация этого не тривиальна, но это и не ракетостроение. Я оставлю это Стиву Хэнову , чтобы объяснить входы и выходы, поскольку он дает намного лучшее объяснение, чем я когда-либо мог.

Answer 6

Каких функций вам нужно, чтобы связанный список не давал вам?

Answer 7

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

Даже если ключи не уникальны, алгоритм все равно будет иметь значение O (1), если Hashmap автоматически увеличивается в размере, если коллекция становится слишком большой (большинство реализаций сделает это автоматически).

Итак, просто используйте Hash map в соответствии с данной документацией, и все будет хорошо. Не придумывайте ничего более сложного, это просто пустая трата времени.

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