Я должен использовать для поиска HashSet или TreeSet для очень больших наборов данных?

У меня есть требование хранить от 2 до 15 миллионов учетных записей (которые являются String длиной 15) в структуре данных для целей поиска и проверки уникальности. Первоначально я планировал хранить их в HashSet, но я сомневаюсь, что скорость поиска будет медленной из-за коллизий хэшей и в конечном итоге будет медленнее, чем карта дерева (с использованием двоичного поиска).

Существует никакого требования в отношении данных, которые должны быть отсортированы. Я использую Java 7. У меня есть 64G система с 48G специально для этого приложение.

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

2 8
performance hashset treeset

2 ответа:

Если у вас есть 48 ГБ выделенной памяти для ваших 2 млн до 15 млн записей, ваш лучший выбор, вероятно, использовать HashMap<Key, Record>, Где ваш ключ является Integer или String в зависимости от ваших требований.

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

Я рекомендую использовать следующий конструктор: new HashMap<>(13_000_000); (на 30% больше, чем ожидаемое количество записей-которое будет автоматически расширено на Реализация HashMap в 2^24 ячейки). Скажите вашему приложению, что этот Map будет очень большим с самого начала, поэтому ему не нужно автоматически расти по мере его заполнения.

HashMap использует время доступа O(1) для своих членов, тогда как TreeMap использует время поиска O(log n), но может быть более эффективным с памятью и не нуждается в умной функции хэширования. Однако, если вы используете ключи String или Integer, Вам не нужно беспокоиться о разработке функции хэширования, и поиск по постоянному времени будет это будет огромным улучшением. Кроме того, еще одно преимущество TreeMap / TreeSet это упорядоченный порядок, о котором вы заявили, что вам все равно; используйте HashMap.

Если единственная цель списка-проверить наличие уникальных номеров счетов , то все, что я сказал выше, по-прежнему верно, но, как вы указали в своем вопросе, вы должны использовать HashSet<String>, а не HashMap. Рекомендации по производительности и аргумент конструктора по-прежнему применимы.

Дальнейшее чтение: HashSet и TreeSet тест производительности

12

Когда мы попытались сохранить 50 миллионов записей в HashMap с соответствующими параметрами инициализации, вставка начала замедляться, особенно после 35 миллионов записей. Переход на TreeMap давал постоянную производительность вставки и извлечения.

Наблюдение: TreeMap даст лучшую производительность, чем HashMap для большого входного набора. Для меньшего набора, конечно, HashMap даст лучшую производительность.

2