简介

在java的集合中，主要分为Collection和Map两大类，而在Map中，HashMap和ConcurrentHashMap无疑是非常重要并且常用的，下面主要介绍在JDK1.7和JDK1.8中的HashMap与ConcurrentHashMap

HashMap

JDK1.7中的HashMap

JDK1.7中的HashMap是由 数组+链表的形式构成，没有红黑树。

简介

快速排序，可能是应用最为广泛的排序算法，它实现简单，适合于各种不同输入数据，并且一般来讲比其他排序算法都快很多，并且是原地排序(只需要一个很小的辅助栈)，将长度为N的数组排序所需的时间和NlgN成正比

基本原理：将一个数组分为两个子数组，将两部分独立排序，当两子数组都有序时，整个数组也就自然有序了，不需要归并子数组。

快速排序与归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。

简介

归并，就是将两个有序的数组归并成一个更大的有序数组。 归并排序，就是要将一个数组排序，可以先递归地将它分成两半分别排序，然后将结果归并起来。
使用归并排序，能够保证任意长度为N的数组排序所需时间和NlogN成正比，主要缺点就是它所需额外空间和N成正比。

对于归并排序，一种非常直接的办法就是将两个不同的有序数组归并到第三个数组中，但是，当使用归并排序对一个大数组排序时，需要进行很多次归并，如果每次归并时都创建一个新数组来存储排序，会带来不必要的空间损耗和其他问题。因此，原地归并是一个非常需要的办法，但是实现起来比较复杂。

简介

对于插入排序来说，如果数组初始阶段越混乱，倒置元素对越多，那么插入排序所需要时间就越多，甚至达到N^2级别时间复杂度。而对于几乎已经排好序的数组来说，插入排序的性能又很高，可以达到线性排序的效率。因此对于这样的特点，对插入排序进行了改进，改进后的算法被称为希尔排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的h有序数组被称为h有序数组，也就是h个互相独立的有序数组交错在一起组成的一个数组。
实现希尔排序的方法思想：先将整个待排序的数组根据间隔h分割成多个子数组，对于这些子数组进行插入排序，然后不断的减少间隔h，重复这样的操作，等到整个数组基本有序时，再对整体记录进行插入排序即可。

简介

冒泡排序，经常出现在各类计算机教材关于排序算法的第一个，它是一种比较简单的排序算法。
冒泡排序的原理是不停的比较数组中相邻的两个元素，如果元素的顺序与所需顺序不同，则将其进行交换，然后索引向前移动一位，再进行比较，当数组中所有元素都不再需要交换时，数组就是有序状态了。
从原理中我们可以看到，这种算法能很快的得到数组中较大的元素。

• 假定数组a[]的第一个元素是a[0]，它与a[1]进行比较，a[0]>a[1],那么就交换a[0]与a[1]
• 交换后的a[1]与a[2]比较，重复过程，如果当 a[1]与a[i]交换之后，此时 a[i]< a[i+1]了，那么就不会再交换它们
• 接下来又会比较a[i+1]与a[i+2]，以此到最后，此轮循环结束，数组末尾的元素一定是最大值
• 每一轮循环都会得到一个在当前无序范围数组中的最大值存放到末尾
  这样的算法流程，看起来就像是一个最大的水泡在向上冒，因此称为冒泡排序法。 more >>