On 24/12/15 17:22, Dmitry Yemanov wrote: >> I suspect that "true hash" could make distribution of hash values more >> equival >> > and thus improve overall timing for lock table search.
> A couple of years ago I played a bit with different hash functions that > are considered good nowadays. Quite surprisingly, none of them provided > consistently better value distribution. > Once you get a decent number of buckets, it's almost impossible to spread stuff evenly ... Talking from experience with Pick (which puts its data in hashed files) its normal to have a few buckets seriously overflowed. You just can't avoid it. Let's say I have 80 objects, with space for 5 per bucket. That gives me 20 buckets. Pretty much any algorithm will probably give me one or two empty buckets, and one bucket with 11 necessitating storing it as three groups of five. That said, we reckon on finding 19 out of 20 records in the very first group we try. If you want a reasonably objective measure, try calculating the average distance an item is from the head of the chain. So let's assume we have 20 items, in 10 chains as follows: 1 1 3 1 0 4 0 4 3 3 So that gives us 0, 0, 1+2, 0, 0, 1+2+3, 0, 1+2+3, 1+2, 1+2 which = 21. So with an average of two items per chain, that's a score of just over 1. With perfection being 0.5 and a worst case of 10, that's not bad. (Pick would score this differently, putting them in five buckets we get 1+4 1+0 3+4 1+3 0+3. That gives us one bucket with 7, which scores 2. That gives us an overall score of 0.1. But for Pick each group access is a disk hit, so the cost of searching a group for the required item is lost in the noise). But if you want some figures for comparison, add 25% to the number of items to give the number of buckets. So with 20 items, that gives 25 buckets. If your algorithm then returns a score of 0.05, you're doing very well. Cheers, Wol ------------------------------------------------------------------------------ Firebird-Devel mailing list, web interface at https://lists.sourceforge.net/lists/listinfo/firebird-devel
