在Java中，有什么好的数据结构可以用来解决这个问题？

Question

因此，我有以下问题：

我希望有某种数据存储存储某种类型的宇宙飞船(宇宙飞船ID)。每艘宇宙飞船都有一个名字。

情景1

一种特殊类型的宇宙飞船只能在数据存储中存储一次。因此，如果用户试图存储以下内容，名称1:宇宙飞船类型1和名称2:宇宙飞船类型1只会存储在数据结构中的宇宙飞船类型1的实例。

情景2

如果用户输入名称1:宇宙飞船类型1，然后输入名称1:宇宙飞船类型2，则数据结构只应存储名称1:宇宙飞船类型2。这意味着，宇宙飞船类型1已被2型宇宙飞船取代，因为它们的名称相同。

我最初处理这个问题的方法是使用散列图，我会散列宇宙飞船id，这样如果两个飞船ID是相同的，我将只在散列图中存储一次宇宙飞船ID，作为值，我将有一个映射到同一个宇宙飞船ID的名称数组。这解决了情况1。

情况2更有问题。哈希映射可能相当大，我认为迭代每个桶中的每个数组是效率低下的，以便确定是否已经使用了名称，以便从散列图中删除名称，并可能删除宇宙飞船ID，并添加一个带有新的宇宙飞船ID及其相应名称的条目。

在这种情况下，最好使用散列映射，还是可以使用另一种数据结构来解决这两种情况。也许我得自己创造一个。任何指向正确方向的指针都是有帮助的。

Answer 1

您可以使用两个映射实现自己的类，如下所示：

public final class Spaceship {
    private final int    id;
    private final String name;
    public Spaceship(int id, String name) {
        this.id = id;
        this.name = name;
    }
    public int getId() {
        return this.id;
    }
    public String getName() {
        return this.name;
    }
    @Override
    public String toString() {
        return this.id + ":" + this.name;
    }
}

public final class Spacedock {
    private Map<Integer, Spaceship> byId   = new HashMap<>();
    private Map<String, Spaceship>  byName = new TreeMap<>(); // so getSpaceships() lists ordered by name
    public boolean containsSpaceship(Spaceship spaceship) {
        Spaceship shipInDock = this.byId.get(spaceship.getId());
        return (shipInDock != null && shipInDock.getName().equals(spaceship.getName()));
    }
    public void addSpaceship(Spaceship spaceship) {
        if (! containsSpaceship(spaceship)) {
            Spaceship prevShip = this.byId.put(spaceship.getId(), spaceship);
            if (prevShip != null)
                this.byName.remove(prevShip.getName());
            prevShip = this.byName.put(spaceship.getName(), spaceship);
            if (prevShip != null)
                this.byId.remove(prevShip.getId());
        }
    }
    public void removeSpaceship(Spaceship spaceship) {
        if (containsSpaceship(spaceship)) {
            this.byId.remove(spaceship.getId());
            this.byName.remove(spaceship.getName());
        }
    }
    public Collection<Spaceship> getSpaceships() {
        return this.byName.values();
    }
    public Spaceship getById(int id) {
        return this.byId.get(id);
    }
    public Spaceship getName(String name) {
        return this.byName.get(name);
    }
    @Override
    public String toString() {
        return this.byName.values().toString();
    }
}

测试

Spacedock spacedock = new Spacedock();
spacedock.addSpaceship(new Spaceship(1, "Name1"));
System.out.println(spacedock);
spacedock.addSpaceship(new Spaceship(2, "Name2"));
System.out.println(spacedock);
spacedock.addSpaceship(new Spaceship(1, "Name2"));
System.out.println(spacedock);
spacedock.addSpaceship(new Spaceship(2, "Name2"));
System.out.println(spacedock);
spacedock.addSpaceship(new Spaceship(2, "Name1"));
System.out.println(spacedock);

输出

[1:Name1]
[1:Name1, 2:Name2]
[1:Name2]
[2:Name2]
[2:Name1]

正如您所看到的，不同的宇宙飞船被存储，通过添加一个新的船的id或名称已经存在将删除现有的船(S)。

如果您使用的是Java8，并且不喜欢空值，请使用新的Optional

public Optional<Spaceship> getById(int id) {
    return Optional.ofNullable(this.byId.get(id));
}
public Optional<Spaceship> getName(String name) {
    return Optional.ofNullable(this.byName.get(name));
}

Answer 2

一个单独的地图将是理想的，但如果您决心绕过任何第三方库(我不同意这个决定，除非目的是学习如何创建您自己的Map)，那么最简单的方法是如果您有两个Maps。

Map<String, String> typeToName; //if you could have multiple of the Value, it could be Set<String>
Map<String, String> nameToType;

//put "Type1", "DoubleDouble's Destroyer" in typeToName
//put "DoubleDouble's Destroyer", "Type1" in nameToType

如果要添加一个"Type1", "DistractionBoat"，首先要查看typeToName中是否有"Type1"，然后从nameToType中删除相应的名称。

然后进行反向操作，检查nameToType中是否存在nameToType，并从typeToName中删除任何相应的type

然后加上你的新宇宙飞船，它将取代任何相同的type或name的宇宙飞船。

在此基础上可能会有许多改进(最明显的是使其更通用和自己的类)。事实上，你为了速度牺牲了记忆。