转载本文，请联系粥夏雪公众号。本文主要分享Collections.sort()隐藏的坑。如果你有兴趣，你可以忽略你已经知道的。没错，今天在review邓哥的代码的时候，看到了这样一段实现。大家看看这种写法有没有问题？认为没有问题的hxds请仔细阅读本文。记得三年前的一个雨天，依萍回卢家收生活费的那天，雨比依萍还大。我颤抖着走进一间办公室，脚步沉重，毕竟是第一次。采访“缺乏自信的小凡凡”：你好，我是小凡凡，我是来面试的瘦子我。森，你的简历还不错，很少有实习生敢写精通java的，来，我测试一下，你这样写有没有问题？是的，不过好在这题不难(⊙o⊙)...很简单，updateTime1和updateTime2都是long类型，用int强制转换可能会溢出。继续说“没底气的小凡凡：”还有呢？我想想，这样会导致顺序混乱，可能会导致大的在前。不足小凡凡：“还有吗？没有了，其他的我就不知道了。”大佬：“嗯，如果你能回答前两个，说明你对Java很熟悉，但还没有达到熟练的程度还有一个问题，溢出的时候，会被int转成负数，导致调用这个函数的时候会触发下面的异常。大佬：“你可能不知道底层的排序算法实现了JDK6和JDK7中的Collections.sort()是不同的。JDK6中使用MergeSort，JDK7中使用TimSort。TimSort用于排序算法之所以对比较大小要求比较高，是因为对于一些数据，上面的代码会造成compare(a,b)<0和compare(b,a)<0，也就是当这样的时候数据遇到这种异常发生在一些特殊情况下。贴一波大家看不懂的源码。privatevoidmergeHi(intbase1,intlen1,intbase2,intlen2){assertlen1>0&&len2>0&&base1+len1==base2;//CopysecondrunintotemparrayT[]a=this.a;//ForperformanceT[]tmp=ensureCapacity(len2);inttmpBase=this.tmpBase;System.arraycopy(a,base2,tmp,tmpBase,len2);intcursor1=base1+len1-1;//Indexesintoaintcursor2=tmpBase+len2-1;//Indexesintotmparrayintdest=base2+len2-1;//Indexesintoa//Movelaselementoffirstrunanddealwithdegeneratecasesa[dest--]=a[cursor1--];if(--len1==0){System.arraycopy(tmp,tmpBase,a,dest-(len2-1),len2);返回;}if(len2==1){dest-=len1;cursor1-=len1;System.arraycopy(a,cursor1+1,a,dest+1,len1);a[dest]=tmp[cursor2];return;}比较器c=this.c;//UselocalvariableforperformanceintminGallop=this.minGallop;//"""""outer:while(true){intcount1=0;//Numberoftimesinarowthatfirstrunwonintcount2=0;//Numberoftimesinarowthatsecondrunwon/**Dothestraightforwardthinguntil(ifever)onerun*出现towinconsistently.*/do{assertlen1>0&&len2>1;if(c.compare(tmp[cursor2],a[cursor1])<0){a[dest--]=a[cursor1--];count1++;count2=0;if(--len1==0)breakouter;}else{a[dest--]=tmp[cursor2--];count2++;count1=0;if(--len2==1)breakouter;}}while((count1|count2)0&&len2>1;count1=len1-gallopRight(tmp[光标2],a,base1,len1,len1-1,c);if(count1!=0){dest-=count1;cursor1-=count1;len1-=count1;System.arraycopy(a,cursor1+1,a,dest+1,count1);if(len1==0)breakouter;}a[dest--]=tmp[cursor2--];if(--len2==1)breakouter;count2=len2-gallopLeft(a[cursor1],tmp,tmpBase,len2,len2-1,c);if(count2!=0){dest-=count2;cursor2-=count2;len2-=count2;System.arraycopy(tmp,cursor2+1,a,dest+1,count2);if(len2<=1)//len2==1||len2==0breakouter;}a[dest--]=a[cursor1--];if(--len1==0)breakouter;minGallop--;}while(count1>=MIN_GALLOP|count2>=MIN_GALLOP);if(minGallop<0)minGallop=0;minGallop+=2;//Penalizeforleavinggallopmode}//Endof"outer"loopthis.minGallop=minGallop<1?1:minGallop;//Writebacktofieldif(len2==1){assertlen1>0;dest-=len1;cursor1-=len1;System.arraycopy(a,cursor1+1,a,dest+1,len1);a[dest]=tmp[cursor2];//移动firsteltofrun2tofrontofmerge}elseif(len2==0){thrownewIllegalArgumentException("Comparisonmethodviolatesitsgeneralcontract!");}else{assertlen1==0;assertlen2>0;System.arraycopy(tmp,tmpBase,a,dest-(len2-1),len2);}}看不懂也没关系，我也看不懂，但是原理大概是这样的，我们假设：ab可以触发一个“特殊情况”，即经过一定的合并操作后，a和b会同时成为“的临界条件”是否移动元素”。首先，我们有两个排序数组A和B，如下图所示。找到要合并的区间，准备操作：这样，划分完要合并的区间后，结果如下：第一次合并操作：C2落在元素b上；然后，开始第一个合并操作。由于B'[C2]>A'[C1]，我们需要从C2开始，在数组B'中找到一个下标n，所以B'[n]这里需要注意两点：一是比较临界点的条件为B'[n]这样，第一轮合并后的结果如下：第二次合并操作：C1落在元素a上：然后进行第二次合并操作。由于A'[C1]>B'[C2]（这是前提条件中的第三点：b<7&&7>b），我们需要从C1开始，从A'中找到一个下标m使得A'[m]这里需要注意比较的顺序和区间的半包含性。经过这一轮运算，得到的结果是：第三步和第四步运算：存在一个空集，可以看到死循环，因为此时A'[C1]然后，因为B'[C2]如果没有干预，排序操作会在这里无限循环。TimSort的干预方式是在检测到空集时抛出异常。”看不懂没关系，下面三个你都答对了，其实就是满分：”排序因为溢出变成负数，导致排序出现空集和死循环，TimSort中的干预方法是在检测到空集时抛出异常“bigman:”。虽然你已经回答了一半这个问题，但我会给你补救的机会。如何解决这道题是“恢复斗志的小餐”：保证在compare(a,b)操作中，如果a>b，则b表示需要满足以下条件(x的结果opy)必须与(yopx)相同结果相反。也就是说，如果a>b，则b是可传递的。也就是说，如果a>b，b>c，那么a>c。当x==y,(xopz)=(yopz)其实最好把答案委托给Java基础类，也就是“大佬：”嗯，是的，算是有到了及格线，你再坐下是的，我会打电话给二面的面试官。这时候又进来一个魁梧的男人。第二位面试官的面试过程还没结束，未完待续……原文链接：https://mp.weixin.qq.com/s/wPIKqEUgP2mTqFvUAv84Uw
