Получить наименьший доступный ключ (> = 1) в HashMap

Question

Я использую карту, в которой я сохраняю все треки, которые регистрирует пользователь. Каждой новой дорожке должен быть присвоен новый идентификатор, который начинается с 1. Однако, если дорожки 1, 2, 3, 4 существуют, и пользователь удаляет дорожку с идентификатором 1, следующая добавленная дорожка получает наименьший доступный идентификатор> = 1, что в этом случае будет 1.

Как это можно сделать эффективно? Или есть лучший тип данных?

private Map<Integer, Track> tracks;

public Register() {
    this.trains = new HashMap<>();
}

public void addTrack(Track track) {
    int id = <get Smallest Value Available >= 1>;
    this.tracks.put(id, track);
}

public void removeTrack(int id) {
    if (tracks.containsKey(id)) {
        this.tracks.remove(id);
    } else {
        Terminal.printError("track with ID " + id + " doesn't exist.");
    }
}

Answer 1

Подход 1: Вы можете использовать TreeMap и перебирать его ключи, и, если между двумя ключами есть пробел, вы можете вставить свой элемент в этот пробел. Добавление будет работать в O(currentKeysCount) наихудшем случае, удаление будет работать в O(log(currentKeysCount)).

private TreeMap<Integer, Track> tracks;

public Register() {
    this.trains = new TreeMap<>();
}

public void addTrack(Track track) {
    int id = 1;
    for (int key : this.trains.keySet) {
        if (key > id) break;
        id = key + 1;
    }
    this.tracks.put(id, track);
}

public void removeTrack(int id) {
    if (tracks.containsKey(id)) {
        this.tracks.remove(id);
    } else {
        Terminal.printError("track with ID " + track.getId() + " doesn't exist.");
    }
}

Подход 2: Вы можете создать PriorityQueue, в котором будут храниться удаленные ключи. Добавление и удаление будут работать в O(log(currentKeysCount) + log(deletedKeysCount)).

private Map<Integer, Track> tracks;
private PriorityQueue<Integer> deletedKeys;
private int nextKey;

public Register() {
    this.trains = new HashMap<>();
    this.deletedKeys = new PriorityQueue<>();
    this.nextKey = 0;
}

public void addTrack(Track track) {
    int id = nextKey;
    if (!deletedKeys.isEmpty()) id = deletedKeys.poll();
    this.tracks.put(id, track);
}

public void removeTrack(int id) {
    if (tracks.containsKey(id)) {
        this.tracks.remove(id);
        this.deletedKeys.add(id);
    } else {
        Terminal.printError("track with ID " + track.getId() + " doesn't exist.");
    }
}

Подход 3: Может быть намного проще игнорировать отсутствующие ключи и просто увеличивать счетчик nextKey при каждом добавлении (вы можете даже используйте long вместо int). Если вы не добавляете новый ключ чаще, чем один раз в миллисекунду, ваша программа не выйдет из строя раньше, чем весь код, который использует System.currentTimeMillis() (и он потерпит неудачу в течение более 292 миллионов лет). Добавление и удаление будет работать в O(log(currentKeysCount))

Answer 2

Я бы сделал это с помощью al oop и увидел бы, какое значение еще не включено в карту

public Integer getId(Map<Integer, Track> tracks) {
    // Set on max-value
    Integer id = Collections.max(tracks.keySet()) + 1;

    for (int i = 1; i <= tracks.keySet().size(); i++) {
        if (!tracks.keySet().contains(i)) {
            // lower value available
            id = i;
            break;
        }
    }

    return id;
}

Answer 3

Скажите, если из 100 поездов номер 40 и номер 60 свободны, вы хотите получить 40 из {40, 60}.

private final Map<Integer, Track> tracks = new HashMap<>();;
private final SortedSet<Integer> freeIds = new TreeSet<>();

public synchronized void addTrack(Track track) {
    int id;
    if (freeIds.isEmpty()) {
        id = 1 + tracks.size(); // Numbering from 1
    } else {
        id = freeIds.first();
        freeIds.remove(id);
    }
    track.setId(id);
    tracks.put(id, track);
}

public synchronized void removeTrack(int id) {
    Track track = tracks.remove(id);
    if (track != null) {
        track.setId(-1);
        freeIds.add(id);
    } else {
        Terminal.printError("track with ID " + track.getId() + " doesn't exist.");
    }
}

Answer 4

Наиболее эффективным способом будет использование SortedMap , так как вам не нужно будет искать наименьший доступный ключ. Наименьший доступный ключ всегда будет находиться в начале Map. Вы можете использовать SortedMap :: firstKey , чтобы получить самый маленький ключ.