Data Structures - Introduction
- Abstract data types
- Linear Data Structures
- Linked List Introduction
- Single Linked List
- Stacks using Array
- Stacks using linkedlist
- Queues using array
- Queues using linkedlist
- Stack Applications
- Infix to Postfic Converstion
- Postfix Evaluation
- Dictionaries
- Introduction to Dictionaries
- Linear list representation
- Skip list representation
- Hash Table
- Introduction Hash Table
- Hash functions
- Collision Resolution
- Separate chaining
- Open addressing
- Rehashing
- Extendible hashing
- Trees
- Introduction to Tree
- Binary trees Representation
- Binary tree traversals
- Binary Search Tree
- AVL Tree
- Red Black Tree
- Splay Tree
- B Tree
- B+ Tree
- Comparison of Trees
- Graphs
- Introduction to Graph
- Graph Representation
- Breadth-First Search
- Depth-First Search
- Sorting
- Quick Sort
- Merge Sort
- Heap Sort
- Pattern Matching
- Introduction to pattern Matching
- Brute force Pattern Matching
- Boyer–Moore Pattern Matching
- KMP Pattern Matching
- Tries
- Introduction to Tries
- Standard Trie
- Compressed tries
- Suffix Trie
Hash functions
A hash function is a mathematical function that converts a given input value into a resulting hash value. A hash function can be used to generate a checksum for data, index data in a database, or encrypt data. In data structures, a hash function is used to calculate the hash value of a key, which is then used to store and retrieve the corresponding data.
Definition of hash function
A hash function is a function that takes an input (or 'key') and returns a fixed-size string of bytes. The output is typically a "hash code" or "hash value."
Purpose of hash function
The primary purpose of a hash function in data structures like hash tables is to distribute keys evenly across an array, minimizing the likelihood of collision (where two keys hash to the same index).Properties of Good Hash Functions
- Deterministic: The same input should always produce the same hash value.
- Fast Computation: It should be quick to compute the hash value for any given input.
- Uniform Distribution: It should uniformly distribute the data across the entire set of possible hash values to minimize collisions.
- Minimize Collisions: While collisions are inevitable, a good hash function should minimize them. Different keys should hash to different values as much as possible.
- Avalanche Effect: A small change to the input should produce a significantly different hash value.
Types of Hash Functions
Division Method
Takes a key and divides it by a prime number, then uses the remainder as the hash value. This method is simple but effective for certain types of keys.
Multiplication Method
Multiplies the key by a constant, extracts a certain portion of the resulting number, and uses it as the hash value.
Folding Method
Splits the key into parts, adds them together, and then uses the sum or a portion of it as the hash value.
Challenges in Designing Hash Functions
- Handling Collisions: When two keys hash to the same index, a strategy is needed to resolve this (e.g., chaining, open addressing).
- Choosing the Right Hash Function: The choice depends on the type of keys and the expected key distribution. No single hash function is perfect for all scenarios.
- Avoiding Clustering: Poor hash functions can lead to clustering, where many keys hash to the same or nearby indices, leading to performance degradation.
- Security Concerns: In cryptographic applications, hash functions need additional properties like resistance to pre-image attacks, which are beyond the scope of typical data structure usage.
Next Topic :Collision Resolution