README
¶
hashset
Introduction
In this repository, we implemented one foundational data structure: Set based on Map in golang. We have:
Add(value int64): Adds the specified element to this set.
Contains(value int64) bool: Returns true if this set contains the specified element.
Remove(value int64): Removes the specified element from this set.
Range(f func(value int64) bool): Function f executes by taking element in the set as parameter sequentially until f returns false
Len() int: Returns the number of elements of this set.
We made two experiments in order to measure the overall performance of the new hashset:
- the chosen value's type: empty struct vs. bool
- the impact of checking the existence of the key before add/remove an item
Features
- The API of hashset is totally compatible with skipset link
- Usually, developers implement the set in golang by setting the value of <key,value> pair to
boolorint. However, We proved that using empty struct is more space efficiency and slightly time efficiency.
When to use hashset
Hashset doesnt guarantee concurrent safe. If you do need a concurrent safe set, go for skipset [link] -> https://github.com/bytedance/gopkg/tree/develop/collection/skipset
Quickstart
package main
import (
"fmt"
"github.com/bytedance/gopkg/collection/hashset"
)
func main() {
l := hashset.NewInt()
for _, v := range []int{10, 12, 15} {
if l.Add(v) {
fmt.Println("hashset add", v)
}
}
if l.Contains(10) {
fmt.Println("hashset contains 10")
}
l.Range(func(value int) bool {
fmt.Println("hashset range found ", value)
return true
})
l.Remove(15)
fmt.Printf("hashset contains %d items\r\n", l.Len())
}
Benchmark
go version: go1.15.10 linux/amd64
CPU: Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz (4C8T)
OS: Debian 4.14.81.bm.15
MEMORY: 16G
$ go test -run=None -bench=. -benchtime=1000000x -benchmem -count=10 -cpu=4 > 1000000x20x4.txt
$ benchstat 1000000x20x4.txt
name time/op
ValueAsBool-4 301ns ± 7%
ValueAsEmptyStruct-4 300ns ± 7%
AddAfterContains-4 334ns ± 5%
AddWithoutContains-4 303ns ± 9%
RemoveAfterContains_Missing-4 177ns ± 4%
RemoveWithoutContains_Missing-4 176ns ± 7%
RemoveAfterContains_Hitting-4 205ns ± 2%
RemoveWithoutContains_Hitting-4 135ns ±16%
name alloc/op
ValueAsBool-4 54.0B ± 0%
ValueAsEmptyStruct-4 49.0B ± 0%
AddAfterContains-4 49.0B ± 0%
AddWithoutContains-4 49.0B ± 0%
RemoveAfterContains_Missing-4 0.00B
RemoveWithoutContains_Missing-4 0.00B
RemoveAfterContains_Hitting-4 0.00B
RemoveWithoutContains_Hitting-4 0.00B
Documentation
¶
Overview ¶
Example ¶
l := NewInt()
for _, v := range []int{10, 12, 15} {
l.Add(v)
}
if l.Contains(10) {
fmt.Println("hashset contains 10")
}
l.Range(func(value int) bool {
fmt.Println("hashset range found ", value)
return true
})
l.Remove(15)
fmt.Printf("hashset contains %d items\r\n", l.Len())
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Float32Set ¶
type Float32Set map[float32]struct{}
func NewFloat32WithSize ¶
func NewFloat32WithSize(size int) Float32Set
NewFloat32WithSize returns an empty float32 set initialized with specific size
func (Float32Set) Add ¶
func (s Float32Set) Add(value float32) bool
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
func (Float32Set) Contains ¶
func (s Float32Set) Contains(value float32) bool
Contains returns true if this set contains the specified element
func (Float32Set) Len ¶
func (s Float32Set) Len() int
func (Float32Set) Range ¶
func (s Float32Set) Range(f func(value float32) bool)
Range calls f sequentially for each value present in the hashset. If f returns false, range stops the iteration.
func (Float32Set) Remove ¶
func (s Float32Set) Remove(value float32) bool
Remove removes the specified element from this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type Float64Set ¶
type Float64Set map[float64]struct{}
func NewFloat64WithSize ¶
func NewFloat64WithSize(size int) Float64Set
NewFloat64WithSize returns an empty float64 set initialized with specific size
func (Float64Set) Add ¶
func (s Float64Set) Add(value float64) bool
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
func (Float64Set) Contains ¶
func (s Float64Set) Contains(value float64) bool
Contains returns true if this set contains the specified element
func (Float64Set) Len ¶
func (s Float64Set) Len() int
func (Float64Set) Range ¶
func (s Float64Set) Range(f func(value float64) bool)
Range calls f sequentially for each value present in the hashset. If f returns false, range stops the iteration.
func (Float64Set) Remove ¶
func (s Float64Set) Remove(value float64) bool
Remove removes the specified element from this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type Int16Set ¶
type Int16Set map[int16]struct{}
func NewInt16WithSize ¶
NewInt16WithSize returns an empty int16 set initialized with specific size
func (Int16Set) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type Int32Set ¶
type Int32Set map[int32]struct{}
func NewInt32WithSize ¶
NewInt32WithSize returns an empty int32 set initialized with specific size
func (Int32Set) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type Int64Set ¶
type Int64Set map[int64]struct{}
func NewInt64WithSize ¶
NewInt64WithSize returns an empty int64 set initialized with specific size
func (Int64Set) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type IntSet ¶
type IntSet map[int]struct{}
func NewIntWithSize ¶
NewIntWithSize returns an empty int set initialized with specific size
func (IntSet) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type Uint16Set ¶
type Uint16Set map[uint16]struct{}
func NewUint16WithSize ¶
NewUint16WithSize returns an empty uint16 set initialized with specific size
func (Uint16Set) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type Uint32Set ¶
type Uint32Set map[uint32]struct{}
func NewUint32WithSize ¶
NewUint32WithSize returns an empty uint32 set initialized with specific size
func (Uint32Set) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type Uint64Set ¶
type Uint64Set map[uint64]struct{}
func NewUint64WithSize ¶
NewUint64WithSize returns an empty uint64 set initialized with specific size
func (Uint64Set) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
type UintSet ¶
type UintSet map[uint]struct{}
func NewUintWithSize ¶
NewUintWithSize returns an empty uint set initialized with specific size
func (UintSet) Add ¶
Add adds the specified element to this set Always returns true due to the build-in map doesn't indicate caller whether the given element already exists Reserves the return type for future extension
Source Files