认识达内从这里开始

数据结构是程序员在学习软件编程开发技术的时候需要重点掌握的一个知识，而今天我们就一起来了解一下，数据结构的重要性都有哪些。

数据结构之所以重要是因为不同的数据结构表现出来的数学性质是构成特定算法的基础。就好比各种化学元素可以搭建各种性质不同的化合物，而不同性质的化合物正式化学工程所依赖的基础。计算机科学的数据结构可以大致分为两种，一种是数组，另一种是链表。两种性质截然相反的“物质”。

数组——线性性能好，支持随机访问，按照索引取数组中的元素时间复杂度是O(1)，而插入与删除元素时间复杂度是O(n);

链表——扩展性能好，支持动态的增减元素，插入、删除元素的时间复杂度是O(1)，而检索元素的时间复杂度变成了O(n);

(注：O标记是数学语言，用于标记一个函数的增长快慢，是一个渐进界函数，具体细节可以参考屈婉玲教授的详细解释)

这个世界有时候是惊人对称的，对称是美妙的。这样一对性质完全互斥的结构就是构成所有高等数据结构的基础。就像中国传统文化中的太极一样，你中有我我中有你，互相补充，世间万物的运行法则皆可解释。

举几个例子，有些高等数据结构具有耀眼的数学特性，比如“堆”，或者叫做优先级队列、二叉堆，就是以数组作为基础的。它在插入、删除、查询元素时的性能可以稳定在O(logn)量级;在互联网行业中，只有logn级别的算法可以适用，因为当数据规模急剧增加的时候，对数函数能够很好的平稳压力，所以，"logn"的算法对互联网行业贡献巨大，具有整流器的作用。比如，在微服务流量控制，大数据流处理、topN、高性能定时器都有很多应用。而堆只有在数组实现的算法中才能保持这个特性，如果用链表就会退化为O(nlogn)，失去魔力。

另一个例子是二叉树，这就是链表的一个使用场景。二叉树是一种树状结构，其中平衡二叉树在插入与删除的过程中只要移动logn次就能找到自己的新位置，而且代码简单易于维护(不容易写错也是工程中一个重要的考虑点，如果写得代码过于复杂就要反思下是否使用错了数据结构)。比如：红黑树就是一个综合性能很好的平衡二叉查找树;它是一个动态的数据结构，可以在动态添加与查找过程中稳定在O(logn)量级;在Linux内核中大量使用;而且在Java中的ConcurrentHashMap在冲突大的情况下，冲突元素大于8也会升级成红黑树存储冲突元素，来平衡工程与算法效率之间的矛盾。

当然，数据结构是可以融合的，比如Java中的LinkedHashMap就是融合了数组、哈希表与链表的优秀实践。普通的哈希表因为通过哈希函数将元素链接到数组的索引号上面，实现高速的查找性能，但是丢失了元素的插入顺序，而有时候我们需要这个顺序性来实现特殊的需求，比如缓存淘汰策略;而如果使用链表，形成一个插入的队列，先插入的在队列头，后插入在队列尾部;但是这样虽然保存了插入的顺序但是丢失了查找性能;为了平衡，我们可以在哈希表的基础上，每个元素再增加一个指针用来连接前后插入的元素，形成队列，这样没插入一个元素不仅在哈希表上挂载新的索引点，还要将新元素挂接到队列的尾部，而每一步都是O(1)的开销，是可以接受的，这就是LinkedHashMap的实现原理。

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请在707945861群中学习了解。