Как хранится карта хэша?

Question

У меня появилось интервью, и я просматривал некоторые вопросы, связанные с техническим интервью, и я наткнулся на this one. Он запрашивает временную сложность для функций вставки и удаления хэш-карты. По-видимому, консенсус заключается в том, что временная сложность O (1), если карта распределена равномерно, но O (n), если они все находятся в одном пуле.

Я думаю, мой вопрос в том, как точно хранятся хэш-карты в памяти? Как произойдут эти 2 случая?

Answer 1

Один ответ на связанном странице:

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

Это не очень хороший ответ. Обобщенный ответ на временную сложность для HashMap придет к подобному заявлению, как Wikipedia article on hash tables:

Time complexity 
in big O notation 

      Average Worst case 
Space  O(n)  O(n) 
Search O(1)  O(n) 
Insert O(1)  O(n) 
Delete O(1)  O(n) 

адресовать свой вопрос, как хэш-карты хранятся в памяти: Есть целый ряд «ковши», которые хранят значение средний случай, но должен быть расширен до некоторого списка, когда происходит хеш-столкновение. Хорошие объяснения хэш-таблиц в статье Википедии, this SO question и this C++ example.

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

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