go源码数据结构数组

概念

数组是相同类型元素的结合，描述数组需要两个信息：元素类型、元素个数。

存储方式

无论数组放在栈上还是堆上，都是连续的一段内存。元素的变量指向内存的开始位置。(无论哪一种类型的数据，底层都是存储在内存中，以二进制的形式。只不过对于不同类型的数据，从内存读取之后采用对应的解析方式进行解析)

访问方式

底层访问数组中的元素时，根据三个信息(内存的开始位置、元素类型所占字节大小、访问第几个元素),来计算目标元素的地址。访问数组时，分三个步骤：加载数组、计算目标地址、进行操作(取值、赋值)

1-新建数组

新建数组源码地址：src/cmd/compile/internal/types/type.go:NewArray

// NewArray returns a new fixed-length array Type.
func NewArray(elem *Type, bound int64) *Type {
	if bound < 0 {
		base.Fatalf("NewArray: invalid bound %v", bound)
	}
	t := newType(TARRAY)
	t.extra = &Array{Elem: elem, Bound: bound}
	if elem.HasShape() {
		t.SetHasShape(true)
	}
	return t
}

NewArray函数两个参数：元素类型、元素个数。常量TARRAY代表的是数组类型(名称源于TYPE+ARRAY)，go语言将所有的类型封装成了一个结构体Type，newType方法被调用是传入常量，根据常量判断新建的元素类型。newType代码如下：

func newType(et Kind) *Type {  
    t := &Type{  
        kind: et,  
        width: BADWIDTH,  
    }  
    t.underlying = t  
    // TODO(josharian): lazily initialize some of these?  
    switch t.kind {  
    case TMAP:  
        t.extra = new(Map)  
    case TFORW:  
        t.extra = new(Forward)  
    case TFUNC:  
        t.extra = new(Func)  
    case TSTRUCT:  
        t.extra = new(Struct)  
    case TINTER:  
        t.extra = new(Interface)  
    case TPTR:  
        t.extra = Ptr{}  
    case TCHANARGS:  
        t.extra = ChanArgs{}  
    case TFUNCARGS:  
        t.extra = FuncArgs{}  
    case TCHAN:  
        t.extra = new(Chan)  
    case TTUPLE:  
        t.extra = new(Tuple)  
    case TRESULTS:  
        t.extra = new(Results)  
    }  
    return t  
}

有人会有疑问，为什么newType方法里的case里没有TARRAY等其他类型呢？

本人认为（对于map、func、chan等数据类型类说，他们的结构体里的字段就是一些指针，而指针的大小是可以确定的，也就是说，对于这些数据结构来说，他们新建的时候，大小是固定的，不确定的是他们的各个字段的指针指向的内容，这些内容是后面才需要初始化的，所以可以直接使用new()。而对于TARRAY、TINT8、TSTRING等，初始化的时候就需要确定内部细节以及根据输入确定内存分配的大小，所以不直接new(),而是手动创建。如newArray方法中的代码中的t.extra = &Array{Elem: elem, Bound: bound}）.

如果数组元素小于等于四个，默认放在栈上，如果大于4个则将其移到静态区中。

func anylit(n ir.Node, var_ ir.Node, init *ir.Nodes) {
    case ir.OSTRUCTLIT, ir.OARRAYLIT:  
    n := n.(*ir.CompLitExpr)  
    if !t.IsStruct() && !t.IsArray() {  
        base.Fatalf("anylit: not struct/array")  
    }  
   
    if isSimpleName(var_) && len(n.List) > 4 {// 移动到静态区中
         
        // lay out static data  
        vstat := readonlystaticname(t)  

        ctxt := inInitFunction  
        if n.Op() == ir.OARRAYLIT {  
        ctxt = inNonInitFunction  
        }  
        fixedlit(ctxt, initKindStatic, n, vstat, init)  

        // copy static to var  
        appendWalkStmt(init, ir.NewAssignStmt(base.Pos, var_, vstat))  

        // add expressions to automatic  
        fixedlit(inInitFunction, initKindDynamic, n, var_, init)  
        break  
    }
}

除此之外，在fixedlit函数中，还会对数组的生命方式进行优化，如果元素少于等于4个，会将[3]int{1,2,3}转换成更原始的语句：

var arr [3]int
arr[0] = 1
arr[1] = 2
arr[2] = 3

如果元素大于4个，会直接在静态存储区初始化数组，然后将地址赋值给数组变量，后续再复制到栈上。

越界检查

数据的越界检查包括编译时和运行时：对于数组的访问，如果使用整数或常量访问，能够直接在编译时检查出来。而如果使用变量访问，则只能在运行期间进行检查。在访问数组时的第二个步骤-(计算目标地址)之后，就可以检查出是否越界。

参考文献：《Go语言设计与实现》 @Draven