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 與名字雜湊值相加。

雜湊值構建過程如下圖所示

---