Consider searching a linked list of length n and each element in the linked list consist a key along with a hash value. Where, key k is a long character string. Since the list contains hash value, using the hash values for searching the linked list is an advantage.

• Since the key k is a long character string, string comparison operation is performed at every node along the length or the list. Since the string comparison is a time consuming process, searching the list also takes much time.

• Instead of comparing the given key with key k of each node, generating the hash value for the given search key and comparing it with the hash value of each node in the list is advantageous and festers the search.

• Thus, first generate the hash value for the given search key then compare the hash value with hash value of every node in the list along the length of the linked list.

• Since the hash value is a numeric value, comparison is faster and search takes less time.

Therefore, in this case, using hash values for searching linked list is an advantage, as it fasters the search.

Consider the following basic number theory principles of modulo arithmetic:

…… (1)

and

…… (2)

Where, and are integers.

Now, consider the string of r characters. This r characters string can be hashed using the division method with constant space.

The conversion of any string of length r to a radix-128 number takes place in the following way:

…… (3)

Where, denotes thecharacter starting from the least significant end with 0. In other words it can also be viewed as its ASCII code’s integer.

Apply the division hashing function in the equation (3):

Therefore, from the above, it need to take modulo operation after every multiplication, which gives a result a constant number. It gives a constant number because, the term given below gives a number less than, equal to or greater than.

Now, after taking the modulus of a number, even the number is less than, equal to or greater than, it will give a constant number less than.

Therefore, the division method applied to compute the hash value of the given character string using more than a constant number of words storag e outside the string itself.

It is known that permutations can be generated in a string by interchanging any pair of characters. This property can be proved in the following way:

• First consider quick sort and heap sort both work by interchanging pair of elements. So, it can be used to generate a number of permutations of its input array.

• Therefore, it enough to prove that two strings and hash to the same value. Where string is obtained from the string by exchanging a pair of characters.

• Suppose denotes thecharacter in and denotes thecharacter in. So, the interpretation of in radixwill be given asand the interpretation of in radix will be given as.

• Therefore,

, As is given.

Similarly,

• Assume that and are identical strings of characters except that the characters in positions and are interchanged.

That is, and …… (1)

• Now, suppose then:

…… (2)

• Now by Euclidian algorithm,

and

Then

• Now, take in equation (2), then

• As and are similar strings of characters other than the characters in position and are exchanged,

Now, use and from equation (1)

• Now, multiply the above with and factor out the, then user will obtained:

Now, factor out the,

…… (3)

• Now consider the following equation:

Now, multiply with on each side, then

• Now put this value in the equation (3),

Then,

Now, the above expression consists as a factor, therefore the above value can be exactly divided by.

Thus,

will be zero.

Therefore,

Hence, it can be concluded that,

And thus,

Example:

Now consider the following example of a dictionary. If and a character string is represented in radix , then two strings that are similar other than for a transposed character hash to the same value.

Now, suppose

Now consider two strings u= “abcd” and v=“badc”. Here u can be obtained by permuting the characters in v.

Calculate hash values using ASCII values of characters as follows:

• The value of u in radix ,

• Now, its hash value , ,

• The value of v in radix ,,

• Now, its hash value , ,

• Here, two strings u,v hash to the same value. That is .

The property is undesirable in dictionary application:

• A dictionary contains different words such that one word is obtained from another by permuting the characters. For example, TOP, OPT and POT

• If the given property is used for dictionary application, hash values of POT, TOP and OPT are same.

Therefore the given property does not suitable to applications like dictionaries.

|B| and |U| are 2 finite sets from which a family H of hash functions has been defined to be such that probability of a hash function of key is less than or equal to .

Suppose b = |B| and u = |U| and b divides u.

To prove the given inequality, we will take the contradictory case as true.

Contradictory case:

Suppose . It signifies that each key value pair (k, l) that belongs to U. For these value, there are will be n hash functions that have collision on 2 elements and it satisfies the inequalities .

Sum all such pairs.

After summing up, you get

……(1)

With a good hash function, there should be at least colliding pairs.

It means that each slot should have at least 2 colliding keys.

Similarly, for all hash functions, there will be at least = colliding pairs.

Using the inequality (1), it is clear that the total number of colliding pairs are less than required.

Thus, it is a contradiction. Hence, it is proved that .