概要
- Array
- Collection
- Array跟Collection到底什么关系?
- 我写代码的时候需要知道他们的关系嘛?
- Redis为什么会选择List?
- Redis为什么会选择Set?
- Redis为什么会选择ZSet?
- 自己写代码时,什么时候考虑数据类型?
Array
大部分.NET开发中,Array几乎已经不常用了,因为它完全不好使.
比如: var arr=new int[???]; 抱歉,老哥,我真的不知道是几个.
所以会出现下面的代码
var arr=new int[x];
dosometing...
arr=new int[y]; .....
孰不知,Array可以加一个叫做List的文字,就变成了可变的.
例如: ArrayList myAL = new ArrayList();
myAL.Add("Hello");
myAL.Add("World");
myAL.Add("!");
这并不稀奇,这个是肯定的,但是如果我告诉你.如果你写ArrayList其实就是在写new object[y]你又有什么感觉呢?
记住,不是类似,而是完全相等.不过说一个客观的事实,多数情况下,还不如你直接New.
以下为coreclrsrcSystem.Private.CoreLibsharedSystemCollectionsArrayList.cs
private object?[] _items = null!; // Do not rename (binary serialization) if (_items.Length < min) { int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2; // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow. // Note that this check works even when _items.Length overflowed thanks to the (uint) cast if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength; if (newCapacity < min) newCapacity = min; Capacity = newCapacity; }
注意Capacity的Set函数
Collection
在.NET中Collection其实是很多内容的合集.包含了上一章的ArrayList. 单纯的Array就是数组,数组就是Array.
而在Collection里面,其实该命名空间指的是: 列表,队列,位数组,哈希表和字典.
那么听起来似乎跟Array很像? 不然,在Array中,所有东西默认都可以被认定为集合的一部分.
其实从内存上来讲,每次你访问Array里面的内容时,理论上也同时期待他们永远是连续内存的内容. 而在Collection中则并不一定期待他们是连续的.
ArrayList则是例外的,从源码来看,他就是对数组的一个简易封装.
Array跟Collection到底什么关系?
Array 是当你需要严格或者期待严格控制某一些内存或者对象数据时,使用.
而Collection则为你的目的是方便的使用以及利用API去做一些额外的操作时使用.
举例来说: 当你能够明确的知道你的数据大小或者你能够估计你的数据上限时,用Array,当你不能估计时则用Collection.
例如:缓冲区是始终存在大小的,你明确清楚你能够一次处理多少数据(否则的话你的内存怎么管理?).
那么你通常看到的缓冲区都是array.
而当你查询数据库或获取第三方位置所调用的API,然后存储他们的结果时,你往往使用的都是Collection,这是因为你无法估计与预计他们的数量以及个数.
Redis为什么会选择List?
一定要知其然且知其所以然. 咱们来稍微瞄一瞄Redis的List的操作.
(首先redis的list是可重复的哦~)
LPush
RPush
LRange
LPop
RPop
它最多是2^32-1个元素 看出来什么特点了嘛?
数组必须是在内存中有一段连续的内存,所以它必须预先知道长度,数组的访问方式是O(1),而链表是O(N),但是!增加时链表是不用申请整个空间的,时间复杂度是O(1),而数组的话就成了O(N)(而且还要连续紧密).
这时候,一个非常明显的落地特点就出来了. 如果说,我能够保证这个链表始终是从头或者从尾部删除与增加,我甚至减少了查找遍历的时间,也就是O(N)不存在了!
Redis为什么会选择Set?
什么是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
刚才列举了一堆的Redis的Set操作. 可是这对咱们的编码有什么提示呢? 其实是这样的,学习基础知识绝不是让你拿来死记硬背的. 而是让你在合适的地点以合适方式去使用这个知识点,同时利用这个知识点来扩展,优化你的程序.
例如: 他的Set明显能看到浓重的哈希桶的味道. 是的,它利用了两个东西,一个是IntSet,一个是HashTable.
IntSet是 1.当所有元素是整数值的时候
2.集合保存的元素不超过512时.
这时候,请问,当你优化系统时,你会考虑做什么呢?
对了!在使用Redis时,不要SAdd东西时字符串与数字混合.
让Redis能更好的适应你的意图.
那么HashTable呢? 哈希表就没有什么黑科技了,它就是单纯的实现了哈希字典.
字典的每一个键都是一个字符串,每个字符串包含了一个集合元素.
仔细回想刚才的Set的实现. 你会发现,Redis的作者并没有拘泥于Set的定义,他利用他所学习的知识内容的同时尽可能的在优化数据结构在实际中局限性.
例如Set的标准定义应该通常都是HashSet. 但是如果我完全是HashSet,那么就会很尴尬的发生哈希碰撞,而我就需要出现哈希桶.
如果使用教科书级别的哈希桶实现,我又会出现说对应的桶内数据量与条目溢出,存储的编排问题.
这时候又绕回去了,似乎这个事情就做成一个麻瓜版本的HashSet了.
但是作者非常灵巧的利用了他所学习的知识,他拆分了缓存系统所可能存储的值的类型,利用数字与字符的哈希算法不一样,以及性能差异来从第一步区分存储方式.
第二步在实现哈希桶时利用链表的结构,这时候又到了链表的特点了.
Redis为什么会选择ZSet?
Redis的ZSet在实现时,利用了SkipList这种数据结构.
SkipList是一种”基于并联链表”的,随机化的数据结构
论文地址<extension://bfdogplmndidlpjfhoijckpakkdjkkil/pdf/viewer.html?file=https://www.cl.cam.ac.uk/teaching/0506/Algorithms/skiplists.pdf>.
它可以做到平均复杂度为O(LogN)的插入,删除和查找操作.
Redis的作者在实现SkipList的时候. 又做了修改. 他改了下面几个东西:
1.跳跃时允许有重复的分,用来支持有序集合中多个元素有相同的分
2.节点的比较不仅仅比较分,还比较value
3.每个节点还有一个前置的指针,也就是说,它更像是双链表. 源码 注意,每一个版本的redis的源码不大一样.