Graph Implementations: why not use hashing?
I'm doing interview prep and reviewing graph implementations. The big ones I keep seeing are adjacency list and adjacency matrices. When we consider the runtime of basic operations, why do I never see data structures with hashing used?
In Java, for instance, an adjacency list is typically ArrayList<LinkedList<Node>>, but why don't people use HashMap<Node, HashSet<Node>>?
Let n = number of nodes and m = number of edges.
In both implementations, removing a node v involves searching through all of the collections and removing v. In the adjacency list, that's O(n^2), but in the "adjacency set", it's O(n). Likewise, removing an edge involves removing node u from v's list and node v from u's list. In the adjacency list , that's O(n), while in the adjacency set, it's O(1). Other operations, such as finding a nodes successors, finding if there exists a path between two nodes, etc. are the same with both implementations. The space complexities are also both O(n + m).
The only downside to the adjacency set I can think of is that adding nodes/edges is amortized O(1), while doing so in the adjacency list is truly O(1).
Perhaps I'm not seeing something or I forgot to consider things when calculating the runtimes, so please let me know.
Answer
In the same vein of thought as DavidEisenstat's answer, graph implementations vary a lot. That's one of the things that doesn't come across well in lecture. There are two conceptual designs:
1) Adjacency list
2) Adjacency matrix
But you can easily augment either design to gain properties like faster insertion/removal/searches. The price is often just storing extra data! Consider implementing a relatively simple graph algorithm (like... Euler's) and see how your graph implementation causes huge effects on the run-time complexity.
To make my point a bit clearer, I'm saying that an "adjacency list" doesn't really require you to use a LinkedList. For instance, wiki cites this on their page:
An implementation suggested by Guido van Rossum uses a hash table to associate each vertex in a graph with an array of adjacent vertices. In this representation, a vertex may be represented by any hashable object. There is no explicit representation of edges as objects.