In This Article.
I can explain the concept of hashing and related terminologies, properties of good hash functions, hash functions such as division function, MID square, and folding methods, as well as collision resolution techniques including open addressing and chaining.
**4.1 Concept of Hashing**
Hashing is a technique used in computer science to store and retrieve data in a fast and efficient manner. It involves the use of a hash function to map keys to specific positions in a data structure called a hash table. Hashing is widely used in data retrieval and storage applications such as databases, search engines, and compilers.
**4.2 Terminologies**
Here are some common terminologies used in hashing:
- Hash Table: A data structure that stores keys and their corresponding values in an array using a hash function to determine the position of each key-value pair.
- Hash Function: A function that takes a key as input and returns an index or a hash address, which is used to determine the position of the key-value pair in the hash table.
- Bucket: A slot in the hash table where a key-value pair is stored.
- Collision: Occurs when two or more keys are mapped to the same hash address.
- Synonym: A key that maps to the same hash address as another key is called a synonym.
- Overflow: A situation that occurs when all the buckets in a hash table are full, and a new key-value pair cannot be inserted.
**4.3 Properties of Good Hash Functions**
A good hash function should satisfy the following properties:
- Uniformity: The hash function should uniformly distribute the keys across the hash table, ensuring that each bucket has an equal chance of being selected for each key.
- Deterministic: The hash function should produce the same hash address for the same key every time.
- Efficiency: The hash function should be fast and computationally efficient.
- Collision Avoidance: The hash function should minimize the chances of collision as much as possible.
**4.4 Hash Functions**
There are different types of hash functions, including the following:
- Division Function: A simple hash function that takes the key, divides it by the table size, and returns the remainder as the hash address.
- MID Square: A hash function that takes the key, squares it, and returns the middle digits as the hash address.
- Folding Methods: A hash function that takes the key, breaks it into smaller parts, and adds the parts together to form the hash address.
**4.5 Collision Resolution Techniques**
There are two main techniques for resolving collisions in a hash table:
**4.5.1 Open Addressing**
Open addressing involves probing for an empty bucket when a collision occurs. There are different types of open addressing:
- Linear Probing: A method that looks for the next available bucket in a linear manner, by checking the next bucket until an empty bucket is found.
- Quadratic Probing: A method that looks for the next available bucket using a quadratic function that depends on the number of collisions.
- Rehashing: A method that uses a secondary hash function to calculate a new hash address if a collision occurs.
**4.5.2 Chaining**
Chaining involves creating a linked list of key-value pairs in each bucket when a collision occurs. There are different types of chaining:
- Coalesced: A method that creates a single linked list for all the keys in the hash table.
- Separate Chaining: A method that creates a separate linked list for each bucket in the hash table.
I hope this explanation helps you understand the concept of hashing and related terminologies, properties of good hash functions, hash functions, and collision resolution techniques.
0 Comments