Complexité temporelle de la vérification si une chaîne de caractères est présente dans un HashSet Java

Question

En résumé, je suis confus sur le fait que la complexité temporelle de vérifier si une chaîne existe dans un HashSet est O(1) ou O(m), m étant la longueur de la plus longue chaîne vérifiée.

Je comprends que le compartiment dans lequel la chaîne va être placée est déterminé par la méthode hashCode() de la chaîne modulo la taille du HashSet. Cela signifie donc que pour savoir si une chaîne existe dans un HashSet, le hashCode doit être calculé.

Dans la méthode hashCode de la classe String, je vois que vous devez itérer sur toute la chaîne pour calculer cette valeur. Mais je vois aussi qu'il y a une option de mise en cache de cette valeur.

C'est là que je suis confus. Le hashCode d'une chaîne est-il mis en cache lors de la création d'une chaîne? Ou est-il mis en cache lorsque nous appelons explicitement la méthode hashcode? L'appel implicite à la méthode hashCode (comme dans le cas de la vérification de l'existence d'une chaîne dans un ensemble) met-il également en cache la valeur?

Quelle serait la complexité temporelle de la toute première vérification d'existence d'une chaîne dans HashSet?

Merci.

EDIT : Puisqu'il semble que je n'ai pas expliqué clairement ce que je demande : Je ne parle pas de la complexité temporelle si un chaînage se produit (ce qui se produirait en cas de collisions de hachage) / ou lorsque le Hash Set est redimensionné. Supposons pour l'instant qu'il n'y a pas de collisions dans le Hash Set. Par conséquent, la taille de chaque compartiment est au maximum de 1. Dans ce cas, si je vérifie si une chaîne est présente dans le Hash Set, cela prendra-t-il du temps O(1) ou O(m) (car la chaîne peut avoir O(m) caractères dans le pire des cas et le calcul du code de hachage requiert le parcours de toute la chaîne)?

Answer 1

Si la chaîne que vous vérifiez est une nouvelle chaîne, son code de hachage doit être calculé pour trouver son bucket, ce qui serait O(m) pour le calcul du code de hachage et O(1) pour la vérification de l'existence, donc O(m).

Si l'objet String existe déjà dans l'ensemble (ou si son code de hachage a été calculé autrement), sa vérification est en O(1), car son code de hachage est mis en cache.

Answer 2

Le temps nécessaire pour calculer un hashCode donné dépend de l'algorithme et de savoir s'il doit être calculé à chaque appel. Un Integer ne nécessite aucun calcul car le hashCode est la valeur int. Une chaîne de caractères serait O(n) où n est le nombre de caractères.

Voici l'algorithme de hashCode pour les chaînes Latin1.

public static int hashCode(byte[] value) {
        int h = 0;
        for (byte v : value) {
            h = 31 * h + (v & 0xff);
        }
        return h;
    }

Cependant, le hashCode pour une chaîne de caractères n'est calculé qu'une seule fois car la chaîne est immuable. Ainsi, les appels à hashCode sur une chaîne de caractères renverraient la valeur mise en cache.