Go语言map的多键索引——多个数值条件可以同时查询
发布时间：2020-12-16 09:35:56 所属栏目：大数据 来源：网络整理
导读：在大多数的编程语言中，映射容器的键必须以单一值存在。这种映射方法经常被用在诸如信息检索上，如根据通讯簿的名字进行检索。但随着查询条件越来越复杂，检索也会变得越发困难。下面例子中涉及通讯簿的结构，结构如下： // 人员档案type Profile struct { Na
在大多数的编程语言中，映射容器的键必须以单一值存在。这种映射方法经常被用在诸如信息检索上，如根据通讯簿的名字进行检索。但随着查询条件越来越复杂，检索也会变得越发困难。下面例子中涉及通讯簿的结构，结构如下：
// 人员档案
type Profile struct {
Name string // 名字
Age int // 年龄
Married bool // 已婚
}
并且准备好了一堆原始数据，需要算法实现构建索引和查询的过程，代码如下：
func main() {
list := []*Profile{
{Name: "张三",Age: 30,Married: true},{Name: "李四",Age: 21},{Name: "王麻子",}
buildIndex(list)
queryData("张三",30)
}
需要用算法实现 buildIndex() 构建索引函数及 queryData() 查询数据函数，查询到结果后将数据打印出来。下面，分别基于传统的基于哈希值的多键索引和利用 map 特性的多键索引进行查询。 基于哈希值的多键索引及查询传统的数据索引过程是将输入的数据做特征值。这种特征值有几种常见做法：
数据都基于特征值构建好索引后，就可以进行查询。查询时，重复这个过程，将查询条件转为特征值，使用特征值进行查询得到结果。 基于哈希的传统多键索引和查询的完整代码位于 ./src/chapter12/classic/classic.go，下面是对各个部分的分析。
本套教程所有源码下载地址：https://pan.baidu.com/s/1ORFVTOLEYYqDhRzeq0zIiQ??? 提取密码：hfyf 1) 字符串转哈希值本例中，查询键（classicQueryKey）的特征值需要将查询键中每一个字段转换为整型，字符串也需要转换为整型值，这里使用一种简单算法将字符串转换为需要的哈希值，代码如下：
func simpleHash(str string) (ret int) {
// 遍历字符串中的每一个ASCII字符
for i := 0; i < len(str); i++ {
// 取出字符
c := str[i]
// 将字符的ASCII码相加
ret += int(c)
}
return
}
代码说明如下：
哈希算法有很多，这里只是选用一种大家便于理解的算法。哈希算法的选用的标准是尽量减少重复键的发生，俗称“哈希冲撞”，即同样两个字符串的哈希值重复率降到最低。 2) 查询键有了哈希算法函数后，将哈希函数用在查询键结构中。查询键结构如下：
// 查询键
type classicQueryKey struct {
Name string // 要查询的名字
Age int // 要查询的年龄
}
// 计算查询键的哈希值
func (c *classicQueryKey) hash() int {
// 将名字的Hash和年龄哈希合并
return simpleHash(c.Name) + c.Age*1000000
}
代码说明如下：
哈希值构建过程如下图所示 
3) 构建索引本例需要快速查询，因此需要提前对已有的数据构建索引。前面已经准备好了数据查询键，使用查询键获得哈希即可对数据进行快速索引，参考下面的代码：
// 创建哈希值到数据的索引关系
var mapper = make(map[int][]*Profile)
// 构建数据索引
func buildIndex(list []*Profile) {
// 遍历所有的数据
for _,profile := range list {
// 构建数据的查询索引
key := classicQueryKey{profile.Name,profile.Age}
// 计算数据的哈希值,取出已经存在的记录
existValue := mapper[key.hash()]
// 将当前数据添加到已经存在的记录切片中
existValue = append(existValue,profile)
// 将切片重新设置到映射中
mapper[key.hash()] = existValue
}
}
代码说明如下：
具体哈希结构如下图所示。  图：哈希结构 这种多键的算法就是哈希算法。map 的多个元素对应哈希的“桶”。哈希函数的选择决定桶的映射好坏，如果哈希冲撞很厉害，那么就需要将发生冲撞的相同哈希值的元素使用切片保存起来。 4) 查询逻辑从已经构建好索引的数据中查询需要的数据流程如下：
func queryData(name string,age int) {
// 根据给定查询条件构建查询键
keyToQuery := classicQueryKey{name,age}
// 计算查询键的哈希值并查询,获得相同哈希值的所有结果集合
resultList := mapper[keyToQuery.hash()]
// 遍历结果集合
for _,result := range resultList {
// 与查询结果比对,确认找到打印结果
if result.Name == name && result.Age == age {
fmt.Println(result)
return
}
}
// 没有查询到时,打印结果
fmt.Println("no found")
}
代码说明如下：
利用 map 特性的多键索引及查询使用结构体进行多键索引和查询比传统的写法更为简单，最主要的区别是无须准备哈希函数及相应的字段无须做哈希合并。看下面的实现流程。利用map特性的多键索引和查询的代码位于 ./src/chapter12/multikey/multikey.go，下面是对各个部分的分析。
本套教程所有源码下载地址：https://pan.baidu.com/s/1ORFVTOLEYYqDhRzeq0zIiQ??? 提取密码：hfyf 1) 构建索引代码如下：
// 查询键
type queryKey struct {
Name string
Age int
}
// 创建查询键到数据的映射
var mapper = make(map[queryKey]*Profile)
// 构建查询索引
func buildIndex(list []*Profile) {
// 遍历所有数据
for _,profile := range list {
// 构建查询键
key := queryKey{
Name: profile.Name,Age: profile.Age,}
// 保存查询键
mapper[key] = profile
}
}
代码说明如下：
2) 查询逻辑
// 根据条件查询数据
func queryData(name string,age int) {
// 根据查询条件构建查询键
key := queryKey{name,age}
// 根据键值查询数据
result,ok := mapper[key]
// 找到数据打印出来
if ok {
fmt.Println(result)
} else {
fmt.Println("no found")
}
}
代码说明如下：
总结基于哈希值的多键索引查询和利用 map 特性的多键索引查询的代码复杂程度显而易见。聪明的程序员都会利用 Go语言的特性进行快速的多键索引查询。其实，利用 map 特性的例子中的 map 类型即便修改为下面的格式，也一样可以获得同样的结果：
var mapper = make(map[interface{}]*Profile)
代码量大大减少的关键是：Go语言的底层会为 map 的键自动构建哈希值。能够构建哈希值的类型必须是非动态类型、非指针、函数、闭包。
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |