本文由一个在Dictionary中使用String作为key，且支持大小写不敏感匹配的例子来说明Dictionary的内部原理。由Key获取hash值是Dictionary实现的关键。在Dictionary声明的时候，可以通过构造函数传递IEqualityComparer参数来指定比较器，通过该对象来获取哈希值。如果不提供这个参数，则会在内部判断Key是否实现了IEquatable泛型接口，如果提供了，则使用该泛型接口中定义的GetHashCode来获取哈希值，否则会根据Key的类型生成一个通用的EqualityComparer，这个通过的EqualityComparer的参数是object类型，所以如果Key的类型为结构体，则必须为其实现IEquatable泛型接口，否则就会产生装箱从而严重影响性能。 …
在.NET Core的源代码中，除了常用的Dictionary、ConcurrentDictionary之外，还有几种名称包含Dictionary的数据结构，它们是ListDictionary、OrderedDictionary、SortedDictionary、HybirdDictionary和StringDictionary。这些个杂牌Dictionary用得很少，不看源代码可能还不知道😂。表面上看，好像都是Dictionary，但研究发现其内部实现却大不相同。 …
Dictionary是一种存储键值对的数据结构，可以根据Key快速查找对应的Value，它的内部实现原理其实很简单，在浅谈算法和数据结构: 十一 哈希表这篇文章中有详细介绍，但实际的原理和工程实现可能有所不同，在.NET中有.NET Framework和.NET Core的两个版本，大体相同，但细节上有所区别。这里以.NET Core中的Dictionary源码为例，来说明Dictionary的实现细节。 …
和C#中的IEnumerable接口类似，在C++中，遍历标准容器库比如vector、deque、list等，都需要用到迭代器对象(iterator)，根据容器的类型不同以及访问时是否需要读写，迭代器也分为可读写迭代器iterator，只读迭代器const_iterator以及反向迭代器reverse_itertaor。 调用容器类型成员的begin和end方法(或者cbegin,cend,rbegin,rend)方法，这两个方法分别返回指向容器首元素，以及尾元素之后的位置(one past the last element)，简称尾后的迭代器。 这里面有一个容易误解的地方在于，end方法返回的迭代器，从来都不会指向容器的最后一个元素，而是指向最后一个元素之后的元素。如果容器v的第一个和最后一个元素分别记为first和last，那么调用v.begin()和v.end()返回的迭代器范围( …
布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数，主要用于判断一个元素是否在一个集合中。与直接存储数据不同，布隆过滤器是通过一系列随机映射函数，将待存储的数据通过映射函数提取特征，然后将这些特征存储到二进制向量对应的二进制位上（类似于前文的Bitmap存储），当查找某个值时，通过随机映射函数，提取特征，然后检查这些特征所在的二进制位上是否都为1，如果都为1，表示该可能存在在集合中，但只要有一个为0，则一定不在集合中。 …
位运算符作用于整型对象，并把运算对象看作是二进制位的集合。位运算提供了检查和设置二进制位的功能。通常在编写代码中，相比加减乘除，位运算并不常用，但在有些情况下，位运算有用处。本文首先介绍为位运算的基本概念，然后介绍位运算的应用场景，包括使用Bitmap来存储整型数据，并介绍了在此基础上如何对大量不重复的整型数据进行快速排序，对大量整型数进行去重和快速查找，最后介绍了编程语言对Bitmap思想的实现，包括C++里面的bitset，C#里面的BitArray，并介绍了枚举值中使用位运算的一些例子。 …
当多个线程同时访问共享数据对象时，就需要线程同步，以保证数据状态不会被破坏。线程同步的通常做法是加“锁”，以保证某一时刻只有拥有这个锁的对象才能够去操作数据。加“锁”能够保证共享数据不会被破坏，但是它增加了代码的复杂性，并且有时候不容易测试和重现。另外“锁”增加了系统开销，会损害系统性能。本文介绍了C#中的基元用户模式构造和基元内核模式构造两类基本类型构造，并详细介绍了在C#中的实现。 …
股票的行情这种时序数据类型，数据冗余度和相似度较高，天然适合进行压缩。本文分析了几种无损压缩算法，分别是C#内置的和SharpZipLib的GZip、Zstd、LZ4以及Snappy。在对比这几种算法的压缩率，压缩时间后发现，Zstd具有比较好的压缩率和压缩速度，基本能满足行情数据处理以及传输效率的要求。 …
集合竞价是电子撮合交易中的重要撮合方式，通常用来在开盘或者收盘时产生开盘价或者收盘价，或者对于某些流动性差的产品，通过一段时间集中进行撮合，找出能产生最大成交量的价格的方式，（即市场大多数人认可的价格）防止价格被不小心操纵。 中国大陆市场中，由于人口众多，流动性几乎从不缺乏，所以从一开始就是采用把集合竞价生成开盘价和连续竞价高效撮合组合在一体的方式。具体上，沪深交易所都是以集合竞价来场开盘价和收盘价，在收盘价上，如果集合竞价不能产生收盘价，则采用最后一分钟加权平均价（上交所最开始的收盘价是使用的1分钟均价，后来改成了也采用集合竞价的方式产生）。本文对沪深交易所的开盘集合竞价算法作了简单论述和实现。 …
在前面的系列文章中，依次介绍了基于无序列表的顺序查找，基于有序数组的二分查找，平衡查找树，以及红黑树，下图是他们在平均以及最差情况下的时间复杂度： 可以看到在时间复杂度上，红黑树在平均情况下插入，查找以及删除上都达到了lgN的时间复杂度。 那么有没有查找效率更高的数据结构呢，答案就是本文接下来要介绍了散列表，也叫哈希表(Hash Table) 什么是哈希表 哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。 哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。 使用哈希查找有两个步骤: 使用哈希函数将被查找的键转换为数组的索引。在理想的情况 …