hashing the hash function takes advantage of the fact that overflow is allowed and uses unsigned int to avoid introducing negative number the hash function described in figure is not necessarily the best with respect to table distributionbut it does have the merit of extreme simplicity and is reasonably fast if the keys are very longthe hash function will take too long to compute common practice in this case is not to use all the characters the length and properties of the keys would then influence the choice for instancethe keys could be complete street address the hash function might include couple of characters from the street address and perhaps couple of characters from the city name and zip code some programmers implement their hash function by using only the characters in the odd spaceswith the idea that the time saved computing the hash function will make up for slightly less evenly distributed function the main programming detail left is collision resolution ifwhen an element is insertedit hashes to the same value as an already inserted elementthen we have collision and need to resolve it there are several methods for dealing with this we will discuss two of the simplestseparate chaining and open addressingthen we will look at some more recently discovered alternatives separate chaining the first strategycommonly known as separate chainingis to keep list of all elements that hash to the same value we can use the standard library list implementation if space is tightit might be preferable to avoid their use (since these lists are doubly linked and waste spacewe assume for this section that the keys are the first perfect squares and that the hashing function is simply hash(xx mod (the table size is not prime but is used here for simplicity figure shows the resulting separate chaining hash table to perform searchwe use the hash function to determine which list to traverse we then search the appropriate list to perform an insertwe check the appropriate list to see whether the element is already in place (if duplicates are expectedan extra data member is figure separate chaining hash table