算法

如何判断一个数是否在某个集合中，我们最简单的方式是遍历集合判断是否存在这样一个元素，更高级一点的方式是使用哈希表，可以以 O(1) 的时间复杂度判断一个元素是否在集合中，但是当数据量达到亿级别的时候，再采用这种方式就会出现问题，那IPV4来说，现有ip数量为 256^4个（假设每一个不同的都算），以 map 存储的话，假如key是字符串，占用15字节，val是布尔型1个字节，一个k-v 占16个字节，至少也得占用2^36个字节，折算下来就是 2^36/1024/1024/1024 = 2^6 = 64G，这么大内存肯定是放不下的，因此需要一种特殊的算法来进行处理，接下来所要介绍的算法就是解决大数据下，元素是否存在于集合中这么一个问题的。

排序算法可以说是算法中最基础的，但是一直以来都没有系统地去整理过，而且其中有些细节还是值得好好推敲的，因此把遇到过的排序算法进行整理了一下。目前整理地还不够全面，后续会继续慢慢完善。