Examples of implementation methods of type Set in Golang are explained in detail

  • 2020-06-07 04:39:39
  • OfStack

preface

This article mainly tells you how to use the grammar features of Go language to achieve the Set type of data structure, sharing for your reference and learning, not to say more, let's have a look at the detailed introduction.

demand

For data structures of type Set, they are not much different from List in nature. It is simply that Set cannot contain repeated Item features. Set has initialization, Add, Clear, Remove, Contains and other operations. Next look at the concrete implementation method analysis.

implementation

Still thinking about how to implement basic Set functionality based on your programming experience, it's easy to know in Java that the underlying implementation of HashSet is HashMap, and the core is to populate the Value option in the Map key-value pair with 1 constant. In addition, focus on the DATA structure of Map in Go. Key does not allow duplication, as shown below:


m := map[string]string{
 "1": "one",
 "2": "two",
 "1": "one",
 "3": "three",
 }
 fmt.Println(m)

The program will directly report an error, prompting the repetition of the Key value, which is very much in line with the Set feature requirements.

define

Above analysis shows that Value of Set is a fixed value, which can be replaced by a constant. But the author analysis of the source code, using an empty structure to achieve, as shown below:


//  Empty structure 
var Exists = struct{}{}
// Set is the main interface
type Set struct {
 // struct Is a variable of structure type 
 m map[interface{}]struct{}
}

To figure out why the empty structure is used as the constant Value above, take a look at the following tests:


import (
 "fmt"
 "unsafe"
)

//  Defines a non-empty structure 
type S struct {
  a uint16
  b uint32
}

func main() {
 var s S
 fmt.Println(unsafe.Sizeof(s)) // prints 8, not 6
 var s2 struct{}
 fmt.Println(unsafe.Sizeof(s2)) // prints 0
}

Print out the empty structure variable with a memory footprint of 0. Take a look at this test:


a := struct{}{}
b := struct{}{}
fmt.Println(a == b) // true
fmt.Printf("%p, %p\n", &a, &b) // 0x55a988, 0x55a988

It is interesting that a and b are equal, and the addresses of a and b are the same. Now you can see why:


var Exists = struct{}{}

This constant will fill all Map's Value, Go is amazing!!

Initialize the

Initialization of data structures of type Set, which you can choose to pass in or not pass in at the time of declaration. When declaring Map slices, Key can be any type of data, implemented using an empty interface. According to the above analysis, the empty structure can be used:


func New(items ...interface{}) *Set {
 //  To obtain Set The address of the 
 s := &Set{}
 //  The statement map Type of data structure 
 s.m = make(map[interface{}]struct{})
 s.Add(items...)
 return s
}

add

Simplified operations can add an indefinite number of elements into Set, using the variable length parameter feature to achieve this requirement, because Map does not allow Key values to be the same, so there is no need for a rearrangement operation. The Value value is also specified as an empty structure type.


func (s *Set) Add(items ...interface{}) error {
 for _, item := range items {
 s.m[item] = Exists
 }
 return nil
}

contains

The Contains operation is actually a query operation to see if the corresponding Item exists. It can be implemented by using the features of Map. However, since the value of Value is not needed, it can be achieved by using _,ok:


func (s *Set) Contains(item interface{}) bool {
 _, ok := s.m[item]
 return ok
}

Length and clearance

Getting the LENGTH of Set is easy, just get the length of the underlying implementation of Map:


func (s *Set) Size() int {
 return len(s.m)
}

The cleanup operation can be achieved by reinitializing Set as follows:


func (s *Set) Clear() {
 s.m = make(map[interface{}]struct{})
}

equal

To determine whether two Set are equal or not, it can be achieved through a loop through the history. Each element in A is asked whether it exists in B. As long as one does not exist, A and B are not equal.


//  Empty structure 
var Exists = struct{}{}
// Set is the main interface
type Set struct {
 // struct Is a variable of structure type 
 m map[interface{}]struct{}
}
0

A subset of

Determining whether A is a subset of B is also a process of loop traversal. Specific analysis has been described above, and the implementation method is as follows:


//  Empty structure 
var Exists = struct{}{}
// Set is the main interface
type Set struct {
 // struct Is a variable of structure type 
 m map[interface{}]struct{}
}
1

Ok, the above is Set in the Go main function implementation, or very interesting. Keep it up.

conclusion


Related articles: