Design: A Thread-safe Hashmap
|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
Q: Use case of concurrent hashmap?
Q: How to deal with hashing conflict?
- 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?
- Lock the whole array.
- Create a bigger array, then deep copy
- Relase the lock
Q: How ConcurrentHashMap is implemented in popular programming languages?