Java hashtable или hashmap?

Question

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

Мои очереди:

• Ява hashmap самая быстрая структура данных, реализованная в Java для вставки / удаления / поиска?
• Во время чтения несколько постов были обеспокоены использованием памятиhashmap, В одном посте упоминается, что пустой hashmap занимают 300 байт. Является hashtable более эффективная память, чем hasmap?
• Кроме того, является hash функция в каждом наиболее эффективна дляstrings?

Answer 1

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

Является ли java hashmap самой быстрой структурой данных, реализованной в java для вставки / удаления / поиска?

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

Во время чтения у нескольких постов были проблемы с использованием памяти hashmap. В одном посте упоминалось, что пустой хэш-файл занимает 300 байт.

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

Является ли hashtable более эффективной памятью, чем hasmap?

Это может быть, но не достаточно, чтобы иметь значение. Hashtable начинается с меньшего размера по умолчанию. Если вы создадите HashMap с меньшей емкостью, он будет меньше.

Кроме того, является ли хеш-функция в каждой из них наиболее эффективной для строк?

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

Answer 2

1.HashMap - это только одна из самых быстрых структур данных, реализованных в java для вставки / удаления / поиска. HashSet работает так же быстро, как HashMap для вставки / удаления / поиска, а ArrayList так же быстр, как HashMap, когда вставляется элемент в конец.

2.Hashtable не более эффективен по памяти, чем HashMap, все они реализованы с помощью отдельной цепочки.

3. Хэш-функции двух структур данных одинаковы, но вы можете написать подкласс, расширить их, а затем переопределить хеш-функцию, чтобы она максимально подходила вашему приложению.

Answer 3

HashMap (или, более вероятно, HashSet), вероятно, хорошее место для начала, с вашей точки зрения. Он не идеален, и он потребляет больше памяти, чем, например, список, но он должен использоваться по умолчанию, когда вам нужно быстро добавлять, удалять и содержать операции. String.hashCode() Реализация - не лучшая хеш-функция, хотя она быстра и достаточно хороша для большинства целей.

Answer 4

Как вы указали, Hashtable полностью синхронизирован, поэтому он зависит от вашей среды. Если у вас много потоков, то ConcurrentHashMap будет лучшим решением. Однако вы можете посмотреть на Trove4J - возможно, он лучше подойдет вашим потребностям. Trove использует хеширование цепочек, аналогичное хеш-таблицам

Answer 5

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

Для начала рекомендую HashSet или же TreeSet (в случае, если заказ важен). HashMap сопоставляет ключи со значениями, которые отличаются. Обратитесь к этому обсуждению, чтобы понять различия между HashMap а также Hashtable, Я лично не использовал Hashtable с 2007 года.

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

РЕДАКТИРОВАТЬ: Что касается вопросов эффективности, это спорный вопрос. В качестве руководства используйте структуру данных (как в абстрактной концепции структуры данных), которая наилучшим образом соответствует вашей проблеме, и выберите доступную реализацию ванили. Если вы можете доказать, что у вас есть проблемы с производительностью в вашем коде, вы можете начать думать о том, чтобы использовать что-то "более эффективное". Это в цитате, потому что это очень свободное определение: мы говорим об эффективности памяти, эффективности вычислений, эффективности сбора мусора и т. Д. Никогда не забывайте правила оптимизации кода.

Answer 6

Время доступа к HashMap (и, я полагаю, также к HashTable) равно O (1), поскольку внутреннее размещение заданного значения во время put () определяется вычислением (хэш ключа значения)% (общее количество сегментов). Это O (1) - среднее время доступа, если, однако, много хэшей ключей к одному и тому же сегменту, то время доступа будет стремиться к O (n), поскольку все значения, помещенные в один и тот же сегмент, растут, и все они растут в виде связанного списка.

Как вы сказали, учитывая издержки синхронизации внутри Hashtable, я бы, вероятно, выбрал Hash map. Кроме того, вы можете точно настроить Hashmap, установив его различные параметры, такие как коэффициент загрузки, который предлагает средства оптимизации памяти. Я голосую за HashMap...