Introduction –
One popular data structures for the implementation of associate arrays are hash tables. To analyze the asympotic efficiency of hash tables we have to explore a new point of view, that of average case complexity. Hashing is a technique use for storing and retrieving information as quickly as possible. It is use to perform optical searches and is useful in implementing symbol tables.
Why Hashing ?
In the trees we saw that balanced binary search trees support operations such as insert, delete and search in O(logn) time. In applications, if we need this opearations in O(1), then hashing provides a way. Remenber that worst case complexity of hashing is O(n), but it gives O(1) on average
Hash Table ADT –
The hash table structure is an unordered collection of association between key and a data value. The keys in hash table are all unique; so that there is a one-to-one relationship between key and value. The operation are given below.
- Hash table: Creates a new hash table
- Get: Searches the hash table with the key and return the value if it finds the element with the given key.
- Put: Inserts a new key-value pair into hash table.
- Delete: Deletes a key-value pair from hashtable.
- Delete hashtable: Deletes the hash table.
Understanding Hashing –
In simple terms we can treat array as a hash table. For understanding the use of hashtable, let us condsider the following examples: Give an algorithm for printing the first repeated character if there are duplicated elements in it. Let us think about the possible solutions.
The simple and brut force way of the solving is: given a string, for each character check wheather that character is repeated or not. The time complexity of these approach is O(n^2) with O(1) space complexity.
Now let us find a better solution of possible character is 256 (for simplicity assume ASCII characters only.)Crate an array of size 256 and initialize it with all zeros. For each of the input characters goto the corresponding position and increment its count. Since we are using arrays, it takes constant time for reaching any location. While scanning theinput, if we get a character whose counter is already one then we can say that the character is one which is repeating for the first time.
