we would have problem according to the hash functiontwo or more items would need to be in the same slot this is referred to as collision (it may also be called "clash"clearlycollisions create problem for the hashing technique we will discuss them in detail later hash functions given collection of itemsa hash function that maps each item into unique slot is referred to as perfect hash function if we know the items and the collection will never changethen it is possible to construct perfect hash function (refer to the exercises for more about perfect hash functionsunfortunatelygiven an arbitrary collection of itemsthere is no systematic way to construct perfect hash function luckilywe do not need the hash function to be perfect to still gain performance efficiency one way to always have perfect hash function is to increase the size of the hash table so that each possible value in the item range can be accommodated this guarantees that each item will have unique slot although this is practical for small numbers of itemsit is not feasible when the number of possible items is large for exampleif the items were nine-digit social security numbersthis method would require almost one billion slots if we only want to store data for class of studentswe will be wasting an enormous amount of memory our goal is to create hash function that minimizes the number of collisionsis easy to computeand evenly distributes the items in the hash table there are number of common ways to extend the simple remainder method we will consider few of them here the folding method for constructing hash functions begins by dividing the item into equalsize pieces (the last piece may not be of equal sizethese pieces are then added together to give the resulting hash value for exampleif our item was the phone number - we would take the digits and divide them into groups of ( after the addition we get if we assume our hash table has slotsthen we need to perform the extra step of dividing by and keeping the remainder in this case % is so the phone number hashes to slot some folding methods go one step further and reverse every other piece before the addition for the above examplewe get which gives % another numerical technique for constructing hash function is called the mid-square method we first square the itemand then extract some portion of the resulting digits for exampleif the item were we would first compute by extracting the middle two digits and performing the remainder stepwe get ( % table shows items under both the remainder method and the mid-square method you should verify that you understand how these values were computed we can also create hash functions for character-based items such as strings the word "catcan be thought of as sequence of ordinal values ord(' ' ord(' ' ord(' ' searching