Использование HashMap для структур данных Node & Graph

Question

Я никогда не видел учебника, использующего классы HashMap для классов 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 
} 

также, вот моя идея о классе графов

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), если вы не предоставили хороший хэш-код, однако вы можете считать, что хэш-карты имеют асимптотическое постоянное время поиска.

Я думаю, что ваша реализация графика в порядке (я не уверен, что она семантически корректна, но в принципе я не понимаю, почему она не может быть реализована с использованием Hashmaps, когда у вас есть привязки клавиш/значений). Чтобы ответить на ваш основной вопрос, я думаю, в учебнике по компьютерной науке абстракция важнее фактической реализации. В реализации HashMap на Java есть определенные предположения о контрактах hashcode/равенства, и я думаю, что большинство учебников пытаются избежать таких деталей.

Answer 2

Получение расстояния от одного узла до его непосредственных соседей редко является проблемой в алгоритмах на графиках. Рассмотрим, например, алгоритм Дейкстры для кратчайшего пути между A и некоторым другим узлом (не обязательно соседом) Z. Алгоритм исходит из текущего узла (изначально A) ко всем соседям, которые еще не были посещены. Любой контейнер, который может быть (быстро) повторен, будет делать; Карта (Хеш) даже для этого не является первым выбором.

Кроме того, HashMaps, как правило, потребляют больше места, чем требуется для данных istself. Умножается на большое количество узлов, что может быть проблемой (или, по крайней мере, может быть).

И, наконец, если число соседей в среднем довольно мало (~ 10), даже немой последовательный поиск списка даст вам сосед на основе его содержимого. Более того, поскольку графики часто стабильны, даже большие числа могут эффективно обрабатываться путем сортировки и двоичного поиска.

И учебник предполагает, что читатели знают о структурах данных и могут выбирать импликацию в соответствии с их конкретными потребностями. Как отметил Али, абстракция важнее, чем реализация хаков.