Hashing  

Hash function

Hash function: h(key) = key % table_size

Table size: 5

Keys: 9, 7, 13, 11, 5, 8, 15

Hash table:

index | bucket
-------|--------
0     | []
1     | [9]
2     | [7]
3     | [11, 13]
4     | [5, 8, 15]

As you can see, the keys are hashed into the hash table using the hash function h(key) = key % table_size. The keys are then stored in linked lists in the hash table. The linked lists are used to store the keys that have the same hash value.

For example, the key 9 has a hash value of 1, so it is stored in the first bucket of the hash table. The keys 7 and 13 also have a hash value of 1, so they are stored in the same bucket.

The keys 5, 8, and 15 have a hash value of 4, so they are stored in the same bucket.

Difference between processing using hash function and hashtable (using separate chaining)

• Processing using hash function: In this approach, the keys are hashed into the hash table using the hash function. The keys are then stored in the hash table at the index of their hash value. This approach is simple and efficient, but it can lead to collisions, which occur when two or more keys have the same hash value.
• Hashtable (using separate chaining): In this approach, the keys are hashed into the hash table using the hash function. The keys are then stored in linked lists in the hash table. The linked lists are used to store the keys that have the same hash value. This approach does not suffer from collisions, but it is more complex and less efficient than the processing using hash function approach.

differences between the two approaches:

Feature	Processing using hash function	Hashtable (using separate chaining)
Collisions	Can occur	Does not occur
Complexity	Simple	Complex
Efficiency	Efficient	Less efficient

• Hashing is a technique for storing and retrieving data in a way that is efficient and fast.
• Hash tables are data structures that use hashing to store data.
• Hash functions are functions that take a key as input and return an index into the hash table.
• Collisions occur when two or more keys have the same hash value.
• There are two main ways to deal with collisions:
  • Separate chaining: This approach stores all keys with the same hash value in a linked list.
  • Linear probing: This approach searches for the next available slot in the hash table when a collision occurs.

Here are some of the advantages of using hashing data structures:

• Efficiency: Hashing can be very efficient for storing and retrieving data.
• Speed: Hashing can be very fast for storing and retrieving data.
• Space: Hashing can be very space-efficient for storing data.

Here are some of the disadvantages of using hashing data structures:

• Collisions: Collisions can occur, which can slow down the performance of the hash table.
• Heterogeneous data: Hashing is not as efficient for storing heterogeneous data as it is for storing homogeneous data.
• Hash functions: Hash functions can be difficult to design, and they can be sensitive to the distribution of the data.

Overall, hashing data structures are a powerful tool for storing and retrieving data. They are efficient, fast, and space-efficient. However, they can be sensitive to the distribution of the data and collisions can occur.