(kord(kmod it has the property that the key values are spread evenly over the index rangeand it is therefore the basis of most key transformations it is also very efficiently computableif is power of but it is exactly this case that must be avoidedif the keys are sequences of letters the assumption that all keys are equally likely is in this case mistaken in factwords that differ by only few characters then most likely map onto identical indicesthus effectively causing most uneven distribution it is therefore particularly recommended to let be prime number [ - this has the conseqeunce that full division operation is needed that cannot be replaced by mere masking of binary digitsbut this is no serious drawback on most modern computers that feature built-in division instruction oftenhash funtions are used which consist of applying logical operations such as the exclusive or to some parts of the key represented as sequence of binary digits these operations may be faster than division on some computersbut they sometimes fail spectacularly to distribute the keys evenly over the range of indices we therefore refrain from discussing such methods in further detail collision handling if an entry in the table corresponding to given key turns out not to be the desired itemthen collision is presenti two items have keys mapping onto the same index second probe is necessaryone based on an index obtained in deterministic manner from the given key there exist several methods of generating secondary indices an obvious one is to link all entries with identical primary index (ktogether in linked list this is called direct chaining the elements of this list may be in the primary table or notin the latter casestorage in which they are allocated is usually called an overflow area this method has the disadvantage that secondary lists must be maintainedand that each entry must provide space for pointer (or indexto its list of collided items an alternative solution for resolving collisions is to dispense with links entirely and instead simply look at other entries in the same table until the item is found or an open position is encounteredin which case one may assume that the specified key is not present in the table this method is called open addressing [ - naturallythe sequence of indices of secondary probes must always be the same for given key the algorithm for table lookup can then be sketched as followsh : ( ) : repeat if [hkey then item found elsif [hkey free then item is not in table else (*collision* : + : (kg(iend until found or not in table (or table fullvarious functions for resolving collisions have been proposed in the literature survey of the topic by morris in [ - stimulated considerable activities in this field the simplest method is to try for the next location considering the table to be circular until either the item with the specified key is found or an empty location is encountered henceg(iithe indices hi used for probing in this case are (khi (hi- imod ni - this method is called linear probing and has the disadvantage that entries have tendency to cluster around the primary keys (keys that had not collided upon insertionideallyof coursea function should be chosen that again spreads the keys uniformly over the remaining set of locations in practicehowever