Concurrent HashMap에 대한 연구

[codingskynet]

논문을 모아두거나, 이것저것 정리해서 아이디어를 정리해놓는 이슈

[codingskynet]

• https://ldhulipala.github.io/readings/split_ordered_lists.pdf
• https://lrita.github.io/images/posts/datastructure/Dynamic-Sized-Nonblocking-Hash-Tables.pdf
• https://www.sjalander.com/research/mcc2016/MCC2016_paper_17.pdf

[codingskynet]

HashMap은 Tree와는 달리 rebalance가 전혀 필요없기 때문에, 간단하게 Lock-Free로까지 만들어볼 수 있는 모양인 거 같다. 일단, 개략적으로 생각해둔 것은 hash key의 크기는 u64로 하고 key collision시에는 일단 cuckoo hashmap?처럼 만들어볼까 싶기도 하다. 영 느리면, chaining에서 concurrent list/avl tree 정도로 취해볼 수 있지 않을까.

[codingskynet]

일단은 concurrent list 구현해서 써먹는게 간단하고 적당히 효율적일 거 같긴 하네.