（9）Go实现映射和集合

映射：Map
map 是一种无序的键值对的集合。映射的key是不重复的，因此map 最重要的一点是通过 key 来快速检索数据，key 类似于索引，指向数据的值。
map 是一种集合，所以我们可以像迭代数组和 slice 那样迭代它。不过，map 是无序的，我们无法决定它的返回顺序，这是因为 map 是使用 hash 表来实现的，hash算法看下面:《从头到尾彻底解析Hash表算法》
https://blog.csdn.net/fly542/article/details/6696446

// map创建的3种方法
1) dict := make(map[string]int)
// 通过字面值创建
2) dict := map[string]string{"hello": "world", "china": "best"}

如果不初始化 map，那么就会创建一个 nil map, nil map 不能用来存放键值对，
否则会报运行时错误：
var dict map[string]string
dict["hello"] = "world"

panic: assignment to entry in nil map

集合就是不同对象的无序聚集，在定义上跟映射挺像的，下面用go的映射来实现
一种集合
//
type set struct {
    size int
    sets map[string]bool
}

func NewSet() *set {
    return &set{
        size: 0,
        sets: map[string]bool{},
    }
}

func (set *set) Add(str string) {
    if str == "" {
        return
    }
    v := set.sets[str]
    if !v {
        set.sets[str] = true
        set.size++
    }
}

func (set *set) Remove(str string) error {
    v := set.sets[str]
    if v {
        set.sets[str] = false
        set.size--
        return nil
    }
    return errors.New("failed to remove,value is no exists.")
}

func (set *set) GetSize() int {
    return set.size
}

func (set *set) Contains(str string) bool {
    return set.sets[str]
}

func (set *set) IsEmpty() bool {
    return set.size == 0
}

分别用映射和集合来解决leetcode的804题目

// 用映射解决方法
func uniqueMorseRepresentations(words []string) int {
    m1 := map[int]string{}
    strs := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-",                       ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
    for i, v := range strs {
        m1[97+i] = v
    }

    count := 0
    m2 := map[string]bool{}
    words = []string{"gin", "zen", "gig", "msg"}
    for _, str := range words {
        buf := ""
        for _, key := range str {
            v1, ok1 := m1[int(key)]
            if !ok1 {
                buf=""
                break
            }
            buf = buf + v1
        }
        if buf == "" {
            continue
        }
        v2 := m2[buf]
        if !v2 {
            m2[buf] = true
            count++
        }
    }
    return count
}

// 用集合解决方法
func main() {
    m := map[string]string{}
    strs := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
    for i, v := range strs {
        m[string(97+i)] = v
    }
    fmt.Println(m)

    s := set1.NewSet()
    words := []string{"gin", "zen", "gig", "msg"}
    for _, str := range words {
        buf := ""
        for _, v := range str {
            k, ok := m[string(v)]
            if !ok {
                buf = ""
                break
            }
            buf = buf + k
        }
        if buf == "" {
            continue
        }
        s.Add(buf)
    }
    fmt.Println(s.GetSize())
}

用这种方法实现的映射和集合的增删改查操作，时间复杂度都为O（1），但因为是无序的，在要求顺序输出，求最大值最小值这种操作都要去遍历整个集合，速度就较慢
待续

有bug欢迎指出，转载请注明出处。