图形邻接表如何实现节点/顶点的O（1）查找。阵列？

我阅读了使用“邻接列表”实现的图形的规范，即在不变的时间内添加边。但是这需要使用O（1）进行节点查找。我想要尽可能好的表现。这里的问题是哪个数据类型会给我这个问题。已经考虑了散列表，最坏的情况是散列表仍然是O（n）。图形邻接表如何实现节点/顶点的O（1）查找。阵列？

我可以用这个数组吗？该节点可以是任何数据类型，泛型。这可以通过一些基于节点的散列函数生成索引值来完成吗？那会给我O（1）。当然，我可以大写并使用LinkedList和indexOf。持续时间最好。

2009-11-18 Algific

假设你有一个好的散列，通常假定HashMap有O（1）运行时，特别是对于作业目的。 – notnoop 2009-11-18 21:54:04

我问我的小组组长，一个博士研究生。 O（1）预计运行时间，我需要分析的是最坏的情况。 – Algific 2009-11-19 09:07:10

任何使用哈希算法的步骤都会产生碰撞风险，所以最坏的情况（不太可能）是欧米茄（N）。

使用列表时，同时插入和检索的最佳保证渐近性能为O（log N）。如果您将节点存储为堆或平衡树之类的东西，就会得到这个结果。你不能在两个操作上做得更好，因为它会让你违反排序时可证明的O（N log N）。

2009-11-23 23:56:08 Eric

一般而言，绝对是。只要输入集合是有限的并且已知的，完美的哈希可以完全避免碰撞。 – 2010-09-29 01:27:27

回答