хэш-карта или хэш-набор?

У меня есть два списка, содержащие

List<MyObj>.

и MyObj имеет член "String ID".

Мне нужно перебирать их время от времени, а иногда мне нужно найти объекты, которые похожи на обоих.
Мне нужен более быстрый способ, чем списки. поэтому я могу знать, что могу использовать hashMap (чем ask содержит (String) при сравнении)

я должен использовать hashmap или hashset?

примечание: в хэш-наборе - мне нужно реализовать мои равные, и когда я запускаю contains() - я думаю, что это будет медленнее, чем хэш-карта, где при вставке я помещаю идентификатор строки в ключ. Я прав?


java hashmap hashset
person Bick    schedule 17.05.2011    source источник
comment
Похоже на Java -> Добавлен тег java. Если это не java, пожалуйста, отметьте свой вопрос соответствующим образом.   -  person ThiefMaster    schedule 17.05.2011

Ответы (3)


arrow_upward
1
arrow_downward

Что ж, используя HashMap, вы будете вынуждены хранить данные таким образом:

<ID1><MyObject> 
<ID2><MyObject>

Это не лучший способ, потому что у вас уже есть поле ID в MyObject.

Используя HashSet, вы сможете хранить только уникальные экземпляры MyObject, и вам также потребуется реализовать hashCode() в MyObject.

Вам решать.

person StKiller    schedule 17.05.2011
comment
Интересно, если запрос содержит - над хэш-набором - вычисляет хэш-код для всех . и при запросе contains() на hashmap - уже содержит индекс и извлекает его быстрее. - person Bick; 17.05.2011
comment
HashSet не вычисляет хэш элемента каждый раз. Я не думаю, что разница в производительности между HashSet и HashMap заметна. Есть разница в том, как они хранят данные. - person StKiller; 17.05.2011

arrow_upward
5
arrow_downward

примечание: в хэш-наборе - мне нужно реализовать мои равные, и когда я запускаю contains() - я думаю, что это будет медленнее, чем хэш-карта, где при вставке я помещаю идентификатор строки в ключ. Я прав?

Я не думаю, что вы заметите разницу в производительности. HashSet<E> реализован с использованием HashMap<E, E> под капотом. Таким образом, единственная разница будет заключаться в вызове MyObj.equals() (который предположительно вызывает String.equals()) и вызове String.equals() напрямую. И компилятор JIT довольно хорош для встраивания вызовов...

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

person Péter Török    schedule 17.05.2011

arrow_upward
2
arrow_downward

Это на самом деле не имеет никакого значения, потому что, если вы посмотрите на исходный код JDK, реализация Sun HashSet использует экземпляр HashMap для внутреннего хранения своих значений:

   public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
......

И даже если бы это было не так, все остальные ответы о том, что это на самом деле не имеет значения для производительности POV, применимы. Единственная реальная разница заключается в том, что вместо использования equals() и hashCode() реализации вашего ключевого класса вам нужно написать свою собственную для использования Set, но это может быть так же просто, как делегирование в поле id вашего класса, в случае, если id поле является уникальным идентификатором.

person BertNase    schedule 17.05.2011
comment
Не совсем потому, что set использует ключ как значение. - person teodozjan; 22.03.2013