Hello, Pedro Falcato ---------------------------- Thank you for your advice. Hash Tree is a new implementation and does not have any users yet. And it will likely take some time for many people to recognize and demonstrate its superiority. Hello, Darrick J. Wong ------------------------------ rhashtable was coded using the structure below, struct rhash_head struct rhashtable It doesn't seem to be a Linux Kernel standard API. And, as for the Rosebush you mentioned, I checked the related information in the link below. https://lore.kernel.org/lkml/20240222203726.1101861-1-willy@xxxxxxxxxxxxx/ I think "Matthew Wilcox" who developed this would be well aware of this. Since he developed XArray which is currently running in the kernel, I would appreciate his advice. Hello, lsahn@xxxxxxxxxxxxxx ------------------------------------------ The Hash Tree I implemented uses HTREE_HASH_KEY to keep the tree balanced. You can check the macro below in include/linux/htree.h. #define HTREE_HASH_KEY(idx, d, bits) ( sizeof(idx) <= 4 ? \ (((u32)idx + d) * htgr32[d]) >> (32 - bits) : \ (((u64)idx + d) * htgr64[d]) >> (64 - bits) ) The hash keys are distributed using each GOLDEN RATIO value at each depth of the tree. The standard deviation of the hash key is less than 4. The function that tests and computes this is _htree_hash_dev() in the lib/htree-test.c Thanks.
