我的 HashMap 实现的性能改进

Question

我决定尝试制作自己的 HashMap (here)

对于读取，它比标准库实现慢 28%，我想知道是否可以加快以下代码的速度，Index()，这对查找至关重要:

const numOnes = uint8(20)
const ones = uint32(1 << numOnes - 1)

func (m *Map) Index(num uint64) uint32 {
    part := uint32(num) & ones
    remaining := num >> numOnes
    start := m.starts[part]
    bitsNum := m.bitNums[part]
    matchedBits := bitsNum & uint16(remaining)
    offset := BitScoreCache[bitsNum][matchedBits]
    return start + uint32(offset)
}

请注意 BitScoreCache 是 var BitScoreCache [5000][5000]uint16，它应该是只读的并且在多个不同的 map 实例之间共享。

示例用法:

func (pa PrimeAdvancedAnagrammar) GetAnagrams(word string) []string {
    return pa.m[pa.locator.Index(PrimeProduct(word))] //pa.m is an [][]string
}

与标准库对比:

func (pba PrimeBasicAnagrammar) GetAnagrams(word string) []string {
    return pba.m[PrimeProduct(word)] //pba.m is a map[uint64][]string
}

它在如此少的操作方面比标准库慢的主要原因是什么？

Answer 1

将两个数组组合成一个结构数组减少了缓存未命中，是最大的性能改进。

也尽早返回没有碰撞提高性能的情况。