Hash Function To avoid situations like the one above,it is usually a good idea to ensure that the table size is prime. When the input keys are random integers,then this function is not only very simple to compute but also distributes the keys evenly
Hash Function ◼ To avoid situations like the one above, it is usually a good idea to ensure that the table size is prime. ◼ When the input keys are random integers, then this function is not only very simple to compute but also distributes the keys evenly
Hash Function Usually,the keys are strings;in this case,the hash function needs to be chosen carefully. One option is to add up the ASCII values of the characters in the string. int Hash(char *Key,int TableSize) unsigned int HashVal=0; while(*Key！=O') HashVal+=*Key++; return HashVal%TableSize;
Hash Function ◼ Usually, the keys are strings; in this case, the hash function needs to be chosen carefully. ◼ One option is to add up the ASCII values of the characters in the string. int Hash(char *Key, int TableSize) { unsigned int HashVal=0; while (*Key!=‘\0’) HashVal+=*Key++; return HashVal%TableSize; }
Hash Function However,if the table size is large,the function does not distribute the keys well. For instance,suppose that 7ab/eSize=10007 (10007 is a prime number),and all keys are eight or fewer characters long. ■ Since a charhas an integer value that is always at most 127,the hash function can only assume values between 0 and 1016,which is 127*8. This is clearly not an equitable distribution!
Hash Function ◼ However, if the table size is large, the function does not distribute the keys well. ◼ For instance, suppose that TableSize=10007 (10007 is a prime number), and all keys are eight or fewer characters long. ◼ Since a char has an integer value that is always at most 127, the hash function can only assume values between 0 and 1016, which is 127*8. ◼ This is clearly not an equitable distribution!