hosteons中文网

在大多数的编程语言中，映射容器的键必须以单一值存在。这种映射方法经常被用在诸如信息检索上，如根据通讯簿的名字进行检索。但随着查询条件越来越复杂，检索也会变得越发困难。下面例子中涉及通讯簿的结构，结构如下：

// 人员档案
type Profile struct {
    Name    string   // 名字
    Age     int      // 年龄
    Married bool     // 已婚
}

并且准备好了一堆原始数据，需要算法实现构建索引和查询的过程，代码如下：

func main() {

    list := []*Profile{
        {Name: "张三", Age: 30, Married: true},
        {Name: "李四", Age: 21},
        {Name: "王麻子", Age: 21},
    }

    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
}

代码说明如下：

• 第 1 行传入需要计算哈希值的字符串。
• 第 4 行，根据字符串的长度，遍历这个字符串的每一个字符，以 ASCII 码为单位。
• 第 9 行，c 变量的类型为 uint8，将其转为 int 类型并累加。

哈希算法有很多，这里只是选用一种大家便于理解的算法。哈希算法的选用的标准是尽量减少重复键的发生，俗称“哈希冲撞”，即同样两个字符串的哈希值重复率降到最低。

2) 查询键

有了哈希算法函数后，将哈希函数用在查询键结构中。查询键结构如下：

// 查询键
type classicQueryKey struct {
    Name string  // 要查询的名字
    Age  int     // 要查询的年龄
}

// 计算查询键的哈希值
func (c *classicQueryKey) hash() int {
    // 将名字的Hash和年龄哈希合并
    return simpleHash(c.Name) + c.Age*1000000
}

代码说明如下：

• 第 2 行，声明查询键的结构，查询键包含需要索引和查询的字段。
• 第 8 行，查询键的成员方法哈希，通过调用这个方法获得整个查询键的哈希值。
• 第 10 行，查询键哈希的计算方法：使用 simpleHash() 函数根据给定的名字字符串获得其哈希值。同时将年龄乘以 1000000 与名字哈希值相加。

哈希值构建过程如下图所示