.Net框架中的算法与数据结构

最近复习基础算法,顺带浏览了一下.Net框架的源码,通过本文简要总结一下.Net框架中常见数据结构和算法的实现。

1 集合类

1.1 List

List<T>使用动态数组实现,列表为空时,数组长度为0,加入第一个数据后,数组长度为16,以后当长度不够时会加倍,这时需要新建长数组,并完成复制操作,所以数据量预计很大时,建议指定初始化时的capacity,否则会进行很多复制操作。没有进行数组的自动缩减,而是提供了显式的TrimExcess方法,当数组使用率低于90%时,会去除数组中未使用部分,此外也可显式设定Capacity,这些方法都会产生复制操作。支持二分查找和排序,算法都使用数组的。

1.2 LinkedList

使用双向环形链表实现,内部直接保存的只有一个head节点。

1.3 Stack Queue

基本类似List,都使用动态数组实现,默认大小均为4,

1.4 Dictionary<TKey,TValue>

字典使用散列表实现,具体使用的是桶加链表的实现,键值对使用数组存储(初始大小和桶大小相同),链表指针使用的是数组的index,桶的大小由大于指定capacity的一个最小质数确定,最小为3,最大为7199369。Tkey的哈希值去除符号位后对桶大小取模得到Hash位置,当键值对数组不够用时需要扩大(使用质数数组中的下一个大小),桶的大小也随之扩大,如果冲突数超过100,则重新进行Hash。

1.5 SortedSet SortedDictionary<TKey, TValue>

SortedDictionary<TKey, TValue>本质上使用SortedSet<T> 实现的,而SortedSet<T> 则是经典的红黑树结构。

待续…