The element type, the client doesn't know how many buckets there are, and This is because the implementer doesn't understand Is the composition of two functions, one provided by the client and implementerĪs we've described it, the hash function is a single function that mapsįrom the key type to a bucket index.

For example, a one-bit change to the key should causeĮvery bit in the index to flip with 1/2 probability. Randomly flip the bits in the bucket index. Writing the bucket index as a binary number, a small change to the key should Should change the bucket index in an apparently random way. If it is to look random, this means that any change to a key, even a small one, Simple uniform hashing assumption - that the hash function should look random. Recall that hash tables work well when the hash function satisfies the While hash tables are extremely effective when used well, all too often poor hash functions are used We want our hash function to use all of the information in the key. Length would be a very poor function, as would a hash function that used only If we're mapping names to phone numbers, then hashing each name to its A lot of obvious hash function choices are bad.

Hash function, or make it difficult to provide a good hash function.Ĭlearly, a bad hash function can destroy our attempts at a constant Hash table abstractions do not adequately specify what is required of the Generators, invalidating the simple uniform hashing assumption.

Clients choose poor hash functions that do not act like random number.

Tables often falls far short of achievable performance. Unfortunately, they are also one of the most misused. Hash tables are one of the most useful data structures ever invented. Lecture 21: Hash functions CS 312 Lecture 21

Better with mods well bucket