Список смежности графиков Как реализовать поиск O (1) для узлов / вершин. Массив?

Question

В спецификациях для графиков, реализованных с помощью Списка смежности, я прочел, что добавление ребер выполняется за постоянное время НО это потребовало бы поиска узла с O (1). Я хотел бы получить наилучшие результаты. Вопрос в том, какой тип данных даст мне это. Hashmap был рассмотрен, наихудший случай с hashmap все еще O (n).

Могу ли я использовать массив для этого? Узлы могут иметь любой тип данных, дженерики. Можно ли это сделать с помощью некоторой хэш-функции, генерирующей значения индекса на основе одного узла? Это дало бы мне O (1). Конечно, я могу просто использовать заглавные буквы и использовать LinkedList с indexOf. Постоянное время лучше.

Answer 1

При любом шаге хэширования вы рискуете столкнуться, поэтому наихудшим (хотя и маловероятным) случаем является Омега (N).

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