避坑-4-map多键索引

一 map多键索引

1.0 需求示例

示例如下：

package main

type Profile struct{
	Name string
	Age int
	Married bool
}

func main() {

	list := []*Profile{
		{
			Name: "zs",
			Age: 30,
			Married: true,
		},
		{
			Name: "ls",
			Age: 15,
			Married: false,
		},
		{
			Name: "ww",
			Age: 60,
			Married: false,
		},
	}

	buildIndex(list)            // 生成索引函数
	queryData("ww", 60)         // 实现查询方法：按照名字和年龄

}

本示例需要用算法实现 buildlndex() 构建索引函数及 queryData() 查询数据函数。

1.1 方式一：基于哈希值的多键索引

传统的数据索引过程是将输入的数据做特征值，这种特征值有几种常见做法:

• 使用某种算法将特征转换为整数，即哈希值，使用整型值做索引
• 将特征转为字符串，使用字符串做索引

/**
	字符串转哈希值方法：这里将查询键的每一个字段转换为整数，生成的特征值也不一定唯一，因为可能会出现碰撞，不过这里只是一个举例
 */

// 查询键
type classicQueryKey struct {					
	Name string
	Age int
}

// 生成特征值的方法
func (c *classicQueryKey)buildHash() int {		
	var ret int
	for i := 0; i < len(c.Name); i++ {
		c := c.Name[i]
		ret += int(c)							// ASCII码相加
	}
	return ret + c.Age*1000000
}

// 创建哈希值到数据的索引关系
var mapper = make(map[int][]*Person)

// 构建数据索引
func buildIndex(list []*Person) {				
	for _, p := range list {
		key := classicQueryKey{p.Name, p.Age}	// 构建数据的查询索引
		existValue := mapper[key.buildHash()]
		existValue = append(existValue, p)
		mapper[key.buildHash()] = existValue
	}
}
func queryData(name string, age int) {
	keyToQuery := classicQueryKey{name , age}
	resultList := mapper[keyToQuery.buildHash()]
	for _, result := range resultList {
		if result.Name == name && result.Age == age {
			fmt.Println(result)
			return
		}
	}
	fmt.Println("not found")
}

这种多键的算法就是哈希算法。 map 的多个元素对应哈希的“桶 ” 。哈希函数的选择决定桶的映射好坏，如果哈希冲撞很厉害，那么就需要将发生冲撞的相同哈希值的元素使用切片保存起来。

1.2 方式二：利用map的多键索引

使用结构体进行多键索引和查询比传统的写法更为简单 ， 最主要的区别是无须准备哈希函数及相应的宇段无须做哈希合并。

type classicQueryKey struct {					// 查询键
	Name string
	Age int
}
var mapper = make(map[classicQueryKey]*Person)

func buildIndex(list []*Person) {				// 构建数据索引
	for _, p := range list {
		key := classicQueryKey{p.Name, p.Age}	// 构建数据的查询索引
		mapper[key] = p
	}
}
func queryData(name string, age int) {
	keyToQuery := classicQueryKey{name , age}
	result, ok := mapper[keyToQuery]
	if ok {
		fmt.Println(result)
	} else {
		fmt.Println("not found")
	}
}

解释：基于哈希值的多键索引查询和利用 map 特性的多键索引查询的代码复杂程度显而易见。其实，利用 map 特性的例子中的 map 类型即便修改为下面的格式，也 一样可以获得同样的结果:

var mapper = make(map[interface{})*Person)

代码量大大减少的关键是: Go语言的底层会为 map 的键自动构建哈希值。

能够构建哈希值的类型必须是非动态类型、非指针、函 数 、闭包 。

• 非动态类型 : 可用数组，不能用切片。
• 非指针: 每 个指针数值都不同， 失去哈希意义。
• 函数、闭包不能作为 map的键。