Hashing and Methods used to implement hashing(Hashing with chaining)

 Hashing and Methods used to implement hashing(Hashing with chaining and hashing with open addressing)

Hashing is a widely used class of data structures that support the operations of insert,delete and search on a dynamic set of keys S.These keys are mapped into a hash table using a hash function.The size of the hash table is usually within a constant factor of the number of elements in the current set S.

Hash table

Hash table consists of an array in which data is accessed via a special index called a key.The primary idea behind a hash table is to establish a mapping between the set of all possible keys and positions in the array using a hash function.A hash function accepts a key and returns its hash coding.Both computing a hash value and indexing into an array can be performed in constant time .Hashing can use it to perform constant time searches.

When two keys map to the same position they collide.A good hash function minimizes collisions but we must still be prepared to deal with them.

Application of hash tables

• Database systems.
• Symbol table.
• Data dictionaries.

There are two main methods used to implement hashing

• Hashing with chaining
• Hashing with open addressing. 

Hash functions

Hash function is a function which when applied to the key produces an integer which can be used as an address in a hash table.Good hash function minimize collisions by spreading the elements uniformly throughout the array.

Hash functions are

• Division method.
• Multiplication method.

Division method

Division method for creating hash functions map a key k into one of m slots by taking the remainder of k divided by m.

Hash function is

h(k)=k mod m

Multiplication Method

Multiplication method for creating hash functions operates in two steps.First multiply the key K by a constant A in the range 0<A<1 and extract the fractional part of kA. Then multiply this value by m and take the floor of the result.

h(k)=floor(m(kAmod1)

Hashing with chaining

All keys that hash into the same slot are placed in a linked list associated with that slot.This linked list is called the chain at that slot.In hashing with chaining inserts and deletes can be performed in constant time with suitable linked list representation for the chains.In the worst case a search operation can take as long as n steps if all keys hash into the same slot.The main drawback with this method is the requirement that the scheme implements simple uniform hashing.

Example

Consider the insertion of elements 5,28,19,15,20,33,12,17,10 into a chained-hash table.The hash table has 9 slots and the hash function be h(k)=k mod 9.

Solution

h(5)=5 mod 9=5

create a linked-list for T[5] and store  value 5 in it.

h(28)=28 mod 9=1

create a linked list for T[1] and store value 28 in it.

h(19)=19 mod 9=1

Insert value 19 in the slot T[1] in the beginning of the link-list.

h(15)=15 mod 9=6

create a linked-list for T[6] and store  value 15 in it.

h(20)=20 mod 9=2

Insert value 20 in the slot T[2] in the beginning of the link-list.

h(33)=33 mod 9=6

Insert value 33 in the slot T[6] in the beginning of the link-list.

h(12)=12 mod 9=3 in T[3]

h(17)=17 mod 9=8 in T[8]

h(10)=10 mod 9=1 in T[1]

Thus chained hash table after inserting key 10.