Search code examples
data-structuresgraphhashtableadjacency-list

graph - What are the disadvantages if I replace each linked list in adjacency-list with hash table?

In CLRS excise 22.1-8 (I am self learning, not in any universities)

Suppose that instead of a linked list, each array entry Adj[u] is a hash table containing the vertices v for which (u,v) ∈ E. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in the graph? What disadvantages does this scheme have? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table?

So, if I replace each linked list with hash table, there are following questions:

  1. what is the expected time to determine whether an edge is in the graph?
  2. What are the disadvantages?
  3. Suggest an alternate data structure for each edge list that solves these problems
  4. Does your alternative have disadvantages compared to the hash table?

I have the following partial answers:

  1. I think the expected time is O(1), because I just go Hashtable t = Adj[u], then return t.get(v);
  2. I think the disadvantage is that Hashtable will take more spaces then linked list.

For the other two questions, I can't get a clue.

Anyone can give me a clue?

Solution

  • It depends on the hash table and how it handles collisions, for example assume that in our hash table each entry points to a list of elements having the same key.

    If the distribution of elements is sufficiently uniform, the average cost of a lookup depends only on the average number of elements per each list(load factor). so the average number of elements per each list is n/m where m is the size of our hash table.

    1. The expected time to determine whether an edge is in the graph is O(n/m)
    2. more space than linked list and more query time than adjacency matrix. If our hash table supports dynamic resizing then we would need extra time to move the elements between the old and new hash tables and if not we would need O(n) space for each hash table in order to have O(1) query time which results in O(n^2) space. also we have just checked expected query time, and In worst case we may have query time just like linked list(O(degree(u))) so it seems better to use adjacency matrix in order to have deterministic O(1) query time and O(n^2) space.
    3. read above
    4. yes, for example if we know that every vertices of our graph has at most d adjacent vertices and d less than n, then using hash table would need O(nd) space instead of O(n^2) and would have expected O(1) query time.