JAVA: самый эффективный метод поиска объекта, хранящегося в hashMap

У меня есть куча объектов, хранящихся в hashMap<Long,Person> мне нужно найти объект person с определенным атрибутом, не зная его ID.



Например класс 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"));


Ответы, которые я нашел здесь, были довольно старыми.
662   7  

7 ответов:

Если вы хотите скорости и всегда ищете один конкретный атрибут, то лучше всего создать еще одну хэш-карту "кэша" с ключом этого атрибута.

Занимаемая память будет незначительна для менее чем миллиона записей, и поиск хэш-карты будет намного быстрее, чем любое другое решение.

В качестве альтернативы вы можете поместить все атрибуты поиска в одну карту (т. е. имена и удостоверения личности). Префикс Ключей с чем-то уникальным, если вы обеспокоены коллизиями. Что-то вроде:

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

В этот момент вы действительно входите в дизайн сумки для захвата, но все еще очень эффективны, если вы не ожидаете миллионов записей.

5  
2018-01-19 01:34:40

Лучший метод с точки зрения производительности, который я могу придумать,-это иметь другой HashMap, с ключом, являющимся атрибутом, который вы хотите найти, и значением, представляющим собой список объектов.

Для вашего примера это будет HashMap<String, List<Person>>, а ключом будет имя пользователя. Недостатком является то, что вы должны поддерживать две карты.

Примечание: я использовал List<Person> в качестве значения, потому что мы не можем гарантировать, что username является уникальным среди всех пользователей. То же самое относится и к любому другому полю.

Например, чтобы добавить a 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");
1  
2018-01-18 19:35:46

Получение одной или нескольких записей из изменчивой карты
Если карта, на которой вы работаете, может часто меняться, и вы хотите получить только несколько записей, то повторение записей карты нормально, так как вам потребуется пространство и время для построения других структур или сортировки данных.

Получение большого количества записей из изменчивой карты
Если вам нужно получить много записей из этой карты, вы можете получить лучшую производительность, либо сортируя записи сначала (например, построить список и сортировать это), а затем с помощью бинарного поиска. В качестве альтернативы вы можете построить промежуточную карту, которая использует атрибут (ы), необходимый для поиска, в качестве своего ключа.

Обратите внимание, однако, что оба подхода, по крайней мере, требуют времени, так что это дает только лучшую производительность, когда вы ищете много записей.

Получение записей несколько раз из "постоянной" карты
Если ваша карта и ее значения не меняются (или не так часто), вы можете сохранить атрибут карты - > человек. Это будет означать, что некоторые усилия по первоначальной настройке и обновлению дополнительной карты (если ваши данные не изменятся), а также некоторые затраты памяти, но значительно ускоряют поиск позже. Это стоящий подход, когда вы делаете очень мало "записывает" по сравнению с тем, как часто вы делаете поиск и если вы можете сэкономить накладные расходы памяти (зависит от того, насколько большие эти карты будут и сколько памяти у вас есть, чтобы сэкономить).

0  
2018-01-18 17:51:37

Рассмотрим одну хэш-карту на альтернативный ключ. Это будет иметь "высокую" стоимость установки, но приведет к быстрому извлечению альтернативным ключом.

  1. настройте хэш-карту, используя значение ключа Long.
  2. прогоните объекты hashmap Person и создайте вторую hashmap (HashMap<String, Person>), для которой имя пользователя является ключом.

Возможно, заполнить обе хэш-карты одновременно.

В вашем случае, в итоге вы получите что-то вроде HashMap<Long, Person> idKeyedMap и HashMap<String, Person> usernameKeyedMap.

Вы также можете поместить все ключи значения в одной и той же карте, если вы определяете карту как Map<Object, Person>. Затем, когда вы добавляете пара (идентификатор, человек) , вам также нужно добавить пару (имя пользователя, персона). Будьте осторожны, это не очень хорошая техника.

0  
2018-01-18 18:09:33

Как лучше всего решить эту проблему?

Есть много способов решить эту проблему, как вы можете видеть в ответах и комментариях.

Как используется карта (и, возможно, как она создается). Если карта построена из оператора select с помощью long id значение из столбца таблицы мы могли бы подумать, что мы должны использовать 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).

Это будет самый быстрый способ получить объект, который вы хотите найти на карте, содержащей объекты человека в качестве его значений.

0  
2018-01-18 18:13:44

Вы можете просто преобразовать Hashmap в список, используя:

List list = new ArrayList (map.values ());

Теперь вы можете легко перебирать объект списка. Таким образом, вы можете искать значения Hashmap по любому свойству класса Person, не ограничиваясь только firstname.

Единственным недостатком является то, что вы в конечном итоге создадите объект списка. Но с помощью stream api вы можете дополнительно улучшить код для преобразования Hashmap в список и итерации за одну операцию, экономя место и повышая производительность. параллельный поток.

0  
2018-01-18 20:29:30

Сортировка и нахождение объекта value могут быть выполнены путем проектирования и использования соответствующего класса компаратора.

Класс компаратора: проектирование компаратора по определенному признаку может быть выполнено следующим образом: 

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

    }
0  
2018-01-19 07:58:08

Comments

    Ничего не найдено.
Click here to cancel reply.