在 Java 中，针对此问题使用什么数据结构比较好？

Question

所以我遇到了以下问题：

我想要某种类型的数据存储来存储一种类型的飞船（飞船 ID）。每艘飞船都有一个名字。

情况一

特定类型的宇宙飞船只能在数据存储中存储一次。因此，如果用户尝试存储以下内容，name 1 : spaceship type 1 和 name 2 : spaceship type 1 只有 1 个 spaceship type 1 实例将存储在数据结构中。

情况二

如果用户输入 name 1 : spaceship type 1 然后输入 name 1 : spaceship type 2，那么数据结构应该只存储 name 1 : spaceship type 2。这意味着 spaceship type 1 已经被 spaceship type 取代2 因为他们有相同的名字。

我最初解决这个问题的方法是使用哈希映射，我会对飞船 ID 进行哈希处理，这样如果两个飞船 ID 相同，我将在哈希映射中仅存储一次飞船 ID，并将其作为值我会有一个映射到同一个飞船 ID 的名称数组。解决了情况 1.

情况2问题更大。哈希映射可能非常大，我认为迭代每个存储桶中的每个数组以确定是否已使用某个名称以便从哈希映射中删除该名称和可能的太空飞船 ID 并添加一个条目是低效的使用新的飞船 ID 及其对应的名称。

在这种情况下最好使用散列映射吗，或者是否有其他数据结构可以用来解决这两种情况。也许我必须自己创建一个。任何指向正确方向的指示都会有所帮助。

Answer 1

一个单独的地图是理想的，但如果你决定绕过任何第 3 方库（我不同意这个决定，除非目的是学习如何创建你自己的 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中是否有"DistractionBoat"，并从typeToName

中删除任何对应的type

然后添加你的新飞船，它将替换任何相同type或name.

的任何飞船

在此基础上可能还有很多改进（最明显的是让它更通用并拥有自己的 class）。事实上，你为了速度牺牲了内存。

Answer 2

您可以使用两个地图实现自己的 class，如下所示：

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 或名称已存在的新飞船将删除现有飞船。

如果您使用 Java 8 并且不喜欢空值，请使用新的 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));
}

在 Java 中，针对此问题使用什么数据结构比较好？

What's a good data structure to use for this issue in Java?

java

hash

dictionary

structure

我想要某种类型的数据存储来存储一种类型的飞船（飞船 ID）。每艘飞船都有一个名字。