• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号
登陆 注册

Go语言实现HashSet

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

set.go

// set project set.go
package set

type Set interface {
    Add(e interface{}) bool
    Remove(e interface{})
    Clear()
    Contains(e interface{}) bool
    Len() int
    Same(other Set) bool
    Elements() []interface{}
    String() string
}

// 将集合other添加到集合one中
func AddSet(one Set, other Set) {
    if one == nil || other == nil || other.Len() == 0 {
        return
    }
    for _, v := range other.Elements() {
        one.Add(v)
    }
}

// 判断集合 one 是否是集合 other 的超集
func IsSuperset(one Set, other Set) bool {
    if one == nil || other == nil {
        return false
    }
    oneLen := one.Len()
    otherLen := other.Len()
    if oneLen == 0 || oneLen <= otherLen {
        return false
    }
    if oneLen > 0 && otherLen == 0 {
        return true
    }
    for _, v := range other.Elements() {
        if !one.Contains(v) {
            return false
        }
    }
    return true
}

// 生成集合 one 和集合 other 的并集
func Union(one Set, other Set) Set {
    if one == nil && other == nil {
        return nil
    }
    unionedSet := NewSimpleSet()
    AddSet(unionedSet, one)
    AddSet(unionedSet, other)
    return unionedSet
}

// 生成集合 one 和集合 other 的交集
func Intersect(one Set, other Set) Set {
    if one == nil || other == nil {
        return nil
    }
    intersectedSet := NewSimpleSet()
    if one.Len() == 0 || other.Len() == 0 {
        return intersectedSet
    }
    if one.Len() < other.Len() {
        for _, v := range one.Elements() {
            if other.Contains(v) {
                intersectedSet.Add(v)
            }
        }
    } else {
        for _, v := range other.Elements() {
            if one.Contains(v) {
                intersectedSet.Add(v)
            }
        }
    }
    return intersectedSet
}

// 生成集合 one 对集合 other 的差集
func Difference(one Set, other Set) Set {
    if one == nil {
        return nil
    }
    differencedSet := NewSimpleSet()
    if other == nil || other.Len() == 0 {
        AddSet(differencedSet, one)
        return differencedSet
    }
    for _, v := range one.Elements() {
        if !other.Contains(v) {
            differencedSet.Add(v)
        }
    }
    return differencedSet
}

// 生成集合 one 和集合 other 的对称差集
func SymmetricDifference(one Set, other Set) Set {
    diffA := Difference(one, other)
    if other == nil || other.Len() == 0 {
        return diffA
    }
    diffB := Difference(other, one)
    return Union(diffA, diffB)
}

// 返回一个HashSet
func NewSimpleSet() Set {
    return NewHashSet()
}

// 判断给定value是否为集合
func IsSet(value interface{}) bool {
    if _, ok := value.(Set); ok {
        return true
    }
    return false
}

hash_set.go

// hash_set
package set

import (
    "bytes"
    "fmt"
)

type HashSet struct {
    m map[interface{}]bool
}

// 创建和初始化HashSet的方法
func NewHashSet() *HashSet {
    return &HashSet{m: make(map[interface{}]bool)}
}

// 向HashSet中添加元素的方法
func (set *HashSet) Add(e interface{}) bool {
    if !set.m[e] {
        set.m[e] = true
        return true
    }
    return false
}

// 删除HashSet中指定的元素
func (set *HashSet) Remove(e interface{}) {
    delete(set.m, e)
}

// 清除HashSet中的所有元素
func (set *HashSet) Clear() {
    set.m = make(map[interface{}]bool)
}

// 判断HashSet是否包含指定元素
func (set *HashSet) Contains(e interface{}) bool {
    return set.m[e]
}

// 获取HashSet中元素值数量
func (set *HashSet) Len() int {
    return len(set.m)
}

// 判断两个Set类型值是否相同
func (set *HashSet) Same(other Set) bool {
    if other == nil {
        return false
    }
    if set.Len() != other.Len() {
        return false
    }
    for key := range set.m {
        if !other.Contains(key) {
            return false
        }
    }
    return true
}

// 生成HashSet的一个快照
func (set *HashSet) Elements() []interface{} {
    initialLen := len(set.m)
    snapshot := make([]interface{}, initialLen)
    actualLen := 0
    for key := range set.m {
        if actualLen < initialLen {
            snapshot[actualLen] = key
        } else {
            snapshot = append(snapshot, key)
        }
        actualLen++
    }
    if actualLen < initialLen {
        snapshot = snapshot[:actualLen]
    }
    return snapshot
}

