Data Structures For Storing Chains
1. Linked lists
- Search: O(l) where l = length of linked list
- Delete: O(l)
- Insert: O(l)
- Not cache friendly
2. Dynamic Sized Arrays ( Vectors in C++, ArrayList in Java, list in Python)
- Search: O(l) where l = length of array
- Delete: O(l)
- Insert: O(l)
- Cache friendly
3. Self Balancing BST ( AVL Trees, Red-Black Trees)
- Search: O(log(l)) where l = length of linked list
- Delete: O(log(l))
- Insert: O(log(i))
- Not cache friendly
- Java 8 onwards use this for HashMap
Related Post: Hashing | Set 1 (Introduction)
Next Post:
Open Addressing for Collision Handling
Separate Chaining Collision Handling Technique in Hashing
Separate Chaining is a collision handling technique. Separate chaining is one of the most popular and commonly used techniques in order to handle collisions. In this article, we will discuss about what is Separate Chain collision handling technique, its advantages, disadvantages, etc.