程序员之东邪西毒
佛典有云
旗未动 风也未吹
是人的心自己在动
每个程序员都会经过这个阶段，
见到一个技术，
就想知道技术后面是什么。
我很想告诉他，
可能了解之后，
你会发现没有什么特别。
回望之下，可能会觉得原来的技术更好一些。
但是我知道他不会听，
以他的好奇心，
自己不试试怎么会甘心。
其实甩一个锅不是很容易，
不过为了工作，
很多人都会冒这个险。
一个人接了锅之后，
或多或少总会找个借口来掩饰自己。
其实堵包、延迟，
只不过是同一个bug的两种结果。
在这两个结果后面，躲藏着一个加着班的人。
排期什么时候给是有邮件的，
锅什么时候甩过来却没人知道。
立春之后，
很快就到了惊蛰。
每年这个时候，
会有一个KPI发到我这，
但是今年没有来。
没多久，我收到一封邮件。
因为结构调整，我们的...
skiplist简介
skiplist，即跳表是由William Pugh在1989年发明的，允许快速查询一个有序连续元素的数据链表，搜索、插入、删除的平均时间复杂度均为O(lgn)。
本文介绍下对于skiplist的理解，包括背景、推导过程、伪代码以及复杂度的证明。
1. 背景
有序数组的好处是可以通过二分实现O(lgn)的高效查找，然而插入元素时，为了保证有序性，时间复杂度是O(n)的。链表则刚好相反，插入数据是O(1)，查找元素则是O(n)的。即使链表数据是有序的，查找元素仍然是O(n)的，因为本质上，链表不支持random access.
那么，是否存在一种链表，既支持高效的数据插入，又可以实现高效的查找？
介绍skiplist前，我们先举一个坐火车的例子。
假设公司组织出去bui，我们...
232 post articles, 29 pages.