java - 哪种是存储关注者和关注者最有效的数据结构

Question

我在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() 的速度

Answer 1

将数据存储在您喜欢的任何数据结构中。这就是数据库要做的非常粗略的事情。重要的一步是它的指数。特别是你有

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<>();

是的，这是多余的。索引是多余的。请注意，它们并不是多余的，因为它们不会存储从头开始重复的用户，无论您使用什么 key 。您必须使用 AnyDataStructure 来维护这些，即每当添加、删除用户或者添加或删除关注者时，您也必须维护 map 。

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

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

因此，更新关注者/关注者只会更新用户本身。随着您添加越来越多的功能，这可能无法维护，但此时您几乎肯定应该在真正的关系数据库或 NoSQL 数据库中执行此操作。