Le hachage est-il utilisé pour accélérer les recherches d'objets dans les collections?

Question

IIUC il deux objets différents du même type peuvent être stockés dans un HashSet même si les deux objets retournent la même valeur lorsque hashCode() est appelée. Par exemple, selon this article "Aa" et "BB" retournent le même hashcode (2112), mais évidemment je peux mettre ces deux chaînes dans un HashSet et ils seront tous deux contenus dans le Set sans "Aa" écrasant "BB".

L'objectif principal de hashCode() est-il donc de trouver une instance dans un ensemble, ou des collections en général, plus rapidement? Cela implique également que si nous retournons une constante pour hashCode() que cela va ralentir les performances d'une collection qui stocke de tels objets (Dans un JPA context as suggested by this linked article for example)?

Answer 1

Oui. Les bases de tout algorithme basé sur un compartiment sont que vous souhaitiez que vos éléments soient répartis uniformément dans N buckets, où N << |all elements|. Avoir un hashCode constant forcerait tous les éléments dans le même compartiment, réduisant toutes les opérations find/contains à exécuter en utilisant uniquement la structure sous-jacente (la per-bucket), qui pourrait être une List ou quelque chose comme ça.

Voir https://en.wikipedia.org/wiki/Hash_table#Choosing_a_hash_function pour l'explication générique. En ce moment Java HashSet est juste soutenu par HashMap (à partir de Javadoc) (https://en.wikipedia.org/wiki/Hash_table#Sets).