# 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.

## 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 K2.

h(k) = K2 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                       S1                           S2                           S3                             S4                       S5

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

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