Hashing in Design and Analysis of Algorithm Study Notes with Example

Hashing

Hashing is a common method of accessing data records. Hashing is the process of mapping large amount of data item to a smaller table with the help of hashing function.         

Linear Search Versus Hashing

• A  linear search  looks down a list, one item at a time, without jumping. In complexity terms, this is an 0(n) search, the time taken to search the list. if we use hashing to search, data  need not be sorted. Without collision and overflow, search only takes 0(1) time.

Hash Table

A hash system that stores records in an array, called a hash table. A hash table uses a hash function to compute an index into an array of buckets, from which  the correct value can be found.

Hash  Function

Hash function primarily is responsible to map between the original data items and the smaller table or in other words, we can say that the fixed  process, to convert a key into a hash key is known as a hash function.

• A hash function is used whenever access to the table is needed.

Hash function

Key______________________ > Index to array

• A good hash function satisfies (approx) the assumption of simple uniform Each key is equally likely to hash to any of the m slots, independently of where any other key has hashed to.

There are many hash functions approaches as follows

Division Method

Mapping a key K into one of m slots by taking the remainder of K divided by m.

                h (K) = K mod m

e.g., Let’s say, there are three numbers or keys that we want to map into the hash table of 10 slots

1 2 3 4 5 6,            1 2 3 4 6 7,  1 2 3 4 5 0

key 1                                          key 2                         key 3

• 123456% 10 =>            6

The he remainder is 6, so the key would be placed at 6th

index.

• 123467% 10               =>                     7

The remainder is 7, so the key would be placed at 7th index.

• 123450% 10 =>           0

   The remainder is 0, so the key would be placed at 0th index.

Mid- Square Method

 Mapping a key k into one of m slots, by getting the some middle digits from value K².

h(k) = K² and get middle (log _io m)

Folding Method

Divide the key K into some sections, besides the last section, have length. Then, add these sections together.       

• Shift folding
• Folding at the boundaries

h(K) = (section divided from K) by a  or  b                                                                                                                                                                             Key 123 20 03 241112 20, section length = 3

eg:

 Sections                       S₁                           S2                           S3                             S4                       S₅

(a) If we use shift folding method, then add all the sections

(b) If we use fuLding at the boundaries method, then

 

 

---

Sorting in Design and Analysis of Algorithm Study Notes with Example

Follow Us on Social Platforms to get Updated : twiter,  facebook, Google Plus

Learn Sorting in Handbook Series:  Click here