JAVA :查找存储在hashMap中的对象的最佳性能方法

Question

我在hashMap<Long,Person>中存储了一堆对象，我需要在不知道它的ID的情况下找到具有特定属性的person对象。

例如，person类：

public person{
    long id;
    String firstName;
    String lastName;
    String userName;
    String password;
    String address;
    ..
   (around 7-10 attributes in total)
    }

假设我想找到用户名= "mike“的对象。是否有任何方法可以在没有实际迭代整个散列映射的的情况下找到：

for (Map.Entry<Long,Person> entry : map.entrySet()) {
        if(entry.getValue().getUserName().equalsIgnoreCase("mike"));

我在这里找到的答案很旧。

Answer 1

如果你想要速度，并且总是在寻找一个特定的属性，你最好的选择是创建另一个“缓存”哈希映射，并使用该属性键控。

占用的内存对于不到一百万个条目来说是微不足道的，哈希映射查找将比任何其他解决方案快得多。

或者，您可以将所有搜索属性放入一个单一的地图(即。(姓名和ids)。如果您关心冲突，请在键前加上一些独特的内容。类似于：

String ID_PREFIX = "^!^ID^!^";
String USERNAME_PREFIX = "^!^USERNAME^!^";
String FIRSTNAME_PREFIX = "^!^FIRSTNAME^!^";
Map<String,Person> personMap = new HashMap<String,Person>();

//add a person
void addPersonToMap(Person person)
{
    personMap.put(ID_PREFIX+person.id, person);
    personMap.put(USERNAME_PREFIX+person.username, person);
    personMap.put(FIRSTNAME_PREFIX+person.firstname, person);
}

//search person
Person findPersonByID(long id)
{
    return personMap.get(ID_PREFIX+id);
}

Person findPersonByUsername(String username)
{
    return personMap.get(USERNAME_PREFIX+username);
}

//or a more generic version:
//Person foundPerson = findPersonByAttribute(FIRSTNAME_PREFIX, "mike");
Person findPersonByAttribute(String attr, String attr_value)
{
    return personMap.get(attr+attr_value);
}

上述假设假设每个属性在所有Person中都是唯一的。对于ID和用户名，这可能是正确的，但是问题指定的firstname=mike不太可能是唯一的。

在这种情况下，您希望使用列表进行抽象，因此它更像这样：

Map<String,List<Person>> personMap = new HashMap<String,List<Person>>();

//add a person
void addPersonToMap(Person person)
{
    insertPersonIntoMap(ID_PREFIX+person.id, person);
    insertPersonIntoMap(USERNAME_PREFIX+person.username, person);
    insertPersonIntoMap(FIRSTNAME_PREFIX+person.firstname, person);
}

//note that List contains no duplicates, so can be called multiple times for the same person.
void insertPersonIntoMap(String key, Person person)
{
    List<Person> personsList = personMap.get(key);
    if(personsList==null)
        personsList = new ArrayList<Person>();
    personsList.add(person);
    personMap.put(key,personsList);
}

//we know id is unique, so we can just get the only person in the list
Person findPersonByID(long id)
{
    List<Person> personList = personMap.get(ID_PREFIX+id);
    if(personList!=null)
        return personList.get(0);

    return null;
}

//get list of persons with firstname
List<Person> findPersonsByFirstName(String firstname)
{
    return personMap.get(FIRSTNAME_PREFIX+firstname);
} 

在这一点上，你真的进入了一个抓斗袋的设计，但仍然非常有效，如果你没有期待数百万的条目。

Answer 2

我能想到的最佳性能方法是有另一个HashMap，键是要搜索的属性，值是一个对象列表。

对于您的示例，这将是HashMap<String, List<Person>>，其中的键是用户名。缺点是你必须维护两张地图。

注意:我使用List<Person>作为值，因为我们不能保证username在所有用户中都是唯一的。其他任何字段也是如此。

例如，要向这个新映射添加一个Person，您可以这样做：

Map<String, List<Person>> peopleByUsername = new HashMap<>();

// ...

Person p = ...;

peopleByUsername.computeIfAbsent(
        p.getUsername(), 
        k -> new ArrayList<>())
    .add(p);

然后，返回用户名为joesmith的所有用户

List<Person> matching = peopleByUsername.get("joesmith");

Answer 3

从易失性映射获取一个或几个条目

如果您正在操作的映射经常发生变化，并且您只想得到几个条目，那么迭代映射的条目就可以了，因为您需要空间和时间来构建其他结构或排序数据。

从易失性映射获取多个条目

如果您需要从该映射中获取许多条目，则可以先对条目进行排序(例如，构建一个列表并对其进行排序)，然后使用二进制搜索来获得更好的性能。或者，您可以构建一个使用需要搜索的属性作为其键的中间映射。

但是，请注意，这两种方法至少都需要时间，因此在寻找许多条目时，这只会产生更好的性能。

多次从“持久化”映射获取条目

如果您的地图及其值没有变化(或者不经常)，您可以维护map属性-> person。这意味着在初始设置和更新附加地图(除非数据没有改变)方面需要付出一定的努力，以及一些内存开销，但随后会极大地加快查找速度。这是一种很有价值的方法，因为与进行查找的频率以及是否可以节省内存开销相比，“写”非常少(取决于这些映射的大小和需要节省多少内存)。