java - 这是用于存储关注者和关注者的最有效的数据结构

我在Java中有这两种方法


public Int[] getFollows
public Int[] getFollowers


其中getfollows(user1)返回users后跟的user1数组

并且getfollowers(user1)返回在users之后的user1数组

我当前的数据结构是一个二维数组，所以我有

对于user1的每个新关注者，我运行followerArray[user1][followers++]=newFollower
这意味着getFollowers()将在O（1）时间运行，就像我只是return followerArray[user1]

但是方法getFollows()将要求我使用两个for循环N次遍历所有数组，因此将在O（N ^ 2）中运行。

有没有一种方法可以降低方法getFollows的时间复杂度而又不牺牲getFollowers()的速度

最佳答案

将数据存储在所需的任何数据结构中。这就是数据库要执行的工作。重要的一步是其索引。特别是你有

AnyDataStructure users; // supports get(userKey) operation for some userKey; e.g. array index, integer, etc.

并且您需要创建两个索引，您将对其进行维护以进行查找。

Map<UserKey, List<UserKey>> followers = new HashMap<>();
Map<UserKey, List<UserKey>> follows = new HashMap<>();

是的，这是多余的。索引是多余的。请注意，它们并不是那么多余，因为它们不会存储从头开始再次复制的用户，无论您使用什么密钥。您将必须使用AnyDataStructure来维护这些地图，即，每次添加，删除用户或添加或删除关注者时，您也必须维护地图。

请注意，这些映射也许应该只是User类的成员变量。

List<UserKey> followers;
List<UserKey> following;

这样更新关注者/关注者只会更新用户本身。当您添加越来越多的功能时，这可能无法维持，但是到现在为止，您几乎可以肯定应该在真正的关系数据库或NoSQL数据库中执行此操作。

关于java - 这是用于存储关注者和关注者的最有效的数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22129136/