hash - 您将使用哪种数据结构来存储指向非常大图的邻接链表的指针？

Question

假设你想实现一个可以有百万个节点的图。但是节点数会从0增加到百万。不确定它是否会达到百万大关。它也可能跨越到数百万个节点。

我知道邻接表是用来做这个的。但是一个典型的邻接表有一个数据结构维护指向链表的指针。

那么应该使用什么数据结构来存储指向邻接表的指针？

以 Facebook 为例。它拥有数百万用户。假设每个用户代表一个节点。现在所有用户都表示为一个非常大的单个图的节点，您想对其进行操作，您将如何存储它？

score 2 · Accepted Answer

好吧，如果您了解它们背后的基础知识，那应该不会太难。

通常，您会创建一个名为“buckets”的数组，其中包含键和值，以及用于创建链接列表的可选指针。

当您使用键访问哈希表时，您使用自定义哈希函数处理该键，该函数将返回一个整数。然后你取结果的模数，这就是你的数组索引或“桶”的位置。然后你用存储的密钥检查未散列的密钥，如果匹配，那么你找到了正确的位置。

否则，您就发生了“冲突”，必须爬过链表并比较键，直到匹配为止。（注意一些实现使用二叉树而不是链表来解决冲突）。

查看这个快速哈希表实现：

1 回答 1