Skip to content

Implementation of a Robinhood hashmap backed by an FX hasher

License

Notifications You must be signed in to change notification settings

null-char/rhmap

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

18 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Robinhood Hashmap built on top of the FX hasher

Implementation of a basic Robinhood hashmap where the idea is to keep an FCFS approach but with the added condition that we'll evict an entry if it is "rich" (rich entry PSL is less than current entry PSL) and then reinsert the evicted entry with the same rules in place. We'll essentially have an arrangement such that for an entry to be pushed some distance d, it'll have been displaced by some other entry that travelled at least d - 1. An additional advantage of this rule being enforced is that we can stop probing on lookup based on this. If we walk d steps and come across an entry that is displaced by some distance less than d from its home, we can stop the probing.

About

Implementation of a Robinhood hashmap backed by an FX hasher

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages