Get smallest available key (>= 1) in a HashMap

Question

I am using a Map in which I save all tracks that the user registers. Every new track should be assigned a new ID which starts at 1. However, if tracks 1, 2, 3, 4 exist and the user deletes track with ID 1 the next added track gets the smallest available ID >=1 which in this case would be 1.

How is it possible to do this efficiently? Or is there a better datatype available?

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.");
    }
}

This solution looks for me: https://stackoverflow.com/questions/18345131/fastest-way-to-determine-the-lowest-available-key-in-java-hashmap — Oliver Wespi, Feb 14 '20 at 12:11
I don't need the smallest saved value. I want to prevent gaps when deleting a track. E. g. tracks 1, 2, 3 exist. The user deletes track 2. Then he adds another track that gets ID 2 — , Feb 14 '20 at 12:15
You will get unpopular fast if you first post, then within 7 minutes answer and then shortly after delete (for another Q/A). — Maarten Bodewes, Feb 14 '20 at 15:53

ardenit · Accepted Answer · 2020-02-14T12:38:40.493

Approach 1: You can use TreeMap and iterate through its keys, and if there is a gap between two keys, you can insert your element in this gap. Addition will work in O(currentKeysCount) worst-case, deletion will work in 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.");
    }
}

Approach 2: You can create a PriorityQueue that will store deleted keys. Addition and deletion will work in 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.");
    }
}

Approach 3: It may be much easier to ignore missing keys and just increase nextKey counter on every addition (you can even use long instead of int). Unless you add a new key more often than once per millisecond, your program won't fail earlier than all code that uses System.currentTimeMillis() (and it will fail in more than 292 million years). Addition and deletion will work in O(log(currentKeysCount))

tgallei · Answer 2 · 2020-02-14T12:20:56.607

1

I would do it with a loop and see if the which value is not yet included in the map

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;
}

edited Feb 14 '20 at 12:20

answered Feb 14 '20 at 12:13

tgallei

827
3
13
22

I don't need the smallest saved value. I want to prevent gaps when deleting a track. E. g. tracks 1, 2, 3 exist. The user deletes track 2. Then he adds another track that gets ID 2 – Feb 14 '20 at 12:17
@LudwigvonDrake Yes, i know. First you remove the track from the map and then you call the "getId" method, which determines the current lowest Id. – tgallei Feb 14 '20 at 12:22

score 0 · Answer 3 · answered Feb 14 '20 at 12:23

Say if from 100 trains number 40 and number 60 are free, you want to get 40 from {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.");
    }
}

Get smallest available key (>= 1) in a HashMap

3 Answers3