Hashing

Direct Address Table

Direct Address Table is a data structure that uses arrays to store the data. In the Direct Address Table, the element key values are used as their indexes in the array to store the record by the technique known as Direct Addressing.

So now, the question arises what is Direct Addressing?

It is a technique in which we make use of direct address tables to map their values with their keys. 

It uses the keys as indexes of the buckets and then stores the values at those bucket locations.

Though Direct Addressing does facilitate fast searching, fast inserting, and fast deletion operations, at a cost, Direct Address Table cannot handle collisions.

If a different data for the same key needs to be inserted in the table, then it won’t happen here. 

Therefore, DAT cannot be used in the real world practically, and this function of DAT makes it different from Hash Tables.

Hash Tables overcome the major disadvantage of DAT by resolving hashing collisions by using hash function through various hashing techniques such as:

  • Linear Probing
  • Quadratic Probing
  • Chaining

Now, what is Hash Function?

A hash function is a function that can be used to map data of arbitrary size to fixed-sized values. The values returned by hash functions are called hash values.

Hash functions should be chosen carefully because it minimizes the total number of collisions as much as possible.

Now coming back to the process of Direct Address Table:

Let’s take an example,

We have a problem searching for an element with a value of 15 in the range of [0,100000].

Now using binary search we can solve this problem in O(Nlogn) time complexity, where N is used for the iteration process, but with DAT we can solve this problem in O(N) where N is for the iteration process, searching will take O(1) time complexity.

Create an array of size (100000 + 1) and initialize every record with value 0.

Now iterate over the array, and update the record with “1” for every element encountered.

After this step check if DAT[15] is equal to 0 or not.

If it is then, 15 is present else 15 is not present.

Algorithm of DAT functions

SEARCH (T, K) // O(1) operation

return T[k];

INSERT (T, x) // O(1) operation

T[x.key] = x;

DELETE (T, x) // O(1) operation

  T[x.key] = NIL;

Advantages of Direct Address Table:

  • Insertion in O(1) time: Inserting an element in a direct address table is the same as inserting an element in an array, hence we can do that in O(1) time as we already know the index(via key).
  • Deletion in O(1) time: Deleting an element from a direct address table is the same as deleting from an array, hence the O(1) time.
  • Searching in O(1) time: Searching an element takes linear time(O(1)) as we can easily access an element in an array in linear time if we already know the index of that element.

Disadvantages of Direct Address Table:

  • It is not recommended using the direct address table if the key values are very large.
  • It cannot handle the case where two keys are equal and contain different data.

Special thanks to Sagar Srivastava for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article