Czy warto przechowywać dane jako klucze w HashMap przy pustych/pustych wartościach?

Question

Pierwotnie napisałem numer ArrayList i zapisałem w nim unikalne wartości (nazwy użytkowników, tj. Strings). Później musiałem użyć ArrayList, aby wyszukać, czy istnieje w nim użytkownik. To jest O(n) dla wyszukiwania.

Mój szef techniczny chciał, żebym to zmienił na HashMap i zapisał nazwy użytkowników jako klucze w tablicy, a wartości jako puste Strings.

Więc w Javie -

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

mogę sprawdzić, czy użytkownik istnieje później uruchamiając -

hashmap.containsKey("johndoe"); 

To O(1) prawda?

Mój szef powiedział, że był to skuteczniejszy sposób na zrobienie tego i miał dla mnie sens, ale wydawało się, że jest trochę za późno, aby umieścić puste/puste wartości w hashmap i przechowywać w nim elementy jako klucze.

Moje pytanie brzmi, czy to dobre podejście? Efektywność bije na poziomie ArrayList#contains lub ogólnie w poszukiwaniu tablic. To działa. Martwię się, nie widziałem, żeby ktokolwiek inny zrobił to po wyszukiwaniu. Być może brakuje mi jakiegoś oczywistego problemu, ale nie widzę go.

Answer 1

Ponieważ masz zestaw unikatowych wartości, odpowiednią strukturą danych jest Set. Możesz umieścić swoje wartości wewnątrz HashSet, implementacji interfejsu Set.

Moja ołowiu stwierdzono, że był bardziej skuteczny sposób to zrobić i to dla mnie sens, ale to po prostu wydawało się trochę off umieścić/null pusty jako wartości w HashMap i przechowywać elementy w nim jako kluczy.

Porada potencjalnego klienta jest wadliwa. Map nie jest odpowiednią abstrakcją do tego, Set jest. A Map jest odpowiedni dla par klucz-wartość. Ale nie masz wartości, tylko klucze.

Przykład użycia:

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 

Korzystanie z Map byłoby niewygodne, ponieważ to, co powinno być typ wartości? To pytanie nie ma sensu w twoim przypadku użycia, , ponieważ masz tylko klucze, a nie pary klucz-wartość. Dzięki Set nie musisz tego pytać, użycie jest całkowicie naturalne.

To jest O (1) prawda?

tak, szukając w HashMap lub HashSet O (1) zamortyzowane najgorszego przypadku, a wyszukiwanie w List lub tablicę O (n) w najgorszym przypadku.

---

Niektóre komentarze wskazują, że HashSet realizowany jest pod względem HashMap. To dobrze, na tym poziomie abstrakcji. Na poziomie abstrakcji wykonywanego zadania --- do przechowywania kolekcji unikalnych nazw użytkowników, użycie zestawu jest naturalnym wyborem, bardziej naturalnym niż mapa.

Answer 2

Jest to zasadniczo sposób implementacji HashSet, więc można powiedzieć, że to dobre podejście. Równie dobrze możesz użyć HashSet zamiast swoich HashMap z pustymi wartościami.

Na przykład

HashSet „S realizacja add jest

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

gdzie map jest podkład HashMap i PRESENT jest wartością obojętne.

Martwię się, nie widziałem, żeby ktokolwiek inny zrobił to po przeszukaniu. Być może brakuje mi jakiegoś oczywistego problemu, ale nie widzę go.

Jak już wspomniałem, twórcy JDK stosują to samo podejście.