Должны ли мы использовать HashSet?

Question

HashSet поддерживается HashMap. От его JavaDoc:

Этот класс реализует интерфейс Set, поддержанный хэш-таблицу (фактически экземпляр HashMap)

Когда взглянуть на источник, мы также можем видеть, как они относятся к друг с другом:

// Dummy value to associate with an Object in the backing Map 
private static final Object PRESENT = new Object(); 
public boolean add(E e) { 
    return map.put(e, PRESENT)==null; 
} 

Поэтому HashSet<E> опирается на HashMap<E,Object>. Для всех HashSets в нашем приложении у нас есть один ссылочный объект PRESENT, который мы используем в значении HashMap. Хотя память, необходимая для хранения PRESENT, пренебрежимо мала, мы все равно сохраняем ссылку на нее для каждого значения на карте.

Не эффективнее было бы использовать null вместо PRESENT? Далее следует рассмотреть вопрос об отказе от HashSet и непосредственно использовать HashMap, учитывая обстоятельства, позволяющие использовать Map вместо Set.

Моя основная проблема, что вызвало эти мысли следующая ситуация: У меня есть коллекция объектов на со следующими свойствами:

• большая коллекция объектов> 30'000
• порядок вставки не имеет значения
• Эффективная проверка, если элемент содержится
• Добавление новых элементов в коллекции не имеет значения выбранное решение должно выполнить оптимальным в контексте к указанным выше критериям, а также свести к минимуму CO памяти nsumption. Исходя из этого, на память приходят данные HashSet и HashMap. Размышляя об альтернативных подходах, ключевой вопрос:

Как эффективно проверить containement?

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

Я имел взгляд на различные вопросы, которые даже пролить свет на вопрос, но не спокойно ответил на мой вопрос:

• Java : HashSet vs. HashMap
• clarifying facts behind Java's implementation of HashSet/HashMap
• Java HashSet vs HashMap

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

Answer 1

Короче говоря, да, вы должны использовать HashSet. Возможно, это не самая эффективная реализация Set, но это почти никогда не имеет значения, если вы не работаете с огромным количеством данных.

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

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

Что вы могли бы сделать, если вы действительно хотите сохранить последний бит памяти и не заботитесь о вставке, использует массив фиксированного размера, сортируя его и выполняя бинарный поиск каждый раз. Но я сомневаюсь, что он более эффективен, чем HashSet.

Answer 2

Hashtables и HashSets следует использовать совершенно по-другому, поэтому, возможно, их нельзя сравнивать как «которые более эффективны». Хешсет будет более подходящим для математического «набора» (например, {1,2,3,4}). Они не содержат дубликатов и допускают только одно значение null. В то время как hashmap больше представляет собой систему ценностей key-> pair. Они допускают множество нулевых значений, а также дубликатов, а не дублируют ключевые значения. Я знаю, что это, вероятно, отвечает «разница между хеш-таблицей и хешсет», но я думаю, что мой смысл в том, что они действительно не могут сравниться.