Slashdot Mirror

← Back to Stories (view on slashdot.org)

Probing Hash Tables?

Posted by Cliff on from the interesting-thought-excercises dept.

David Rusenko asks: "I've been taking a datastructures class at CMU as part of a summer CS program. One of these structures we have gone over is hash tables. After going through many different probing methods (linear, quadratic), multiple hash functions, and double hashing, I was all too curious to know if these are the best methods currently known. Some other interesting ideas came up, such as using the Fibonacci numbers for probing, but I haven't had time to test them yet. Any comments?"

1 of 48 comments (clear)

  1. Fibonacci. by OnyxRaven · · Score: 3, Informative

    As I dig out my Algorithms textbook, I see mention that Fibonacci heaps give fast times in Dijkstra and Prim's algorithms for Shortest dag path and Minimum Spanning Trees respectively: O(m+nlogn) in both cases. This is very fast for dense graphs.

    Shrug.

    --
    --onyx--