Go泛型接口约束

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 {
    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,
    }
}