Using a hash map adds a log(n) complexity to all accesses (then traversing the whole mesh will cost n log(n) in general), so clearly it is not the best solution.
Now your question is how you can efficiently store and traverse adjacency information, i.e. for each cell the list of adjacent cells. First thing you can do for mapping a cell to its list of neighbors: you can use an array instead of a hash, this will remove the log(n) cost.
Then, using an array, this means you need to store an array of lists of different lengths (if your mesh has arbitrary polyhedra), which is in general not very efficient: each list has its own memory overhead to be added to the memory used by the elements it contains.
A more efficient way of storing this type of information (i.e. an array of lists of different lengths) is the "compressed row storage" (called CRS, CSR or Yale format) representation , used to store sparse matrices.
Edit If adjacency information is not present in your input, then you will need to recreate it. Instead of using a hash or associative map as suggested in the other answer, an alternative is to store all facets in an array then sort this array. After sorting, the pairs of facets that correspond to adjacent cells are contiguous in the array. I observed that it is significantly more efficient (at least in C++, I did not test that in Python). See also my answer to this question . To adapt my answer to your polyhedral grid, facet records will have a facet index and as a key, three vertex indices (the lowest vertex id in the facet and the two ones connected to it with an edge, in increasing order). By sorting facet records with the lexicographic order, you will retrieve the pair of adjacent facets contiguously in the array.
For each cell c
For each facet f of cell c
Find v1 the smallest vertex index in facet f
Find v2 and v3, the vertices before and after v1 in facet f
If v3 < v2, swap v2 and v3
Append a new record [v1, v2, v3, c] to the array
Sort the record array with the lexicographic order on (v1,v2,v3)
In the record array, find (by scanning the array) the contiguous
pairs of record (v1,v2,v3,c1);(v1,v2,v3,c2) with the same (v1,v2,v3).
For each such pair, c1 and c2 are adjacent.
If input data has facet ids, then records are simply (f,c) couples, and they are sorted by f (instead of (v1,v2,v3)).
 Meshing options to generate number of the sides of and element (tetgen-triangle)