Hashing Implementation

Q1 Why do we need hashing ?What’s the advantage of hashing?

Hashing is a way to store data into some data structure (generally Hash Table is used) in such a way that the basic operations on that data i.e. the insertion, deletion ,and searching can be performed in O(1) time.

Suppose we want to store N numbers and range of that numbers can be 1≤element≤10⁷. So what data structure can we use to store this array of numbers .And we want following operations to perform efficiently.

Insertion.

Deletion.

Searching.

We can thing of using following Data structures .

1. Unsorted Array: If we use this, the Time Complexity of above operations will be : (a)Insertion — O(1) :-We simple insert data directly at end of array , (b) Deletion — O(N):- We search required data in the array or we iterate over the array and delete that data . (c) Searching — O(N) :- We search data in the entire array by traversing.
2. Sorted Array : If we use this, then the TC of above operation will be : (a) Insertion — O(N):- Here we have to maintain the sorting order and we have to search the correct position of data which we are inserting in sorted array . (b) Deletion -- O(N):- We have to search for the data which we are deleting it from array .So, that’s why TC will be O(N). (c )Searching — O(log(N)) :- We can use divide and conquer algorithm i.e. Binary Search for searching the data, so TC for BS is O(logN) .
3. Singly Linked List(SLL) : It’s time complexity for the above operations will be same as Unsorted Array .
4. Sorted Singly Linked List(SSLL): As we can’t apply Binary Search in SSLL ,so TC for Searching will be O(N) . Insertion TC will be also O(N) and Deletion will also have TC as O(N) because we have to maintain to sorting order.
5. Binary search Trees (BST): BST is a special type of binary tree in which left child of a node has value less than the parent and right child has value greater than parent.

1. Searching: For searching element 1, we have to traverse all elements (in order 3, 2, 1). Therefore, searching in binary search tree has worst case complexity of O(n). In general, time complexity is O(h) where h is height of BST.

• Insertion: For inserting element 0, it must be inserted as left child of 1. Therefore, we need to traverse all elements (in order 3, 2, 1) to insert 0 which has worst case complexity of O(n). In general, time complexity is O(h).
• Deletion: For deletion of element 1, we have to traverse all elements to find 1 (in order 3, 2, 1). Therefore, deletion in binary tree has worst case complexity of O(n). In general, time complexity is O(h).

Note : Height of BST : If there are n nodes in a binary search tree, maximum height of the binary search tree is n-1 and minimum height is floor(log(N)).

Best case TC — O(log(N)) and Worst case TC — O(N) (in case of skewed BST)

6. BBST or AVL Tree : AVL tree is binary search tree with additional property that difference between height of left sub-tree and right sub-tree of any node can’t be more than 1. For example, BST shown in Figure 1 is not AVL as difference between left sub-tree and right sub-tree of node 3 is 2. However, BST shown in Figure 2 is AVL tree.

• Searching: For searching element 1, we have to traverse elements (in order 5, 4, 1) = 3 = log2n. Therefore, searching in AVL tree has worst case complexity of O(log2n).
• Insertion: For inserting element 12, it must be inserted as right child of 9. Therefore, we need to traverse elements (in order 5, 7, 9) to insert 12 which has worst case complexity of O(log2n).
• Deletion: For deletion of element 9, we have to traverse elements to find 9 (in order 5, 7, 9). Therefore, deletion in binary tree has worst case complexity of O(log2n).

7 . DAT’s (Direct Access Tables ): We will make a big array and use data or element as index in the array. We can store data here ,Time Complexity wise this solution is the best among all ,we can do all operations in O(1) time ,since we have to go to particular index that is actually our data point and see if it is present or not for searching and for deletion we have to simply mark it as -1 and for insertion we simply go to that index ,which is data here and mark it as 1.

Note: Limitations of DAT.

a) Most of the programming language may not store N digit number ,there some range up to which numbers can be stored .

b) There is a lot of space wastage in DAT’s.

Idea is if we can map the given data to a smaller index value ,then we can use DAT ‘s. (Hashing) . Hashing is an Improvement over DAT.

I’ll explain rest of concept in next blog .

Thank you for your time!.