Graph adjacency using Hashing
With hash the space needed is $\mathcal O(|E| + |V|)$ (depending on array size given), and the time is expected $\mathcal O(1)$, but might degrade to $\mathcal O(|V|)$ (depending on collision resolving scheme).
With minimal perfect hash the space is exactly $|E| + |V|$ of entries (of appriopriate entry size).

Minimal perfect hash will map without collisions the given set - array for $n$ elements will have exactly $n$ length, so the $|E|$ edges will occupy exactly $|E|$ array elements. Defined function $h$ will disregarding the number of entries, as opposed to normal hash which might be several times bigger than number of entries and collisions degrade the query time (as linked-list).

This is very efficient scheme for static graph, in case of dynamic one the same issue of rehashing holds. It does not matter how the nodes are encoded (string, int etc.).

How MPH works.