Build fails if key count is a power of two

func TestCHD_Pow2(t *testing.T) {
    check := func(n int) (err error) {
        cb := Builder()
        for i:=0; i<n; i++ {
            cb.Add([]byte(strconv.Itoa(i)), []byte(strconv.Itoa(i)))
        }
        _, err = cb.Build()
        return
    }
    for i:=1;i<1025;i++ {
        if err := check(i); err != nil {
            t.Errorf(`failed with n=%d: %v`, i, err)
        }
    }
}

Output:

chd_test.go:98: failed with n=16: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/8 with 3 entries: bucket{0, 8, 11, }
    chd_test.go:98: failed with n=24: failed to find a collision-free hash function after ~10000000 attempts, for bucket 4/12 with 3 entries: bucket{1, 9, 21, }
    chd_test.go:98: failed with n=32: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/16 with 3 entries: bucket{1, 18, 21, }
    chd_test.go:98: failed with n=48: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/24 with 5 entries: bucket{7, 16, 27, 30, 41, }
    chd_test.go:98: failed with n=64: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/32 with 3 entries: bucket{5, 32, 43, }
    chd_test.go:98: failed with n=96: failed to find a collision-free hash function after ~10000000 attempts, for bucket 32/48 with 2 entries: bucket{55, 82, }
    chd_test.go:98: failed with n=128: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/64 with 4 entries: bucket{22, 71, 93, 110, }
    chd_test.go:98: failed with n=192: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/96 with 7 entries: bucket{19, 20, 55, 73, 91, 112, 138, }
    chd_test.go:98: failed with n=256: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/128 with 5 entries: bucket{20, 73, 91, 237, 246, }
    chd_test.go:98: failed with n=384: failed to find a collision-free hash function after ~10000000 attempts, for bucket 5/192 with 5 entries: bucket{86, 224, 277, 295, 318, }
    chd_test.go:98: failed with n=512: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/256 with 5 entries: bucket{1, 218, 346, 427, 485, }
    chd_test.go:98: failed with n=768: failed to find a collision-free hash function after ~10000000 attempts, for bucket 1/384 with 6 entries: bucket{32, 250, 526, 575, 647, 760, }
    chd_test.go:98: failed with n=1024: failed to find a collision-free hash function after ~10000000 attempts, for bucket 0/512 with 5 entries: bucket{81, 223, 638, 740, 982, }

alecthomas / mph

Build fails if key count is a power of two #10