title: graph - What are the disadvantages if I replace each linked list in adjacency-list with hash table?
body: <p>In CLRS excise 22.1-8 (I am self learning, not in any universities)</p>
  
  <blockquote>
    <p>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?</p>
  </blockquote>
  
  <p>So, if I replace each linked list with hash table, there are following questions:</p>
  
  <ol>
  <li>what is the expected time to determine whether an edge is in the graph?</li>
  <li>What are the disadvantages?</li>
  <li>Suggest an alternate data structure for each edge list that solves these problems</li>
  <li>Does your alternative have disadvantages compared to the hash table?</li>
  </ol>
  
  <p>I have the following partial answers:</p>
  
  <ol>
  <li>I think the expected time is O(1), because I just go Hashtable t = Adj[u], then return t.get(v);</li>
  <li>I think the disadvantage is that Hashtable will take more spaces then linked list.</li>
  </ol>
  
  <p>For the other two questions, I can't get a clue. </p>
  
  <p>Anyone can give me a clue?</p>