this idea is not very practical if we are dealing with relatively small number of keys out of huge collection of possible keys for examplemany american companies use their employees -digit social security number as keyeven though they have nowhere near employees british national insurance numbers are even worsebecause they are just as long and usually contain mixture of letters and numbers clearly it would be very inefficientif not impossibleto reserve space for all social security numbers which might occur insteadwe use non-trivial function hthe so-called hash functionto map the space of possible keys to the set of indices of our array for exampleif we had to store entries about employeeswe might create an array with entries and use three digits from their social security number (maybe the first or last threeto determine the place in the array where the records for each particular employee should be stored this approach sounds like good ideabut there is pretty obvious problem with itwhat happens if two employees happen to have the same three digitsthis is called collision between the two keys much of the remainder of this will be spent on the various strategies for dealing with such collisions first of allof courseone should try to avoid collisions if the keys that are likely to actually occur are not evenly spread throughout the space of all possible keysparticular attention should be paid to choosing the hash function in such way that collisions among them are less likely to occur iffor examplethe first three digits of social security number had geographical meaningthen employees are particularly likely to have the three digits signifying the region where the company residesand so choosing the first three digits as hash function might result in many collisions howeverthat problem might easily be avoided by more prudent choicesuch as the last three digits collision likelihoods and load factors for hash tables one might be tempted to assume that collisions do not occur very often when only small subset of the set of possible keys is chosenbut this assumption is mistaken the von mises birthday paradox as an exampleconsider collection of peopleand hash function that gives their birthdays as the number of the day in the yeari st january is nd january is st december is one might think that if all we want to do is store modest number of people in this way in an array with locationscollisions will be rather unlikely howeverit turns out that the probability of collision is bigger than this is so surprising at first sight that this phenomenon has become known as the von mises birthday paradox although it is not really paradox in the strict sense it is easy to understand what is happening suppose we have group of people and want to find out how likely it is that two of them have the same birthdayassuming that the birthdays are uniformly distributed over the days of the year let us call this probability (nit is actually easier to first compute the probability (nthat no two of them share birthdayand then ( (nfor this probability is clearly ( for we get ( / becausefor the added second person of the days are not the birthday of the first person for we get ( (