Я пишу словарь, который сильно использует String в качестве ключа в Map<String, Index>
. Что касается меня, то какая из HashMap
и TreeMap
приведет к лучшей (более быстрой) производительности при поиске ключа на карте?
Улучшение TreeMap или HashMap
Ответ 1
Учитывая, что хэш-карты с коллизацией не так много, вы получите производительность o (1) (при большом количестве колонок это может ухудшиться до потенциально O (n), где N - количество записей (колонок) в любом одном ведре). TreeMaps, с другой стороны, используются, если вы хотите иметь какую-то сбалансированную древовидную структуру, которая дает извлечение O (logN). Так что это действительно зависит от вашего конкретного случая использования. Но если вы просто хотите получить доступ к элементам, независимо от их порядка используйте HashMap
Ответ 2
public class MapsInvestigation {
public static HashMap<String, String> hashMap = new HashMap<String, String>();
public static TreeMap<String, String> treeMap = new TreeMap<String, String>();
public static ArrayList<String> list = new ArrayList<String>();
static {
for (int i = 0; i < 10000; i++) {
list.add(Integer.toString(i, 16));
}
}
public static void main(String[] args) {
System.out.println("Warmup populate");
for (int i = 0; i < 1000; i++) {
populateSet(hashMap);
populateSet(treeMap);
}
measureTimeToPopulate(hashMap, "HashMap", 1000);
measureTimeToPopulate(treeMap, "TreeMap", 1000);
System.out.println("Warmup get");
for (int i = 0; i < 1000; i++) {
get(hashMap);
get(treeMap);
}
measureTimeToContains(hashMap, "HashMap", 1000);
measureTimeToContains(treeMap, "TreeMap", 1000);
}
private static void get(Map<String, String> map) {
for (String s : list) {
map.get(s);
}
}
private static void populateSet(Map<String, String> map) {
map.clear();
for (String s : list) {
map.put(s, s);
}
}
private static void measureTimeToPopulate(Map<String, String> map, String setName, int reps) {
long start = System.currentTimeMillis();
for (int i = 0; i < reps; i++) {
populateSet(map);
}
long finish = System.currentTimeMillis();
System.out.println("Time to populate " + (reps * map.size()) + " entries in a " + setName + ": " + (finish - start));
}
private static void measureTimeToContains(Map<String, String> map, String setName, int reps) {
long start = System.currentTimeMillis();
for (int i = 0; i < reps; i++) {
get(map);
}
long finish = System.currentTimeMillis();
System.out.println("Time to get() " + (reps * map.size()) + " entries in a " + setName + ": " + (finish - start));
}
}
Дает следующие результаты:
Warmup populate
Time to populate 10000000 entries in a HashMap: 230
Time to populate 10000000 entries in a TreeMap: 1995
Warmup get
Time to get() 10000000 entries in a HashMap: 140
Time to get() 10000000 entries in a TreeMap: 1164
Ответ 3
HashMap - это O (1) (обычно) для доступа; TreeMap - O (log n) (гарантировано).
Это предполагает, что ваши ключевые объекты неизменяемы и имеют надлежащим образом написанные методы equals и hashCode. См. Joshua Bloch "Эффективная Java" глава 3 о том, как правильно переопределить значения equals и hashCode.
Ответ 4
a HashMap
- средний показатель O (1), поэтому он должен быть быстрее, а для больших карт, вероятно, будет иметь лучшую пропускную способность.
Однако a HashMap
требует перезагрузки, когда Load Balance становится слишком высоким. rehashing - O (n), поэтому в любое время жизни программы вы можете неожиданно потерять производительность из-за переименования, что может быть критическим в некоторых приложениях [высокая латентность]. Поэтому подумайте дважды, прежде чем использовать HashMap
, если latency является проблемой!
a HashMap
также уязвим для слабых функций хеширования, что может вызвать O (n), если многие используемые элементы хэшируются в одном и том же месте.
Ответ 5
HashMap работает быстрее. Однако, если вам часто нужно обрабатывать словарь в алфавитном порядке, вам будет лучше с TreeMap, поскольку вам в противном случае нужно было бы сортировать все ваши слова каждый раз, когда вам нужно обрабатывать их в алфавитном порядке.
Для вашего приложения HashMap - лучший выбор, так как я сомневаюсь, что вам понадобится отсортированный по алфавиту список часто, если когда-либо.