Re:In-memory hash tree implementation
by _ak on Sunday March 27, 2016 @09:58AM
(#11369953)
Assuming that the underlying implementations of the Item interface will use some form of hash algorithm to determine the return value of the Key method, how does this deal with hash collisions of two distinct items?
[ Parent
| on HN ]
It doesn't. It's not a hash, it's the actual key.
Yep.
For this case, conflicts can be solved via the traditional separate chaining strategy, to open a list on the Item.
This htree was originally implemented as the indexing container to store key-value poisition informations for the bitcask storage engine. And string keys are not stored in the htree to save more memory. Collisions of two string keys are distinguished by checking the disk.
And the origin string keys are stored in the htree item only if there is collision. So the string key distinguishing checks are at most once.