// 获取HashSet自身字符串表示形式
func (set *HashSet) String() string {
    var buf bytes.Buffer
    buf.WriteString("Set{")
    first := true
    for key := range set.m {
        if first {
            first = false
        } else {
            buf.WriteString(" ")
        }
        buf.WriteString(fmt.Sprintf("%v", key))
    }
    buf.WriteString("}")
    return buf.String()
}

功能测试：

set_test.go

// set_test
package set

import (
    "bytes"
    "fmt"
    "math/rand"
    "runtime/debug"
    "strings"
    "testing"
    "time"
)

func testSetLenAndContains(t *testing.T, newSet func() Set, typeName string) {
    t.Logf("Starting Test%sLenAndContains...", typeName)
    set, expectedElemMap := genRandSet(newSet)
    t.Logf("Got a %s value: %v.", typeName, set)
    expectedLen := len(expectedElemMap)
    if set.Len() != expectedLen {
        t.Errorf("ERROR: The length of %s value %d is not %d!\n",
            set.Len(), typeName, expectedLen)
        t.FailNow()
    }
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
    for k := range expectedElemMap {
        if !set.Contains(k) {
            t.Errorf("ERROR: The %s value %v do not contains %v!",
                set, typeName, k)
            t.FailNow()
        }
    }
}

func testSetAdd(t *testing.T, newSet func() Set, typeName string) {
    t.Logf("Starting Test%sAdd...", typeName)
    set := newSet()
    var randElem interface{}
    var result bool
    expectedElemMap := make(map[interface{}]bool)
    for i := 0; i < 5; i++ {
        randElem = genRandElement()
        t.Logf("Add %v to the %s value %v.\n", randElem, typeName, set)
        result = set.Add(randElem)
        if expectedElemMap[randElem] && result {
            t.Errorf("ERROR: The element adding (%v => %v) is successful but should be failing!\n",
                randElem, set)
            t.FailNow()
        }
        if !expectedElemMap[randElem] && !result {
            t.Errorf("ERROR: The element adding (%v => %v) is failing!\n",
                randElem, set)
            t.FailNow()
        }
        expectedElemMap[randElem] = true
    }
    t.Logf("The %s value: %v.", typeName, set)
    expectedLen := len(expectedElemMap)
    if set.Len() != expectedLen {
        t.Errorf("ERROR: The length of %s value %d is not %d!\n",
            set.Len(), typeName, expectedLen)
        t.FailNow()
    }
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
    for k := range expectedElemMap {
        if !set.Contains(k) {
            t.Errorf("ERROR: The %s value %v do not contains %v!",
                set, typeName, k)
            t.FailNow()
        }
    }
}

func testSetRemove(t *testing.T, newSet func() Set, typeName string) {
    t.Logf("Starting Test%sRemove...", typeName)
    set, expectedElemMap := genRandSet(newSet)
    t.Logf("Got a %s value: %v.", typeName, set)
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
    var number int
    for k, _ := range expectedElemMap {
        if number%2 == 0 {
            t.Logf("Remove %v from the HashSet value %v.\n", k, set)
            set.Remove(k)
            if set.Contains(k) {
                t.Errorf("ERROR: The element removing (%v => %v) is failing!\n",
                    k, set)
                t.FailNow()
            }
            delete(expectedElemMap, k)
        }
        number++
    }
    expectedLen := len(expectedElemMap)
    if set.Len() != expectedLen {
        t.Errorf("ERROR: The length of HashSet value %d is not %d!\n", set.Len(), expectedLen)
        t.FailNow()
    }
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
    for _, v := range set.Elements() {
        if !expectedElemMap[v] {
            t.Errorf("ERROR: The HashSet value %v contains %v but should not contains!", set, v)
            t.FailNow()
        }
    }
}

func testSetClear(t *testing.T, newSet func() Set, typeName string) {
    t.Logf("Starting Test%sClear...", typeName)
    set, _ := genRandSet(newSet)
    t.Logf("Got a %s value: %v.", typeName, set)
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
    t.Logf("Clear the HashSet value %v.\n", set)
    set.Clear()
    expectedLen := 0
    if set.Len() != expectedLen {
        t.Errorf("ERROR: The length of HashSet value %d is not %d!\n", set.Len(), expectedLen)
        t.FailNow()
    }
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
}

