每次添加新曲目时递增计数器，并且始终 select 尚未分配的最小值 (>=1)

Question

我目前正在做一个火车模拟项目，我有一个列表，其中保存了所有轨道：

    private List<Track> tracks;

    public void addTrack(Track track) {
        this.tracks.add(track);
    }

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

我想在添加时为每个曲目分配一个 ID（从 1 开始）。此外，总是选择下一个空闲 ID。例如，如果分配了 ID 1、3、4、5，则使用下一个 ID 2。

E. g.:

添加曲目... -> ID: 1

添加曲目... -> ID: 2

删除曲目 1

添加曲目... -> ID: 1

我会使用地图，每次添加新轨道时，计数器都会加一。但是，如果我删除一个 ID 并添加一个新曲目，将会有 "gaps"。

执行此操作的好方法是什么？

Answer 1

一种方法是在另一个数据结构（可能是 BitSet）中跟踪每个分配的 ID，尤其是 BitSet#nextClearBit(int) 方法

因此，每次将内容放入 List<Tracks> 时，您都会在 BitSet 中设置相对索引，并在删除 Track 时删除。

类似下面的内容

BitSet b = new BitSet();
// set the bits while adding tracks
b.set(0);
b.set(1);
b.set(2);

b.clear(1); // some track gets removed, so unset the bit
System.out.println(b); // {0, 2}

System.out.println(b.nextClearBit(0)); // 1

Answer 2

就像 Saif Asif 在他的回答中提到的那样，您可以使用另一种数据结构来跟踪 ID。

BitSet 是一种方法，另一种方法是使用 TreeSet 跟踪您分配和撤销的 ID，这将为您保持 ID 的顺序

例如

public class IdTracker {

    private TreeSet<Long> available;
    private TreeSet<Long> current;

    public IdTracker() {
        this.available = new TreeSet<Long>();
        this.current = new TreeSet<Long>();
    }

    public long getNextId() {
        //Check to see if this is the first time being called, setting initial id to 1
        if (available.isEmpty() && current.isEmpty()) {
            current.add(1L);
            return 1L;
        }

        //Check to see if we have any available values to use
        if (!available.isEmpty()) {
            //Remove from available and assign to current
            Long availableId = available.first();
            available.remove(availableId);
            current.add(availableId);
            return availableId;
        }

        //There are no available id's, get the highest current id and increment
        Long highestCurrentId = current.last();
        Long nextId = highestCurrentId + 1;
        current.add(nextId);
        return nextId;
    }

    public void removeId(long id) {
        //Remove from the current (if there) and place into available
        if (current.remove(id)) {
            available.add(id);
        } else {
            //Handle your failure case
        }
    }
}

所以在你的例子中你会做

private List<Track> tracks;
private IdTracker idTracker;

public void addTrack(Track track) {
    long id = idTracker.getNextId();
    track.setId(id);
    this.tracks.add(track);
}

public void removeTrack(Track track) {
    if (tracks.contains(track)) {
        this.tracks.remove(track);
        this.idTracker.removeId(track.getId());
    } else {
        Terminal.printError("track with id " + track.getId() + " doesn't exist.");
        }
    }

每次添加新曲目时递增计数器，并且始终 select 尚未分配的最小值 (>=1)

Increment counter each time a new track is added and always select the smallest value (>=1) that is not already assigned

java

dictionary

increment