开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数组、集合、链表、哈希表、跳跃链表 -> 正文阅读

[数据结构与算法]数组、集合、链表、哈希表、跳跃链表

文章目录

声明数组变量并不是声明 number0、number1、…、number99 一个个单独的变量，而是声明一个就像 numbers 这样的变量，然后使用 numbers[0]、numbers[1]、…、numbers[99] 来表示一个个单独的变量。数组中某个指定的元素是通过索引来访问的。

所有的数组都是由连续的内存位置组成的。最低的地址对应第一个元素，最高的地址对应最后一个元素。
在这里插入图片描述
大部分.NET开发中,Array几乎已经不常用了,因为它完全不好使.
比如:
var arr=new int[???];
抱歉,老哥,我真的不知道是几个.
所以会出现下面的代码
var arr=new int[x];

dosometing…
arr=new int[y];

集合

ArrayList

如果要动态地改变数组所占用内存空间的大小，则需以数组为基础进一步抽象，以实现这个功能。
Array可以加一个叫做List的文字,就变成了可变的.
例如:
ArrayList myAL = new ArrayList();
myAL.Add(“Hello”);
myAL.Add(“World”);
myAL.Add(“!”);

这并不稀奇,这个是肯定的,但是如果我告诉你.如果你写ArrayList其实就是在写new object[y]你又有什么感觉呢?
记住,不是类似,而是完全相等.查看 ArrayList 源码:

public virtual int Capacity {
    get {
        Contract.Ensures(Contract.Result<int>() >= Count);
        return _items.Length;
    }
    set {
        if (value < _size) {
            throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
        }
        Contract.Ensures(Capacity >= 0);
        Contract.EndContractBlock();
        // We don't want to update the version number when we change the capacity.
        // Some existing applications have dependency on this.
        if (value != _items.Length) {
            if (value > 0) {
                Object[] newItems = new Object[value];
                if (_size > 0) { 
                    Array.Copy(_items, 0, newItems, 0, _size);
                }
                _items = newItems;
            }
            else {
                _items = new Object[_defaultCapacity];
            }
        }            
    }
}

在Array中,所有东西默认都可以被认定为集合的一部分.
其实从内存上来讲,每次你访问Array里面的内容时,理论上也同时期待他们永远是连续内存的内容.
而在Collection中则并不一定期待他们是连续的.
ArrayList则是例外的,从源码来看,他就是对数组的一个简易封装.
优点:并且不存在---->运行时泛型

List

1）、表示可通过索引访问的对象的强类型列表；提供用于对列表进行搜索、排序和操作的方法。
2）、是ArrayList类的泛型等效类。
3）、可以使用一个整数索引访问此集合中的元素；索引从零开始。
4）、可以接收null空引用（VB中的Nothing）。
5）、允许重复元素

使用List的时候，如果能提前知道List的最大容量，可以直接在初始化的时候初始化容量，这样List就不必频繁扩容，加剧GC负担了 查看List 源码:

 public int Capacity {
            get {
                Contract.Ensures(Contract.Result<int>() >= 0);
                return _items.Length;
            }
            set {
                if (value < _size) {
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
                }
                Contract.EndContractBlock();

                if (value != _items.Length) {
                    if (value > 0) {
                        T[] newItems = new T[value];
                        if (_size > 0) {
                            Array.Copy(_items, 0, newItems, 0, _size);
                        }
                        _items = newItems;
                    }
                    else {
                        _items = _emptyArray;
                    }
                }
            }
        }

List和ArrayList相比，减少了装箱。运行时泛型

总结:
Array 是当你需要严格或者期待严格控制某一些内存或者对象数据时,使用.
而Collection则为你的目的是方便的使用以及利用API去做一些额外的操作时使用.
当一个项目中Collection过多，系统的性能可能也就有瓶颈了。无法控制内存

链表

单链表

在学习 redis 的 list 实现之前，我们先来看一下单链表 list 怎么实现：

每一个节点都有一个向后的指针（引用）指向下一个节点，最后一个节点指向NULL表示结束，有一个Head（头）指针指向第一个节点表示开始。

类似于这样，新建和删除虽然只需要 O(1)，但是查找需要 O(n) 的时间；无法反向查找，一旦错过需要从头开始。

增加一个节点：
在这里插入图片描述

删除一个节点：
在这里插入图片描述

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
在这里插入图片描述

特点：

