太刺激了，面试官让我手写跳表，而我用两种实现方式吊打了TA！

稳定度，跳表的随机性太大了，要实现O(log n)的时间复杂度，随机算法要做得很好才行，这方面可以对比看看ConcurrentSkipListMap和redis中zset的实现，而红黑树还算比较稳定; 范围查找，HashMap更多地是运用在查找单个元素，并没有范围查找这种需求，所以，使用跳表的必要性不大; 成熟度，红黑树是经过很多实践检验的，比如linux内核、epoll等，而跳表很少，目前已知的好像只有redis的zset使用了跳表; 空间占用，红黑树不管层高多少，每个节点稳定增加左右两个指针和颜色字段，而跳表不一样，随着层高的不断增加，每个元素需要增加的指针也会增加很多，比如，最高为16层，则head和最高的节点需要维护16个向右的指针，这个空间占用是很大的，所以，实现跳表一般也要指定最高只能达到多少层; 流程化，跳表实现可以多种多样，每个人写出来的跳表可能都不一样，但红黑树不一样，流程固化，每个人写出来的差异性不大; 可测试性，跳表很难测试，因为多次运行的结果肯定不一样，而红黑树不一样，只要元素顺序不变，运行的结果肯定是固定的，可测试性好很多;

目前，差不多只能想到这么多，你有想到的也可以告诉我。

后记

本节，我们一起用两种方式实现了跳表，并将其运用到了HashMap的改写中，相信通过本节的学习你一定可以自信地告诉面试官我可以手写跳表了。

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!