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?"

3 of 48 comments (clear)

  1. Read the Bible by Woodblock · · Score: 2, Informative

    Do yourself a favour and read the bible on it. The information might be a bit dated, but I doubt hashing has changed that much since the last edition.

  2. 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--
  3. CAM table by frantzen · · Score: 2, Informative

    CAM tables if you're gluing together your own hardware. kinda like a hash table in hardware that never gets collisions until it is full.

    the insertion/deletion maintance isn't free so you gotta be careful with your search/modify ratio.