Итерация по объединению несколько эффективных наборов ключей Java Map
В одной из моих Java 6 проекты у меня есть массив экземпляров LinkedHashMap в качестве входных данных для метода, который должен перебирать все ключи (т.е. через объединение наборов ключей всех карт) и работать со связанными значениями. Не все ключи существуют во всех картах, и метод не должен проходить через каждый ключ более одного раза или изменять входные карты.
Моя текущая реализация выглядит так:
Set
Экземпляр HashSet гарантирует, что нет key будет задействован более одного раза.
К сожалению, эта часть кода довольно критична с точки зрения производительности, так как очень часто называется . Фактически, согласно профилировщику, более 10% времени ЦП тратится на метод HashSet.add () .
Я пытаюсь максимально оптимизировать этот код. Использование LinkedHashMap с его более эффективными итераторами (по сравнению с обычным HashMap ) стало значительным стимулом, но я надеялся сократить время бухгалтерского учета до минимума. .
Предварительная установка всех ключей в HashSet с использованием addAll () оказалась менее эффективной из-за стоимости последующего вызова HashSet.contains () . .
На данный момент я смотрю, могу ли я использовать растровое изображение (ну, boolean [] , чтобы быть точным), чтобы полностью избежать HashSet, но это может быть вообще невозможно, в зависимости от моего диапазона ключей .
Есть ли более эффективный способ сделать это? Желательно то, что не будет ограничивать ключи?
РЕДАКТИРОВАТЬ:
Несколько пояснений и комментариев:
Мне нужны все значения с карт - я не могу отбросить ни одно из них .
Мне также нужно знать, из какой карты взято каждое значение. Недостающая часть ( ... ) в моем коде будет примерно такой:
for (Map m: input) {
Object v = m.get (ключ);
// Делаем что-нибудь с v
}
Простой пример, чтобы понять, что мне нужно делать с картами, - это распечатать все карты параллельно следующим образом:
Key Map0 Map1 Map2
F 1 null 2
B 2 3 null
C null null 5
...
На самом деле я этим не занимаюсь, но вы должны уловить идею.
Входные карты чрезвычайно переменные. Фактически, каждый вызов этого метода использует другой их набор. Поэтому я ничего не получу, кэшируя объединение их ключей.
Мои ключи - это все экземпляры String. Они как бы интернированы в куче с использованием отдельной HashMap, поскольку они довольно часто повторяются, поэтому их хэш-код уже кэширован, и большинство хеш-проверок (когда реализация HashMap проверяет, действительно ли два ключа равны, после их хэш-кодов match) сводятся к сравнению идентичности ( == ). Профилировщик подтверждает, что только 0,5% времени ЦП тратится на String.equals () и String.hashCode () .
РЕДАКТИРОВАТЬ 2:
На основе предложения в ответах, я сделал несколько тестов, профилирование и тестирование производительности.В итоге производительность увеличилась примерно на 7%. Что я сделал:
Я установил начальную емкость HashSet, чтобы удвоить общий размер всех входных карт. Это дало мне что-то в районе 1-2% за счет устранения большинства (всех?) вызовов resize () в HashSet.
Я использовал Map.entrySet () для карты, которую я сейчас повторяю. Изначально я избегал этого подхода из-за дополнительного кода и опасений, что дополнительные проверки и вызовы метода Map.Entry получателя перевешивают любые преимущества. Оказалось, что в целом код был немного быстрее.
Я уверен, что некоторые люди начнут кричать на меня, но вот оно: сырые типы. В частности, в приведенном выше коде я использовал необработанную форму HashSet. Поскольку я уже использовал Object в качестве типа содержимого, я не теряю безопасность типов. Стоимость этой бесполезной операции checkcast при вызове HashSet.add () , по-видимому, была достаточно важной для повышения производительности при удалении на 4%. Почему JVM настаивает на проверке приведений к Объект вне меня ...