Самый быстрый способ получить доступ к этому объекту

Question

Допустим, у меня есть список из 1 000 000 пользователей, где их уникальный идентификатор - это строка имени пользователя.Чтобы сравнить два объекта User, я просто переопределяю метод compareTo() и сравниваю имя пользователя.

По заданной строке имени пользователя я хочу найти объект User из списка.Что, в среднем случае, было бы самым быстрым способом сделать это.

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

Answer 1

Если вам не нужно хранить их в базе данных (что является обычным сценарием), HashMap<String, User> будет работать нормально - он имеет сложность O (1) для поиска.

Как уже отмечалось, обычным сценарием является их размещение в базе данных. Но для получения более быстрых результатов используется кэширование. Вы можете использовать EhCache - он похож на ConcurrentHashMap, но у него есть время жизни для элементов и возможность распределения по нескольким машинам.

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

Answer 2

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

Answer 3

С точки зрения структур данных HashMap может быть хорошим выбором.Это одобряет большие наборы данных.Время для вставок считается постоянным O (1).

В этом случае звучит так, как будто вы будете выполнять больше операций поиска, чем вставок.Для поисков средняя сложность по времени составляет O (1 + n / k), ключевым фактором (извините за каламбур) является то, насколько эффективен алгоритм хеширования для равномерного распределения данных по сегментам.

рискздесь имя пользователя короткое и использует небольшой набор символов, такой как az.В этом случае будет много коллизий, из-за которых HashMap загружается неравномерно и, следовательно, замедляет поиск.Одним из способов улучшить это может быть создание собственного объекта ключа пользователя и переопределение метода hashcode() с помощью алгоритма algorthim, который лучше подходит вашим ключам.

в итоге, если у вас большой набор данных, хороший / подходящийалгоритм хэширования и у вас есть место для хранения всего этого в памяти, тогда HashMap может обеспечить относительно быстрый поиск

Я думаю, учитывая ваш последний пост в ArrayList и его масштабируемость, я бы принял предложение Божо и пошел бы закэш целевой сборки, такой как EhCache .Это позволит вам контролировать использование памяти и политики удаления.Все еще намного быстрее, чем доступ к БД.

Answer 4

Я уверен, что вы хотите хэш-карту.Они работают быстрее всего и экономят память.Как также отмечалось в других ответах, String работает как отличный ключ, поэтому вам не нужно ничего переопределять.(Это также относится к следующему.)

Основной альтернативой является TreeMap .Это медленнее и использует немного больше памяти.Однако это намного более гибко.Та же карта будет отлично работать с 5 записями и 5 миллионами записей.Вам не нужно заранее это указывать.Если ваш список сильно различается по размеру, TreeMap будет захватывать память по мере необходимости и отпускать, когда этого не происходит.Хеш-карты не так хороши в том, чтобы отпускать, и, как я объясню ниже, они могут быть неудобны, когда занимают больше памяти.

TreeMap лучше работает с сборщиками мусора.Они просят памяти маленькими, легко найденными кусками.Если вы запустите хеш-таблицу с местом для 100 000 записей, когда она заполнится, она освободит массив из 100 000 элементов (почти мегабайт на 64-битной машине) и запросит еще более крупный.Если он делает это неоднократно, он может опередить GC, который имеет тенденцию генерировать исключение нехватки памяти, а не тратить много времени на сбор и концентрацию разбросанных битов свободной памяти.(Он предпочитает поддерживать свою репутацию скорости за счет репутации вашей машины как имеющей много памяти. Вы действительно можете исчерпать память, если 90% вашей кучи не используется, потому что она фрагментирована.)

Так что, если вы запускаете программу с полным наклоном, ваш список имен сильно различается по размеру - и, возможно, у вас даже есть несколько списков имен, сильно различающихся по размеру - TreeMap будет работать намного лучше для вас.

Хеш-карта, несомненно, будет именно тем, что вам нужно.Но когда все становится по-настоящему сумасшедшим, появляется ConcurrentSkipListMap .Это все, что есть в TreeMap, за исключением того, что оно немного медленнее.С другой стороны, он позволяет добавлять, обновлять, удалять и читать из нескольких потоков, без синхронизации, без синхронизации.(Я упоминаю это только для полноты.)