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. Who cares? by Screaming+Lunatic · · Score: 5, Insightful
    It's a table. Which means it'll be faster than a list. That's all you have to worry about.

    What's that about a little bit of knowledge and it being dangerous. In school you'll beat every algorithm under the sun to death. In the real world you'll link to the STL and use a hash map.

    Write well-designed, clean, maintainable code. Then profile it. If your table lookup blips on the profiler, then *THINK* about optimizing it. After you've *THOUGHT* about optimizing it, then decide if it makes sense to squeeze the time and effort into the schedule.

    Random quotes:

    Premature optimization is the root of all evil. -- Knuth

    There is never a best solution, only tradeoffs to consider. --Eberly

    The best optimizer is between your ears. --Abrash

    The Ferrai's are only gravy, honest! --Carmack

    Alright I threw the last one in for shits and giggles. Don't blame me, I can't get through a Sunday night without drinking a poop load of beer. Anyway, the point is that there is a difference between *FAST* and *FAST ENOUGH*. If it's fast enough, who cares.

    [CYNICISM]

    Unless you're an academic and you're looking for funding.

    [/CYNICISM]