Go泛型也出来很久了，最近也用泛型去实现一些功能，例如数据结构一些应用还是没有什么问题的。但是如果做一些类型上限制，还是有点问题，和其他语言有一些不一样的地方，想要基于泛型做一些类型上的限制，必须使用组合的模式，或者嵌套。这篇我将记录一下我在Go泛型上遇到一些问题。

阅读这篇文章读者需要了解Go泛型怎么使用和泛型能做什么，还有了解map结构原理，并且本文会以LinkedHashMap作为一个泛型结构讲解一些关于Go泛型不完美的地方。读者要知道LinkedHashMap底层是怎么工作的才能读懂这篇文章。

原生Map局限性

大家都知道Go的内置map结构在遍历的时候是无序的，如果要让其有序输出那么就要对key进行排序，然后收集排序完的key依次索引输出这样子，但是很麻烦的样子，并且还不能保证map存储的的顺序不是以插入值的顺序而存储，并且还不能按照访问操作顺序重排底层存储结构元素的关系，了解的原生map应该知道底层是通过hash function打乱并且存储在不同桶里，遍历只能从不同的桶里随机输出这些元素，这就是无序的原因。

LinkedHashMap

使用过Java朋友应该知道一个数据结构叫LinkedHashMap，这个数据结构是可以保证数据存储顺序的，并且还能按照配置动态调整存储的元素的顺序关系，下面这是一段Java代码，介绍一下工作原理：

