算法 -- IT技术博客大学习 -- 共学习共进步！

• XML和JSON

不久前看到一个讨论帖，说的是XML和JSON的比较，说着说着后来就变成了JSON到底比XML牛逼在哪里。不吹不黑，客观地来比较一下二者的异同。 XML比JSON更胖吗？有的情况下是的，但也不一定，比较这样的片段....

• STL笔记之hashtable

之前对hash一直存在恐惧感，毕竟没用过……最近在一个组件里面自己实现了一个hashtable，感觉也就这么回事；回头看看书上对hashtable的分析，发现是极其的相似。不过，旧版本的C++标准里面并没有hashtable这个东西，而C++11中引入了相关的容器（std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap），所以可以直接使用C++11里面的容器了。

• STL笔记之二叉查找树

SGI STL的关联容器（map、set、multimap、multiset）底层都是基于红黑树（Red Black Tree，RBT）来实现的，红黑树是一种被广泛使用的二叉查找树（Binary Search Tree，BST），有比较良好的操作效率。

• Redis编程小技巧拾遗

最近接触了一下Redis数据，出于好奇看了下它的源码，觉得这是一个值得一读的开源项目。关于Redis的源码分析，已经有很多网友写了各种分析笔记，而且也有相关的书籍《Redis设计与实现》，因此我觉得完整的写一系列的博客就没有必要了，这里主要记录一些个人觉得有意思或者是值得了解的东西（之前面试也有问到一些问题，如果我早一点接触这些东西的话，可以回答的更好）。

• 围住神经猫 1步玩法-”作弊”

今天被“围住神经猫”的游戏在微信朋友圈刷票了~ 自己也试了试，运气好能在10步左右OK。然后点击别人分享的页面直接进入游戏状态，发现分享的时候仅仅是分享网页的title不一样而已，且击败的对手百分比=(100-步数)%。于是“作弊”了下，仅仅“娱乐”罢了。

• 位运算小结（按位与、按位或、按位异或、取反、左移、右移）

位运算不管是在Java语言，还是在C语言中，或者其他语言，都是经常会用到的，所以本文也就不固定以某种语言来举例子了，原始点就从0、1开始。位运算主要包括按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(<<)、右移(>>)这几种，其中除了取反(~)以外，其他的都是二目运算符，即要求运算符左右两侧均有一个运算量。

• 如何编写一个JSON解析器

解析JSON和解析XML类似，最终都是解析为内存的一个对象。出于效率考虑，使用流的方式几乎是唯一选择，也就是解析器只从头扫描一遍JSON字符串，就完整地解析出对应的数据结构。

• 如何正确地处理时间

日期和时间在程序中应用广泛，每种程序开发语言都自带处理日期和时间的相关函数，很多开发者把日期和时间存入数据库中，但是，一旦涉及到跨时区的日期和时间的处理时，大多数开发者根本就不明白如何正确地处理日期和时间。

• 红黑树并没有我们想象的那么难(下)

根据上一节的红黑树分析, 结合 sgi stl map 的实现, 看看红黑树的源码是如何实现的. 以下主要以代码的注释为主. sgi stl map 底层实现是 _Rb_tree类, 为了方便管理, _Rb_tree 内置了 _M_header, 用于记录红黑树中的根节点, 最小节点和最大节点. 在插入删除中都会对其进行维护.

• 红黑树并没有我们想象的那么难(上)

红黑树并没有想象的那么难, 初学者觉得晦涩难读可能是因为情况太多. 红黑树的情况可以通过归结, 通过合并来得到更少的情况, 如此可以加深对红黑树的理解. 网络上的大部分红黑树的讲解因为没有「合并」.

• 并发编程系列之一：锁的意义

