Время выполнения сравнения Hashmap

Question

Я сравниваю 2 HashMaps и пытаюсь выяснить временную сложность цикла сравнения.Код выглядит следующим образом:

//map1 is a HashMap and contains m elements and keys
//map2 is a HashMap and contains n elements and keys 
List<myObject> myList = new ArrayList<myObject>()  
for (String key: map1.keySet()){ 
    if(!map2.containsKey(key)){
        myList.add(map.get(key));
   }
 }

Первый цикл for будет O (m) .На другом форуме я обнаружил, что функция containsKey () занимает lg (n) время.Может кто-нибудь подтвердить это?Я не смог найти его в JavaDocs.Если это так, то общая сложность времени составит O (mlg {n}) .Также были бы полезны любые идеи о том, как сделать это сравнение лучше.

Answer 1

Зависит от вашего алгоритма хеширования и коллизий.

Используя идеальный хеш-код, теоретически поиск карты составляет O (1), постоянное время, если есть коллизии, оно может быть до O (n).Так что в вашем случае, если у вас есть хорошие алгоритмы хеширования, это будет O (m).

, если вы посмотрите на wiki , вы сможете лучше понять концепцию.Вы также можете посмотреть исходный код карты.

Answer 2

Вы правы относительно сложности времени внешнего цикла: O (n) .Асимптотическая сложность HashMap.containsKey() равна O (1) , если вы не сделали что-то нелепое в своей реализации myObject.hashCode().Таким образом, ваш метод должен выполняться за O (n) время.Оптимизация будет заключаться в том, чтобы обеспечить цикл по меньшей из двух карт.

Обратите внимание, что TreeMap.containsKey() имеет O (log n) сложность, а не HashMap ...Хватит смотреть на эти форумы:)

Answer 3

Реализация Java HashMap должна постоянно изменять размер внутренней структуры данных, чтобы она была на определенную величину больше, чем количество элементов в карте, и алгоритм хеширования хорош, поэтому я бы предположил, что коллизии минимальны, и вы будете намного ближедо O (1), чем O (n).

Какой HashMap вы используете?Тот, который поставляется с Java?Ваш собственный?