func testSetElements(t *testing.T, newSet func() Set, typeName string) {
    t.Logf("Starting Test%sElements...", typeName)
    set, expectedElemMap := genRandSet(newSet)
    t.Logf("Got a %s value: %v.", typeName, set)
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
    elems := set.Elements()
    t.Logf("The elements of %s value is %v.\n", typeName, elems)
    expectedLen := len(expectedElemMap)
    if len(elems) != expectedLen {
        t.Errorf("ERROR: The length of HashSet value %d is not %d!\n", len(elems), expectedLen)
        t.FailNow()
    }
    t.Logf("The length of elements is %d.\n", len(elems))
    for _, v := range elems {
        if !expectedElemMap[v] {
            t.Errorf("ERROR: The elements %v contains %v but should not contains!", set, v)
            t.FailNow()
        }
    }
}

func testSetSame(t *testing.T, newSet func() Set, typeName string) {
    t.Logf("Starting Test%sSame...", typeName)
    set, _ := genRandSet(newSet)
    t.Logf("Got a %s value: %v.", typeName, set)
    t.Logf("The length of %s value is %d.\n", typeName, set.Len())
    set2 := newSet()
    t.Logf("Clone the HashSet value %v...\n", set)
    for _, v := range set.Elements() {
        set2.Add(v)
    }
    result := set2.Same(set)
    if !result {
        t.Errorf("ERROR: Two sets are not same!")
    }
    t.Logf("Two sets are same.")
}

func testSetString(t *testing.T, newSet func() Set, typeName string) {
    t.Logf("Starting Test%sString...", typeName)
    set, _ := genRandSet(newSet)
    t.Logf("Got a %s value: %v.", typeName, set)
    setStr := set.String()
    t.Logf("The string of %s value is %s.\n", typeName, setStr)
    var elemStr string
    for _, v := range set.Elements() {
        elemStr = fmt.Sprintf("%v", v)
        if !strings.Contains(setStr, elemStr) {
            t.Errorf("ERROR: The string of %s value %s do not contains %s!",
                typeName, setStr, elemStr)
            t.FailNow()
        }
    }
}

// ----- Set 公用函数测试 -----

func TestIsSuperset(t *testing.T) {
    defer func() {
        if err := recover(); err != nil {
            debug.PrintStack()
            t.Errorf("Fatal Error: %s\n", err)
        }
    }()
    t.Log("Starting TestIsSuperset...")
    set, _ := genRandSet(func() Set { return NewSimpleSet() })
    set2 := NewSimpleSet()
    for _, v := range set.Elements() {
        set2.Add(v)
    }
    for extraElem := genRandElement(); ; {
        if set2.Add(extraElem) {
            break
        } else {
            time.Sleep(10 * time.Millisecond)
        }
    }
    if !IsSuperset(set2, set) {
        t.Errorf("ERROR: The HashSet value %v is not a superset of %v!\n", set2, set)
        t.FailNow()
    } else {
        t.Logf("The HashSet value %v is a superset of %v.\n", set2, set)
    }
    for extraElem := genRandElement(); ; {
        if set.Add(extraElem) {
            break
        } else {
            time.Sleep(10 * time.Millisecond)
        }
    }
    if IsSuperset(set2, set) {
        t.Errorf("ERROR: The HashSet value %v should not be a superset of %v!\n", set2, set)
        t.FailNow()
    } else {
        t.Logf("The HashSet value %v is not a superset of %v.\n", set2, set)
    }
}

func TestUnion(t *testing.T) {
    defer func() {
        if err := recover(); err != nil {
            debug.PrintStack()
            t.Errorf("Fatal Error: %s\n", err)
        }
    }()
    t.Log("Starting TestUnion...")
    set, _ := genRandSet(func() Set { return NewSimpleSet() })
    t.Logf("The set value: %v", set)
    set2, _ := genRandSet(func() Set { return NewSimpleSet() })
    uSet := Union(set, set2)
    t.Logf("The set value (2): %v", set2)
    for _, v := range set.Elements() {
        if !uSet.Contains(v) {
            t.Errorf("ERROR: The union set value %v do not contains %v!",
                uSet, v)
            t.FailNow()
        }
    }
    for _, v := range set2.Elements() {
        if !uSet.Contains(v) {
            t.Errorf("ERROR: The union set value %v do not contains %v!",
                uSet, v)
            t.FailNow()
        }
    }
    t.Logf("The set value %v is a unioned set of %v and %v", uSet, set, set2)
}

