关于adj数组中存放哈希表的空间复杂度疑问

Question

波波老师您好，如果adj数组中每一个元素都是一个哈希表，那么此时每一个哈希表我们可以用一个长度为V-1的数组来表示所有可能相邻的顶点。如果顶点v与另一个顶点w相邻，则我们可以将adj[v][w]设置为1表示true。那么在这种情况下，虽然我们查找两点是否相邻的时间复杂度降到了O(1)级别，但是数据结构本质上变回了一个邻接矩阵，空间复杂度变回了O(V*V)。

而反观红黑树的实现，虽然查找两点相邻的时间复杂度是O(logV)级别，但空间复杂度依旧维持了O(V + E)。

请问波波老师，这样对比下来，是否可以说红黑树的实现会更优于哈希表的实现？还是说其实存在更好的哈希函数能避开哈希表空间复杂度的尴尬呢？

多谢老师！

Answer 1

liuyubobobo 2019-08-08 23:51:59

1）

首先你的分析是对的，课程中也介绍过，使用哈希表是费空间的。当然，这也依赖哈希表的具体实现。但是，红黑树稳稳地是O(V+E)的空间。不过，因为在大多数情况下，现代计算机解决问题，不是特别特殊的情况，对空间都是不敏感的，所以，我们在通常情况下做算法设计，一般都不强调空间。比如在一般的算法比赛中，我没有见过使用哈希表超空间，使用红黑树就ok的情况。

2）

使用哈希表或者红黑树的关键优势还是在于，遍历一个顶点的所有相邻顶点，时间是O(degree(v))级别的操作，而不是O(V)级别的操作。这非常重要，使得很多图论算法的时间复杂度成为了O(V+E)，而不是O(V^2)。

3）

使用红黑树或者哈希表的另一个优点，是能够快速查找某两个节点是否相邻。

但是，后续学习很多具体的图论算法，你就会看到，其实，我们在大多数算法中，都并不需要这个操作。最重要的核心操作，还是遍历一个顶点的所有相邻顶点。因此，邻接表的一个经典实现，还是使用链表：）

继续加油！：）

• 提问者 软件工程小白菜 #1

  非常感谢！

• 提问者 软件工程小白菜 #2

  但是老师还想问一下，如果使用我上述的方法构建哈希表，或者说用数组构建哈希表，遍历一个顶点的所有相邻顶点的时间复杂度应该还是O(V)呀（因为遍历了一遍数组，而数组大小为V-1），是不是有别的哈希表实现能把这个操作简化至O(degree(V))呢？

• liuyubobobo 回复 提问者 软件工程小白菜 #3

  和HashSet具体的内部实现有关。普通的HashSet，遍历的复杂度是O(B+n)的，B是哈希表中的地址数量，是一个常数，n是实际存储的元素个数。也就是遍历每一个哈希地址下存储的每一个元素。理论分析，此时哈希表的遍历时间复杂度依然是O(n)的，和有多少哈希地址无关，因为是常数。但确实，如果B太大，大于V，那就是O(V)的。但是，由于哈希表是动态的，有rehash的过程，所以，如果degree(v)不大，B也不会太大。B是n的低阶项。当然，HashSet也有其他实现方案，比如里面再放一个链表，存储所有元素，专门用于遍历，这样，就不需要遍历每一个哈希地址，此时，复杂度是精准的O(degree(V))。不管怎样实现，哈希表遍历的时间复杂度都是O(n)的。

点开查看后面1条评论