Golang中的Map集合

Question

如果我有一个像这样的结构体：

type Foo struct {
  title string
  Tags map[string]string
}

我该如何维护这样一组结构体？据我所知，尽管结构体相等是可行的，但映射相等却不行。这意味着我不能比较上述结构体。因此，我不能仅实现将映射作为集合模式。

我能想到的两个可能有效的选择是：将标签转换为已排序的[][]string或使用reflect.Deepequal函数。还有更好的建议吗？

- Kyle Brandt

---

我认为你可能想要使用 DeepEqual。 - Eve Freeman

你是否真的需要 map[string]string，通常情况下，一个 map 集合是 map[string]bool 吗？ - Eve Freeman

@WesFreeman：希望创建一组结构体，而不仅仅是结构体内的映射。 - Kyle Brandt

使用[][]string类型的标签也无法解决问题；切片相等性也未被定义。 - andybalholm

Answer 1

有几种实现方法。James Henstridge提出了一个好主意，我试图实现它。仅仅使用map的性能表现非常差，没有自己的哈希算法。

我解决这个问题的方式是保持一个结构体数组，并在插入时删除任何重复项。

package structset

type Foo struct {
  title string
  Tags  map[string]string
}

func (f Foo) Equals(f2 Foo) bool {
  if f.title != f2.title {
    return false
  }

  if len(f.Tags) != len(f2.Tags) {
    return false
  }

  for k, v := range f.Tags {
    if w, ok := f2.Tags[k]; !ok || v != w {
      return false
    }
  }

  return true
}

type FooSet []Foo

func (this FooSet) Add(value Foo) {
  if !this.Contains(value) {
    this = append(this, value)
  }
}

func (this FooSet) Length() int {
  return len(this)
}

func (this FooSet) Contains(f Foo) bool {
  for _, v := range this {
    if v.Equals(f) {
      return true
    }
  }
  return false
}

func NewSet() FooSet {
  return FooSet(make([]Foo, 0, 100))
}

我在我的 i7-3770K Windows 机器上进行了基准测试，得到如下结果：

BenchmarkSmallSetWithFewCollisions         50000             46615 ns/op
BenchmarkSmallSetWithMoreCollisions        50000             46575 ns/op
BenchmarkSmallSetWithManyCollisions        50000             46605 ns/op
BenchmarkMediumSetWithFewCollisions         1000           2335296 ns/op
BenchmarkMediumSetWithMoreCollisions        1000           2352298 ns/op
BenchmarkMediumSetWithManyCollisions        1000           2336796 ns/op
BenchmarkLargeSetWithFewCollisions            50          46805944 ns/op
BenchmarkLargeSetWithMoreCollisions           50          47376016 ns/op
BenchmarkLargeSetWithManyCollisions           50          46815946 ns/op

为了提高一点点性能，你可以先将所有数据插入到数组中，然后再删除所有重复项。

删除重复项的代码如下：

func (this FooSet) RemoveDuplicates() {
  length := len(this) - 1
  for i := 0; i < length; i++ {
    for j := i + 1; j <= length; j++ {
      if this[i].Equals(this[j]) {
        this[j] = this[length]
        this = this[0:length]
        length--
        j--
      }
    }
  }
}

这个的基准是：

BenchmarkSmallSetWithFewCollisions         50000             45245 ns/op
BenchmarkSmallSetWithMoreCollisions        50000             45615 ns/op
BenchmarkSmallSetWithManyCollisions        50000             45555 ns/op
BenchmarkMediumSetWithFewCollisions         1000           2294791 ns/op
BenchmarkMediumSetWithMoreCollisions        1000           2309293 ns/op
BenchmarkMediumSetWithManyCollisions        1000           2286290 ns/op
BenchmarkLargeSetWithFewCollisions            50          46235870 ns/op
BenchmarkLargeSetWithMoreCollisions           50          46515906 ns/op
BenchmarkLargeSetWithManyCollisions           50          45865824 ns/op

这里是将Foo分配给map[string]Foo的基准测试。

BenchmarkSmallSetWithFewCollisions         50000             65718 ns/op
BenchmarkSmallSetWithMoreCollisions        50000             64238 ns/op
BenchmarkSmallSetWithManyCollisions        50000             55016 ns/op
BenchmarkMediumSetWithFewCollisions          500           3429435 ns/op
BenchmarkMediumSetWithMoreCollisions         500           3117395 ns/op
BenchmarkMediumSetWithManyCollisions        1000           2826858 ns/op
BenchmarkLargeSetWithFewCollisions            20          82635495 ns/op
BenchmarkLargeSetWithMoreCollisions           20          85285830 ns/op
BenchmarkLargeSetWithManyCollisions           20          73659350 ns/op

我认为即使地图是可哈希的，它仍然不会表现得很好。

- kdar

Answer 2

根据您的操作，可能的一种选择是将结构体存储为映射中的值而不是键。但是，为了使其正常工作，您需要创建某种方法从每个结构体值生成唯一的键。

可能会使用以下方式：

// Doesn't have to be a string: just has to be suitable for use as a map key.
func (foo *Foo) key() string {
    return key_string
}

fooSet := make(map[string] *Foo)

// Store a Foo
fooSet[x.key()] = x

// Check if x is in the set:
if fooSet[x.key()] != nil {
    println("x is in the set")
}

这取决于您为结构体推导密钥的效率。

- James Henstridge

Answer 3

你确定你的例子可行吗？ 我认为你必须将指针传递给Add()方法才能使你的代码运行。不管怎样，这是我的实现：

package math

// types

type IntPoint struct {
    X, Y int
}

// set implementation for small number of items
type IntPointSet struct {
    slice []IntPoint 
}

// functions

func (p1 IntPoint) Equals(p2 IntPoint) bool {
    return (p1.X == p2.X) && (p1.Y == p2.Y)
}

func (set *IntPointSet) Add(p IntPoint) {
    if ! set.Contains(p) {
        set.slice = append(set.slice, p)
    }
}

func (set IntPointSet) Contains(p IntPoint) bool {
  for _, v := range set.slice {
    if v.Equals(p) {
      return true
    }
  }
  return false
}

func (set IntPointSet) NumElements() int {
    return len(set.slice)
}

func NewIntPointSet() IntPointSet {
  return IntPointSet{(make([]IntPoint, 0, 10))}
}

- amahfouz