hashing notes in many applications we require to use data object called symbol table symbol table is nothing but set of pairs (namevaluewhere value represents collection of attributes associated with the nameand this collection of attributes depends upon the program element identified by the name for exampleif name is used to identify an array in programthen the attributes associated with are the number of dimensionslower bound and upper bound of each dimensionand the element type therefore symbol table can be thought of as linear list of pairs (namevalue)and hence you can use list of data object for realizing symbol table symbol table is referred to or accessed frequently either for adding the nameor for storing the attributes of the nameor for retrieving the attributes of the name therefore accessing efficiency is prime concern while designing symbol table hence the most common way of getting symbol table implemented is to use hash table hashing is method of directly computing the index of the table by using some suitable mathematical function called hash function the hash function operates on the name to be stored in the symbol tableor whose attributes are to be retrieved from the symbol table if is hash function and is namethen (xgives the index of the table where along with its attributes can be stored if is already stored in the tablethen (xgives the index of the table where it is stored to retrieve the attributes of from the table there are various methods of defining hash function like division method in this methodyou take the sum of the values of the charactersdivide it by the size of the tableand take the remainder this gives us an integer value lying in the range of to ( if the size of the table is the other method is mid square method in this methodthe identifier is first squared and then the appropriate number of bits from the middle of square is used as the hash value since the middle bits of the square usually depend on all the characters in the identifierit is expected that different identifiers will result into different values the number of middle bits that you select depends on the table size therefore if is the number of middle bits that you use to form hash valuethen the table size will be hence when you use this method the table size is required to be power of another method is folding in which the identifier is partitioned into several partsall but the last part being of the same length these parts are then added together to obtain the hash value to store the name or to add attributes of the nameyou compute hash value of the nameand place the name or attributes as the case may beat that place in the table whose index is the hash value of the name for retrieving the attribute values of the name kept in the symbol tablei apply the hash function to the name to obtain index of the table where you get the attributes of the name hence you find that no comparisons are required to be done hence the time required for the retrieval is independent of the table size therefore retrieval is possible in constant amount of timewhich will be the time taken for computing the hash function therefore hash table seems to be the best for realizationof the symbol tablebut there is one problem associated with the hashingand it is of collisions hash collision occurs when the two identifiers are mapped into the same hash value this happens because hash function defines mapping from set of valid identifiers to the set of those integerswhich are used as indices of the table therefore you see that the domain of the mapping defined by the hash function is much larger than the range of the mappingand hence the mapping is of many to one nature therefore when implement hash table suitable collision handling mechanism is to be provided which will be activated when there is collision collision handling involve finding out an alternative location for one of the two colliding symbols for exampleif and are the different identifiers and if (xh( ) and are the colliding symbols if is encountered before ythen the ith entry of the table will be used for accommodating symbol xbut later on when comes there is hash collisionand therefore you have to find out an alternative location either for or this means you find out suitable alternative location and either accommodate in that locationor you can move to that location lovely professional university