Est-ce une bonne idée de stocker des données sous forme de clés dans HashMap avec des valeurs vide / nulle?

Question

J'avais écrit à l'origine d'un ArrayList et stockées des valeurs uniques (noms d'utilisateur, c'est à dire Strings). Plus tard, j'ai besoin d'utiliser l' ArrayList pour rechercher si un utilisateur existe. C'est O(n) pour la recherche.

Mon tech responsable voulu me le changer pour un HashMap et de stocker les noms d'utilisateur comme clés dans le tableau et les valeurs vides Strings.

Donc, en Java

hashmap.put("johndoe","");

Je peux voir si cet utilisateur n'existe plus tard en cours d'exécution -

hashmap.containsKey("johndoe"); 

C'est - O(1) droit?

Mon chef a dit que c'était un moyen plus efficace de le faire et il fait sens pour moi, mais il me semblait un peu hors de mettre null/vide comme des valeurs dans la table de hachage et de stocker des éléments clés.

Ma question est, est-ce une bonne approche? L'efficacité beats ArrayList#contains ou un tableau de recherche en général. Elle fonctionne. Mon souci est que je n'ai pas vu quelqu'un d'autre le faire après une recherche. J'ai peut-être manquant un évident problème quelque part, mais je ne peux pas le voir.

Answer 1

Puisque vous avez un ensemble de valeurs uniques, Set est la structure de données. Vous pouvez mettre vos valeurs à l'intérieur d' HashSet, une mise en œuvre de l' Set interface.

Mon chef a dit que c'était un moyen plus efficace de le faire et il fait sens pour moi, mais il me semblait un peu hors de mettre null/vide comme des valeurs dans la table de hachage et de stocker des éléments clés.

Les conseils de la sonde est défectueuse. Map n'est pas le droit d'abstraction pour cela, Set . Un Map est approprié pour les paires clé-valeur. Mais vous n'avez pas les valeurs, les seules touches.

Exemple d'utilisation:

Set<String> users = new HashSet<>(Arrays.asList("Alice", "Bob"));

System.out.println(users.contains("Alice"));
// -> prints true

System.out.println(users.contains("Jack"));
// -> prints false

À l'aide d'un Map serait maladroit, parce que ce qui devrait être le type des valeurs? Cette question n'a aucun sens dans votre cas d'utilisation, comme vous venez de touches, pas de paires clé-valeur. Avec un Set, vous n'avez pas besoin de demander que l'utilisation est parfaitement naturel.

Ce est O(1) droit?

Oui, la recherche dans une HashMap ou HashSet O(1) amorti pire des cas, tandis que la recherche dans une List ou un tableau est O(n) le pire des cas.

---

Certains commentaires soulignent qu'un HashSet est mis en œuvre en termes de HashMap. C'est très bien, à ce niveau d'abstraction. Au niveau d'abstraction de la tâche à accomplir --- pour stocker une collection unique de noms d'utilisateur, à l'aide d'un ensemble est un choix naturel, plus naturel qu'une carte.

Answer 2

C'est fondamentalement la façon dont HashSet est mis en place, donc je suppose que vous pouvez dire que c'est une bonne approche. Vous pourriez tout aussi bien utiliser des HashSet au lieu de votre HashMap avec des valeurs vides.

Par exemple :

HashSet's la mise en œuvre de l' add est

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

où map est le soutien HashMap et PRESENT est une valeur factice.

Mon souci est que je n'ai pas vu quelqu'un d'autre le faire après une recherche. J'ai peut-être manquant un évident problème quelque part, mais je ne peux pas le voir.

Comme je l'ai mentionné, les développeurs du JDK sont en utilisant la même approche.