并发编程网 - ifeve.com

本文是《Java特种兵》的样章，感谢博文视点和作者授权本站发布

1.2 一些简单算法，你会如何理解

终于迎来第二次聚会的机会，本节内容会轻松许多，也许一盏茶的工夫就可以听完这个小故事。

注：其实本节并不是讨论算法，例子也会很简单，如果你对算法很熟悉，请跳过此节。

想要从一堆数据中找出一个max、min。

想要从100万个数字中找出最大的10个数字。

你的想法是什么？你会如何找？先排序，再找，或者摸不到头脑。

胖哥的一些方法也许会帮到你：“想想学校里面排队、找人是怎么做的”。

假如一个学校有几千人，你要找一个人，胖哥给你提供几种方法，你选哪一种？

◎ 方法1：几千个人我逐个去问，你是不是我要找的人，如果回答是，那么就是我要找的；如果不是，则继续问下一个。

◎ 方法2：我知道学生的年级，然后在年级中每个班级按照方法1继续做同样的事情。

◎ 方法3：我知道具体的班级，然后在班级里面像“方法1”一样逐个问。

◎ 方法4：我知道姓名，通过姓名得到有几个班级同名的人，这几个人我逐个问。

◎ 方法5：我知道班级和姓名，也许就1个或2个学生同名，然后逐个问。

◎ 方法6：我知道“学号”，直接找到人。

上面6种方法属于思维上的方法学，在不同的场景下使用不同的手段，但你会毫不犹豫地说：第1种方法肯定是最傻的方法。没错，但是我们的程序往往就是这样写的，一个长长的for循环加匹配，就是逐个问的道理，对于人数不多的情况它其实也是实用的，但人数多了自然会有问题。后面几种方法都是知道某些前提内容后，然后通过不同的索引手段找到了人。好了，下面我们回到正题，探讨几种计算方法的场景。

†† 1.2.1 从一堆数据中找max和min

在一堆数据中找到一个最大的数据，如果它是无序的，就不存在“班级、年级”的维度概念，也就是说，没有数据分组的概念，在这种场景下不得不去做一次数组遍历，和学校的学生不按照班级站队的道理一样。但是需要做一次排序吗？当然不需要，因为我们只要找出最大值和最小值就可以了，排序的代价太大了。如果要求最大值，则可以先给一个临时变量赋值为Integer.MIN_VALUE或数组中的第1个元素值，然后循环数组的每个下标，只要比当前的这个值大，就给它赋予最新的值。这个时间复杂度是循环一次就可以搞定的，自然就不需要排序那么大的时间复杂度了。而排序会是什么样的呢？

在学校排队的时候，学生有自己的主见，每人都有大脑（CPU），当“校长”（号令者）下达命令后，每个学生自己知道去找位置，可以将自己的大致位置找好，细节的可以再由班主任来排序，但计算机中的CPU是有限的，不能这样干，这种方式的时间复杂度减少不了，因此排序的代价是巨大的，除非有一天计算机的内存不通过CPU或很少通过CPU就可以自己排序。

寓意：“所有的算法来自生活，而且没有生活那么复杂。”

进一步来看这个问题，100个人进行羽毛球比赛，最终需要挑选出水平最高的那一个人，最少会比赛99场。用这种方式就像擂台比武一样，倒下的人下台，胜利者继续在台上，在实际生活中，水平高的可能会累死，但在计算机中不会。

比赛的次数99次是最少的，有没有其他的方法呢？或许可以让两两之间进行较量，高手再两两之间继续较量，最后决出胜负，但是比赛的次数我们发现还是N-1次（例如8个人，首先4场胜出4人，然后2场胜出2人，最后1场加起来就是7场）。这种方式有一个重要的特征——在两两比赛的时候，只要有足够多的场地，就可以一起比赛，那么总体时间就节约下来了，在计算机中就是“多线程”技术。前者的设计方法由于简单，无法实现这种并行，但是它足够简单，只要for循环里面需要处理的内容足够简单，效率依然是很高的。

寓意：即使是多线程技术，在生活中也能找到活生生的例子。

将这个问题再做一点“发散性”扩展：在一堆杂乱无章的数据中，需要求出某个数据从大到小的“排名”情况，你会将所有的数据全部重排序一次吗？当然不会，因为完全重排序通常是n²的时间复杂度。

不过，聪明的同学会给自己找一个理由：完全重排序后的数据是可以反复使用的，如果排序导致时间开销过多，则可以定时做完全排序，外部的请求直接从排序结果中获取即可。这样我们需要忍受数据上的一点小延迟，因为这个排名可能随时在变化，由于是定时排序，所以变化后的数据并不会立即更新到排序后的结果中，或许在没有面临大数据的时候，换个思路会更快捷——在很多时候（只要数据量不是特别大），只需要找出比这个数据大的数据个数就自然知道排名了。这种思维其实是相通的，将上面的思路放在这里使用就是一种“变通”。

