Java hashtable или hashmap?

Question

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

Моих queations являются:

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

EDIT: Что касается эффективности, это спорный вопрос. В качестве ориентира используйте структуру данных (как в абстрактной концепции структуры данных), которая наилучшим образом соответствует вашей проблеме и выбирает доступную версию ванили. Если вы можете доказать, что у вас есть проблема с производительностью в вашем коде, вы можете начать думать о том, чтобы использовать что-то «более эффективное». Это в цитате, потому что это очень простое определение: мы говорим об эффективности памяти, эффективности вычислительного времени, эффективности сбора мусора и т. Д. Никогда не забывайте rules for code optimization.

Answer 5

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

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

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

Answer 6

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

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

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

При чтении несколько сообщений беспокоились об использовании памяти hashmap. В одном сообщении упоминалось, что пустой hashmap занимает 300 байт.

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

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

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

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

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