怎样快速对链表排序
1.怎么对单向链表进行快速排序？
1.怎么对单向链表进行快速排序？
将单向链表拓展为双向链表，然后按照快排的方式排序，这需要O(n)的空间，比数组O(logn)大不少，但能保证O(nlogn)完成
LinkdHashSet底层怎么实现元素有序？
从源码的角度来对LinkedHashSet寻根问底！
先一览LinkedHashSet类中的所有方法，发现就是一些构造方法，没什么特别的。。spliterator方法也只是个迭代器！
从构造器中的super方法点过去可得见端倪，原来构造器中的父级构造器使用的是LinkedHashMap进行实例化，那么LinkedHashSet的特性势必跟LinkedHashMap息息相关，换句话说LinkedHashSet的输出有序来自于LinkedHashMap；
下面对LinkedHashMap进行详细分析：
LinkedHashMap继承HashMap，实现了Map，很明显LinkedHashMap也算是HashMap，还保存了数组 链表的结构，至于有序的原因肯定不会是因为Map接口和继承HashMap，也就是说LinkedHashMap的有序，肯定就是在LinkedHashMap类中实现的；
HashMap的底层数据结构是使用数组中的位置作为桶，每个桶中放置一份链表（或者红黑树），而hashCode落在哪一个桶是不确定的，没有关联关系，所以HashMap不能做到有序输出，而LinkedHashMap使用的是双重链表形式，保存在map中的数据不仅在每一个桶里使用链表维护有序，还在每个值上维护链表来维护有序；
借用图一张，如下：
不仅如此，LinkedHashMap的迭代方式有两种，一种是按照插入顺序排序（迭代时就像队列一样），一种是访问排序（像栈一样，后访问的放在栈头，可作为LRU实现）
下面分析下主要源码：
1，先看LinkedHashMap中的内部类Entry：
Entry继承于，Node对象中有hash，key，value等一个key-value结构，还有next作为hashMap中同一个桶下面的entry指向，LinkedHashMap.Entry新获得了这些属性，且新定义了两个属性Entry before, after，用来对所有的entry维护一个指向，变成一个双向链表；
其余的诸如LinkedKeyIterator，LinkedEntrySet等内部类都是作为迭代器，
2，再看LinkedHashMap中的属性：
LinkedHashMap中的主要属性有是三个head，tail（维护链表的头尾，很容易理解），accessOrder：注释写的很清楚，就是true的时候就是访问顺序，false的时候是插入顺序；
3，LinkedHashMap中的方法： ①，put方法：LinkedHashMap中溜了一圈，并没发现有put方法，难道是使用的HashMap的put方法？那entry的链表是怎么做到的呢？
从HashMap中的put方法可以看到，计算了hash值之后就调用了putVal方法，而在生成新插入的元素的时候，使用的是newNode方法，LinkedHashMap确实没有重写put方法，但是重写了newNode方法，从代码中可以看到HashMap中的newNode方法，只是单纯的new了一个Node返回，而LinkedHashMap中的newNode方法不仅new了对象，还调用linkNodeLast，将对象挂在了链表的tail节点上，形成链表；（by the way，由此可见jdk中数据结构对于多态特性（重写之后调用子类方法）使用的淋漓尽致）
跟newNode方法类似的还有一个newTreeNode方法，这个也是在HashMap中的put方法里进行调用的，也就是红黑树结构；
②，get方法：
从get方法中可以看到，如果accessOrder为false，那么LinkedHashMap使用的get方法和HashMap一样，计算相应的hash值，比较key值（,equals），匹配上则返回，如果accessOrder为true，则调用afterNodeAccess方法，判断各种情况，然后把这个值设置为tail，保证是栈头的位置，下次最先查找到； 代码如上截图！
③，remove方法：
LinkedHashMap中的remove方法和HashMap中的是一样的，但是最后的afterNodeRemoval方法在HashMap中的方法体是空的，而在LinkedHashMap中进行了重写，把这个node的后一个节点接到了前一个节点上，这个node相当于脱链了。。 代码如下截图：
总的来说LinkedHashMap相比HashMap增加了链表特性，维护了元素的有序，虽然方法大部分都是用的HashMap的方法，但是使用重写这种多态特性，在LinkedHashMap中进行了不同了实现，可以说这也是我们开发代码时应该要学习的，以后再扩展其他类型的HashMap，只用重写部分方法即可实现！
LinkedHashMap就说到这，笔者已经分享了很多java方面的技术，有很多帮助到了一些朋友！还会一直持续分享，敬请关注。。。