# Unit-6 Hashing- Data Structure | BCA 3rd year 2023

**Unit-6 Hashing- Data Structure | BCA 3rd year 2023-**Hello everyone welcome to the pencilchampions.com website. This website provide Hashing unit 6 BCA 2nd Year and b.tech student. Thankyou for visiting in pencilchampions.com

# Introduction of Hashing

- Hashing is the process of mapping large amount of data item to smaller table with the help of hashing function.
- Hashing is a technique or process of mapping keys and values into the has table by using a hash function
- It is used to facilitate the next level searching method when compared with the linear or binary search.
- Constant time O(1) means the operation does not depend on the size of the data.
- Hashing is used with a database to enable items to be retrieved more quickly.
- It is used in the encryption and decryption of digital signatures.

## There are three component of hashing

- Key
- Hash Table
- Hash function

### Advantage of hashing

- Key value support
- Security
- Memory use reduction
- Efficiency

## Heap sort

- Heap sort is a comparison based sorting technique based on the binary heap data structures
- It is same to the selection sort.
- We first find the minimum element and place the minimum element at the beginning.

### Advantages

- Simplicity
- Memory usage

## What is Hash Function

- A fixed process converts a key to a hash key is known as a
**Hash Function.** - This function takes a key and maps it to a value of a certain length which is called a
**Hash value**or - Hash value represents the original string of characters, but it is normally smaller than the original.
- It transfers the digital signature and then both hash value and signature are sent to the receiver. Receiver uses the same hash function to generate the hash value and then compares it to that received with the message.
- If the hash values are same, the message is transmitted without errors.

**Read external link-**https://bcastudyguide.com/unit-6-sorting-technique/

## What is Hash Table

- It contains value based on the key.
- The above figure shows the hash table with the size of n = 10. Each position of the hash table is called as
**Slot**. In the above hash table, there are n slots in the table, names = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Slot 0, slot 1, slot 2 and so on. Hash table contains no items, so every slot is empty. - The hash function takes any item in the collection and returns an integer in the range of slot names between 0 to n-1.

**Read more- https://bcastudyguide.com/unit-6-sorting-technique/**

- Suppose we have integer items {26, 70, 18, 31, 54, 93}. One common method of determining a hash key is the division method of hashing and the formula is :

- Hash Key = Key Value % Number of Slots in the Table

## Sorting Technique

- Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.

**Insertion sort**

- Insertion Sort arrange N elements of array by the inserting particular item in a particular place such a way that the item are in the sorted order.

**Selection sort**

- Selection sort is a simple sorting algorithm.
- Selection sort arrange N elements of array by placing the smallest element in proper position in case of ascending order arrangement.
- This algorithm is not suitable for large data sets as its average and worst case complexities are of Ο(n
^{2}), where**n**is the number of items.

## Merge sort

- Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms.
- Merge sort first divides the array into equal halves and then combines them in a sorted manner.

## Searching

- Searching is the process of finding a given value position in a list of values.
- It decides whether a search key is present in the data or not.
- It is the algorithmic process of finding a particular item in a collection of items.

### Searching Techniques

- Sequential search
- Binary search

**Sequential Search**

- Sequential search starts at the beginning of the list and checks every element of the list.
- It is a basic and simple search algorithm.
- Sequential search compares the element with all the other elements given in the list.

**Binary Search**

- It is a fast search algorithm with run-time complexity of O(log n).
- Binary search works on the principle of divide and conquer.
- This searching technique looks for a particular element by comparing the middle most element of the collection.
- It is useful when there are large number of elements in an array.
**For example,**if searching an element 25 in the 7-element array, following figure shows how binary search works:- Binary searching starts with middle element. If the element is equal to the element that we are searching then return true. If the element is less than then move to the right of the list or if the element is greater than then move to the left of the list. Repeat this, till you find an element.

### Discover more from

Subscribe to get the latest posts sent to your email.