C語言中文網 目錄

Go語言map的多鍵索引——多個數值條件可以同時查詢

在大多數的編程語言中,映射容器的鍵必須以單一值存在。這種映射方法經常被用在諸如信息檢索上,如根據通訊簿的名字進行檢索。但隨著查詢條件越來越復雜,檢索也會變得越發困難。下面例子中涉及通訊簿的結構,結構如下:
// 人員檔案
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 與名字哈希值相加。

哈希值構建過程如下圖所示

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
    }
}
代碼說明如下:
  • 第 2 行,實例化一個 map,鍵類型為整型,保存哈希值;值類型為 *Profile,為通訊簿的數據格式。
  • 第 5 行,構建索引函數入口,傳入數據切片。
  • 第 8 行,遍歷數據切片的所有數據元素。
  • 第 11 行,使用查詢鍵(classicQueryKey)來輔助計算哈希值,查詢鍵需要填充兩個字段,將數據中的名字和年齡賦值到查詢鍵中進行保存。
  • 第 14 行,使用查詢鍵的哈希方法計算查詢鍵的哈希值。通過這個值在 mapper 索引中查找相同哈希值的數據切片集合。因為哈希函數不能保證不同數據的哈希值一定完全不同,因此要考慮在發生哈希值重復時的處理辦法。
  • 第 17 行,將當前數據添加到可能存在的切片中。
  • 第 20 行,將新添加好的數據切片重新賦值到相同哈希的 mapper 中。

具體哈希結構如下圖所示。

圖:哈希結構

這種多鍵的算法就是哈希算法。map 的多個元素對應哈希的“桶”。哈希函數的選擇決定桶的映射好壞,如果哈希沖撞很厲害,那么就需要將發生沖撞的相同哈希值的元素使用切片保存起來。

4) 查詢邏輯

從已經構建好索引的數據中查詢需要的數據流程如下:
  1. 給定查詢條件(名字、年齡)。
  2. 根據查詢條件構建查詢鍵。
  3. 查詢鍵生成哈希值。
  4. 根據哈希值在索引中查找數據集合。
  5. 遍歷數據集合逐個與條件比對。
  6. 獲得結果。
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")

}
代碼說明如下:
  • 第 1 行,查詢條件(名字、年齡)。
  • 第 4 行,根據查詢條件構建查詢鍵。
  • 第 7 行,使用查詢鍵計算哈希值,使用哈希值查詢相同哈希值的所有數據集合。
  • 第 10 行,遍歷所有相同哈希值的數據集合。
  • 第 13 行,將每個數據與查詢條件進行比對,如果一致,表示已經找到結果,打印并返回。
  • 第 20 行,沒有找到記錄時,打印 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 行,與基于哈希值的查詢鍵的結構相同。
  • 第 8 行,在 map 的鍵類型上,直接使用了查詢鍵結構體。注意,這里不使用查詢鍵的指針。同時,結果只有 *Profile 類型,而不是 *Profile 切片,表示查到的結果唯一。
  • 第 17 行,類似的,使用遍歷到的數據的名字和年齡構建查詢鍵。
  • 第 23 行,更簡單的,直接將查詢鍵保存對應的數據。

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")
    }
}
代碼說明如下:
  • 第 5 行,根據查詢條件(名字、年齡)構建查詢鍵。
  • 第 8 行,直接使用查詢鍵在 map 中查詢結果。
  • 第 12 行,找到結果直接打印。
  • 第 14 行,沒有找到結果打印 no found。

總結

基于哈希值的多鍵索引查詢和利用map特性的多鍵索引查詢的代碼復雜程度顯而易見。聰明的程序員都會利用Go語言的特性進行快速的多鍵索引查詢。

其實,利用 map 特性的例子中的 map 類型即便修改為下面的格式,也一樣可以獲得同樣的結果:
var mapper = make(map[interface{}]*Profile)
代碼量大大減少的關鍵是:Go 語言的底層會為 map 的鍵自動構建哈希值。能夠構建哈希值的類型必須是非動態類型、非指針、函數、閉包。
  • 非動態類型:可用數組,不能用切片。
  • 非指針:每個指針數值都不同,失去哈希意義。
  • 函數、閉包不能作為 map 的鍵。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo