哈希表

基础与数据结构

说明

用键快速定位值；Go map 的查找与更新平均为 O(1)。

分析

Frequencies 用字符串作键，遇到一次就把计数加一。Go 的 map 在读取不存在的键时返回零值，因此无需预先插入每个单词。

哈希缩小候选范围，最终仍需比较键。碰撞是不同键落到相同候选位置，不能直接覆盖；go出现两次得到计数2，rust独立计数1。下图是概念流程，不表示某一Go版本的具体桶结构。

查看图表代码

适用前提与边界

平均查找很快，但迭代顺序未定义；需要稳定输出时应先排序键。 示例键为string、统计从空map开始；并发写入需同步，计数超过int范围也须另行处理。

示例输入与调用

fmt.Println(Frequencies([]string{"go", "go", "rust"})["go"])

运行输出

2

完整 Go 示例

package main

import "fmt"

func Frequencies(a []string) map[string]int {
	counts := map[string]int{}
	for _, s := range a {
		counts[s]++
	}
	return counts
}

func main() {
	fmt.Println(Frequencies([]string{"go", "go", "rust"})["go"])
}