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?

  1. Eventually store data of hashmap in an array
  2. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *