key transformations (hashing introduction the principal question discussed in chap at length is the followinggiven set of items characterized by key (upon which an ordering relation is defined)how is the set to be organized so that retrieval of an item with given key involves as little effort as possibleclearlyin computer store each item is ultimately accessed by specifying storage address hencethe stated problem is essentially one of finding an appropriate mapping of keys (kinto addresses ( )hk in chap this mapping was implemented in the form of various list and tree search algorithms based on different underlying data organizations here we present yet another approach that is basically simple and very efficient in many cases the fact that it also has some disadvantages is discussed subsequently the data organization used in this technique is the array structure is therefore mapping transforming keys into array indiceswhich is the reason for the term key transformation that is generally used for this technique it should be noted that we shall not need to rely on any dynamic allocation proceduresthe array is one of the fundamentalstatic structures the method of key transformations is often used in problem areas where tree structures are comparable competitors the fundamental difficulty in using key transformation is that the set of possible key values is much larger than the set of available store addresses (array indicestake for example names consisting of up to letters as keys identifying individuals in set of thousand persons hencethere are possible keys which are to be mapped onto possible indices the function is therefore obviously many-toone function given key kthe first step in retrieval (searchoperation is to compute its associated index ( )and the second evidently necessary step is to verify whether or not the item with the key is indeed identified by in the array (tablet to check whether [ ( )key we are immediately confronted with two questions what kind of function should be used how do we cope with the situation that does not yield the location of the desired itemthe answer to the second question is that some method must be used to yield an alternative locationsay index 'andif this is still not the location of the wanted itemyet third index "and so on the case in which key other than the desired one is at the identified location is called collisionthe task of generating alternative indices is termed collision handling in the following we shall discuss the choice of transformation function and methods of collision handling choice of hash function prerequisite of good transformation function is that it distributes the keys as evenly as possible over the range of index values apart from satisfying this requirementthe distribution is not bound to any patternand it is actually desirable that it give the impression of being entirely random this property has given this method the somewhat unscientific name hashingi chopping the argument upor making mess is called the hash function clearlyit should be efficiently computablei be composed of very few basic arithmetic operations assume that transfer function ord(kis avilable and denotes the ordinal number of the key in the set of all possible keys assumefurthermorethat the array indices range over the intergers - where is the size of the array then an obvious choice is