Complex/Hybrid data structures- do people ever combine structures like graphs and hash tables together?

Question

I just built a LRU cache that combines a hash table and a double linked list. To me it was a brilliant idea to combine those two structures and use the strengths of each together, so it got me thinking, can people or do people combine hash tables with other more complex data structures like trees and graphs? Are there use cases and what would they be called? I don't see much written about these on the usual sites like Wikipedia.

Obviously the hash table gives constant lookup time (or nearly so allowing for collision resolution), and the tree or graph gives you ways and means of doing traversals.

I know you can hang a new tree's parent node from every single hash entry but I mean having one tree main tree or graph overlayed and interconnected with one main hash table

Answer 1

I am convinced that in many practical cases such hybrid data structures are key to effectiveness, so I like your question pretty much!

There are many examples, and I would like to detail one that makes a true difference both in practice and in theory.

First, a bit of context. There are two main data structures for representing graphs: adjacency lists, where we have the list of neighbors for each vertex; and adjacency matrices, where we have a double-entry array in which cell $i,j$ tells if there is an edge between vertices $i$ and $j$.

Let us consider a graph $G$ with $n$ vertices and $m$ edges. In practice, $m$ is generally much lower than its maximal value $\frac{n\cdot (n-1)}{2} \sim n^2$. This makes adjacency lists appealing, because they need only $O(m)$ space, whereas adjacency matrices need $O(n^2)$ space. However, one cannot query edge existence in constant time in an adjacency list representation, whereas one can do this in an adjacency matrix. This is why the two approaches coexist in the wide world of graph algorithms, with some relying on adjacency lists, and some on adjacency matrices.

In some cases, though, it is possible to take advantage of the best of the two worlds. This is particularly true when one considers large graphs with heterogeneous degrees. The degree of a vertex is its number of neighbors. Heterogeneous degrees mean that there are vertices with only few neighbors, as well as some with many many neighbors. In practice, there are often many nodes with low degree, as well as few nodes with very high degree (and some nodes with intermediate degrees). This leads to the following idea: represent low degree neighborhoods by adjacency lists, and then parsing them is fast (as they are small); and represent each high degree neighborhors by an array of size $n$. If one carefully chooses which degrees are considered small and which are considered large, then it is possible to have a compact graph representation that allows very fast edge existence queries.

I used this approach in triangle listing/counting algorithms (triangles are sets of three vertices all linked together): Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs

In this case, one may formally show that the algorithmic complexity depends on the way vertices are divided into low and high degrees. The practical benefit is huge too.