chap searching probability that some pair of students shares the same birthday ( the same day of the yearnot necessarily the same year)if there are studentsthen the odds are about even that two will share birthday this is despite the fact that there are days in which students can have birthdays (ignoring leap years)on most of which no student in the class has birthday with more studentsthe probability of shared birthday increases the mapping of students to days based on their birthday is similar to assigning records to slots in table (of size using the birthday as hash function note that this observation tells us nothing about which students share birthdayor on which days of the year shared birthdays fall to be practicala database organized by hashing must store records in hash table that is not so large that it wastes space typicallythis means that the hash table will be around half full because collisions are extremely likely to occur under these conditions (by chanceany record inserted into table that is half full will have collision half of the time)does this mean that we need not worry about the ability of hash function to avoid collisionsabsolutely not the difference between good hash function and bad hash function makes big difference in practice technicallyany function that maps all possible key values to slot in the hash table is hash function in the extreme caseeven function that maps all records to the same slot is hash functionbut it does nothing to help us find records during search operation we would like to pick hash function that stores the actual records in the collection such that each slot in the hash table has equal probability of being filled unfortunatelywe normally have no control over the key values of the actual recordsso how well any particular hash function does this depends on the distribution of the keys within the allowable key range in some casesincoming data are well distributed across their key range for exampleif the input is set of random numbers selected uniformly from the key rangeany hash function that assigns the key range so that each slot in the hash table receives an equal share of the range will likely also distribute the input records uniformly within the table howeverin many applications the incoming records are highly clustered or otherwise poorly distributed when input records are not well distributed throughout the key range it can be difficult to devise hash function that does good job of distributing the records throughout the tableespecially if the input distribution is not known in advance there are many reasons why data values might be poorly distributed performance is required an example is searching for data on read-only cd here the database will never changethe time for each access is expensiveand the database designer can build the hash table before issuing the cd