主要内容：
泛型作为现代语言的一大重要特性，与 1.18 版本被引入。泛型的引入不仅节省了针对不同类型的代码的代码量，也改变了“接口”这一重要概念的定义。
提示
Go 的泛型说实话实现的有点也不能说是残缺，就是说别扭吧。除了这个[T]符号选的贼怪异（与切片声明混合容易造成语义不明）之外，泛型还不支持方法和匿名函数也是虽然可以说无伤大雅，但也可以说是功能残缺。不过我个人就不太想纠结这些事情，我什么水平去直接关心语言的实现（），用就是了。
Go 中的泛型声明使用[]这一符号，一个简单的泛型函数示例如下：
gofunc GenericFuncTest [T comparable] (param1 T) T {
return param1
}
func t () {
GenericFuncTest[int](1)
}
在上述代码中，引入了泛型T，每次调用GenericFuncTest函数时，都要指定这个泛型的实际类型。而T的后面用comparable指定了该泛型的类型范围。这一段话里就引出了三个概念：
T，即每次使用泛型时，可以理解为那个泛型的代指int，每次使用泛型时，实际要用的类型comparable，该泛型能够匹配的类型除了泛型函数，类型也是可以指定泛型的，而且上面三个概念依然沿用。
gotype GenericMapTest [Key comparable, Value string | int | []string | []Key] map[Key]Value // 没错 泛型可以一次性指定多个 还能互相嵌套
func t () {
m := GenericMapTest[int, string]{}
m[1] = "1"
}
但是有些写法是会报错的，比如这样：
go//type GenericSliceTest [Elem *GenericMapTest[int, string]] []Elem
// 会报错 主要原因就在那个 * 上
// 下面这个写法就没问题 如果泛型出了语法问题可以考虑包上一层 interface
type GenericSliceTest [Elem interface{*GenericMapTest[int, string]}] []Elem
另外，匿名结构体和匿名函数是不支持泛型的。
既然有了泛型类型和泛型函数，那么泛型方法也有，虽然多少有点功能不全。
gotype GenericMapTest [Key comparable, Value any] map[Key]Value
func (receiver GenericMapTest[Key, Value]) DeleteElement(key Key) (deleteValue Value) {
deleteValue, ok := receiver[key]
if ok {
delete(receiver, key)
return deleteValue
}
return
}
关于泛型方法，要提的点有这几条：
gofunc (receiver GenericMapTest[Key, Value]) DeleteElement[T any](key Key) (deleteValue T)
提示
关于为什么方法不能引入除了调用者泛型以外的泛型，最简洁的回答是：可以做，但是为了避免编译器复杂度所以没做。具体点说的话，原因如下：
GenericMapTest的时候先过，到具体的要用到这个类型的时候m := GenericMapTest[int, string]{}再编译int，string对应代码。any断言为 A 类型，调用泛型方法。此时编译器是不知道 B 类型的那个泛型方法实现有没有被针对实际类型编译过的。最极端的情况下，它得扫描整个包才能确定这件事，那开销就大了。更别提类型断言是在运行期而不是编译期的事（我到写这篇文的时候才知道），那更没法编译了。上面的话多少有点别扭，主要是我理解的也有点别扭。看原文的话详情参见：Type Parameter Proposal
之前在指定类型约束的时候，其实很容易一写就写很长的泛型约束，并且这么长的泛型约束也不好复用。所以 Go 将这个问题交给接口来解决。
gotype Int interface {
int | int8 | int16 | int32 | int64
}
type Uint interface {
uint | uint8 | uint16 | uint32
}
type Float interface {
float32 | float64
}
type Slice[T Int | Uint | Float] []T
type SliceElement interface {
Int | Uint | Float | string
}
type Slice[T SliceElement] []T
如上，接口中可以通过指定类型约束来形成一个新的类型，该类型可以在别的泛型中嵌套，也可以和普通的类型一起用。
类型约束可以通过三个运算符来指定：|``~和换行，分别表示类型取并集，类型取底层类型，类型取交集。另外，指定了类型约束的接口仍然可以指定要实现的函数原型。
gotype GenericInterfaceTest interface {
~uint8 | ~uint16 | uint32
byte
String() string
}
如上，该泛型接口所指定的类型约束就是以 uint8 为底层类型的所有类型。首先是上面三个 uint 取并集，之后和下面的 byte 取交集，那么取完之后就剩底层为 uint8 的类型了。
由此可以看到，从 Go 加入泛型之后，以前的接口定义已经不适用了，毕竟不止有要实现的函数。来回顾一下以前的接口是如何定义的：
An interface type specifies a method set called its interface.（一个声明了方法集的接口类型即为接口）
再看看 Go 1.18之后接口的定义：
An interface type defines a type set.（一个接口定义了一个类型的集合）
接口从一个方法集变成了类型集。按照此定义，GenericInterfaceTest的定义即为：所有底层类型为 uint8 的，并且持有String方法的类型的集合；而interface{}类型（Go 1.18后新增其别名any）的定义即为：所有的类型的集合。而原来的接口定义依然可以套这个新的定义，即如果一个类型持有一个接口所定义的所有函数原型的对应方法，那么可以认为该类型属于该接口所定义的类型集。
comparable
特殊的，Go 定义了一个类型comparable，该类型是所有可以用==``!=比较的类型的集合。需要注意，它仅仅是可比较，而不是可以比较大小，它只能比较是否相同。
另外，comparable不能被直接或间接地和其他类型合并。
接口也可以引入泛型，如下示例：
go// 泛型接口定义
type GenericInterfaceTest [T any] interface {
int | struct{ testValue string }
GenericInterfaceFuncTest (value T) string
}
// 如果该接口没有指定类型集的话 可以通过类似 GenericInterfaceTest[string] 这样的方式成为一个变量的类型
// 实现接口
type GenericInterfaceImplement struct {
testValue string
}
func (g *GenericInterfaceImplement) GenericInterfaceFuncTest (value string) string {
return g.testValue + value
}
// 子接口
type GenericInterfaceImplement2 [T any] interface {
int
GenericInterfaceFuncTest (value T) string
}
提示
该实现是在plar/go-adaptive-radix-tree的基础上写的。我阅读了所有源码，对着源码写了自己的代码，并且加入了泛型。
ART 树（adaptive radix tree）是一个在前缀树的基础上进行改进的树，它的主要功能是以字节数组为键，进行键值对的有序存储。相比于一般的前缀树，它可以通过不同的节点大小和压缩前缀来大幅减少内存占用的同时，达到相近的性能。
前缀树：一种按字节数组存储的树。假设它要存储的目标只有a到z这26个字节，那么它的每个节点都有一个长度为26的字节数组，每个元素存储指向子节点的指针。从根节点开始，每个节点按顺序使用字节数组的一个元素来指向子节点，所以前缀树的高度取决于存储的最长的字节数组。
ART 树有四种节点类型：node4，node16，node48，node256。每种节点能存储对应上限个子节点：node4能存储4个子节点，node16能存储16个子节点，以此类推。节点之间可以按需互相转换，比如如果有需求要在node4节点下新增一个子节点的话，该节点就可以转换为node16。
除了可转换的节点以外，ART 树还能重用共有的前缀。举例来说，假如树上存储了以apple，app为键的两个值，那么共同的前缀app就会存储到一个节点中，而不是分成三个节点存储。
该树所能支持的操作如下：
go// New 获取一棵新的树
func New[T Value]() Tree[T] {}
type Node[T Value] interface {
Kind() Kind
Key() Key
Value() T
}
// Iterator 迭代器实例
type Iterator[T Value] interface {
// HasNext 是否存在下一个节点
HasNext() bool
// Next 获取下一个节点 如果下一个节点不存在或者树结构被修改 就返回 NoMoreNodeErr 或者 TreeIsModifiedErr
Next() (node Node[T], e error)
}
// Tree 树的接口
type Tree[T Value] interface {
// Insert 根据指定的键插入新值 如果键在树中已经有值 就更新值 返回旧的值 并且返回 true
Insert(key Key, value T) (oldValue T, isUpdated bool)
// Delete 根据指定的键删除对应的值 并且返回被删除的旧值 如果键不存在将返回 false
Delete(key Key) (deleteValue T, isDeleted bool)
// Search 根据指定的键寻找对应的值
Search(key Key) (value T, isFound bool)
// ForEach 对树进行遍历 对于每个被遍历到的 符合条件的节点调用 callback 函数 默认情况下遍历只遍历叶子节点
ForEach(callback Callback[T], options ...int)
// ForEachWithPrefix 对树进行遍历 对于每个被遍历到的 前缀和指定的键匹配的 符合条件的节点调用 callback 函数 默认情况下遍历只遍历叶子节点
ForEachWithPrefix(keyPrefix Key, callback Callback[T], options ...int)
// Iterator 获取一个新的迭代器 默认只遍历叶子节点
Iterator(options ...int) Iterator[T]
// Minimum 获取当前树上字典序最小的键所对应的值
Minimum() (min T, isFound bool)
// Maximum 获取当前树上字典序最大的键所对应的值
Maximum() (max T, isFound bool)
// Size 获取树上键值对数量
Size() int
}
具体的实现就不说了，就写几个写的过程中出现的问题吧。
原作者的节点实现是这样的：
gotype artNode[T Value] struct {
reference unsafe.Pointer
kind Kind
}
type nodePrototype[T Value] struct {
prefixLen uint32
prefix prefix
childrenNum uint16
zeroChild *artNode[T] // 这东西是给正好断在别的键的中间的键用的 比如说 apple 和 appleWatch apple对应的叶子节点就放在这
}
type node4[T Value] struct {
nodePrototype[T]
children [node4Max]*artNode[T]
keys [node4Max]byte
isExist *bitmap
}
type node16[T Value] struct {
nodePrototype[T]
children [node16Max]*artNode[T]
keys [node16Max]byte
isExist *bitmap
}
type node48[T Value] struct {
nodePrototype[T]
children [node48Max]*artNode[T]
keys [node256Max]byte
isExist *bitmap
}
type node256[T Value] struct {
nodePrototype[T]
children [node256Max]*artNode[T]
}
type leaf[T Value] struct {
key Key
value T
}
它的结构是这样的：所有的节点首先是一个artNode类型的结构体，在该结构体内部另有一个指针指向实际的节点内容nodePrototype，该类型是所有节点类型的原型，其他的节点类型（除了叶子节点以外）都将其组合进去了。这一点看它们的工厂方法就很明显了：
gofunc newNode4[T Value]() *artNode[T] {
return &artNode[T]{
reference: unsafe.Pointer(&node4[T]{
isExist: newBitmap(4),
}),
kind: Node4,
}
}
func newNode16[T Value]() *artNode[T] {
return &artNode[T]{
reference: unsafe.Pointer(&node16[T]{
isExist: newBitmap(16),
}),
kind: Node16,
}
}
func newNode48[T Value]() *artNode[T] {
return &artNode[T]{
reference: unsafe.Pointer(&node48[T]{
isExist: newBitmap(256),
}),
kind: Node48,
}
}
func newNode256[T Value]() *artNode[T] {
return &artNode[T]{
reference: unsafe.Pointer(new(node256[T])),
kind: Node256,
}
}
func newLeaf[T Value](key Key, value T) *artNode[T] {
clonedKey := make(Key, len(key))
copy(clonedKey, key)
return &artNode[T]{
reference: unsafe.Pointer(&leaf[T]{
key: clonedKey,
value: value,
}),
kind: Leaf,
}
}
这种设计一方面是为了转型方便：unsafe.Pointer可以被毫无限制的转型成想要的指针类型。
gofunc (a *artNode[T]) node() *nodePrototype[T] {
return (*nodePrototype[T])(a.reference)
}
另一方面是为了便于替换节点，比如下面两个函数：
gofunc replaceRef[T Value](oldNode **artNode[T], newNode *artNode[T]) {
*oldNode = newNode
}
func replaceNode[T Value](oldNode *artNode[T], newNode *artNode[T]) {
*oldNode = *newNode
}
第一个是替换指针内容，将原本是指向oldNode的指针修改为指向newNode；第二个是替换实际的指向内容，将newNode的内容拷贝到存储oldNode的内存中。这两个的区别是改指向还是该内容，基于这个区别，前者一定是在树这个层面上用，后者一定是在节点这个层面上用，但是这两个操作的前提都是基于相同的类型才可以。
因为字节0也是有实际意义的，所以节点内不仅有字节数组来存储子节点所代表的字节，还需要一个结构来存储哪个字节是有实际意义的。原作者针对不同的节点，用的是不同的位图：[node4Max]byte，uint16，[4]uint64（node256是不需要这个结构的，只需要检查子节点是否为空即可）。如果字节数组对应位置有意义，那么对应的位为1，反之则为0。鉴于原作者的位运算实在过于复杂而且感觉还有问题（？），我自己封装了一个统一的位图。
go// bitmap 对位图进行封装 把读写逻辑都封进来
// 其底层为 uint16 的切片
type bitmap struct {
data []uint16
effectiveLength int
}
// newBitmap 获取一个新的 bitmap length 用于指定 bitmap 的有效长度
//
// 如果 length 不足16也是用 uint16 进行存储
func newBitmap(length int) *bitmap {
arrayLength := length / 16
if length%16 != 0 {
arrayLength += 1
}
return &bitmap{
data: make([]uint16, arrayLength),
effectiveLength: length,
}
}
// set1 将指定的数位设置为1 如果指定的数位超过了初始化 bitmap 时指定的长度 将不做任何操作
func (b *bitmap) set1(index int) {
if index >= b.effectiveLength {
return
}
arrayIndex := index / 16
i := index % 16
if i == 0 {
b.data[arrayIndex] |= 1
return
}
b.data[arrayIndex] |= 1 << i
}
// set0 将指定的数位设置为0 如果指定的数位超过了初始化 bitmap 时指定的长度 将不做任何操作
func (b *bitmap) set0(index int) {
if index >= b.effectiveLength {
return
}
arrayIndex := index / 16
i := index % 16
if i == 0 {
b.data[arrayIndex] &= 65534 // 655534 = 1111111111111110
return
}
b.data[arrayIndex] &= ^(1 << i)
}
// get 指定数位是否为1 如果指定的数位超过了初始化直接返回 false
func (b *bitmap) get(index int) bool {
if index >= b.effectiveLength {
return false
}
arrayIndex := index / 16
i := index % 16
return (b.data[arrayIndex] & (1 << i)) != 0
}
// getNum 获取当前位图中数位为1的位的数量
func (b *bitmap) getNum() int {
count := 0
s := b.string()
for i := range s {
if s[i] == 49 {
count += 1
}
}
return count
}
func (b *bitmap) string() string {
strBuilder := &strings.Builder{}
for i := range b.data {
if b.data[i] == 0 {
strBuilder.WriteString("0 ")
} else {
strBuilder.WriteString(numToBinIncludeLeadingZero(b.data[i]))
strBuilder.WriteString(" ")
}
}
return strBuilder.String()
}
位图是个应用挺广的东西，除了这种代替布尔数组来指示是否的用途以外，也可以用来方便的传递多配置项：
goconst (
TraverseLeaf = 1
TraverseNode = 2
TraverseAll = TraverseLeaf | TraverseNode
)
目前 String 类型所能支持的操作如下：
set，不多说。get，不多说。setnx，只有在键不存在的时候设置值。getrange，获取对应的值的在[start, end]范围内的字符。getset，先按key获取旧的值，然后再设置新的值并且返回旧值。append，在key存在的情况下，向其已经存在的value追加一个字符串。del，不多说。这个索引结构也没啥可说的了，就是 ART 树。
到这之后，这个类 Redis 数据库也就差不多了，再另加功能的话一个是自动整理存档文件，另外的就涉及分布式了。
本文作者:御坂19327号
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！