每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
相对于单向链表, 必然占用内存空间更大一些.
既可以从头遍历到尾, 又可以从尾遍历到头
这好像就解决 redis 可以实现前后都可以遍历的问题了

Redis为什么会选择List

咱们来稍微瞄一瞄Redis的List的操作.(首先redis的list是可重复的哦~)
LPush
RPush
LRange
LPop
RPop
它最多是2^32-1个元素
看出来什么特点了嘛?

数组必须是在内存中有一段连续的内存,所以它必须预先知道长度,数组的访问方式是O(1),而链表是O(N),但是!增加时链表是不用申请整个空间的,时间复杂度是O(1),而数组的话就成了O(N)(而且还要连续紧密).
这时候,一个非常明显的落地特点就出来了.
如果说,我能够保证这个链表始终是从头或者从尾部删除与增加,我甚至减少了查找遍历的时间,也就是O(N)不存在了!

哈希表

即散列存储结构。
散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。
这样，不经过比较，一次存取就能得到所查元素的查找方法
优点：查找速度极快（O(1)）,查找效率与元素个数n无关！

Redis为什么会选择Set

Redis的Set是哈希表实现的,所以添加,删除,查找的复杂度都是O(1).
其中最大的成员数量是:2^32-1个.

他的命令有:
SADD GroupName Vaue 插入值
SADD GroupName 查看组数据个数
SDIFF GroupName1 GroupName2 查看两个组的差集
SDIFFSTORE DesGroupName1 SourceGroupName2 SourceGroupName3 对比2跟3然后把差集存到1里面
SINTER GroupName1 GroupName2 返回1跟2的交集
SINTERSTORE DesGroupName1 SourceGroupName2 SourceGroupName3 对比2跟3把交集存到1里面
SISMEMBER GroupName Value 看看Value是不是组的成员
SMEMBERS GroupName 查看所有的组员
SMOVE SourceGroupName DesGroupNamke Value 移动成员
SPOP GroupName 移除并返回组的一个随机成员
SRANDMEMBER GroupName Number 随机返回N个集合中的Item
SREM GroupName Value 移除N个成员
SUNION DesGroupName1 SourceGroupName2 SourceGroupName3 获取2跟3的并集存储在1中
SSCAN GroupName 当前下标匹配方式(一个简易的匹配模式) 返回数量默认10

他的Set明显能看到浓重的哈希桶的味道.
是的,它利用了两个东西,一个是IntSet,一个是HashTable.
IntSet是
1当所有元素是整数值的时候
2集合保存的元素不超过512时.

Redis IntSet源码:

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

这时候,请问,当你优化系统时,你会考虑做什么呢?
对了!在使用Redis时,不要SAdd东西时字符串与数字混合.让Redis能更好的适应你的意图.

那么HashTable呢?
哈希表就没有什么黑科技了,它就是单纯的实现了哈希字典.
字典的每一个键都是一个字符串,每个字符串包含了一个集合元素.

SkipList

skiplist本质上是一个list, 它其实是由有序链表发展而来
我们先来看一个有序链表，如下图（最左侧的灰色节点表示一个空的头结点）：
在这里插入图片描述
在这样一个链表中，如果我们要查找某个数据，那么需要从头开始逐个进行比较，直到找到包含数据的那个节点，或者找到第一个比给定数据大的节点为止（没找到）。也就是说，时间复杂度为O(n)。同样，当我们要插入新数据的时候，也要经历同样的查找过程，从而确定插入位置
在这里插入图片描述

假如我们每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：
在这里插入图片描述

在这里插入图片描述

这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半（上图中是7, 19, 26）。现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比如，我们想查找23，查找的路径是沿着下图中标红的指针所指向的方向进行的：
在这里插入图片描述

Redis为什么会选择ZSet

Redis的ZSet在实现时,利用了SkipList这种数据结构.
SkipList是一种”基于并联链表”的,随机化的数据结构论文地址https://www.cl.cam.ac.uk/teaching/0506/Algorithms/skiplists.pdf
它可以做到平均复杂度为O(LogN)的插入,删除和查找操作.同样的,Redis的作者在实现SkipList的时候.
又又又做了修改.
他改了下面几个东西:

1.跳跃时允许有重复的分,用来支持有序集合中多个元素有相同的分
2.节点的比较不仅仅比较分,还比较value
3.每个节点还有一个前置的指针,也就是说,它更像是双链表.

注意,每一个版本的redis的源码不大一样原本的源码存放于Redis.h中后期不晓得那个版本变成了Server.h