在Go中检查字符串切片是否包含某个值

Question

什么是检查特定值是否在字符串切片中的最佳方法？我会在其他语言中使用Set，但Go没有。

到目前为止，我的最佳尝试是：

package main

import "fmt"

func main() {
    list := []string{"a", "b", "x"}
    fmt.Println(isValueInList("b", list))
    fmt.Println(isValueInList("z", list))
}

func isValueInList(value string, list []string) bool {
    for _, v := range list {
        if v == value {
            return true
        }
    }
    return false
}

http://play.golang.org/p/gkwMz5j09n

这个解决方案对于小的切片应该没问题，但对于有很多元素的切片该怎么办？

- deamon

Answer 1

如果你有一个字符串切片，但其中的元素顺序是任意的，那么查找其中是否存在某个值需要O(n)的时间。这适用于所有编程语言。

如果你打算多次进行搜索，可以使用其他数据结构来加快查找速度。但是，构建这些数据结构至少需要O(n)的时间。因此，只有在多次使用数据结构进行查找时才能获得好处。

例如，你可以将字符串加载到映射中。然后查找时间为O(1)。插入也需要O(1)的时间，使初始构建需要O(n)的时间：

set := make(map[string]bool)
for _, v := range list {
    set[v] = true
}

fmt.Println(set["b"])

你还可以对字符串切片进行排序，然后进行二分查找。二分查找的时间复杂度为O(log(n)). 排序可能需要O(n*log(n))的时间。

sort.Strings(list)
i := sort.SearchStrings(list, "b")
fmt.Println(i < len(list) && list[i] == "b")

虽然理论上，如果给定无限数量的值，使用 Map 会更快，但实际应用中，搜索一个已排序的列表很可能更快。你需要自己进行基准测试。

- Stephen Weinberg

Answer 2

为了替换集合，应该使用map[string]struct{}。这是高效和惯用的方式，"值"完全不占空间。

初始化集合：

set := make(map[string]struct{})

放置一个项目：

set["item"]=struct{}{}

检查一个元素是否存在：

_, isPresent := set["item"]

删除一个元素：

delete(set, "item")

- Denys Séguret

Answer 3

你可以使用地图，将值设置为布尔类型。

m := map[string] bool {"a":true, "b":true, "x":true}
if m["a"] { // will be false if "a" is not in the map
    //it was in the map
}

还有一个sort包，这样您就可以对切片进行排序和二分搜索。

- nos

---

请注意，您不必使用bool虚拟值。您可以使用空结构体，例如：map[string]struct{}。 - nemo

为了澄清 @nemo 所说的，使用 struct{} 作为值的优点是它不占用内存。 - Thomas Kappler

当说到“它不占用内存”时，指的是在值方面并不会占用额外的内存。当然，该映射表仍会为键和哈希表（或其他实现）占用内存，只是通过减少映射表所需的内存来达到了最小化映射表内存的目的（以牺牲一些代码语法，需要使用“if _, ok := map ["a"]; ok”样式的检查，而不仅仅是 “if map["a"]”）。 - Dave C