数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号，而不是从1开始的问题，进入主题。

数组如何实现随机访问

1. 数组是一种线性表
   顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
   而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
2. 连续的内存空间和相同类型的数据

正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。

低效的插入和删除

1. 插入：从最好O(1) 最坏O(n) 平均O(n)
2. 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。作者举例说明
3. 删除：从最好O(1) 最坏O(n) 平均O(n)
4. 多次删除集中在一起，提高删除效率
   记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

支持动态扩容的数组实现

考虑3个问题

• 主要的操作
• 扩容的策略
• 数据迁移策略

package array

type Array struct {
	data []interface{}
	size int
}

func CreateArray(cap int) *Array {
	if cap == 0 {
		panic("不能创建容量为0的数组！")
	}
	return &Array{
		data: make([]interface{}, cap),
		size: 0,
	}
}
func (a *Array) GetSize() int {
	return a.size
}
func (a *Array) GetCap() int {
	return len(a.data)
}
func (a *Array) Get(index int) interface{} {
	if index < 0 || index >= a.size {
		panic("index 出界了！")
	}
	return a.data[index]
}
func (a *Array) Set(index int, e interface{}) {
	if index < 0 || index >= a.size {
		panic("index 出界了！")
	}
	a.data[index] = e
}
func (a *Array) Add(index int, e interface{}) {
	if index < 0 || index > a.size {
		panic("index 出界了！")
	}
	// 如果当前元素个数等于数组容量，则将数组扩容为原来的2倍
	if a.size == len(a.data) {
		*a = a.resize(a.size * 2)
	}
	for i := a.size - 1; i >= index; i-- {
		a.data[i+1] = a.data[i]
	}
	a.data[index] = e
	a.size++
	return
}
func (a *Array) resize(len int) Array {
	newArray := CreateArray(len)
	*newArray = newArray.copyArr(a)
	*a = *newArray
	return *a
}
func (a *Array) copyArr(na *Array) Array {
	for i := 0; i < na.size; i++ {
		a.data[i] = na.data[i]
	}
	a.size = na.size
	return *a
}
func (a *Array) Remove(index int) interface{} {
	if index < 0 || index > a.size {
		panic("index 出界了！")
	}
	ret := a.data[index]
	for i := index + 1; i < a.size; i++ {
		a.data[i-1] = a.data[i]
	}
	a.size--

	if a.size == len(a.data)/4 {
		*a = (a.resize(len(a.data) / 2))
	}
	return ret
}
func (a *Array) RemoveElement(e interface{}) {
	index := a.FindFirst(e)
	if index != -1 {
		a.Remove(index)
	}
}
func (a *Array) FindFirst(e interface{}) int {
	for i := 0; i < a.size; i++ {
		if a.data[i] == e {
			return i
		}
	}
	return -1
}
func (a *Array) IsEmpty() bool {
	return a.size == 0
}

为什么很多编程语言中数组都从0开始编号

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k * type_size，但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：a[k]_address = base_address + (k-1)*type_size。对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。