Ist es eine gute Idee, Daten als Schlüssel in HashMap mit leeren/Null-Werten zu speichern?

Question

Ich hatte ursprünglich eine ArrayList geschrieben und eindeutige Werte (Benutzernamen, d. H. Strings) darin gespeichert. Ich brauchte später die ArrayList, um zu suchen, ob ein Benutzer darin existierte. Das ist O(n) für die Suche.

Mein technischer Leiter wollte, dass ich das zu einem HashMap ändere und die Benutzernamen als Schlüssel im Array und Werte als leer Strings speichern.

also in Java -

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

ich sehen kann, wenn dieser Benutzer später existiert, indem Sie -

hashmap.containsKey("johndoe"); 

Dies ist O(1) richtig?

Meine Führung sagte, dies sei ein effizienter Weg, dies zu tun und es ergab Sinn für mich, aber es schien nur ein wenig aus, leer/leer als Werte in der Hashmap und speichern Elemente in ihm als Schlüssel.

Meine Frage ist, ist das ein guter Ansatz? Die Effizienz schlägt ArrayList#contains oder eine Array-Suche im Allgemeinen. Es klappt. Meine Sorge ist, ich habe niemanden gesehen, der das nach einer Suche macht. Ich vermisse vielleicht ein offensichtliches Problem, aber ich kann es nicht sehen.

Answer 1

Da Sie eine Reihe von eindeutigen Werten haben, ist eine Set die geeignete Datenstruktur. Sie können Ihre Werte in HashSet, eine Implementierung der Set Schnittstelle setzen.

Meine Führung sagte, dies eine effizientere Art und Weise ist, dies zu tun, und es machte Sinn für mich, aber es schien nur ein bisschen in dem hashmap und Speicherelementen darin null/leer als Wert als Schlüssel beiseite zu legen.

Der Rat der Leitung ist fehlerhaft. Map ist nicht die richtige Abstraktion dafür, Set ist. A Map ist für Schlüssel-Wert-Paare geeignet. Aber du hast keine Werte, nur Schlüssel.

Beispiel Nutzung:

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 

ein Map Verwendung wäre umständlich, weil das, was die Art des Wertes sein sollte? Diese Frage ergibt in Ihrem Anwendungsfall keinen Sinn, da Sie nur Schlüssel und keine Schlüssel/Wert-Paare haben. Mit einem Set müssen Sie nicht fragen, die Verwendung ist vollkommen natürlich.

Das ist O (1) richtig?

Ja, in einem HashMap oder einem HashSet suchen ist O (1) worst case amortisieren, während sie in einem List Suche oder ein Array ist O (n) im ungünstigsten Fall.

---

Einige Kommentare weisen darauf hin, dass ein HashSet in Bezug auf HashMap umgesetzt wird. Das ist in Ordnung, auf dieser Ebene der Abstraktion. Auf der Ebene der Abstraktion der Aufgabe zur Hand --- zum Speichern einer Sammlung von eindeutigen Benutzernamen, mit einem Satz ist eine natürliche Wahl, natürlicher als eine Karte.

Answer 2

Dies ist im Grunde, wie HashSet implementiert ist, so denke ich, können Sie sagen, es ist ein guter Ansatz. Sie können auch HashSet anstelle Ihrer HashMap mit leeren Werten verwenden.

Zum Beispiel:

HashSet ‚s Umsetzung add ist

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

wo map werden die Träger HashMap und PRESENT ist ein Dummy-Wert.

Meine Sorge ist, ich habe niemanden gesehen, der dies nach einer Suche tut. Ich vermisse vielleicht ein offensichtliches Problem, aber ich kann es nicht sehen.

Wie bereits erwähnt, verwenden die Entwickler des JDK denselben Ansatz.