# 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^{2}.

*h(k) = K ^{2}* 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** _{1}* S2 S3 S4 S

_{5}

**(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 **

** **