search

real-logic / agrona

High Performance data structures and utility methods for Java
Apache License 2.0
2.9k stars 403 forks source link

Add single writer concurrent hash maps #23

Open mjpt777 opened 9 years ago

mjpt777 commented 9 years ago

Open addressing hash maps that have only a single mutator thread but many reader threads.

tmontgomery commented 9 years ago

There are some interesting aspects of Robin Hood hashing that might be good to include. http://sebastiansylvan.com/2013/05/08/robin-hood-hashing-should-be-your-default-hash-table-implementation/

mjpt777 commented 9 years ago

Robin Hood hashing can be a good approach. However I would not use tombstones like in how your link works. I've found for high removal rates that tombstones degrade lookup performance.

bobymicroby commented 9 years ago

@tmontgomery @mjpt777 Here is an interesting paper on replacing Hood's tombstones with 'backward shift deletion' : http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/

mjpt777 commented 9 years ago

@bobymicroby Thanks I'll take a look.

loveyoupeng commented 7 years ago

any plan to add a Object2IntHashMap, it could be used as a pojo counter?

mjpt777 commented 7 years ago

@loveyoupeng We have no immediate need for this but would happily accept a PR for this.

loveyoupeng commented 7 years ago

@mjpt777 i create a copy cat version of Object2InthashMap as a PR, Please help to review