获取哈希图中的最小可用键 (>= 1)

Question

我正在使用一个地图，我在其中保存用户注册的所有曲目。应为每个新轨道分配一个新 ID，该 ID 从 1 开始。但是，如果轨道 1、2、3、4 存在，并且用户删除了 ID 为 1 的轨道，则下一个添加的轨道将获得最小的可用 ID>=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()的代码更早失败(并且它将在超过 2.92 亿年后失败(。添加和删除将在O(log(currentKeysCount))

Answer 2

我会用循环来做，看看哪个值是否尚未包含在地图中

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， 60} 获得 40 列。

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