Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hash tables (Features (Hash function (Minimize collisions (Perfect hash…
Hash tables
Features
Collisions
Closed addressing
Chaining items
Linked list
Balanced binary search tree
Logarithmic time
Less storage
Preserve order
Open addressing
Linear probing
Linear search
Clustering
Plus 3 rehash
Quadratic probing
Double hashing
Hash function
Minimize collisions
Perfect hash function
Uniform distribution
Collision resolution
Easy to calculate
Data array
Load factor
Motivation
Very fast retrieval of data independent of collection size
Array access
Brute force access of an array is linear time
Direct index access is constant time
Best case complexity is constant time and worst case complexity is linear time
Implementation
Key is passed to a hashing function
An index is derived using the hashed key by factoring the array length
Value is stored in that index
Hash map
Operations
Insertion
Deletion
Retrieval
Applications
Database indexing
Compilers