Profile cover photo
Profile photo
Roman Leventov
620 followers
620 followers
About
Posts

Post has attachment
Add a comment...

Post has attachment
+Rajiv Kurian Some notes on RH:

your keys are primiitives, you should either:
- store hash codes along with the keys, that could nearly double HT footprint
- when walking through a collision chain, re-compute hash codes of the stored keys, to compare "distances" of that keys with the current key (searched/inserted)
- omit distance comparison, when searching for a key without plans to insert (when intert, you should compare distances, otherwise this is just a plain linear probing)

The first option is the intended Robin-Hood design, when keys are complex objects with expensive hash code computation. In C/C++ world, where everyone has own strings, this is a perfect solution e. g. to move hash code to the hash table, out of the string Object. (In Java, we have that hash code field baked into the String class). But, for scalar primitive keys, this approach is very doubtful.

The second option slows down insertions, deletions and lookups.

The third option makes search no better than search in simple linear probing HT, because Robin Hood reduces chain lengths, but the chains could be adjacent without gaps. I think, the average expected probes would be the same as in simple linear probing. (But I'm not sure. Requires more deep thinking).

See implementation and benchmarks near https://github.com/OpenHFT/Koloboke/blob/0b4898817f41b0820e0d9a2839fb593f112f9edc/benchmarks/research/src/main/javaTemplates/net/openhft/koloboke/collect/research/hash/NoStatesRHoodSimpleHashCharSet.java

Add a comment...

Post has attachment
Memcached design and comparison with Redis
Memcached is a simple in-memory key-value store, which primary use case is shared cache for several processes within the server, or for occasionally starting and dying processes (e. g. how PHP processes behind Apache server used to do). Memcached gained inc...
Add a comment...

Post has attachment
Neo4j architecture
This post compiles some information about architecture of Neo4j , the leading graph database. There are three main kinds of primitives in Neo4j: nodes , relationships and properties . Nodes are connected via relationships. Properties could be attached to bo...
Add a comment...

Post has attachment
Redis core implementation
I hope Redis doesn't need long introduction for readers of the post in a blog about key-value stores, because Redis is by far the most popular key-value store (according to db-engines.com ). This post surveys Redis internal implementation: data structures, ...
Add a comment...

Post has attachment
Persisted off-heap Map implementation from one-nio
one-nio  is a group of dependent on each other re-implementations of many systems, required for building servers in Java: serialization, sockets, I/O, pooling, protocols, off-heap caching, and more: see the list of all modules with brief descriptions . The ...
Add a comment...

Post has attachment

Post has attachment

Post has attachment
Add a comment...

Post has attachment
Wait while more posts are being loaded