snappy是google开源的压缩算法实现，通过测试表明snappy拥有极高的性能表现，但google并没有发表相关论文，可以认为snappy是一个工业算法。snappy借鉴了LZ77的思路，LZ77的匹配过程时间复杂度过高，google对其做了许多优化。在讲snappy之前，我先简单说明LZ77的基本思想。
布隆过滤器
布隆过滤器是一种空间高效的数据结构，用于判断一个元素是否位于集合中，但空间高效是有代价的。它基本实现方式是把元素计算成一个小序列存到数据结构中，多个序列有一定几率会在数据结构中重叠，所以有一定几率会判断错误，而且数据转换成序列后是不可逆的。所以，该数据结构一般用于容错高的场景，作为一个额外的数据结构来判断元素是否在集合中。
AVL Tree Implementation
AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. I will try to implement it and log in this article. You can find the source code in here.
