Кэширование хэшей в коллекциях Java?

Question

Когда я реализую коллекцию, которая использует хеши для оптимизации доступа, я должен кэшировать значения хешей или предполагать эффективную реализацию hashCode()?

С другой стороны, когда я реализую класс, который переопределяет hashCode(), следует ли мне предполагать, что коллекция (т. Е. HashSet) кэширует хэш?

Этот вопрос касается только производительности в сравнении с объемом памяти.Я знаю, что хэш-значение объекта не должно изменяться.

Уточнение: Изменяемый объект, конечно, должен очистить кэшированное значение при его изменении, тогда как коллекция полагается на объектыне меняетсяНо это не относится к моему вопросу.

Answer 1

При разработке классов ImmutableSet и ImmutableMap в Guava мы выбрали , а не для кэширования хэш-кодов.Таким образом, вы получите лучшую производительность от кэширования хеш-кода тогда и только тогда, когда вы будете достаточно внимательны, чтобы выполнять кэширование самостоятельно.Если бы мы их кэшировали сами, мы бы стоили вам лишних времени и памяти даже в том случае, если вы глубоко заботитесь о скорости и пространстве!

Это правда, что HashMap выполняет это кэширование, но это был автор HashMap (Джош Блох), который настоятельно рекомендовал нам не следовать этому прецеденту!

Редактировать: о, к тому же, если ваш hashCode() медленный, кэширование в коллекции только адресв любом случае, половина проблемы, так как hashCode() все еще должен вызываться для объекта, переданного в get(), несмотря ни на что.

Answer 2

Учитывая, что java.lang.String кэширует свой хеш, я думаю, что hashcode () должен быть быстрым.

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

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

Answer 3

С другой стороны, когда я реализую класс, который переопределяет hashcode (), я должен предположить, что коллекция (то есть HashSet) кэширует хэш?

Нет, вы не должны делать никаких предположений, выходящих за рамки написанного вами класса.

Конечно, вы должны попытаться сделать свой хеш-код дешевым. Если это не так, и ваш класс неизменен, создайте hashCode при инициализации или лениво при первом запросе (см. Java.lang.String). Если ваш класс не является неизменяемым, я не вижу другой возможности, кроме как каждый раз пересчитывать hashCode.

Answer 4

Почему вы хотите его кешировать? Вам нужно спросить объекты, каков их хэш-код, пока вы работаете с ним, чтобы выделить его для хэш-корзины (и любые объекты, которые находятся в одной и той же корзине, могут иметь тот же хеш-код), но тогда вы можете забыть его.

Вы можете хранить объекты в обертке HashNode или что-то в этом роде, но я постараюсь сначала реализовать ее без кэширования (как это делает HashSet и др.) И посмотреть, нужна ли вам дополнительная производительность и сложность, прежде чем идти туда.

Answer 5

Я бы сказал, что в большинстве случаев вы можете положиться на эффективные реализации hashCode(). AFAIK, этот метод вызывается только для методов поиска (например, contains, get и т. Д.) Или методов, которые изменяют коллекцию (add / put, remove и т. Д.).

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