数据结构小结

2020-11-27 本文已影响0人天命_风流

数组

数组是一种非常常见的线性数据结构
它最大的特点是使用一组连续的内存空间，存储一组相同类型的数据：

数组的存储形式.jpg

之所以强调相同类型，是因为相同的类型的数据会占据相等的存储空间，因此就可以通过计算直接获取内存地址。
优点：数组最大的特性，是支持随机访问，即可以通过索引直接访问某个数据
数组的访问性能非常高，还有一个原因是在硬件层面有CPU的高速缓存（cache）提升性能
缺点：数组的添加、删除的性能很低，因为会涉及大量的数据搬移工作。
所以你会发现，go 中给数组和切片的操作很少，低性能可能是其中的原因之一
这也是为什么 go 中指定 slice 长度可以提升性能（减少追加数据时的数据搬移工作）

链表

链表是另一种非常基础的数据结构，与数组不同，它使用零散的内存存储数据：

数组和链表的存储.jpg

单链表.jpg

由于它的存储方式和数组完全不同，所以它和数组的特性完全不同：
优点：高效的插入和删除

链表的插入和删除.jpg

缺点：链表的查找非常低效，只能依次遍历所有节点
在 go 中，container 包里有双向链表、双向循环链表等容器供我们使用，下面是链表的部分方法：

func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveAfter(e, mark *Element)

func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)

func (l *List) Front() *Element
func (l *List) Back() *Element

func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element

func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element

单纯的链表在实际编程中很少用到，但是如果我们对链表进行升级，给一些额外的结构，它就会有非常广泛的应用。
简单的变型有：双向链表、循环链表等，复杂的变型有：红黑树、B+树等。这种变型非常重要，其中就包括 redis 中实现 zset 的跳表：

跳表-二级索引.jpg

栈

一种操作受到限制的线性表，最大的特点是后进先出
栈可以用数组或者链表实现
栈只有两种操作：入栈和出栈

栈.jpg

特定的数据结构是特定使用场景的抽象
对于栈来说，主要的使用场景有：括号匹配，算数运算，浏览器的前进后退功能等
当然，最常见的还是编程中的函数调用栈：

def sum(a,b):
    return a + b

if __name__ == '__main__':
    print(sum(1,2))

下面的图片展示了这个程序执行的过程：

函数调用栈，省略了变量名

队列

队列也是一种操作受限的线性表，它的特性是先进先出

栈和队列.jpg

队列也只有两种主要操作：从队尾入队和从队首出队
队列也可以有变型：循环队列、阻塞队列等：

循环队列.jpg

阻塞队列.jpg

队列可以非常方便地实现生产者-消费者模型，应用有消息队列中间件。

散列表（哈希表）

散列表依赖于数组支持依照下标随机访问的特性
散列表由三个部分组成：键、散列函数和散列值。这个的过程是，键通过散列函数的计算得到散列值，然后去寻找这个值代表的响应的地址：

散列

非常常见的一个问题是，如果多个键的散列值相同（散列冲突），该怎么办？常见的解决办法有两种：

开放寻址法：

散列冲突-开放寻址法.jpg

链表法

散列冲突-链表法.jpg

上面的方法都是最基础的解决方法，实际上，根据场景的不同，会有很多种解决方案。例如，将链表法后接的链表设计成红黑树，可以防止哈希碰撞攻击。
你会发现，数据结构的使用不是孤立的，多种数据结构的组合，会有超乎想象的结果。
在这些组合中，哈希+链表就是一个包打天下的万金油组合，redis中的zset就是这样。