java - 将 HashMap 用于节点和图数据结构

Question

我从未见过任何教科书将 HashMap 用于 Node 或 Graph 类。

这是我对 Node 和 Graph 类的实现。它们对于所有主要操作(例如检查节点、检查邻居、获取两个节点之间的距离等)的时间复杂度是否为 O(1)？

//T as the type of the content in each node
//D as the type of the distance between the nodes
class Node<T,D>{
    private T content;
    private HashMap<T,D> neighbors;
    private boolean marked;

    //an example method
    protected boolean hasNeighbor(T t){
        return this.neighbors.containsKey(t);
    }

    //another example method
    protected D distanceTo(T t){
        return this.neighbors.get(t);
    }

    //this class also overrides equals() and hashCode() methods so that every two nodes
    //equal to each other if and only if their content equal to each other
}

另外，这是我对 Graph 类的想法

public class Graph<T,D>{
    private HashMap<T, Node<T,D>> nodes;

    //an example method
    public D distanceBetween(T a, T b){
        return this.nodes.get(a).distanceTo(b);
    }
}

所以，一切都可以在恒定的时间内完成，对吧？如果是这样，为什么我们看不到任何使用这种实现的教科书？

Answer 1

HashMap 的最坏情况查找时间是O(n)，但是，如果您没有提供良好的哈希码，则可以认为 HashMap 具有渐近常数查找时间。

我认为你的图实现很好(我不确定它在语义上是否正确，但原则上我不明白为什么当你有键/值绑定(bind)时不能使用 HashMap 实现它)。为了回答你的主要问题，我认为，在计算机科学的教科书中，抽象比实际实现更重要。Java 中的 HashMap 实现对哈希码/相等契约有特定的假设，我认为大多数教科书都试图避免此类细节。