func TestIntersect(t *testing.T) {
    defer func() {
        if err := recover(); err != nil {
            debug.PrintStack()
            t.Errorf("Fatal Error: %s\n", err)
        }
    }()
    t.Log("Starting TestIntersect...")
    commonElem := genRandElement()
    set, _ := genRandSet(func() Set { return NewSimpleSet() })
    set.Add(commonElem)
    t.Logf("The set value: %v", set)
    set2, _ := genRandSet(func() Set { return NewSimpleSet() })
    set2.Add(commonElem)
    t.Logf("The set value (2): %v", set2)
    iSet := Intersect(set, set2)
    for _, v := range iSet.Elements() {
        if !set.Contains(v) {
            t.Errorf("ERROR: The set value %v do not contains %v!",
                set, v)
            t.FailNow()
        }
        if !set2.Contains(v) {
            t.Errorf("ERROR: The set value %v do not contains %v!",
                set2, v)
            t.FailNow()
        }
    }
    t.Logf("The set value %v is a intersected set of %v and %v", iSet, set, set2)
}

func TestDifference(t *testing.T) {
    defer func() {
        if err := recover(); err != nil {
            debug.PrintStack()
            t.Errorf("Fatal Error: %s\n", err)
        }
    }()
    t.Log("Starting TestDifference...")
    commonElem := genRandElement()
    set, _ := genRandSet(func() Set { return NewSimpleSet() })
    set.Add(commonElem)
    t.Logf("The set value: %v", set)
    set2, _ := genRandSet(func() Set { return NewSimpleSet() })
    set2.Add(commonElem)
    t.Logf("The set value (2): %v", set2)
    dSet := Difference(set, set2)
    for _, v := range dSet.Elements() {
        if !set.Contains(v) {
            t.Errorf("ERROR: The set value %v do not contains %v!",
                set, v)
            t.FailNow()
        }
        if set2.Contains(v) {
            t.Errorf("ERROR: The set value %v contains %v!",
                set2, v)
            t.FailNow()
        }
    }
    t.Logf("The set value %v is a differenced set of %v to %v", dSet, set, set2)
}

func TestSymmetricDifference(t *testing.T) {
    defer func() {
        if err := recover(); err != nil {
            debug.PrintStack()
            t.Errorf("Fatal Error: %s\n", err)
        }
    }()
    t.Log("Starting TestSymmetricDifference...")
    commonElem := genRandElement()
    set, _ := genRandSet(func() Set { return NewSimpleSet() })
    set.Add(commonElem)
    t.Logf("The set value: %v", set)
    set2, _ := genRandSet(func() Set { return NewSimpleSet() })
    set2.Add(commonElem)
    t.Logf("The set value (2): %v", set2)
    sdSet := SymmetricDifference(set, set2)
    for _, v := range sdSet.Elements() {
        if set.Contains(v) && set2.Contains(v) {
            t.Errorf("ERROR: The element %v can not be a common element of %v to %v!",
                v, set, set2)
            t.FailNow()
        }
    }
    t.Logf("The set value %v is a symmetric differenced set of %v to %v", sdSet, set, set2)
}

// ----- 随机测试对象生成函数 -----

func genRandSet(newSet func() Set) (set Set, elemMap map[interface{}]bool) {
    set = newSet()
    elemMap = make(map[interface{}]bool)
    var enough bool
    for !enough {
        e := genRandElement()
        set.Add(e)
        elemMap[e] = true
        if len(elemMap) >= 3 {
            enough = true
        }
    }
    return
}

func genRandElement() interface{} {
    seed := rand.Int63n(10000)
    switch seed {
    case 0:
        return genRandInt()
    case 1:
        return genRandString()
    case 2:
        return struct {
            num int64
            str string
        }{genRandInt(), genRandString()}
    default:
        const length = 2
        arr := new([length]interface{})
        for i := 0; i < length; i++ {
            if i%2 == 0 {
                arr[i] = genRandInt()
            } else {
                arr[i] = genRandString()
            }
        }
        return *arr
    }
}

func genRandString() string {
    var buff bytes.Buffer
    var prev string
    var curr string
    for i := 0; buff.Len() < 3; i++ {
        curr = string(genRandAZAscii())
        if curr == prev {
             
                       
                    
                    
 
                      





鲜花




握手




雷人




路过




鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
gomap的定义和使用键值对存储发布时间：2022-07-10
下一篇：
go标准库的学习-mime发布时间：2022-07-10
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap