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

Question

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?

Answer 1

The answer to question 3 could be a binary search tree.

In an adjacency matrix, each vertex is followed by an array of V elements. This O(V)-space cost leads to fast (O(1)-time) searching of edges.

In an adjacency list, each vertex is followed by a list, which contains only the n adjacent vertices. This space-efficient way leads to slow searching (O(n)).

A hash table is a compromise between the array and the list. It uses less space than V, but requires the handle of collisions in searching.

A binary search tree is another compromise -- the space cost is minimum as that of lists, and the average time cost in searching is O(lg n).