†† 1.2.2 从100万个数字中找最大的10个数字

通过1.2.1节的介绍，胖哥认为你应该可以领悟到一些什么——既然在寻找最大数字的时候是保留一个最大值，那么在寻找10个最大数字的时候，就可以记录10个数字的最小值，或者将这10个数字排序也是很轻松的。

循环大数组的每个元素，如果当前数字大于这10个数字的最小值，就剔除最小值，将当前数字写进去。如果10个数字是有序的，那么可以快速定位数字要写入的位置；如果是无序的，则只需要重新找出最小值即可。如果数字比较随机，那么随着不断的叠加，这个最小值也会越变越大，这10个数字需要再次插入的概率就会变小很多，即使是在最坏的情况下，每个数字都要插入到10个数字中剔除最小的，也最多是10´100万的运算量，而不会是100万´100万的运算量。

†† 1.2.3 关于排序，实际场景很重要

胖哥算法学得不太好，在胖哥思维中的很多排序算法，没有什么排序算法是特别好的，或者在最坏的情况下，它们都半斤八两。在前面的例子中，一个学校要排队，每个学生都有自己的大脑（CPU），计算机要整体排序应如何排呢？

实际的场景很重要，这里假如有“杂乱无章”的数据（200万个数据），两层for循环得到一个n²的复杂度（200万´200万=4万亿）。胖哥不想用，我们开始分析业务场景。如果我们发现这些数据中有95%以上是相对均匀地分布在1～200万之间的，而且重复数据极少，那么在这种场景下会如何排序？还会用两层for循环去排序吗？

胖哥的第一感觉就是它是有技巧的，胖哥希望先分堆再排序。由于数据较为均匀，所以将它们分成2002份甚至于更多，其中2000份为1～200万之间（每个堆都是一个连续的区间，例如[1-1000]、[1001-2000]、[2001-3000]…），自然每个区间的数据范围是一个小堆，而且小堆之间的数据是有序的，“<1”的数据和“>200万”的数据各自再分一个小堆，2002个堆之间的数据是完全有序的，因此只要它们各自内部有序，就是全局有序。这个过程需要扫描200万数据一次，然后在2002个堆中找到自己的位置，由于它本身有序，所以采用二分查找算法是可以快速找到位置的（每次匹配范围会缩小1倍，在2002个范围中寻找，每个数字最坏匹配11次（因为2的11次方是2048），总体上11´100万=1100万）。

此时平均每个堆大概是1000条数据（200万数据放在2002个堆中），那么每个堆自己排序的最坏时间复杂度将是1000´1000=100万，有2002个堆，因此是100万´2002=20.02亿，加上分堆的开销是20.135亿，计算次数依然很高，但是可以看到，已经比1万亿这个数字降低了500倍。这就是根据业务场景来做逻辑优化的魅力，读者可以在这个基础上继续深度挖掘业务细节。

回顾：是否觉得这也是生活中的一些场景——先排好班级，每个班级之间就不用排序了，而不是全校上千人一起来排队？它采用的是我们熟悉的分块排序，只是唯一的区别是，分块排序完成后就不需要再进行板块之间的排序了。这再次说明，我们实践中运用的还是“基础的算法”，在实际场景中需要变化，“变化后的招数才是最有攻击力的招数”。

内容扩展：当拆分成多个块以后，板块内部的排序是隔离的，因此各个板块是可以并行排序的，而且无须加锁，如果面对的是超大数据，还可以利用多线程来降低处理时间。将这个问题细化，就是分布式计算的基本原理了。

场景扩展：其实排序还有很多实际场景，远远不止这些，而且有些的确是很复杂的算法，不过无论多么复杂，总能在实际的生活中找到逻辑背景。在这种前提下，只要深度挖掘业务背景，就可以在基础算法之上进行灵活扩展。例如，有很多个已经排序后的分块，块内都是有序的，从第1个块到最后一个块的特征是后一个块的最小值大于前一个块的最小值，你会如何排序呢？

由于算法不是本书的重点，这里胖哥就简单说明一下。题目说明了每个块内部是有序的，且后一个块的最小值大于前一个块的最小值，第一想法自然是用后一个块的最小值，找出前一个块小于等于当前值的列表。由于本身是有序的，所以这样排序下来肯定是有序的，且剩下的数据肯定比当前取出的数据要大。

但是有个问题，剩下的数据就无法保证后一个块的最小值大于前一个块的最小值了，但是我们觉得这样“很爽”，还想要这样的情况继续发生。

在取出第1个块的数据后（不论取出几条数据），记录下现在的最小值，并认为是所有的最小值。进一步，下一个块取完后，得到最小值，如果它仍然大于前一个块的最小值，就用链表方式写在前一个块的后面；若小于前一个块的最小值，就放在前一个块的前面。我们也可以用一个单独的数组来存放每个块当前的最小值（这个长度与块个数一致，因此不会占用太多的空间），数组本身是有序的，相继递推的时候还可以用“二分查找算法快速定位”板块的位置。这样取完一次数据后，就得到了一个新的链表或者在分配的数组中记录了新的板块顺序。总之，现在是一个崭新的顺序，那么在进一步取数的过程中我们又可以轻松完成了，这也是一种分块排序的特殊场景。

