java - 如何改进 HashMap 数组中的搜索

Question

在任何 HashMap(或任何基于散列的数据结构)中的搜索都需要单个散列操作，即 O(1)。但是，当我们必须搜索 HashMap 数组时，单次搜索将需要 O(n) 次哈希操作，其中 n 是数组的大小。我想知道由于数组是连续内存位置的集合，因此可能有一种有效的方法可以将 HashMap 数组中的搜索从 O(n) 减少到 O(1)。或者我们可以设计一些对象，它实际上具有数组的优势，并且需要单个哈希操作来进行搜索。有什么建议吗？？？

考虑以下场景，您正在处理来自不同用户的元素，并且您希望根据用户配置文件(彼此分开)保留它们。内存效率最高的方法是使用 HashMap 数组将它们分开。

Answer 1

我已经编辑了您的问题以包含各种用户帐户的假设场景，每个帐户都具有不同的属性。正如另一个答案中提到的，这里的解决方案是 map 的 map 。有两个单独的搜索发生:

1. 找到合适的用户
2. 找到该用户的正确属性

这些搜索中的每一个都可以使用单独的 map 完成。

用户 map :

class Application {

    ...

    Map<String, User> userMap = new HashMap<>();

    public User getUser(String userName) {
        return userMap.get(userName);
    }

    ...
}

属性图:

class User {

    ...

    Map<String, Property> propertyMap = new HashMap<>();

    public Property getProperty(String propertyName) {
        return propertyMap .get(propertyName);
    }

    ...
}

现在查找名为 Arthur Dent 的用户的名为 favoriteTowel 的属性:

myApplication.getUser("Arthur Dent").getProperty("favoriteTowel");