From: John Peterson <jwpeterson@gm...>  20110505 00:35:50

The answer is: "Not bad, but we could do way better!" The plot_key_test.pdf figure attached to this mail shows the worst and average case number of entries in each hash bucket (which I called collisions for lack of a better term) of our current hashes for "build_cube" meshes of Hexes, Tets, and Quads of varying size. Note that a "perfect" hash in this case would have 2 entries in each bucket for a given side key: one for each element adjacent to that side. The graphs count *all* entries in the bucket (and each actual side is in the bucket twice) but the trends are clear. Using the simple hash function available at http://burtleburtle.net/bob/hash/index.html, we can achieve essentially a constant small number of collisions for all these test cases (see the remaining 3 figures.) I think this will speed up the performance of find_neighbors() a bit on really large meshes. Let me know if you'd like to see my test code, and I'll send it to you...  John 