What I'm looking for is a book that explains hashing functions, the formula that takes a value and generates a key, or something like that. If the book explains modern STL and the use of iterators that would be better.

Don't know any books, but wikipedia might be an okay place to start :
http://en.wikipedia.org/wiki/Hash_function

Heat hash. Crumble into pipe. Put pipe in mouth. Burn hash, whilst steadily sucking on pipe. When all hash is glowing red, stop breathing in and remove pipe from mouth. Hold breath. Breathe out hash smoke. Wait. Now write code.

I don't think it's so complex that a book would be dedicated to it. It's more about understanding the (very simple) purpose and properties of a good hashing function, then coming up with one based on your data.

[edit]
What I meant to say is:

In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times.

Game playing programs work by analyzing millions of positions that could arise in the next few moves of the game. Typically, these programs employ strategies resembling depth-first search, which means that they do not keep track of all the positions analyzed so far. In many games, it is possible to reach a given position in more than one way. These are called transpositions.[1] In chess, for example, the sequence of moves 1. d4 Nf6 2. c4 g6 (see algebraic chess notation) has 4 possible transpositions, since either player may swap their move order. In general, after n moves, an upper limit on the possible transpositions is (n!)². Although many of these are illegal move sequences, it is still likely that the program will end up analyzing the same position several times.

To avoid this problem, transposition tables are used. Such a table is a hash table of each of the positions analyzed so far up to a certain depth. On encountering a new position, the program checks the table to see if the position has already been analyzed; this can be done quickly, in expected constant time. If so, the table contains the value that was previously assigned to this position; this value is used directly. If not, the value is computed and the new position is entered into the hash table. This is essentially memoization applied to the search function.

thanks for the help guys, its not that its complicated like BAF said but implementing the code is a little hard to do. And then there a lots of things to learn about.

@Thomas, interesting video but I can't sit through an hour and watch that.

Math doesn't help you when there are known problems with a given hash method. All you have to do is tweak the input for it, and you can stack up as many things as you want in as few buckets as possible.

From the archives:

http://www.allegro.cc/forums/thread/512313

I think you are missing the larger joke.

What they showed in the video relied on POST request, so the limit depends on the stack (PHP defaults to 8MB of data)

You can avoid degenerate hash table cases by simply extending the size of the table dynamically when it gets too crowded.

Linky to my hashtable implementation. It seems to work fine with a few million keys. I haven't tried billions due to lack of memory.

It averages about 2x the performance of STL's hash_map<> on MSVC 7 or GCC 2.x.

The hashing function isn't that great; feel free to replace it with something better.

Most of the requests they sent were much smaller. And often sent them a bit at a time. Some of the requests could be sent at 17kbps or slower and still cause a machine to use up incredible resources.

Better hope the police don't see that

Hash tables are nice and all, but don't forget about balanced binary search trees.

As for hash functions, I liked MurmurHash (2, haven't tried 3).

That's pretty clever, exploiting the fact that inserting into hash tables tends to be O(n) or O(n log(n)) but is routinely confused as being an O(1) operation.

My hash code posted above is exposed to this bug and will fail in the same way. I can't think of a good way of addressing that problem without significantly hurting its performance.

Buckets? Whats that.

It maybe O(1) operation but if a hashing function takes 30ms (I'm guessing, no benchmarks here, well actually I did some with boost unordered_map, if thats a hashing function and it was kinda slow) to do a million times on a 2 ghz processor then its still kinda slow, but since everything else seems slower I guess its better but you have to realize that the one operation is still very cumbersome.