JAVA

What is Hashing and Hash Table

What is Hashing and Hash Table?

CPP Programming, JAVA, Python / By

Hashing and Hash Table

1)Hashing

Hashing is the process of mapping object data to a representative integer value using a function or algorithm.

This hash code (or simply hash) can then be used to narrow our quest when searching for the item on the map.

These hash codes are usually used to create an index at which the value is stored.

2)Hash Table

A hash table is a data structure that stores data associatively. Data is stored in an array format in a hash table, with each data value having its own unique index value. When we know the index of the desired data, we can access it very quickly.

As a result, it becomes a data structure in which insertion and search operations are extremely quick, regardless of the size of the data. Hash Tables use an array as a storage medium and use the hash technique to produce an index from which an element is to be inserted or located.

3)Features of HashTable

  • It works in the same way as HashMap, but it is synchronised.
  • In a hash table, a key/value pair is stored.
  • In Hashtable, we define an object that will be used as a key, as well as the value that will be associated with that key. The key is then hashed, and the resulting hash code serves as the index for storing the value in the table.
  • The default capacity of the Hashtable class is 11, and the loadFactor is 0.75.
  • HashMap does not support Enumeration, while Hashtable does not support fail-fast Enumeration.

4)Adding element in HashTable

When an entity is inserted into a Hash Table, its hash code is measured first, and the bucket in which it will be stored is determined based on that hash code.

Let us illustrate this with an example.

For instance, suppose we want to store some numbers in a Hash Table, i.e.

32 , 45 , 64 , 92 , 57 , 88 , 73

Internally, this Hash Table can use 10 buckets, i.e.

The Hash Code will be returned by our Hash Function.

HashCode=Element_value%10

This Hash code for,

32 will be 2

45 will be 5

64 will be 4

92 will be 2

57 will be 7

88 will be 8

73 will be 3

Now, each element’s hash code will be used to determine where that element will be stored, for example, 45 will be stored in bucket 5 since its hash code is 5. In the same way, all elements will be stored in the bucket that corresponds to their hash code.

5)Hashing Collisions

As we can see, the hash code for both 32 and 92 is the same, which is 2. In Hashing, this is referred to as Collision. Both components would be deposited in the same bucket if they collide.

6)Searching element in Hash Table

If we want to check for an element in a hash table, we must first calculate the hash code for that element. Then, using the hash code, we’ll go straight to the bucket where this element will be saved. Now, there may be several elements in that bucket; in that case, we’ll look for our element only in those elements.

Assume we want to find 45 in the hash table in the previous case.

Then we’ll measure the hash code, which will be 45 %10 = 5.

Then we’ll go straight to bucket no. 5 and search for the factor there.

7)Best Case Time Complexity in Hashing

From the viewpoint of searching, each bucket containing only one element in the Hash table is the best case scenario. In such a case, searching time would require the following effort:

The complexity of calculating hash codes is O(1)

If the bucket only contains one element, choosing that element from the bucket is a complex task O(1)

Consequently In the best case scenario, finding an element would be difficult O(1)

While the complexity of a collision, i.e. several elements in a bucket, will be O(no. of elements in bucket), it will be much less than the complexity of searching an element from a List, which will be O(n).

8)Worst Case Time Complexity in Hashing

The worst case scenario in hashing is when the Hash Function is not correctly implemented, resulting in the same hash code for several elements.

Assume the following is our hash function:

Hash code = given_element / 100

Then, in the preceding case, the hash code for all elements ( 32 , 45 , 64 , 92 , 57 , 88 , 73 ) will be 0. As a result, all elements will be saved in bucket 0.

Since all components are in the same bucket, complexity is at its highest in this case. As a result, the complexity will be O(n) since it must check for the appropriate element among all elements.

Related Programs:

Linked List Data Structure

C Programming, CPP Programming, JAVA, Python / By

Linked List Data Structure:

A linked list is a type of data structure that consists of a chain of nodes, each of which contains a value and a pointer to the next node in the chain.

The list’s head pointer points to the first node, and the list’s last element points to null. The head pointer points to null when the list is empty.

Linked lists can grow in size dynamically, and inserting and deleting elements from them is simple because, unlike arrays, we only need to change the pointers to the previous and next elements to insert or delete an element.

Linked lists are commonly used in the construction of file systems, adjacency lists, and hash tables.

Why Linked List?

Arrays can be used to store similar types of linear data, but they have the following limitations.
1) Because the array size is fixed, we must know the maximum number of elements in advance. Furthermore, regardless of usage, the allocated memory is always equal to the upper limit.
2) Inserting a new element in an array of elements is expensive because room must be made for the new elements, and existing elements must be shifted to make room, whereas in a linked list if we have the head node, we can traverse to any node through it and insert a new node at the required position.

Advantages of Linked Lists over arrays

1)Dynamic Data Structure:

  • Because the linked list is a dynamic data structure that can shrink and grow at runtime by deallocating or allocating memory, there is no need for initial size.
  • In contrast, in an array, an initial size must be declared, and the number of elements cannot exceed that size.

2) No Memory Wastage:

  • There is no memory waste because the size of a linked list can grow or shrink at runtime. Only the necessary memory is allocated.
  • In arrays, we must first initialize it with a size that we may or may not fully utilize. Thus, memory waste may occur.

3)Implementation:

A Linked List can be used to easily implement some very useful data structures such as queues and stacks.

4)Insertion and Deletion Operation:

Insertion and deletion operations in a Linked List are simple because there is no need to shift every element after insertion or deletion. Only the address in the pointers needs to be changed.

Disadvantages of Linked Lists over arrays

1)Memory Usage:

A linked list requires more memory than an array because it includes a pointer field in addition to the data field. The pointer field, like all other fields, requires memory to store the address of the next node.

2)Random Access:

To get to node an at index x in a linked list, we must first go through all the nodes before it. In the case of an array, however, we can use arr[x] to directly access an element at index x.

3)Reverse Traversal:

  • Reverse traversal is not possible in a singly linked list because each node stores only the address of the next node. Reverse traversal is possible in the case of a doubly-linked list, but it consumes more memory because we must allocate extra memory to store the previous pointer.
  • With the help of a for loop, we can perform a simple reverse traversal in arrays.

Representation:

A pointer to the first node of a linked list is used to represent it. The first node is referred to as the head. When the linked list is empty, the value of the head is NULL.
A list node is made up of at least two parts:
1) data (we can store integers, strings, or any type of data).
2) A pointer to the next node (or a reference to it) (connects one node to another)

Example Node of a Linked List