( ( ( ( )it may be surprising that ( and ( which means that as soon as there are more than people in groupit is more likely that two of them share birthday than not note that in the real worldthe distribution of birthdays over the year is not precisely uniformbut this only increases the probability that two people have the same birthday in other wordsbirthday collisions are much more likely than one might think at first implications for hash tables if random locations in table of size have more than chance of overlappingit seems inevitable that collisions will occur in any hash table that does not waste an enormous amount of memory and collisions will be even more likely if the hash function does not distribute the items randomly throughout the table to compute the computational efficiency of hash tablewe need some way of quantifying how full the table isso we can compute the probability of collisionsand hence determine how much effort will be required to deal with them the load factor of hash table suppose we have hash table of size mand it currently has entries then we call / the load factor of the hash table this load factor is the obvious way of describing how full the table currently isa hash table with load factor is fullone with load factor is fulland so on then if we have hash table with load factor lthe probability that collision occurs for the next key we wish to insert is this assumes that each key from the key space is equally likelyand that the hash function spreads the key space evenly over the set of indices of our array if these optimistic assumptions failthen the probability may be even higher thereforeto minimize collisionsit is prudent to keep the load factor low fifty percent is an often quoted good maximum figurewhile beyond an eighty percent load the performance deteriorates considerably we shall see later exactly what effect the table' load factor has on the speed of the operations we are interested in simple hash table in operation let us assume that we have small data array we wish to useof size and that our set of possible keys is the set of -character stringswhere each character is in the range from to obviouslythis example is designed to illustrate the principle typical real-world hash tables are usually very much biggerinvolving arrays that may have size of thousandsmillionsor tens of millionsdepending on the problem we now have to define hash function which maps each string to an integer in the range to let us consider one of the many possibilities we first map each string to number as followseach character is mapped to an integer from to using its place in the alphabet ( is the first letterso it goes to the second so it goes to and so onwith getting value the string therefore gives us three numbers from to say and we can then map the whole string to the number calculated as