C/C++语言的并发程序（Concurrent Programming）设计，一直是一个比较困难的话题。很多朋友都会尝试使用多线程编程，但是却很难保证自己所写的多线程程序的正确性。多线程程序，如果涉及到对共享资源的并发读写，就会产生资源争用（Data Race）。解决资源争用，最直接的想法是引入锁，对并发读写的数据进行保护（更高级的则包括无锁编程—— Lock Free Programming）。但是，锁又有很多种类，例如：自旋锁（Spinlock）、互斥锁（Mutex）、读写锁（Read-Write-Lock）等等。这么多的锁，每种锁有什么特点？对应哪些不同的使用场景？使用过程中需要注意哪些事项？各自分别有哪些不足之处？都是困扰程序员的一个个问题。

• 从LongAdder看更高效的无锁实现

接触到AtomicLong的原因是在看guava的LoadingCache相关代码时，关于LoadingCache，其实思路也非常简单清晰：用模板模式解决了缓存不命中时获取数据的逻辑，这个思路我早前也正好在项目中使用到。

• 从千分位格式化谈JS性能优化

所谓的千分位形式，即从个位数起，每三位之间加一个逗号。例如“10,000”。针对这个需求，做了两个方案，方法一和方法二的强烈对比表明，字符串操作的效率比数组操作的效率要高得多；方法六的测试结果告诉我们，代码长短跟性能高低没有关系。方法四的综合性能是最好的（但为何num为100的时候，性能有所降低呢，这个实在不解）。

• C语言的整型溢出问题

整型溢出有点老生常谈了，bla, bla, bla… 但似乎没有引起多少人的重视。整型溢出会有可能导致缓冲区溢出，缓冲区溢出会导致各种黑客攻击，比如最近OpenSSL的heartbleed事件，就是一个buffer overread的事件。在这里写下这篇文章，希望大家都了解一下整型溢出，编译器的行为，以及如何防范，以写出更安全的代码。

• vfork 挂掉的一个问题

在知乎上，有个人问了这样的一个问题——为什么vfork的子进程里用return，整个程序会挂掉，而且exit()不会？并给出了如下的代码，下面的代码一运行就挂掉了，但如果把子进程的return改成exit(0)就没事。

• 为什么超长列表数据的翻页技术实现复杂（二）

上文为什么超长列表数据的翻页技术实现复杂提到了超长列表翻页技术设计上一些问题，今天讨论下部分解决思路。

• HLLC基数估算算法在腾讯数据仓库TDW中应用

分布式数据仓库(TDW)是一个以hive + hadoop为基础的大规模分布式系统，它提供了一种类SQL语言（称为HQL）让用户可以方便在其上进行编程开发。在数据分析领域，经常需要计算数据集不同元素的唯一值（Distinct值），也称为基数计算。精确的基数计算需要消耗过多的计算资源，当数据量非常大时，这种资源的消耗就更加严重。因此在大数据领域，采用估值算法降低基数计算的成本成为一种新的选择。

• NUMERIC和DECIMAL的区别是什么？

默认情况下，在将数字转换为较低精度和小数位数的 decimal 或 numeric 值时，SQL Server 使用舍入法。然而，如果 SET ARITHABORT 选项为 ON，当发生溢出时，SQL Server 会出现错误。若仅损失精度和小数位数，则不会产生错误。

• Linus：为何对象引用计数必须是原子的

Linus大神又在rant了！这次的吐槽对象是时下很火热的并行技术(parellism)，并直截了当地表示并行计算是浪费所有人时间(“The whole “let’s parallelize” thing is a huge waste of everybody’s time.”)。大致意思是说乱序性能快、提高缓存容量、降功耗。当然笔者不打算正面讨论并行的是是非非（过于宏伟的主题），因为Linus在另一则帖子中举了对象引用计数(reference counting)的例子来说明并行的复杂性。

• 数据分析中位数的应用

怎么从一组数据中计算出这个分界点呢？下面提供两个参考的算法：平均数：是指一组数据中所有数据之和再除以数据的个数，它是反映数据集中趋势的一项指标。中位数：把一组数据按从小到大的顺序排列，在中间的一个数字(或两个数字的平均值)叫做这组数据的中位数。