说了这么多，胖哥还是在讲这句话：实际场景千变万化，切不可死记硬背。

†† 1.2.4 数据库是怎么找数据的

按照1.2.3节中的例子，将一些数据划分为板块，但是由于数据太多，就会造成板块太多或板块内部的数据太多，此时就会有管理板块的板块。数据库通常承载的数据量都上亿（单表大小），甚至十亿以上，它是怎么做的呢？

其实数据库也离不开这些原理，大多数数据库的索引都会用换汤不换药的“B+树”（当然也有使用Hash来做索引的），此思想源自对平衡二叉树的一种扩展，而同时也来自基本算法——二分查找算法，只是在场景中也会有些变化，数据库中的分块、索引、排序等概念在这些理论中体现得非常明显。

例如，SQL操作表与表之间的join的时候，如果是已经排序好的两个列表，join就无须完全的两层for循环来操作，那是N´N的时间复杂度，此时有点类似于1.2.3节中的扩展例子，介绍如下。

假如A表与B表join，到B表中查找A表的一个数据100，它从B表最小的数据开始找，找到了许多小于100的数据，不过都排除在外，不论是否找到100这个数据，当去B表查找A表的下一个数据101的时候，就不会再从最小值开始找了，而是从100开始，因为数据库知道双方是有序的。随着这个规律的推移，扫描的数据范围会越来越小，而不是像两层for循环那样，每一个外部的for循环都需要在内存中从第1个下标开始扫描。

通常，如果SQL没有问题，join表的个数往往不会太多，我们可以进一步做简单化优化。

†† 1.2.5 Hash算法的形象概念

其实Hash有很多种，有简单Hash，还有一致性Hash等，这里我们就谈谈简单Hash算法。关于Hash算法，经常会在教材中看到：Hash桶，快速定位，先计算再定位，并且号称复杂度为O(1)。

胖哥有自己的看法，这样的概念容易让人迷惑Hash到底是“神马”东西，而容易认为O(1)就是没有时间开销的，Hash就是绝对定位的，Hash算法就是无限快等思维都会出现。但实际场景也许并不是这样的。

胖哥不想搞得那么复杂，胖哥认为Hash算法有点像图1-5所示的那样（这里给大家一个简单的感性认识，在后文相关的专业内容介绍中，胖哥会再次讲到Hash）。

简单地看，就是如果知道队名，就能知道在哪个范围，然后在范围内查找名称。在前面的一些介绍中已经有所体现，在找班级的时候就是这样找的，只是各自有自己的排序方法——这里按照“队伍”来分布，而前面的例子是按照“班级”来分布的。

在Java语言里Hash算法通常是按照hashCode来分布的，前面提到过，在不同的场景下这个hashCode会计算出不同的值——可用对象头部的一个标识符，可用某些对象的属性通过一定计算得到，同一个hashCode肯定在同一个分组上，这个分组也就是专业说法上的“桶”，“桶”内部的数据通常是无序的，通常内部用一个链表存放（有的小伙伴会问链表不是有序的吗？其实这里所谓的无序是指链表上存放的数据并没有要求外部写入的数据以先进先出或后进先出的顺序存放，外部程序也不能依赖于遍历的顺序）。

在查找数据时，首先根据hashCode找到桶，然后在这个桶内部需要逐个使用equals()方法来对比内部的值，而在极度冲突的情况下，许多数据将被放在同一个桶中（通常叫作“热点”），导致一个桶的数据链表会非常长，这样一来，分布在该桶上的查找、遍历等操作都会变得很慢。因此，千万不要因为Hash算法的复杂度是O(1)就认为它天下无敌了，其实这只是一个相对量级别的说法，实际场景中的开销我们要用数字来说话。

图1-5 狗狗要找队伍和位置

反过来说，如果要使用Hash来做大量数据的查找，那么需要设计合适多的Hash桶。另外，在设计hashCode、hashCode与桶的下标转换的时候要有足够的离散能力，否则会做“赔了夫人又折兵”的事情。

有人曾经用一种固定Hash的方式来存储网络上的URL，喜欢钻空子的小伙伴利用了这种方式，形成一种网络攻击手段。他们在知道算法的基础上，通过模拟同样hashCode的不同URL，使得某些“桶”内部的数据变得特别多，每一个分布到这个“桶”的请求都会在这个“桶”内部查找，最坏的情况就是一个也没有找到，那么就需要遍历整个链表，这样就可能使得系统性能极度下降。

看到这里，你若有所领悟，胖哥就心满意足了。虽然本节知识会相对枯燥些，但仍然在阐述一些和我们工作密切相关的基础思想。接下来我们再来看看基础知识“运算符”。