Data Structures（数据结构）Course 2Searching.ppt

summary(continued) In direct hashing,the key is the address without any algorithmic manipulation In subtraction hashing,the key is transformed to an address by subtracting a fixed number from it In modulo-division hashing,the key is divided by the list size,recommended to be a prime number In digit-extraction hashing,selected digits are extracted from the key and used as an address In mid-square hashing,the key is squared and the address is selected from the middle of the result In fold shift hashing,the key is divided into parts whose sizes match the size of the required address.then the parts are added to obtain the address summary(continued) In fold boundary hashing,the key is divided into parts whose sizes match the size of the required address.then the left and right parts are reversed and added to the middle part to obtain the address In rotation hashing,the rightmost digit of the key is rotated to the left to determine an address. However,this method is usually used in combination with other methods In the pseudorandom generation hashing,the key is used as the seed to generate a pseudorandom number. The result is then scaled to obtain the address Except in the direct and subtraction methods, collisions are unavoidable in hashing. Collision occur when a new key is hashed to an address that is already occupied summary(continued) Clustering is the tendency of data to build up unevenly across a hashed list. Primary clustering occur when data build up around a home address Secondary clustering occurs when data build up along a collision path in the list To solve a collision, a collision resolution method is used Three general methods are used to resolve collision : open addressing,linked list,and buckets The open addressing method can be subdivided into linear probe,quadratic probe,pseudorandom rehashing,and key-offset rehashing summary(continued) In the linear probe method,when the collision occurs,the new data will be stored in the next available address