graphics in graphicsa central problem is the storage of objects in scene or view for thiswe organize our data by hashing hashing can be used to make grid of appropriate sizean ordinary vertical-horizontal grid (note that grid is nothing but arrayand there is one-to-one correspondence when we move from array to array sowe store the grid as array as we did in the case of sparse matrices all points that fall in one cell will be stored in the same place if cell contains three pointsthen these three points will be stored in the same entry the mapping from the grid cell to the memory location is done by using hash function the key advantage of this method of storage is fast execution of operations like the nearest neighbour search points to remember hash table is data structure in which keys are mapped to array positions by hash function value stored in hash table can be searched in ( time using hash function which generates an address from the key the storage requirement for hash table is ( )where is the number of keys actually used in hash tablean element with key is stored at index ( )not this means that hash function is used to calculate the index at which the element with key will be stored thusthe process of mapping keys to appropriate locations (or indicesin hash table is called hashing popular hash functions which use numeric keys are division methodmultiplication methodmid square methodand folding method division method divides by and then uses the remainder obtained potential drawback of this method is that consecutive keys map to consecutive hash values multiplication method applies the hash function given as (xi (ka mod mid square method works in two steps firstit finds and then extracts the middle digits of the result folding method works by first dividing the key value into parts knwhere each part has the same number of digits except the last part which may have lesser digits than the other partsand then obtaining the sum of kn the hash value is produced by ignoring the last carryif any collisions occur when hash function maps two different keys to the same location thereforea method used to solve the problem of collisionsalso called collision resolution techniqueis applied the two most popular methods of resolving collisions are(aopen addressing and (bchaining once collision takes placeopen addressing computes new positions using probe sequence and the next record is stored in that position in this technique of collision resolutionall the values are stored in the hash table the hash table will contain two types of values--either sentinel value (for example- or data value open addressing technique can be implemented using linear probingquadratic probingdouble hashingand rehashing in linear probingif value is already stored at location generated by ( )then the following hash function is used to resolve the collisionh(ki[ '(kimod though linear probing enables good memory cachingthe drawback of this algorithm is that it results in primary clustering in quadratic probingif value is already stored at location generated by ( )then the following hash function is used to resolve the collisionh(ki[ '(kc mod quadratic probing eliminates primary clustering and provides good memory caching but it is still liable to secondary clustering in double hashingwe use two hash functions rather than single function the hash function in the case of double hashing can be given ash(ki[ (kih ( )mod the performance of double hashing is very close to the performance of the ideal scheme of uniform hashing it minimizes repeated collisions and the effects of clustering when the hash table becomes nearly fullthe number of collisions increasesthereby degrading the performance of insertion and search operations so in rehashingall the entries in the original hash table are moved to the new hash table which is double the size of the original hash table