On Sun, Feb 25, 2024 at 01:53:35PM +0800, Herbert Xu wrote: > On Sun, Feb 25, 2024 at 12:51:06AM -0500, Kent Overstreet wrote: > > > > but your distribution actually is accurate in general, golden ratio hash > > is relly nice for sequential integers. the actual problem with your test > > is that you're testing 100% occupancy - no one does that. > > > > 75% occupancy, siphash: > > 0: 933 > > 1: 60 > > 2: 6 > > 3: 1 > > 4: 0 > > > > that looks about right to me. > > The point is that the worst-case length grows with the size of > the table so it won't always be 3. You need to take into account > the largest table size that you will support. ok, but - one million entries, siphash, 75% fill factor 0: 472053 1: 354786 2: 132663 3: 33267 4: 6218 5: 884 6: 110 7: 17 8: 2 9: 0 100 million: 0: 51342703 1: 34224025 2: 11413241 3: 2534946 4: 421816 5: 56271 6: 6346 7: 593 8: 56 9: 3 10: 0 it's a log curve - chain length of 16 means you picked a bad hash function.
