Hash Function

• If the input keys are integers, then simply returning Key mod TableSize is generally a reasonable strategy
• it is often a good idea to ensure that the table size is prime
• If, when an element is inserted, it hashes to the same value as an already inserted element, then we have a collision and need to resolve it.
• This is the basic idea of hashing. The only remaining problems deal with choosing a function, deciding what to do when two keys hash to the same value (this is known as a collision), and deciding on the table size.
• Hash function

  A function that maps keys to table indices
• Hash function for integer keys

  • Simply returning Key mod TableSize is generally a reasonable strategy, unless Key happens to have some undesirable properties
  • It is often a good idea to ensure that the table size is prime
• Hash function for string keys

  • Adding up the ASCII (or Unicode) values of the characters in the string is a simple option
  • This function does not distribute the keys well if the table size is large
• If the keys are very long, the hash function will take too long to compute. A common practice in this case is not to use all the characters.