数组+链表这种数据结构在《HashMap源码分析》一文中以及在之前分析Linux内核源码的过程中多次碰到，本篇文章专门探讨这种数据结构。
数组与链表各自的优缺点大家肯定都很熟悉了，而数组+链表这种数据结构其实是综合了二者之间的优点，这类似于A*算法综合了广度优先搜索算法与贪心算法的优点一样，这种思想应用比较广，一定要掌握。再举个例子，比如我们知道遗传算法收敛速度比较慢，但是爬山法的收敛速度则比较快，而遗传算法鲁棒性优于爬山算法，那么为何不能结合二者之间的优点呢？如果搜索一下，你会发现这样的论文有很多。
本文中给出的几个使用数组+链表数据结构的情景，其优点都是类似的，因此不过多分析。本文更多的是为了回顾之前的内容。
1.HashMap之table
2.linux内核Buffer之hash_table
关于linux内核的buffer机制可以参考前面的文章《文件系统(二)--buffer.c namei.c truncate.c open.c源码分析》。
这里与HashMap中的table本质上是一致的，不过这里采用的是双向链表。而且，底层buffer_head通过b_next_free与b_pre_free指针链接成空闲链表，极大的方便了我们查找空闲buffer_head的操作。当然，这也增加了维护链表一致性的复杂度。更准确的说，这里是数组+双向链表+双向链表，如果读者对内核缓冲区比较熟悉（可以参考上面文章中的buffer_init函数），这里还可以认为是数组+数组+双向链表+双向链表，因为所有的buffer_head都是在内存中连续分配的，可以看成是一个数组。
3.linux内核进程调度之timer_list
详细内容可参考《sched.c signal.c exit.c sys.c源码分析》，这里timer_list是定时器链表。
这里与前面两个有所不同了：第一，前面两个在定位数组索引时都采用了哈希的方法，而这里则根哈希无关；第二，前面的数组中保存的是引用（指针），而这里数组中的元素就是timer对象。
这里为什么采用这种数据结构呢？如果单纯的采用数组，每次删除一个元素，都要移动剩余元素；每次插入一个元素也要移动其他元素，挪出位置。而采用链表加数组的方式，虽然插入元素时仍然需要遍历（因为需要根据定时值找到其合适的位置），但是删除时可以在常量时间内完成。
4.linux内核网络模块之sock_array
具体内容可以参考《linux0.99网络模块-传输层（TCP接收）》。
5.linux内核网络模块之ip_protols
具体内容请参考《linux0.99网络模块-网络模块初始化》，多说几句，数据链路层中注册的上层协议保存在ptype_base指向的链表中，因此可以通过遍历该链表向上层传递数据报；网络层与之不同，它通过ip数据报首部中的protocol字段（对ip_protos数组大小取余）作为索引来定位到ip_protols中相应位置的链表，遍历该链表来向上层传递数据报。
6.LinkedHashMap源码之table
详细内容请参考《LinkedHashMap源码分析》，其实这个结构与上面介绍的linux内核buffer实现中采用的hash_table是比较相似的。
暂时先写到这里。