Как я могу создать метод поиска и метод вставки для сложности времени (1) в пользовательской реализации HashMap?

Question

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

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

Answer 1

Там много вопросов, позвольте мне попробовать.

Я хочу иметь возможность проверить, существует ли ключ, и вернуть соответствующее значение в O (1) сложности времени ( требование присваивания), но я предполагаю, что это без использования containsKey ().

Это на самом деле не имеет значения. O (1) означает, что время выполнения не зависит от ввода, это не означает, что используется одна операция. Если ваши реализации containsKey() и put() обе являются O (1), то и ваше решение использует оба из них ровно один раз.

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

O (1) является наилучшим случаем, который предполагает отсутствие столкновений ha sh. Худший случай - O (n), если каждый ключ генерирует один и тот же код ha sh. Поэтому, когда производительность поиска или вставки карты ha sh рассчитывается как O (1), это предполагает идеальную реализацию hashCode.

Наконец, когда речь идет о структурах данных, обычный подход заключается в использовании одного массив, где элементы массива являются узлами списка ссылок. Смещения массива соответствуют hashcode() % array size (формул улучшений гораздо больше, чем это, но это хорошая отправная точка). В случае столкновения ha sh вам придется перемещаться по узлам связанного списка, пока вы не найдете правильную запись.

Answer 2

Вы правы в том, что ha sh вставка таблицы не гарантируется равной O(1) из-за коллизий. Если вы используете стратегию открытой адресации для борьбы со столкновениями, процесс вставки элемента займет время, пропорциональное 1/(1-a), где a - это пропорция того, сколько емкости таблицы было использовано. Когда таблица заполняется, a становится равным 1, и время для вставки увеличивается без ограничений.

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

Проблема: изменение размера таблицы с помощью элемента N занимает O(N) время.

Решение: экспоненциально увеличить емкость Например, удваивайте его каждый раз, когда вам нужно изменить размер. Таким образом, размер таблицы изменяется очень редко. Стоимость случайных операций изменения размера «амортизируется» из-за большого количества вставок, и поэтому люди говорят, что вставка таблицы ha sh имеет «амортизированную O (1)» сложность времени.

---

TLDR: Удостоверьтесь, что вы увеличиваете емкость таблицы, когда она заполняется, возможно использование на 70-80%. Когда вы увеличиваете емкость, убедитесь, что она постоянна, например, удвоите ее.