Go 语言编程 — 高级数据类型 — Map 集合

一时失言乱红尘 2023-10-06 12:30 80阅读 0赞

## 目录 ##

#### 文章目录 ####

*  目录
 *  集合
 *  定义 Map
 *  delete() 函数
 *  实现简单 HashMap

## 集合 ##

集合（Map）是一种无序的 HASH 键值对集合。通过 key 来快速检索 value，所以我们可以像迭代字符串、数组和切片那样迭代它。Golang 的 Map 数据类型类似于 Python 的字典数据类型，但封装程度较原始。

## 定义 Map ##

可以使用用 map 关键字来声明一个 Map 变量，也可以使用内建的 make() 函数来定义一个 Map 变量：

var map_variable map[key_data_type]value_data_type
    // or
    map_variable := make(map[key_data_type]value_data_type)

注意，make() 函数会完成变量的初始化，而 map 关键字仅仅是声明了一个变量，没有被初始化的 Map 变量，默认值为 nil，不能直接用于存放键值对。可见 Map 变量是引用语义的。

示例：

package main
    
    import "fmt"
    
    func main() {
        
        var countryCapitalMap map[string]string
        countryCapitalMap = make(map[string]string)
        // countryCapitalMap := make(map[string]string)
    
        countryCapitalMap["France"] = "巴黎"
        countryCapitalMap["Italy"] = "罗马"
        countryCapitalMap["Japan"] = "东京"
        countryCapitalMap["India"] = "新德里"
    
        for key, value := range countryCapitalMap {
        
            fmt.Println(key, "首都是", value)
        }
    
        /* 查看元素在集合中是否存在 */
        capital, ok := countryCapitalMap["American"]
        if ok {
        
            fmt.Println("American 的首都是", capital)
        } else {
        
            fmt.Println("American 的首都不存在")
        }
    }

## delete() 函数 ##

delete() 函数用于删除 Map 集合中指定的元素，参数为 Map 变量和其对应的 key。

示例：

package main
    
    import "fmt"
    
    func main() {
        
    
        countryCapitalMap := map[string]string {
        
            "France" : "Paris",
            "Italy"  : "Rome",
            "Japan"  : "Tokyo",
            "India"  : "New delhi",
        }
    
        /* 删除元素 */
        delete(countryCapitalMap, "France")
        fmt.Println("法国条目被删除")
    
        fmt.Println("删除元素后地图")
        for country := range countryCapitalMap {
        
            fmt.Println(country, "首都是", countryCapitalMap [country])
        }
    }

结果：

法国条目被删除
    删除元素后地图
    Japan 首都是 Tokyo
    India 首都是 New delhi
    Italy 首都是 Rome

## 实现简单 HashMap ##

package main
    
    import (
        "fmt"
    )
    
    type HashMap struct {
        
        key string
        value string
        hashCode int
        next *HashMap
    }
    
    var table [16](*HashMap)
    
    func initTable() {
        
        for i := range table{
        
            table[i] = &HashMap{
        "","",i,nil}
        }
    }
    
    func getInstance() [16](*HashMap){
        
        if(table[0] == nil){
        
            initTable()
        }
        return table
    }
    
    func genHashCode(k string) int{
        
        if len(k) == 0{
        
            return 0
        }
        var hashCode int = 0
        var lastIndex int = len(k) - 1
        for i := range k {
        
            if i == lastIndex {
        
                hashCode += int(k[i])
                break
            }
            hashCode += (hashCode + int(k[i]))*31
        }
        return hashCode
    }
    
    func indexTable(hashCode int) int{
        
        return hashCode%16
    }
    
    func indexNode(hashCode int) int {
        
        return hashCode>>4
    }
    
    func put(k string, v string) string {
        
        var hashCode = genHashCode(k)
        var thisNode = HashMap{
        k,v,hashCode,nil}
    
        var tableIndex = indexTable(hashCode)
        var nodeIndex = indexNode(hashCode)
    
        var headPtr [16](*HashMap) = getInstance()
        var headNode = headPtr[tableIndex]
    
        if (*headNode).key == "" {
        
            *headNode = thisNode
            return ""
        }
    
        var lastNode *HashMap = headNode
        var nextNode *HashMap = (*headNode).next
    
        for nextNode != nil && (indexNode((*nextNode).hashCode) < nodeIndex){
        
            lastNode = nextNode
            nextNode = (*nextNode).next
        }
        if (*lastNode).hashCode == thisNode.hashCode {
        
            var oldValue string = lastNode.value
            lastNode.value = thisNode.value
            return oldValue
        }
        if lastNode.hashCode < thisNode.hashCode {
        
            lastNode.next = &thisNode
        }
        if nextNode != nil {
        
            thisNode.next = nextNode
        }
        return ""
    }
    
    func get(k string) string {
        
        var hashCode = genHashCode(k)
        var tableIndex = indexTable(hashCode)
    
        var headPtr [16](*HashMap) = getInstance()
        var node *HashMap = headPtr[tableIndex]
    
        if (*node).key == k{
        
            return (*node).value
        }
    
        for (*node).next != nil {
        
            if k == (*node).key {
        
                return (*node).value
            }
            node = (*node).next
        }
        return ""
    }
    
    //examples 
    func main() {
        
        getInstance()
        put("a","a_put")
        put("b","b_put")
        fmt.Println(get("a"))
        fmt.Println(get("b"))
        put("p","p_put")
        fmt.Println(get("p"))
    }

结果：

a_put
    b_put
    p_put