LinkedHashMap<String, Integer> lmap = new LinkedHashMap<String, Integer>();
lmap.put("语文", 1);
lmap.put("数学", 2);
lmap.put("英语", 3);
lmap.put("历史", 4);
lmap.put("政治", 5);
lmap.put("地理", 6);
lmap.put("生物", 7);
lmap.put("化学", 8);
for(Entry<String, Integer> entry : lmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

输出结果可以看到：

语文: 1
数学: 2
英语: 3
历史: 4
政治: 5
地理: 6
生物: 7
化学: 8

可以看到是以我们插入时候的顺序输出的结果，可以做到有序的。

这是怎么做到的呢？如果深入底层源代码分析发现，他内部结构入下图：

和HashMap的运行结果不同，LinkedHashMap的迭代输出的结果保持了插入顺序，它底层其实就是一个map加Linked List组成一个结构，map负责索引，而Linked List负责的是数据顺序组织存储方式，可以形成一个完全有序的链表，大部分可能认为就是一个链式存储方式，这是不对的，有兴趣可以源代码，是两种数据结构组合而成，类似于LRU淘汰算法那样，每次操作元素都会发生底层数据交换位置。

元素是被内置的map索引着的只是为了方便快速拿取，而为了数据能和插入时一致的顺序又用链表组织成了有序链表，原理可以想象上面这幅图，你洗衣服拿衣服怎么洗的？如果读者看到这里看不懂话，可以去网上看看关于LinkedHashMap底层实现的代码分析文章吧，我这里不讲解了。

用Go泛型实现

对其工作原理介绍完了，下面我就针对这个这种方式，使用Go去实现类似的，算是重复造轮子吧。但是在泛型key上还是遇到一些问题，顺便写一个文章记录。

下面这是我使用Go复刻的LinkedHashMap代码，Node[K Hashed, V any]结构是为了底层数据存储所设计的，而LinkedHashMap为主体结构，注意里面的table map[uint64]*Node[K, V]字段。

type Node[K Hashed, V any] struct {
    Prev, Next *Node[K, V]
    Key        K
    Value      V
}

// Stored structure
type LinkedHashMap[K Hashed, V any] struct {
    accessOrder bool                   // the iteration ordering method
    capacity    int                    // total capacity
    head, tail  *Node[K, V]            // linked list
    table       map[uint64]*Node[K, V] // data storeage
    size        int                    // current size
}

为了这个map能达到和Java的LinkedHashMap一样的效果，我在key泛型上做了限制，因为要支持双泛型参数声明，有两个泛型参数，如果简单一个话，这个键完全可以设置为string类型，那这样的后果就调用方只能使用string类型做为键了，而value可以泛型，那么就会失去双参数泛型的意义。

type Hashed interface {
    comparable
    string
    HashCode() uint64
}

为了支持更多类型作为key这里我定义了一个Hashed接口作为泛型约束，可以看到comparable和string还有HashCode() uint64，
comparable为了默认一些基础的数据类型例如int和float能作为键，而string大家了解他底层实现的话其实是一个包装的类型，真实的数据是[]byte类型，如果以现在的方式去使用string作为键，那么我还要针对string去做哈希才能得到最终哈希值。

在看一下具体的crud代码：

func NewLinkedHashMap[K Hashed, V any](capacity int, accessOrder bool) LinkedHashMap[K, V] {
    return LinkedHashMap[K, V]{
      accessOrder: accessOrder,
      capacity:    capacity,
      table:       make(map[uint64]*Node[K, V], capacity),
    }
}

func (hashmap *LinkedHashMap[K, V]) Put(key K, value V) bool {

    // 问题就在这：
    // 如果是按照我现在定义接口去实现，自定义结构体实现HashCode() uint64就可以满足这个key类型约束？
    // 但是如果默认内置的数据类型，就没有实现HashCode() uint64，不能满足，如果需要满足就要实现HashCode() uint64
    // 解决方法我在文末列举几种
    

    // 如果按照当前的设计则我就要回归到类型断言，根据不同类型去调用不同计算方法
    // 这种是我不推荐的，我还是建议使用类型组合制造一个新的类型，然后去实现HashCode() uint64
    // 或者把map[uint64]*Node[K, V]的Key也改成泛型版本

    // 如果是字符串 go内置的string没有实现HashCode()uint64
    sum64 := Sum64([]byte(key))

    // 自定义泛型 我们自己可以实现 HashCode()uint64
    sum64 = key.HashCode()

    node := &Node[K, V]{
      Key:   key,
      Value: value,
    }

    if hashmap.size == 0 {
      hashmap.head = node
      hashmap.tail = node
      return true
    }

    if node, ok := hashmap.table[sum64]; ok {
      node.Value = value
      moveNode(node)
      node.Next = nil
      addNodeAtTail(hashmap, node)
      hashmap.size += 1
      return true
    }

    addNodeAtTail(hashmap, node)
    hashmap.table[sum64] = node
    hashmap.size += 1

    return true
}

func (hashmap *LinkedHashMap[K, V]) Remove(key K) {

}

func (hashmap *LinkedHashMap[K, V]) Get(key K) *V {
    return nil
}

func (hashmap *LinkedHashMap[K, V]) Size() int {
    return hashmap.size
}

// 从两个节点中间删除节点
func moveNode[K Hashed, V any](node *Node[K, V]) {
    node.Next.Prev = node.Prev
    node.Prev.Next = node.Next
}

// addTail 添加节点到链表尾巴
func addNodeAtTail[K Hashed, V any](hashmap *LinkedHashMap[K, V], node *Node[K, V]) {
    node.Prev = hashmap.tail
    hashmap.tail.Next = node
    hashmap.tail = node
}

问题来了，看函数签名为(hashmap *LinkedHashMap[K, V]) Put(key K, value V)的函数，问题在这，key我在设计的时候就限制为了Hashed类型，而如果这个key在使用的时候传入的是结构体类型，结构体实现了HashCode() uint64 那么就做成key，如果是默认字符串，go内置的类型没有实现HashCode()uint64，那么我这里就要断言了，看看是不是string 然后函数内置去计算哈希？有木有什么办法不这样搞？

解决方法好几种：

  • 所以最后还是回归到类型断言，我其实想有木有其他好办法解决？
  • 还有一种方法就是我在我自己包里面 自定义一个装个一个string类型代替 默认内置的string类型 去实现HashCode()uint64 接口，这样就可以正确了，不过调用者在泛型字符串的时候必须使用我包里面这个string类型。
  • 如果按照上面这种其他类型也要去实现。
  • 还有一种让内置的table泛型也是和外面的LinkedHashMap一样，交给go编译器自己去处理，那这样就没有HashCode()uint64方法了。

例如下面这样我就自定义造了一个String包装类型满足key要求：

type Hashed interface {
    // comparable
    // string
    HashCode() uint64
}

type String struct {
    string
}

func (s String) HashCode() uint64 {
    return Sum64([]byte(s.string))
}

func MakeString(str string) String {
    return String{
      string: str,
    }
}

内外一致泛型

下面是通过外内map的key泛型类型一直实现的代码，并且为其实现了迭代器代码，但是迭代器还是有点问题，不能返回节点的key：

package sortmap

import "github.com/auula/coffee"

type Node[K comparable, V any] struct {
    Prev, Next *Node[K, V]
    Key        K
    Value      V
}

// Stored structure
type LinkedHashMap[K comparable, V any] struct {
    capacity   int               // total capacity
    head, tail *Node[K, V]       // linked list
    table      map[K]*Node[K, V] // data storeage
    size       int               // current size
}

func New[K comparable, V any](capacity int) LinkedHashMap[K, V] {
    return LinkedHashMap[K, V]{
        capacity: capacity,
        table:    make(map[K]*Node[K, V], capacity),
    }
}

func (hashmap *LinkedHashMap[K, V]) Put(key K, value V) bool {

    node := &Node[K, V]{
        Key:   key,
        Value: value,
    }

    if hashmap.size == 0 {
        hashmap.head = node
        hashmap.tail = node
        hashmap.table[key] = node
        hashmap.size += 1
        return true
    }

    if node, ok := hashmap.table[key]; ok {
        node.Value = value
        return true
    }

    addNodeAtTail(hashmap, node)
    hashmap.table[key] = node
    hashmap.size += 1

    return true
}

func (hashmap *LinkedHashMap[K, V]) Remove(key K) {
    if node, ok := hashmap.table[key]; ok {
        moveNode(hashmap, node)
        hashmap.size -= 1
        delete(hashmap.table, key)
    }
}

func (hashmap *LinkedHashMap[K, V]) Get(key K) (*K, *V) {

    var (
        node *Node[K, V]
        ok   bool
    )

    if node, ok = hashmap.table[key]; !ok {
        return nil, nil
    }

    moveNode(hashmap, node)
    addNodeAtTail(hashmap, node)

    return &node.Key, &node.Value
}

func (hashmap *LinkedHashMap[K, V]) Clear() {
    hashmap.size = 0
    hashmap.head = nil
    hashmap.tail = nil
    hashmap.table = make(map[K]*Node[K, V], hashmap.capacity)
}

func (hashmap *LinkedHashMap[K, V]) Size() int {
    return hashmap.size
}

// 从两个节点中间删除节点
func moveNode[K comparable, V any](hashmap *LinkedHashMap[K, V], node *Node[K, V]) {
    if node == hashmap.head {
        node.Next.Prev = nil
        hashmap.head = node.Next
        return
    }
    if node == hashmap.tail {
        node.Prev.Next = nil
        hashmap.tail = node.Prev
        return
    }
    node.Next.Prev = node.Prev
    node.Prev.Next = node.Next
}

// addTail 添加节点到链表尾巴
func addNodeAtTail[K comparable, V any](hashmap *LinkedHashMap[K, V], node *Node[K, V]) {
    node.Prev = hashmap.tail
    hashmap.tail.Next = node
    hashmap.tail = node
}

func (hashmap *LinkedHashMap[K, V]) Iter() coffee.Iterator[V] {
    return hashmap
}

func (hashmap *LinkedHashMap[K, V]) HasNext() bool {
    return hashmap.size != 0
}

func (hashmap *LinkedHashMap[K, V]) Next() V {
    var node *Node[K, V]
    if node = hashmap.head; node != nil {
        hashmap.head = hashmap.head.Next
        hashmap.size -= 1
        return node.Value
    }
    return node.Value
}

func (hashmap *LinkedHashMap[K, V]) Range(fn func(Node[K, V])) {
    var node *Node[K, V]
    for hashmap.size != 0 {
        if node = hashmap.head; node != nil {
            hashmap.head = hashmap.head.Next
            hashmap.size -= 1
            fn(*node)
        }
    }
}

使用起来很简单：

package main

import (
    "fmt"

    "github.com/auula/coffee/sortmap"
)

func main() {

    var sm = sortmap.New[string, float64](10)

    sm.Put("Go", 91.2)
    sm.Put("Java", 100)
    sm.Put("Rust", 80.1)

    // 因为返回的是地址，如果没有返回值则为nil
    fmt.Println(sm.Get("Go101"))

    // 如果有值则返回对应类型的指针
    k, v := sm.Get("Rust")

    fmt.Printf("\n key:%s \t value:%f \n", *k, *v)

    // coffee.ForEach(sm.Iter(), func(i float64) {
    //     fmt.Println(i)
    // })

    sm.Range(func(node sortmap.Node[string, float64]) {
        fmt.Printf("\n key:%s \t value:%f \n", node.Key, node.Value)
    })
}

Go官方建议

Go官方给出使用泛型的意见是使用泛型去减少一些类型一样的重复代码，例如数据结构，这样子的。但是如果把泛型用一些类型约束上还是和一些其他原因有所差距，要使用嵌套或者组合的方式重新构建新的类型去实现，然后使用构建的类型，例如上面我给出的我的这个例子。

便宜 VPS vultr
最后修改：2023 年 07 月 05 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏 🌹 谢谢 ！