The search time of each algorithm depend on the number n of elements of the collection S of the data. A searching technique called Hashing or Hash addressing which is essentially independent of the number n.
Hashing is the transformation of a string of characters into a usually shorter fixedlength value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than to find it using the original value. It is also used in many encryption algorithms.
Hash Function:
A Hash Function is a Unary Function that is used by Hashed Associative Containers: it maps its argument to a result of type size_t. A Hash Function must be deterministic and stateless. That is, the return value must depend only on the argument, and equal arguments must yield equal results.
Hash functions are mostly used in hash tables, to quickly locate a data record (for example, a dictionary definition) given its search key (the headword). Specifically, the hash function is used to map the search key to the index of a slot in the table where the corresponding record is supposedly stored.
Division Method:
Choose the number n larger then the number n of the keys in K. The number n is ussualy choosen to be a prime number or a number with a small number of divisors. This frequently minimize the number of collisions. The hash function H is defined by
H(k)=k(mod m) or H(k) = (mod m)+1
Midsquare method:
The key k is squared then the hash function H is defined by
H(k)=I
Where I is obtained by deleting digits from both ends of K^{2} we emphasize that the same positions of K^{2} must be used for all of the keys.
Folding Method:
The key K is partitioned into a number of parts k1, k2,….kr where each part except possibily the last has the same number of digits as the required address. Then the parts are edit together ignoring the last carry that is
H(k) = k1+k2+…kr
Where the leading digit carries are ignored some time for extra miling the even numbered parts k2,k4,… are each reversed before the addition.
H(4502) = 54+20 = 74
