Golang 基于 LinkedHashMap 实现的 Set 集合库

在 Golang 标准库中没有提供 Set 集合的实现，但我们可以基于 container/list 和 map 来实现一个类似 Java 中 LinkedHashSet 的有序集合。下面我将介绍一个简单的实现方案。

基本实现

package set

import (
	"container/list"
	"fmt"
)

// LinkedHashSet 基于LinkedHashMap实现的有序集合
type LinkedHashSet struct {
	dataMap  map[interface{}]*list.Element // 用于快速查找
	dataList *list.List                    // 用于维护插入顺序
}

// NewLinkedHashSet 创建一个新的LinkedHashSet
func NewLinkedHashSet() *LinkedHashSet {
	return &LinkedHashSet{
		dataMap:  make(map[interface{}]*list.Element),
		dataList: list.New(),
	}
}

// Add 添加元素到集合中
func (s *LinkedHashSet) Add(value interface{}) bool {
	if _, exists := s.dataMap[value]; exists {
		return false // 元素已存在
	}
	
	element := s.dataList.PushBack(value)
	s.dataMap[value] = element
	return true
}

// Remove 从集合中移除元素
func (s *LinkedHashSet) Remove(value interface{}) bool {
	element, exists := s.dataMap[value]
	if !exists {
		return false // 元素不存在
	}
	
	s.dataList.Remove(element)
	delete(s.dataMap, value)
	return true
}

// Contains 检查集合是否包含指定元素
func (s *LinkedHashSet) Contains(value interface{}) bool {
	_, exists := s.dataMap[value]
	return exists
}

// Size 返回集合大小
func (s *LinkedHashSet) Size() int {
	return s.dataList.Len()
}

// Clear 清空集合
func (s *LinkedHashSet) Clear() {
	s.dataList = list.New()
	s.dataMap = make(map[interface{}]*list.Element)
}

// ToSlice 将集合转换为切片
func (s *LinkedHashSet) ToSlice() []interface{} {
	slice := make([]interface{}, 0, s.dataList.Len())
	for element := s.dataList.Front(); element != nil; element = element.Next() {
		slice = append(slice, element.Value)
	}
	return slice
}

// String 实现Stringer接口
func (s *LinkedHashSet) String() string {
	return fmt.Sprintf("%v", s.ToSlice())
}

// Iterator 返回一个迭代器
func (s *LinkedHashSet) Iterator() *Iterator {
	return &Iterator{
		current: s.dataList.Front(),
	}
}

// Iterator 集合迭代器
type Iterator struct {
	current *list.Element
}

// Next 移动到下一个元素
func (it *Iterator) Next() bool {
	if it.current == nil {
		return false
	}
	it.current = it.current.Next()
	return it.current != nil
}

// Value 获取当前元素值
func (it *Iterator) Value() interface{} {
	if it.current == nil {
		return nil
	}
	return it.current.Value
}

使用示例

package main

import (
	"fmt"
	"yourpackage/set"
)

func main() {
	// 创建一个新的有序集合
	s := set.NewLinkedHashSet()

	// 添加元素
	s.Add("apple")
	s.Add("banana")
	s.Add("orange")
	s.Add("apple") // 重复添加会被忽略

	fmt.Println("集合内容:", s) // 集合内容: [apple banana orange]
	fmt.Println("集合大小:", s.Size()) // 集合大小: 3

	// 检查元素是否存在
	fmt.Println("包含 'banana':", s.Contains("banana")) // true
	fmt.Println("包含 'grape':", s.Contains("grape"))   // false

	// 移除元素
	s.Remove("banana")
	fmt.Println("移除 'banana' 后:", s) // [apple orange]

	// 迭代集合
	fmt.Println("迭代集合:")
	it := s.Iterator()
	for it.Value() != nil {
		fmt.Println(it.Value())
		if !it.Next() {
			break
		}
	}

	// 转换为切片
	slice := s.ToSlice()
	fmt.Printf("转换为切片: %v (类型: %T)\n", slice, slice)

	// 清空集合
	s.Clear()
	fmt.Println("清空后集合大小:", s.Size()) // 0
}

功能特点

1. 有序性：保持元素的插入顺序
2. 唯一性：保证集合中元素的唯一性
3. 高效操作：
   • 添加/删除/查找操作的时间复杂度都是 O(1)
4. 迭代支持：可以通过迭代器遍历集合
5. 类型安全：使用泛型可以进一步增强类型安全

扩展建议

1. 泛型支持：在 Go 1.18+ 中可以使用泛型使集合类型安全
2. 并发安全：添加 sync.RWMutex 实现线程安全版本
3. 更多集合操作：实现并集、交集、差集等操作
4. JSON 序列化：实现 MarshalJSON/UnmarshalJSON 方法

这个简单的实现已经能满足大多数 Set 集合的使用场景，如果需要更复杂的功能，可以考虑使用第三方库如 github.com/deckarep/golang-set。