This document summarizes key aspects of hash tables and hash functions. It discusses how hash tables store key-value pairs using a hash function to map keys to indices. Common hash functions include division, folding, and mid-square methods. Collisions can occur when different keys map to the same index, and techniques like open addressing, closed addressing, linear probing and double hashing are used to resolve collisions. The document provides examples and explanations of these hash table and hash function concepts.
This document summarizes key aspects of hash tables and hash functions. It discusses how hash tables store key-value pairs using a hash function to map keys to indices. Common hash functions include division, folding, and mid-square methods. Collisions can occur when different keys map to the same index, and techniques like open addressing, closed addressing, linear probing and double hashing are used to resolve collisions. The document provides examples and explanations of these hash table and hash function concepts.
This document summarizes key aspects of hash tables and hash functions. It discusses how hash tables store key-value pairs using a hash function to map keys to indices. Common hash functions include division, folding, and mid-square methods. Collisions can occur when different keys map to the same index, and techniques like open addressing, closed addressing, linear probing and double hashing are used to resolve collisions. The document provides examples and explanations of these hash table and hash function concepts.
This document summarizes key aspects of hash tables and hash functions. It discusses how hash tables store key-value pairs using a hash function to map keys to indices. Common hash functions include division, folding, and mid-square methods. Collisions can occur when different keys map to the same index, and techniques like open addressing, closed addressing, linear probing and double hashing are used to resolve collisions. The document provides examples and explanations of these hash table and hash function concepts.
2 2 Hash Table A Hash table is a data structure that stores some information, and the information has basically two main components, i.e., key and value. The hash table can be implemented with the help of an associative array. The efficiency of mapping depends upon the efficiency of the hash function used for mapping. Example For example, suppose the key value is John and the value is the phone number, so when we pass the key value in the hash function shown as below: Hash(key)= index; When we pass the key in the hash function, then it gives the index. Hash(john) = 3; The above example adds the john at the index 3. Drawback of Hash function A Hash function assigns each value with a unique key. Sometimes hash table uses an imperfect hash function that causes a collision because the hash function generates the same key of two different values. Hashing • In Hashing technique, the hash table and hash function are used. Using the hash function, we can calculate the address at which the value can be stored. • The main idea behind the hashing is to create the (key/value) pairs. If the key is given, then the algorithm computes the index at which the value would be stored. It can be written as: Index = hash(key) Continue.. Ways Of Calculating The Hash Function There are three ways of calculating the hash function: • Division method • Folding method • Mid square method Division Method In the division method, the hash function can be defined as: h(ki) = ki % m; where m is the size of the hash table. For example, if the key value is 6 and the size of the hash table is 10. When we apply the hash function to key 6 then the index would be: h(6) = 6%10 = 6 The index is 6 at which the value is stored. Collision When the two different values have the same value, then the problem occurs between the two values, known as a collision. In the above example, the value is stored at index 6. If the key value is 26, then the index would be: h(26) = 26%10 = 6 Therefore, two values are stored at the same index, i.e., 6, and this leads to the collision problem. To resolve these collisions, we have some techniques known as collision techniques. The following are the collision techniques: • Open Hashing: It is also known as closed addressing. • Closed Hashing: It is also known as open addressing. Open Hashing In Open Hashing, one of the methods used to resolve the collision is known as a chaining method. Closed Hashing In Closed hashing, three techniques are used to resolve the collision: • Linear probing • Quadratic probing • Double Hashing technique Linear Probing Linear probing is one of the forms of open addressing. As we know that each cell in the hash table contains a key-value pair, so when the collision occurs by mapping a new key to the cell already occupied by another key, then linear probing technique searches for the closest free locations and adds a new key to that empty cell. In this case, searching is performed sequentially, starting from the position where the collision occurs till the empty cell is not found. Quadratic Probing
• In case of linear probing, searching is performed
linearly. In contrast, quadratic probing is an open addressing technique that uses quadratic polynomial for searching until a empty slot is found. • It can also be defined as that it allows the insertion ki at first free location from (u+i2)%m where i=0 to m-1. Double Hashing Double hashing is an open addressing technique which is used to avoid the collisions. When the collision occurs then this technique uses the secondary hash of the key. It uses one hash value as an index to move forward until the empty location is found. References WEB LINKS • https://www.geeksforgeeks.org/data-structures/ • https://www.javatpoint.com/data-structure- tutorial • https://www.tutorialspoint.com/data_structures_al gorithms/index.htm VIDEO LINK • https://www.youtube.com/watch?v=2E54GqF0H4s THANK YOU
