一 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的键。