Структура данных для хранения только ключей (не заботясь о значении)

Question

Мне нужно сохранить список строк и нужно проверить, существует ли строка в списке.

Обычно я просто использовал бы некоторую Карту с ключом и логическое значение ... то есть

HashMap map<String,Boolean> = new HashMap<String,Boolean)()

И просто сделай map.contains(string)

Так я всегда делал подобные поиски в прошлом, потому что я знаю, что использование карты будет иметь O (1) доступ.

Я знаю, что это может быть придирчиво и неважно, но мне было просто любопытно, была ли какая-то структура, которая могла бы сохранить это логическое значение. Это просто пустая трата памяти, потому что меня не волнует ложное значение, потому что, если ключ не существует, это равняется ложному.

Я думал, что, возможно, указание ключевого слова на null будет делать то, что я хочу, но мне было интересно, существует ли какая-то структура данных, которая бы это делала.

Answer 1

Для этого предназначена коллекция Set<T>.Реализация HashSet<T> - это O (1), и внутри она делает именно то, что вы предлагаете: это HashMap<T,V>, где значение для каждого ключа - это один и тот же внутренний экземпляр Object.То есть источник содержит

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

, а значение каждой записи установлено на PRESENT.

Answer 2

Может быть HashSet<E>?

Или, на самом деле, все, что реализует Set<E>, хотя не у всех есть ожидаемый O (1) поиск.

Answer 3

Вы должны использовать HashSet<E> - «структура данных для хранения только ключей (не заботясь о значении)». Его реализация основана на HashMap<K,V>, где каждый элемент является значением, а ключи - это просто Object, именно то, что вам нужно.

public class HashSet<E> ... {
    ...
    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<E,Object>();
    }
    ...

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

    ...
}

Answer 4

Почему бы не использовать обычный ArrayList<String>, у него есть метод содержимого и все остальное ...

Answer 5

HashSet (или) Реализация интерфейса Someother Set может предоставить вам необходимую функциональность.