Hash Tables

It is a collection of items which are stored in such a way as to make it easy to find them later.

Each position in the hash table is called slot, can hold an item and is named by an integer value starting at 0.

The mapping between an item and a slot where the item belongs in a hash table is called a Hash Function. A hash Function accepts a key and returns its hash coding, or hash value.

Assume we have a set of integers 54, 26, 93, 17, 77, 31. Our first hash function required to be as "remainder method" simply takes the item and divide it by table size, returning remainder as its hash value i.e.

   h item = item % (size of table) 
Let us say the size of table = 11, then
54 % 11 = 10   26 % 11 = 4    93 % 11 = 5
17 % 11 = 6	   77 % 11 = 0    31 % 11 = 9	

Now when we need to search any element, we just need to divide it by the table size, and we get the hash value. So we get the O (1) search time.

Now taking one more element 44 when we apply the hash function on 44, we get (44 % 11 = 0), But 0 hash value already has an element 77. This Problem is called as Collision.

Collision: According to the Hash Function, two or more item would need in the same slot. This is said to be called as Collision.

Figure: using a hash function h to map keys to hash-table slots. Because keys K2 and k5 map to the same slot, they collide.

Why use HashTable?

1. If U (Universe of keys) is large, storing a table T of size [U] may be impossible.
2. Set k of keys may be small relative to U so space allocated for T will waste.

So Hash Table requires less storage. Indirect addressing element with key k is stored in slot k with hashing it is stored in h (k) where h is a hash fⁿ and hash (k) is the value of key k. Hash fⁿ required array range.

Application of Hash Tables:

Some application of Hash Tables are:

1. Database System: Specifically, those that are required efficient random access. Usually, database systems try to develop between two types of access methods: sequential and random. Hash Table is an integral part of efficient random access because they provide a way to locate data in a constant amount of time.
2. Symbol Tables: The tables utilized by compilers to maintain data about symbols from a program. Compilers access information about symbols frequently. Therefore, it is essential that symbol tables be implemented very efficiently.
3. Data Dictionaries: Data Structure that supports adding, deleting, and searching for data. Although the operation of hash tables and a data dictionary are similar, other Data Structures may be used to implement data dictionaries.
4. Associative Arrays: Associative Arrays consist of data arranged so that n^th elements of one array correspond to the n^th element of another. Associative Arrays are helpful for indexing a logical grouping of data by several key fields.