Design: A Thread-safe Hashmap
Similar Posts:
| Name | Summary |
|---|---|
| Typical methods of hashmap | get, update, delete, exists, size |
| Avoid frequent write locking | Instead of lock the whole array, lock at smaller granularity of segments |
| To speed up lookup of conflicts | Change linked list to balanced binary search tree |
| Reference | Link: Internal Working of HashMap in Java |
| Reference | Link: How ConcurrentHashMap Works Internally in Java |
| Reference | YouTube: Advanced Topics in Programming Languages: A Lock-Free Hash Table |
Q: How support basic hashmap?
- Eventually store data of hashmap in an array
- Resize
Q: Use case of concurrent hashmap?
A:
Q: How to deal with hashing conflict?
A:
- Linked list: Open chain
- When hash conflict, storing conflicted items in balanced BST, instead of a linked list.
Q: Would there be write conflicts or dirty reads?
- Lock when updating the map
- Striped internal locks: When updating an item, lock the minimum. Divide the array into small segments. Change one big array lock to multiple small segment locks.
- No locking for reading values
Q: How hashmap extend the capacity? How to resize?
A:
- Lock the whole array.
- Create a bigger array, then deep copy
- Relase the lock
Q: How ConcurrentHashMap is implemented in popular programming languages?
A:
Share It, If You Like It.