Хеш стол понимающий

Question

Я понимаю, что у меня есть хеш-таблица с m ячейками и n элементами, стоимость поиска O (n / m) (в среднем) Давайте рассмотрим два под-алгоритма использования хеш-таблицы: О. Когда у вас есть n элементов, вставьте их в хеш-таблицу с m = 100 и используйте ее для поиска элемента. B. Если у вас есть n элементов, вставьте их в хеш-таблицу с m = n / 3 и используйте ее для поиска элемента.

В случае A сложность поиска составляет O (n / 100) = O (n) В случае B сложность поиска составляет O (n / (n / 3)) = O (1) Это означает, что если мы хотим использовать хеш-таблицу для этого поискового элемента в сложности O (1), мы должны знать количество элементов при создании хеш-таблицы, вычислять m путем деления n на константу и передавать конструктору множества м

Я прав? Должен ли я передать m в конструкторе моей хеш-таблицы, чтобы использовать преимущества хеш-таблицы?

Answer 1

Ответ, как я узнал из комментариев выше, заключается в том, что большинство реализаций автоматически корректируют размер хеш-таблицы, поэтому m всегда что-то вроде n..2n. Когда число элементов становится слишком большим для текущего m, выделяется большая хеш-таблица Это означает, что add to hashtable может быть в худшем случае O (n) (потому что выделена большая хеш-таблица), но в амортизированном виде это O (1), как добавление элемента в ArrayList