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

如果您想要速度,并且总是在寻找一个特定属性,那么最好的办法是创建另一个以该属性为关键字的“缓存”哈希映射。

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

或者,您可以将所有搜索属性放在一个地图中(即名称和ID)。如果您担心碰撞,请在关键点前加上唯一的前缀。类似于:

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

以上假设每个属性在所有人中都是唯一的。ID和username可能是这样,但问题指定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);
} 

在这一点上,你真的进入了一个抓取袋的设计,但如果你不期望有数百万的条目,那么仍然非常有效。

我能想到的最好的性能方面的方法是 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");

从volatile映射中获取一个或几个条目
如果您正在操作的映射可以经常更改,并且您只想获得几个条目,那么迭代映射的条目就可以了,因为您需要空间和时间来构建其他结构或对数据进行排序。

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

然而,请注意,这两种方法至少都需要时间,所以当您查找许多条目时,这只会产生更好的性能。

多次从“持久”映射中获取条目
如果地图及其值没有变化(或变化不太频繁),则可以维护地图属性->人这将意味着在初始设置和更新额外映射(除非数据不变)方面需要一些努力,以及一些内存开销,但稍后会大大加快查找速度。如果与查找的频率相比,您只需进行很少的“写入”,并且您是否可以节省内存开销(取决于这些映射的大小以及您必须节省的内存),那么这是一种值得采用的方法。

考虑每个备用键一个hashmap。 这将有“高”的安装成本, 但会导致通过备用键快速检索。

1. 使用 Long 关键值。
2. 运行hashmap Person 对象并创建第二个hashmap( HashMap<String, Person> )用户名是其密钥。

也许,可以同时填充两个hashmap。

就你而言, 你最终会得到这样的结果 HashMap<Long, Person> idKeyedMap 和 HashMap<String, Person> usernameKeyedMap .

也可以将所有键值放在同一个映射中, 如果将贴图定义为 Map<Object, Person> . 然后 当您添加 (id,人员)对, 您还需要添加(username,person)对。 注意,这不是一个很好的技巧。

解决问题的最佳方法是什么?

正如你在回答和评论中所看到的,有很多方法可以解决这个问题。

地图是如何使用的(可能还有它是如何创建的)。如果映射是从带有 long 身份证件 我们可能认为应该使用的表中的列的值 HashMap<Long, Person> .

看待这个问题的另一种方法是考虑用户名也应该是唯一的(即,任何两个人都不应该共享同一个用户名)。因此,将地图创建为 HashMap<String, Person> . 具有 用户名 作为键,Person对象作为值。

使用后者:

Map<String, Person> users = new HashMap<>();
users = retrieveUsersFromDatabase(); // perform db select and build map
String username = "mike";
users.get(username).

这将是在包含Person对象作为其值的地图中检索要查找的对象的最快方法。

您只需使用以下命令将Hashmap转换为List:

List List=新建ArrayList(map.values());

现在,您可以轻松地遍历列表对象。通过这种方式,您可以在Person类的任何属性上搜索Hashmap值,而不仅仅限于firstname。

唯一的缺点是最终会创建一个列表对象。但使用流api可以进一步改进代码,将Hashmap转换为列表并在单个操作中迭代,从而节省空间并提高并行流的性能。

通过设计和使用适当的比较器类,可以完成值对象的排序和查找。

比较器等级: 针对特定属性设计比较器可以如下所示:

class UserComparator implements Comparator<Person>{

    @Override
    public int compare(Person p1, Person p2) {

        return  p1.userName.compareTo(p2.userName);

    }

}

用法: 上述设计的比较器可按如下方式使用:

    HashMap<Long, Person> personMap = new HashMap<Long, Person>();

                        .
                        .
                        .

    ArrayList<Person> pAL = new ArrayList<Person>(personMap.values()); //create list of values

    Collections.sort(pAL,new UserComparator()); // sort the list using comparator

    Person p = new Person(); // create a dummy object

    p.userName="mike"; // Only set the username

    int i= Collections.binarySearch(pAL,p,new UserComparator()); // search the list using comparator

    if(i>=0){

        Person p1 = pAL.get(Collections.binarySearch(pAL,p,new UserComparator())); //Obtain object if username is present

    }else{

        System.out.println("Insertion point: "+ i); // Returns a negative value if username is not present

    }