algorithm - 对于唯一的整数数组，什么是好的散列函数(或类似函数)？

Question

我正在编写一个简单的程序来分析彩票。我很好奇相同数字模式出现的频率。

这是我在 Golang 中的工作代码:

package main

import (
    "fmt"
    "math/rand"
    "os"
    "sort"
    "sync"

    "github.com/mitchellh/hashstructure"
)

func do(n int, ch chan bool) {
    hashes := make(map[uint64]struct{})

    for i := 0; i < n; i++ {
        numbers := rand.Perm(45)[:6]
        sort.Ints(numbers)

        hash, err := hashstructure.Hash(numbers, nil)
        if err != nil {
            panic(err)
        }

        if _, ok := hashes[hash]; ok {
            ch <- true
            break
        } else {
            hashes[hash] = struct{}{}
        }
    }
}

func main() {
    n := 1000

    ch := make(chan bool)
    duplicated := 0.0
    done := make(chan struct{})

    wg := sync.WaitGroup{}
    for i := 0; i < n; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            do(800, ch)
        }()
    }

    go func() {
        wg.Wait()
        close(done)
    }()

    for {
        select {
        case <-ch:
            duplicated += 1
        case <-done:
            fmt.Printf("duplicated ratio: %.2f%%\n", duplicated/float64(n)*100)
            os.Exit(0)
        }
    }
}

我目前正在使用 https://github.com/mitchellh/hashstructure用于散列整数数组(在 Golang 中，类型为 []int)。我正在寻找一种更有效的方法来测试彩票号码是否重复，因为由于反射，库的功能被认为很慢。

我首先想到的是这样的:

func hashFunc(v []int) int {
    hash := 1
    for _, x := range v {
        hash ^= x
    }
    return hash
}

但是它产生了哈希冲突。你能建议我一个更好的方法来散列 int 数组(元素是唯一的，并且在 1~45 范围内)或者甚至是另一种有效测试过去是否有重复的 int 数组的方法吗？谢谢。

Answer 1

您可以跳过散列，将其视为一个 64 位数字。每个彩票号码小于256，可以包含在1个字节中。你有 6 个数字，所以这是 6 个字节，可以包含在 64 位中，即 8 个字节。

https://play.golang.org/p/JHLfHIhAUdd

package main

import (
    "fmt"
)

func hashFunc(v []uint8) uint64 {
    var hash uint64
    var i uint
    for _, x := range v {
        hash |= uint64(x) << (i * 8)
        i++
    }
    return hash
}

func main() {
    fmt.Printf("hashFunc ({1,2,3,4,5,6}) = %#x", hashFunc([]uint8{1,2,3,4,5,6}))
}