Downloaded 95 times
Hash table in data structure and algorithm
- 1. Hash Table Presenting to:Prof M.Arshad Class: Analysis of Algorithms Department of Computer Science
- 2.
- 3. Searching: Time Complexity LinkList O(n) Array (unsorted) O(n) Aamir sohail 3
- 4. Searching: Time Complexity Array(Sorted) O(log2 n) Binary Search tree O(log2 n) Aamir sohail 4
- 5. Searching: Time Complexity HashTable O(1) Aamir sohail 5
- 6. Example 1 • Tostore the key/values pair, we can use simple array like data structure where keys can be used as index to store values. Aamir sohail 6
- 7. Example 2 • Wehave 10 complaints indexed with a number ranges from 0 to 9 ( say complaint number) • We have an array of 10 spaces to store 10 complaints • Here we can use complaint number as key and it is nothing but index number in an array. Aamir sohail 7
- 8. Example 3 • Wehave 5 students to store in table (nothing but a custom array). Student will be assigned a Roll no, so roll no is the key value to identify a student. • Assume that the table (array) has 10 slots available. • Also assume that a roll no is a 4 digit number Aamir sohail 8
- 9. Terms • Hash Table -Mostly it is an array to store dataset. • Hash Function - a hash function is any function that can be used to map dataset. • Hashing - in hashing large keys are converted in to small ones by using hash function and then the values are stored in hash table. Aamir sohail 9
- 10. Hash Functions • Ahash function usually means a function that compresses. Meaning the output is shorter than the input. • A hash function is any function that can be used to map data of arbitrary size to data of fixed size. Aamir sohail 10
- 11. Parameters of goodhash function • Easy to Compute • Minimize Collision Aamir sohail 11
- 12. Perfect Hashing • Perfecthashing maps each valid input to a different hash value ( No Collision ) Aamir sohail 12
- 13. Hash function example inthash(int x) { return(x%10); } Aamir sohail 13
- 14. Hash Function • Agood hash function to use with integer key values is the mid-square method • The mid-square method squares the key value, and then takes out the middle r bits of the result. Aamir sohail 14
- 15. Collision • A situationwhen the resultant hashes for two or more data elements in data set, maps to the same location in the table, is called a hash collision. • In such situation two or more data elements would qualify to be stored/mapped to the same location in hash table. Aamir sohail 15
- 16. Solution for HashCollision • Two types of solutions for hash collision - Open Hashing (chaining) - Closed Hashing (open Addressing) • The difference between the two has to do with - whether collisions are stored outside the table (open hashing), or - whether collisions result in storing one of the records at another slot in the table (closed hashing). Aamir sohail 16
- 17. Open Hashing • Thesimplest form of open hashing defines each slot in the hash table to be the head of linked list. • All records that hash to a particular slot are placed on that slot’s linked list. Aamir sohail 17
- 18. Closed Hashing • LinearProbing • Quadratic Probing • Double Hashing Aamir sohail 18
- 19. Any Question aboutthe Hashing Hash Function & Hash table? Aamir sohail 19
- 20. References Introduction to Algorithms(Second Edition) - by: Thomas H.Cormen Basics of Data Structure Video Lectures Aamir sohail 20