Java数据结构和算法

 

数据结构是对在计算机内存中（有时候在磁盘中）的数据的一种安排。数据结构包括数组、链表、栈、二叉树、哈希表等等。

 

数据结构有哪些用途呢？首先，可以模拟现实世界数据的存储，进行现实世界的建模，最重要的数据结构是图，可以用来表示城市之间，城市内部的道路，电路中的连接，或是任务的安排关系；其次，有些数据结构并不打算让用户接触，它们仅被程序本身所使用，程序员经常将诸如栈、队列、优先级队列等结构当作程序员的工具来简化另外一些操作。

 

数据结构的特征

数据结构	优点	缺点
数组	插入快，如果知道下标，可以非常快地存取	查找慢，删除慢，大小固定
有序数组	比无序数组查找快	删除和插入慢，大小固定
栈	提供后进先出方式的存取	存取其他项很慢
队列	提供先进先出方式的存取	存取其他项很慢
链表	插入快，删除快	查找慢
二叉树	查找、插入、删除都快（如果树总是平衡）	删除算法复杂
红黑树	查找、插入、删除都快。树总是平衡的	算法复杂
2-3-4树	查找、插入、删除都快。树总是平衡的，类似的树对磁盘存储有用	算法复杂
哈希表	如果关键字已知则存取极快。插入快	删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分
堆	插入，删除快，对最大数据项的存取很快	对其他项存取很慢
图	对现实世界模拟	有些算法慢并且复杂

 

1.   数组

1.1          无序数组

数组是最广泛使用的数据存储结构，被植入到大部分编程语言当中，Java中常用数组操作有：

int[] array = new int[];

int[] array = new int[]{1, 2, 3}

int arrayLength = array.length()

int arrayValue = array[0];

 

 

1.1.1  插入

在数组中由于知道数组中已有数据的长度，数组元素的插入位置能够直接确定，新的数据项就能够轻松地插入到数组中。

 

在不允许出现相同值的情况下，就会涉及到查找的问题，关于查找在以后的章节中介绍。

1.1.2  查找

对于无序数组来说，查找（假设不允许出现重复值）算法必须平均搜索一半的数据项来查找特定的数据项，找数组头部的数据很快，找数组尾部的数据很慢。设数据项为N，则一个数据项的平均查找长度为N/2，最坏情况下，需要查找到N次才能找到。

1.1.3  删除

只有在找到某个数据项之后才能删除它，删除算法暗含一个假设，即数组的数据之间不会有空值，在删除某条中间数据后，下标比它大的数据项会自动填充上，保证数据的长度等于数组中的最后一个元素减一（如果数组数据之间有空值会导致其他算法更加复杂）。因此，删除算法需要查找平均N/2个数据项并平均移动剩余的N/2个数据项来填充删除带来的数据间空值，总共是N步。

 

允许重复和不允许重复的比较

	不允许重复	允许重复
查找	N/2次比较	N次比较
插入	无比较，一次移动	无比较，一次移动
删除	N/2次比较，N/2次移动	N次比较，多于N/2次移动

 

1.2          有序数组

数组中的数据项按照关键字升序排列，即最小的数据项下标为0，每一个单元都比前一个单元的值要大，这种类型的数组就称为有序数组。

 

有序数组中预先设定了不允许重复，这种数据结构的选择提高了查找的速度，但是降低了插入的速度。

 

对于无序的数组查找，只能够采用线性查找的方式，这就导致在无序数组中查找执行需要平均N/2次比较。

 

当使用二分查找时就能够体现出有序数组的好处。这种查找比线性查找要好的多，尤其是对于大数组来说，二分查找就是将每次查找的范围进行缩小，每次缩小一半，比较查找值与当前范围中轴值的大小，直至最终找到所选值。

 

在集合工具类Collections. binarySearch()方法中实现了二分查找。

 

有序数组带来的最大好处就是查找的速度比无序数组快多了，不好的方面是插入操作中由于所有靠后的数据都需要移动以腾开空间，所以速度较慢，有序数组在查找频繁的情况下十分有用，但若是插入与删除较为频繁时，则无法高效工作。

 

为什么不用数组表示一切？

 

仅仅使用数组似乎就可以完成所有的工作，为什么不用它来进行所有的数据存储呢？我们已经见到了使用数组的所有缺点，在一个无序数组中插入数据很快（O(1)），但是查找却需要很长的时间；在一个有序数组中查找数据很快，用O(logN)时间，但插入却需要O(N)的时间；对于这两种数组而言，由于平均半数的数据项为了填补“空洞”必须移动，所以删除操作平均需要O(N)时间。

 

数据的另外一个问题是，它们被new创建出来后，大小尺寸就被固定住了。但通常设计程序时并不会考虑以后会有多少数据项将会被放入至数组中。Java中有Collection集合相关类型，使用起来像数组，而且可以扩展，这些附加功能是以效率为代价的（在插入时检查数组长度，不满足的话新建数组并移动原有数据）。

2.   简单排序

一旦建立一个重要的数据库后，就可能根据某些需求对数据进行不同方式的排序，对数据的排序非常重要，且可能是数据检索的初始步骤，正如刚在有序数组中所讲到的，二分查找要比线性查找快很多，但是它仅适用于有序的数组。

 

在数据排序方面，人与计算机相比有以下的优势：我们可以看到所有的数据，并且可以一下看到最大的数据，而计算机程序却不能像人一样能够通览所有的数据，它只能根据计算机的比较操作原理，在同一时间内对两条数据进行比较。算法的这种“管视”将是一个重复出现的问题，简单排序的算法中都包括大概两个步骤，这两步循环执行，直到全部数据有序为止：

 

1.       比较两个数据项；

2.       交换两个数据项，或复制其中一项。

2.1          冒泡排序

冒泡排序算法运行起来非常慢，但在概念上来说它又是最简单的，因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法。以下是冒泡排序要遵循的规则：

1.       比较两个数据；

2.       如果前面的数据比后面的数据大，则数据之间进行交换操作；

3.       向后移动一个位置，比较下面两个数据；

4.       但碰到第一个排好顺序的队员后，返回队列最前端重新开始下一趟排序.

 

public void sort(T[] toSortArray) {

        int out, in;

        int elementsLength = toSortArray.length;

        for (out = elementsLength - 1; out > 1; out--) {

            for (in = 0; in < out; in++) {

                if (toSortArray[in].compareTo(toSortArray[in + 1]) > 0) {

                    swap(toSortArray, in, in + 1);

                }

            }

        }

    }

 一般来说，数组中有N个数据项，第一趟排序中有N-1次比较，第二趟有N-2次，以此类推。这样算法作了/2次比较。

 

交换和比较操作次数都和成正比，冒泡排序运行需要时间级别。无论何时，只要看到一个循环嵌套在另一个循环里面，就可以怀疑这个算法的运行时间为的时间级。

2.2          选择排序

选择排序改进了冒泡排序，将必要的交换次数从改为O(N)，不幸的是比较次数仍然为。然而，选择排序仍然为大记录量的排序提出了一个非常重要的改进，因为这些大量的记录需要在内存中移动，这就使得交换的时间和比较的时间比起来，交换的时间更为重要（注：一般来说，Java中不是这种情况，Java只是改变了引用位置，而实际对象的位置并没有改变）。

 

public void sort(T[] toSortArray) {

        int in, out;

        int sortArrayLength = toSortArray.length;

        for(out = sortArrayLength - 1; out > 1; out --){

            int highest = 0;

            for(in = 1; in <= out; in++){

                if(toSortArray[highest].compareTo(toSortArray[in]) < 0){

                    highest = in;

                }

            }

            swap(toSortArray, highest, out);

        }

    }

 选择排序和冒泡排序执行了相同的比较次数，N*(N-1)/2。N值很大时，比较的次数是主要的，所以结论是选择排序和冒泡排序一样运行了时间。但是，选择排序无疑更快，因为它进行的交换次数要少得多；但N值较小时，特别是如果交换的时间比比较的时间级别大很多的时候，选择排序是相当快的。

 

2.3          插入排序

大多数情况下，插入排序是简单排序算法之中最好的一种。虽然插入排序仍然需要的时间，但是在一般情况下，它比冒泡排序快一倍，比选择排序还要快一点。尽管它比冒泡排序和选择排序更麻烦一些，但也并不是很复杂。它经常被用在复杂排序中的最后阶段，例如快速排序。

 

public void sort(T[] toSortArray) {

        int in, out;

        for(out=0; out < toSortArray.length; out++){

            T current = toSortArray[out];

            in = out;

            //to save the memory but add the complexity

            while (in > 0 && toSortArray[in - 1].compareTo(current) >= 0){

                toSortArray[in] = toSortArray[in -1];

                in--;

            }

            toSortArray[in] =  current;

        }

    }

 

在每趟排序完成后，所有数据项都是局部有序的，复制的次数大致等于比较的次数。然而，一次复制和一次交换的效率不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。在任意情况下，对于随机的数据进行插入排序也需要的时间级。

 

对于已经有序或者基本有序的数据来说，插入排序要好得多，算法只需要O(N)的时间，而对于逆序排列的数据，每次比较和移动都要执行，所以插入排序不比冒泡排序快。

 

3.   栈和队列

3.1          栈

栈只允许访问一个数据项：即最后插入的数据项。移除这个数据项之后才能访问倒数第二个插入的数据项，以此类推，是那些应用了相当复杂的数据结构算法的便利工具。大部分微处理器运用了基于栈的体系结构，但调用一个方法时，把它的返回地址和参数压入栈，但方法返回时，那些数据出栈，栈操作就嵌入在微处理器中。

 

栈是一个概念上的辅助工具，提供限定性的访问方法push()和pop()，使程序易读而且不易出错。在栈中，数据项入栈和出栈的时间复杂度均为O(1)，栈操作所消耗的时间不依赖栈中数据项的个数，因此操作时间很短，栈不需要比较和移动操作。

3.2          队列

队列是一种类似“栈”的数据结构，只是在队列中第一个插入的数据项会被最先移除（先进先出，FIFO），而在栈中，最后插入的数据项最先移除（LIFO）。

 

队列和栈一样也被用作程序员的工具，队列的两个基本操作是插入一个数据项，即把一个数据项放入队尾；另一个是移除一个数据项，即移除队头的数据项。

 

为了避免队列不满却不能插入新数据的问题，可以让队头队尾指针绕回到数组开始的位置，这也就是循环队列（有时也称为“缓冲环”）。

 

和栈一样，队列中插入数据项和移除数据项的时间复杂度均为O(1)。

3.3          优先级队列

优先级队列是比栈和队列更专用的数据结构，在很多的情况下都很有用，优先级队列中有一个队列头和队列尾，并且也是从队列头移除数据。不过在优先级队列中，数据项按照关键字的值有序，这样关键字最小的项总是在队列头，数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。

 

优先级队列也常常被用作程序员的工具，比如在图的最小生成树算法中就应用了优先级队列。优先级队列在某些计算机系统中应用比较广泛，例如抢占式多任务操作系统中时间片的分配。

 

优先级队列中插入操作需要O(N)的时间，而删除操作需要O(1)的时间。

4.   链表

我们之前的数据结构和算法，都是以数组为基础的，数组存在一种缺陷。在无序数组中，搜索是低效的；而在有序数组中，插入效率又很低；不管在哪种数组中删除效率都很低；况且一个数组创建后，它的大小是不可改变的。

 

链表是继数组之后第二种使用得最广泛的通用存储结构，链表的机制灵活，用途广泛，适用于多种通用的数据库；也可以取代数组，作为其他存储结构的基础，例如栈和队列。

 

在链表中，每个数据项都是被包含在“链接点”中，一个链接点是某个类的对象，一个链表中有许多类似的链接点，所以有必要用一个不同于链表的类来表达链接点，每个链接点都包含一个对下一个链接点的引用。

 

在数组中，每一项占用一个特定的位置。这个位置可以用一个下标号直接访问。在链表中，寻找一个特定元素的唯一方法就是沿着这个元素的链一直向下寻找。

 

链表中在表头插入和删除数据很快，仅需要改变一两个引用值，所以花费O(1)的时间；平均起来，查找、删除和在指定链接点后面插入都需要搜索链表的一半链节点，需要O(N)次比较。在数组中执行这些操作也需要O(N)次比较，但是链表仍然要快一些，因为但插入和删除链接点时，链表不需要移动任何东西，增加的效率是很显著的，特别是当复制的时间远远大于比较时间的时候。

 

链表比数组优越的另外一个重要方面是链表需要用多少内存就可以用多少内存，并且可以扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常由于数组太大导致效率低下，或者数组太小导致空间溢出。Collection集合的ArrayList是一种可扩展的数组，它可以通过可变长度解决这个问题，但是它经常只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍的容量），这个解决方案在内存使用效率上还是要比链表的低。

 

5.   递归

递归是一种方法（函数）调用自己的编程技术。这听起来有点奇怪，或者甚至像是一个灾难性的错误。但是，递归在编程中却是最有趣，又有惊人高效的技术之一，不仅可以解决特定的问题，而且它能为解决很多问题提供了一个独特的概念上的框架。

 

递归的一些典型实例，计算三角数字（第N项是由第N-1项加N得到）：

public static int triangle(int n) {

        return n == 1 ? 1 : n + triangle(n - 1);

    }

 

所有的这些方法都可以看作是把责任推给别人，什么地方是这个传递的终结呢？在这个地方必须不再需要得到其他人的帮助就能够解决问题，如果这种情况没有发生，那么就会有一个无限的一个人要求另外一个人的链，它将永远不会结束。导致递归的方法返回而没有再一次进行递归调用，此时我们称为基值情况，每一个递归方法都会有一个基值（终止）条件，以防止无限地递归下去，以及由此引发的程序崩溃。

 

递归方法的特征：

• 调用自身；
• 但它调用自身的时候，这样做是为了解决更小的问题；
• 存在某个足够简单的问题层次，在这一层次算法不需要调用自己就能直接解答，且返回结果；

 在递归算法中每次调用自身的过程中，参数变小（或者是被多个参数描述的范围变小），这反映了问题变小或变简单的事实。但参数或者范围达到一定的最小值的时候，将会触发一个条件，此时方法不需要调用自身就可以返回。

 

调用一个方法会有一定的额外开销，控制必须从这个调用的位置转移到这个方法的开始处。除此之外，传给这个方法的参数以及这个方法返回的地址都要被压入到一个内部的栈中，为的是这个方法可以返回参数值和知道返回到哪里。

 

另外一个低效性反映在系统内存空间存储所有的中间参数以及返回值，如果有大量的数据需要存储，这就会引起栈溢出的问题。采用递归是因为它在概念上简化了问题，而不是本质上更有效率。

5.1          分治算法

递归的二分查找法是分治算法的一个例子。把一个大问题分成两个相对来说更小的问题，并且分别解决每一个小问题，这个过程一直持续下去直到达到易于求解的基值情况，就不用继续再分了。

分治算法常常是一个方法，在这个方法中含有两个对自身的递归调用，分别对应于问题的两个部分。在二分查找中，就有两个这样的调用，但是只有一个真正执行了。

5.2          归并排序

归并排序就是用递归来实现的，比简单排序中的三种排序方法要有效地多，至少在速度上是这样的。冒泡排序，插入排序和选择排序要用O（N^2）的时间，而归并排序只需要O(N*logN)的时间，归并排序也相当容易实现（至少比起下面章节中介绍的快速排序和希尔排序），一个缺点是它需要在存储器中有另一个大小等于被排序的数据项数目的数组。如果初始数组几乎占满整个存储器的空间，那么归并排序将不能工作。但是，如果有足够的空间，归并排序将是一个很好的选择。

 

归并排序的核心是归并两个已经有序的数组，归并两个有序的数组A和B，就生成了第三个数组C，数组C中包含了A和B的所有数据项，并且他们有序地排列在数组C中，排序算法的实现如下：

 

private void merge(T[] workSpace, T[] toSortArray, int lowPtr, int highPtr, int upperBound) {
        int index = 0;
        int lowerBound = lowPtr;
        int mid = highPtr - 1;
        int number = upperBound - lowerBound + 1;
        while (lowPtr <= mid && highPtr <= upperBound) {
            if (toSortArray[lowPtr].compareTo(toSortArray[highPtr]) < 0) {
                workSpace[index++] = toSortArray[lowPtr++];
            } else {
                workSpace[index++] = toSortArray[highPtr++];
            }
        }

        while (lowPtr <= mid) {
            workSpace[index++] = toSortArray[lowPtr++];
        }
        while (highPtr <= upperBound) {
            workSpace[index++] = toSortArray[highPtr++];
        }
        for (index = 0; index < number; index++) {
            toSortArray[index + lowerBound] = workSpace[index];
        }
    }

  

归并排序的思想是把一个数组分成两半，排序每一半，然后将其执行合并算法。如何对每一部分排序呢？这就需要递归了，将每一半继续分割成1/4，每个1/4进行排序，然后合并成一个有序的一半，依次类推，反复分割数组，直到得到的数组只有一个数据项，这就是其基值条件：设定只有一个数据项的数组是有序的。

 

归并排序中所有的这些子数组都存放在存储器的什么地方？本算法中创建了一个和初始数组一样大小的工作空间数组，子数组就存放在这个工作空间数组的这个部分中。

 

归并排序的运行时间是，算法执行的过程中看这个算法执行复制的次数和比较的次数（假设复制和比较是比较费时的操作，递归调用和返回不增加额外的开销，事实上也如此）。

 

一个算法作为一个递归的方法通常从概念上来讲很容易理解，但是，在实际的应用中证明递归算法的效率不是太高，这种情况下，把递归的算法转换成非递归的算法是非常有用的，这种转换经常会用到栈，任何一个递归程序都有可能作出这种转换（使用栈实现）。

6.   高级排序

前面讲了几个简单排序：冒泡排序，选择排序和插入排序，都是一些比较容易实现的，但速度比较慢的算法。归并排序运行速度比简单排序快，但是它需要的空间是原始数组空间的两倍，通常这是一个严重的缺点。

6.1          希尔排序

希尔排序基于插入排序，但是增加了一个新的特性，大大地提高了插入排序的执行效率。

 

依靠这个特别的实现机制，希尔排序对于多达几千个数据项的，中等大小规模的数组排序表现良好。希尔排序不像快速排序和其他时间复杂度为的排序算法那样快，因此对于非常大的文件排序，它不是最优选择。但是，希尔排序比插入排序和选择排序这种时间复杂度为的排序算法还是要快得多，并且它特别容易实现：希尔排序的算法既简单又很短。

 

它在最坏情况下的执行效率和在平均情况下的执行效率相比而言没有差很多，一些专家提倡差不多任何排序工作在开始时都可以使用希尔排序算法，若在实际情况下证明它不够快，再改换成诸如快速排序这样更高级的排序算法。

 

插入排序，复制的操作太多。在插入排序执行一半的时候，标记符左边这部分数据项都是排过序的，而右边都数据项则没有排过序，这个算法取出标记符所指的数据项，将其存储在一个临时变量中。

 

假设一个很小的数据项在靠右的位置上，这里本来是值比较大的数据项所在位置，将这个小数据移动到在左边的正确位置上，所有的中间项都必须要向右移动一位。这个步骤对每个数据项都执行了将近N次的复制。虽然不是所有的数据项都必须移动N个位置，但是数据项平均起来移动了N/2个位置，总共是N*N/2次复制，因此插入排序的执行效率为。

 

希尔排序通过加大插入排序中元素之间的间隔，并在这些间隔的元素中进行插入排序，从而使得数据项可以大跨度地移动。但这些数据项经过一趟排序之后，希尔排序算法减少数据项的间隔进行排序，依次进行下去。

 

public void sort(T[] toSortArray) {
        int nElements = toSortArray.length;
        int inner, outer;
        T temp;

        int interval = 1;
        while (interval <= nElements / 3) {
            interval = interval * 3 + 1;
        }

        while (interval > 0) {
            for (outer = interval; outer < nElements; outer++) {
                temp = toSortArray[outer];
                inner = outer;
                while (inner > interval - 1 && toSortArray[inner - interval].compareTo(temp) >= 0) {
                    toSortArray[inner] = toSortArray[inner - interval];
                    inner = inner - interval;
                }
                toSortArray[inner] = temp;
            }
            interval = (interval - 1) / 3;
        }
    }

  

希尔排序比插入排序要快很多，这是因为当间隔值很大的时候，数据项每一项需要移动元素的个数较少，但数据项移动的距离很长，这是非常有效率的。但间隔值变小时，每一趟需要移动的元素个数变多，但是此时它们已经接近于它们排序后最终所在的位置，这对于插入排序更有效率。

 

选择间隔序列可以说是一种魔法，例子中使用的是h=h*3+1生成间隔序列，当然使用其他间隔序列也会取得不同程度的成功。只有一个绝对的条件，就是逐渐减少的间隔最后一定要等于1，因此最后一趟的排序是一次普通的插入排序。

 

6.2          快速排序

在介绍快速排序之前，先简单讲一下划分。划分是快速排序的基本机制，其本身也是一个比较有用的操作。划分数据就是把数据分为两组，使所有的关键字大于特定值的在一组，而小于特定值的在另一组。划分前需要确定枢纽，这个值用来判断数据项属于哪一组，关键字的值小于枢纽的数据项放在数组的左边部分，关键字的值大于枢纽的数据项放在数组的右边部分。

 

在完成划分之后，数据还不能称为有序，这只是将数据简单地分成了两组。但是数据还是比没有划分之前要更接近有序了。注意，划分是不稳定的，这也就是说，每一组的数据项并不是按照它原来的顺序排列的，事实上，划分往往会颠倒组中一些数据的顺序。

 

划分算法由两个指针开始工作，两个指针分别指向数组的两头，左边的指针向右移动，右边的指针向左移动。当左边的指针遇到比枢纽值小的数据项时，它继续右移，因为这个数据项的位置已经处在数组的正确一边了；但是，但遇到比枢纽值大的数据项时，它就停下来。类似地，但右边的指针遇到大于枢纽的值的数据项时，它继续左移，但是当发现比枢纽小的数据项时，它也停下来。两个内层的while循环，第一个应用于左边指针，第二个应用于右边指针，控制这个扫描过程，因为指针退出了while循环，所以它停止移动。交换之后，继续移动指针。

 

划分算法的运行时间为O(N)，每一次划分都有N+1或N+2次比较，每个数据项都由这个或那个指针参与比较，这产生了N次比较。交换的次数取决于数据是如何排列的，如果数据是逆序排列，并且枢纽把数据项分成两半，每一对值都需要交换，也就是N/2次交换。

 

快速排序是最流行的排序算法，在大多数情况下，快速排序都是最快的，执行时间为O(N*logN)级（这只序或者说随机存是对内部存储器内的排序而言，对于在磁盘文件中的数据进行排序，其他的排序算法也许更好）。

 

快速排序算法本质上是通过把一个数组划分成两个子数组，然后递归地调用自身为每一个子数组进行快速排序来实现的。但是，对这个基本的设计还需要进行一些加工，算法必须选择枢纽以及对小的划分区域进行排序，有三个基本的步骤：

1.       把数组或者子数组划分成左边（较小关键字）的一组和右边（较大关键字）的一组；

2.       调用自身对左边的一组排序；

3.       调用自身对右边的一组排序；

 

经过一次划分之后，所有在左边子数组的数据项都小于在右边子数组的数据项，只要对左边子数组和右边子数组分别进行排序，整个数组就是有序的了。如何对子数组进行排序？只要递归调用排序算法就可以了。

 

如何选择枢纽？应该选择具体的一个数据项的关键字的值作为枢纽，可以选任意一个数据项，但划分完成之后，如果枢纽被插入到左右子数组之间的分界处，那么枢纽就落到了排序之后的最终位置上了。

 

理想状态下，应该选择被排序的数据项的中值数据作为枢纽，也就是说，应该有一半的数据项大于枢纽，一边的数据项小于枢纽，这会使得数组被划分成为两个大小相等的子数组。对快速排序来说拥有两个大小相等的子数组是最优的情况，如果快速排序算法必须要对划分的一大一小两个子数组排序，那么将会降低算法的效率，这是因为较大的子数组会必须要被划分更多次。

 

N个数据项数组的最坏情况是一个子数组只有一个数据项，而另一个子数组有N-1个数据项。在逆序排列的数据项中实际上发生的就是这种情况，在所有的子数组中，枢纽都是最小的数据项，此时算法的效率降低到了。

 

快速排序以运行的时候，除了慢还有一个潜在的问题，但划分的次数增加的时候，递归方法的调用次数增加了，每一个方法调用都要增加所需递归工作栈的大小。如果调用次数太多，递归工作栈可能会溢出，从而使得系统瘫痪。

 

人们已经设计出了很多选择枢纽的方法，方法应该简单而且能够避免出现选择最大或者最小值作为枢纽的情况。选择任意一个数据项作为枢纽的方法的确非常简单，但是这并不总是一个好的选择，可以检测所有的数据项，并且实际计算哪一个数据项是中值数据项，折中的办法是找到数组第一个，最后一个和中间位置数据项的居中数据项值，并且设置此数据项为枢纽，这称为“三数据项取中”（需要解决处理小划分等小于3个数据项的情况）。

 

快速排序的时间复杂度为，对于分治算法来说都是这样的，在分治算法中用递归的方法把一列数据项分成两组，然后调用自身分别处理每一组数据项。

7.   二叉树

7.1          为什么使用二叉树？

为什么要使用树呢？因为它结合了另外两种数据结构的优点：一种是有序数组，另一种是链表。在树中查找数据项的速度和有序查找一样快，并且插入数据项和删除数据项的速度也和链表一样。

 

在有序数组中插入数据项太慢，用二分查找法可以在有序数组中快速地查找特定的值，它的过程是先查看数组最中间的数据项，如果那个数据项值比要找的大，就缩小查找范围，在数组的后半段找；如果小就在前半段找。反复这个过程，查找数据说需要的时间是，同时也可以按顺序遍历有序数组，访问每个数据项。然而，想在有序数组插入一个数据项，就必须先查找新数据项要插入的位置，然后把所有比数据项大的数据向后移动一位（N/2次移动），删除数据项也需要多次移动，所以也很慢。

 

链表中插入和删除操作都很快，它们只需要改变一些引用值就行了，这些操作的复杂度为O(1)，但是遗憾的是，在链表中查找数据项可不那么容易，查找必须从头开始，依次访问链表中的每个数据项，直到找到该数据项为止。因此，平均需要访问N/2个数据项，把每个数据项和要查找的数据项比较，这个过程很慢，费时O(N)。

 

不难想到可以通过有序的链表来加快查找的速度，链表的数据项是有序的，但是这样做没有任何意义。即使有序的链表还是必须从头开始一次访问数据项，因为链表不能直接访问某个数据项，必须通过数据项间的链式引用才可以。

 

要是能有一种数据结构，既能像链表那样快速地插入和删除，又能像有序数组那样快速查找，树实现了这些特定，称为最有意思的数据结构之一。

 

7.2          树-简介

树由变连接的节点而构成，节点间的直线表示关联节点间的路径。

 

在树的顶层总是有一个节点，它通过边连接到第二层的多个节点，然后第二层节点连向第三层更多的节点，依此类推。所以树的顶部小，底部大。

 

 

 

树有很多种，本节中讨论的是一种特殊的树——二叉树。二叉树的每个节点最多有两个子节点。更普通的树中，节点的子节点可以多于两个，这种树称为多路树。二叉树每个节点的两个子节点被称为左子节点和右子节点，分别对于树图形它们的位置。

 

7.3          二叉搜索树

二叉搜索树特征的定义可以这么说：一个节点的左子节点的关键字值小于这个节点，右子节点的值大于或等于这个父节点。

 

注意有些树是非平衡树：这就是说，它们大部分的节点在根的一边或者另一边，个别的子树也很可能是非平衡的。树的不平衡性是由数据项插入的顺序造成的，如果关键字值是随机插入的，树或多或少更平衡一点。但是，如果插入序列是升序或者降序，则所有的值都是右子节点（升序时）或左子节点（降序时），这样树就是不平衡了。

 

如果树中关键字值的输入顺序是随机的，这样建立的较大的树，它的不平衡性问题可能不会很严重，因为很长一串随机数字有序的概率是很小的。

 

像其他数据结构一样，有很多方法可以在计算机内存中表示一棵树，最常用的方法是把节点存在无关联的存储器中，通过每个节点中指向自己子节点的引用来表示连接（当然，还可以在内存中用数组表示树，用存储在数组中相对的位置来表示节点在树中的位置）。

public class JTreeNode<T extends Comparable> {

    private T data;

    private JTreeNode<T> leftNode;

    private JTreeNode<T> rightNode;

 

 

7.4          查找节点

根据关键字查找节点是树的主要操作中最简单的：

 

public JTreeNode<T> find(T key) {

        JTreeNode<T> current = root;

        while (!current.getData().equals(key)) {

            current = current.getData().compareTo(key) > 0 ? current.getLeftNode() : current.getRightNode();

            if (current == null) {

                return null;

            }

        }

        return current;

    }
 

 

查找节点的时间取决于这个节点所在的层数，假设有31个节点，不超过5层——因此最多只需要5次比较，就可以找到任何节点，它的时间复杂度是O(logN)，更精确地说，应该是以2为底的对数。

7.5          插入节点

要插入一个节点，必须先找到插入的地方。这很像是要找一个不存在的节点的过程。从树的根节点开始查找一个相应的节点，它将是新节点的父节点。当父节点找到了，新的节点就可以连接到它的左子节点和右子节点处，这取决于新节点的值比父节点的值大还是小。

 

public void insert(T data) {

        JTreeNode<T> node = new JTreeNode<T>();

        node.setData(data);

        if (root == null) {

            root = node;

        } else {

            JTreeNode<T> current = root;

            JTreeNode<T> parent = null;

            while (true) {

                parent = current;

                if (data.compareTo(current.getData()) < 0) {

                    current = current.getLeftNode();

                    if (current == null) {

                        parent.setLeftNode(node);

                        return;

                    }

                } else {

                    current = current.getRightNode();

                    if (current == null) {

                        parent.setRightNode(node);

                        return;

                    }

                }

            }     }    }

 

7.6          遍历树

遍历树就是按照某一种特定顺序访问树的每一个节点，这个过程不如查找、插入和删除节点常用，其中一个原因是因为遍历的速度不够快。不过遍历树在某些情况下是有用的，而且在理论上很有意义，有三种简单的方法可以用来遍历树，它们是：前序，中序和后序。二叉搜索树最常用的遍历方法是中序遍历。

 

中序遍历二叉搜索树会使所有的节点按关键字升序被访问到，如果希望在二叉树中创建有序的数据序列，这是一种方法，遍历树的最简单方法是用递归的方法，这个方法只需要做三件事：

1.       调用自身来遍历节点的左子树；

2.       访问节点；

3.       调用自身来遍历节点的右子树；

 

中序遍历的方法：

 

public void inOrderTraverse(JTreeNode<T> currentNode) {

        if (currentNode != null) {

            inOrderTraverse(currentNode.getLeftNode());

            //here to add traverse code

            System.out.println(currentNode.getData());

            inOrderTraverse(currentNode.getRightNode());

        }

    }

 

 

7.7          查找最大值和最小值

在二叉搜索树中得到最大值和最小值是轻而易举的事情。要找最小值时，先走到根的左子节点处，然后接着走到那个节点的左子节点，如此类推，直到找到一个没有左子节点的节点，这个节点就是最小值的节点。

 

public JTreeNode<T> findMinimum() {

        JTreeNode<T> current, last = null;

        current = root;

        while (current != null) {

            last = current;

            current = current.getLeftNode();

        }

        return last;

    }

 同理，查找最大值就是查找最后节点的右子节点，直到找到一个没有右子节点的节点。

 

7.8          删除节点

删除节点是二叉搜索树中常用的一般操作中最复杂的，但是删除节点在很多树的应用中又非常重要。

 

删除节点要从查找要删除的节点开始入手，方法与前面介绍的查找节点和插入节点相同，查找节点代码如下：

public boolean delete(T key) {

        JTreeNode<T> current = root;

        JTreeNode<T> parent = root;

        boolean isLeftChild = true;

        while (!current.getData().equals(key)) {

            parent = current;

            if (key.compareTo(current.getData()) < 0) {

                isLeftChild = true;

                current = current.getLeftNode();

            } else {

                isLeftChild = false;

                current = current.getRightNode();

            }

            if (current == null) {

                return false;

            }

        }

 

找到节点后，有三种情况需要考虑：

1.       该节点是叶子节点；

要删除叶节点，只需要改变该节点的父节点的对应字段值，由指向该节点改为null就可以了，要删除的节点依然存在，但它已经不是树的一部分了；如果要删除的节点是根，直接设置根为空值。

 

因为Java语言有垃圾回收机制，所以不需要非得把节点本身给删掉。一旦Java认识到程序不再与这个节点有关联，就会自动把它清理出存储器。

 

 

if (current.getLeftNode() == null && current.getRightNode() == null) {

            if (current == root) {

                root = null;

            } else if (isLeftChild) {

                parent.setLeftNode(null);

            } else {

                parent.setRightNode(null);

            }

 

 

2.       该节点有一个子节点；

这个节点只有两个连接：连接父节点的和连向它惟一的子节点的。需要从这个序列中剪断这个节点，把它的子节点连接到它的父节点上。这个过程要求改变父节点适当的引用，指向要删除节点的子节点；如果被删除的节点是根，它没有父节点，只是被合适的子树所代替。

 

 

} else if (current.getRightNode() == null) {

            if (current == root) {

                root = current.getLeftNode();

            } else if (isLeftChild) {

                parent.setLeftNode(current.getLeftNode());

            } else {

                parent.setRightNode(current.getLeftNode());

            }

        } else if (current.getLeftNode() == null) {

            if (current == root) {

                root = current.getRightNode();

            } else if (isLeftChild) {

                parent.setLeftNode(current.getRightNode());

            } else {

                parent.setRightNode(current.getRightNode());

            }

 注意应用引用使得移动整棵子树非常容易。这只要断开连向子树的旧的引用，建立新的引用连接到别处即可。

 

3.       该节点有两个子节点

如果要删除的节点有两个子节点，就不能只是用它的一个子节点代替它，就需要用另一种方法，对于每一个节点来说，比该节点的关键字值次高的节点是它的中序后继，可以简称为该节点的后继。这就是窍门：删除有两个子节点的节点，用它的中序后继来代替该节点。

 

怎么找到该节点的后继呢？首先，程序找到初始节点的右子节点，它的关键字一定比初始节点大，然后转到初始节点的右子节点的左子节点那里（如果有的话），然后到这个左子节点的左子节点，以此类推，顺着左子节点的路径一直向下找，这个路径上的最后一个左子节点就是初始节点的后继，算法如下：  

 

 

private JTreeNode<T> getSuccessor(JTreeNode<T> delNode) {

        JTreeNode<T> successorParent = delNode;

        JTreeNode<T> successor = delNode;

        JTreeNode<T> current = delNode.getRightNode();

        while (current != null) {

            successorParent = successor;

            successor = current;

            current = current.getLeftNode();

        }

        if (successor != delNode.getRightNode()) {

            successorParent.setLeftNode(successor.getRightNode());

            successor.setRightNode(delNode.getRightNode());

        }

        return successor;

    }

 

 

如果后继是当前current的右子节点，情况相对简单，只需要把后继为根的子树移到删除节点的位置；

 

如果后继节点有子节点怎么办？首先，后继节点是肯定不会有左子节点的，这是由查找后继节点的算法导致的，后继只能有右子节点。当后继节点是要删除节点右子节点的左后代，执行删除要经过如下的步骤：

1.       把后继父节点的左子节点字段设置为后继的右子节点；

2.       把后继的右子节点设置为要删除节点的右子节点；

3.       把当前节点从它父节点的右子节点删除，把这个值设置为后继；

4.       把当前左子节点从当前节点移除，后继节点的左子节点设置为当前节点的左子节点。

 

 

JTreeNode<T> successor = getSuccessor(current);

            if(current == root){

                root = successor;

            } else if(isLeftChild){

                current.setLeftNode(successor);

            } else {

                current.setRightNode(successor);

            }

            successor.setLeftNode(current.getLeftNode());

 

 

看到这里，就会发现删除是相当棘手的操作，实际上，因为它非常复杂，一些程序员都尝试躲开它。他们在树节点的node类中增加了一个Boolean的字段，用来表示是否已经被删除，要删除一个节点时，就将该字段设置为true，其他操作如查找之前，就必须先判断该字段是否已经被设置为true。这种方法也许有些逃避责任，但如果树中没有那么多删除操作时也不失为一个好方法。

7.9          二叉树的效率

树的大部分操作都需要从上到下一层一层地查找某个节点，一棵满树中，大约一半的节点在最底层。因此，查找、插入和删除节点的操作大约有一半都需要找到最底层的节点（以此类推，大约四分之一节点的这些操作要到倒数第二层）。因此，常见的树的操作时间复杂度大概是N以2为底的对数，表示为O(logN)。

 

把树和其他数据结构作比较，相比于无序数组或链表中，查找数据会变得很快；有序数组可以很快地找到数据项，但插入数据平均需要移动N/2，相比起来，树在插入数据时复杂度较低。因此，树对所有常用的数据存储操作都有很高的效率。

 

唯一不足的就是遍历不如其他操作快，但是遍历在大型数据库中不是常用的操作。

7.10    哈夫曼（Huffman）编码

二叉树并不全是搜索树，本节中介绍一种算法，它使用二叉树以令人惊讶的方式来压缩数据，数据压缩在很多领域中都是非常重要的。

 

首先来看简单一些的解码是怎样完成的，消息中出现的字符在树中的叶子节点，它们在消息中出现的概率越高，在树中的位置也越高，每个圆圈外面的数字就是频率，非叶节点外面的数字是它子节点频率的和。

 

如何使用该树进行解码？每个字符都是从根开始，如果遇到0，就向左走到下个节点，如果遇到1，就向右，这样就找到了相应的节点A。

 

 

 

下面是建立哈夫曼树的方法：

1.       为消息中的每个字符创建一个Node对象，每个节点有两个数据项：字符和字符在消息中出现的频率；

2.       为这些节点创建tree对象，这些节点就是树的根；

3.       把这些树都插入到一个优先级队列中，它们按照频率排序，频率最小的节点拥有最高的优先级。因此，删除一棵树的时候，它就是队中最少用到的字符。

  

现在做下面的事情：

1.       从优先级队列中删除两棵树，并把它们作为一个新节点的子节点。新节点的频率是子节点频率的和；它们的字符字段可以是空的；

2.       把这个新的三节点树插回到优先级队列中；

3.       反复重复第一步和第二步，树会越变越大，队列中的数据项会越来越少，但队中只有一棵树时，它就是建立后的哈夫曼树了。

 

8.   红-黑树

普通的二叉树作为数据存储工具有着重要的优势：可以快速地找到给定关键字的数据项，并且可以快速地插入和删除数据项。其他的数据存储结构，例如数组、有序数组和链表，执行这些操作却很慢。因此二叉树似乎是很理想的数据存储结构。

 

遗憾的是，二叉搜索树有一个很麻烦的问题，如果树中插入的是随机数据，执行效果很好；但是如果插入的数据是有序的，速度会变得非常慢，此时二叉树就是非平衡的了，对于非平衡树，它的快速查找指定数据项的能力就丧失了。

 

但树没有分支时，它其实就是一个链表。数据的排列是一维的，而不是二维的，这种情况下，查找的速度下降到O(N)，对于随机数据的实际数量来说，一棵树特别不平衡的情况是不大可能的，但是可能会有一小部分有序数据使树部分非平衡。搜索部分非平衡树的时间介于O(N)和O(logN)之间，这取决于树的不平衡程度。

 

红-黑树的平衡是在插入的过程中取得的，对于一个要插入的数据项，插入例程要检查不会破坏树一定的特征。如果破坏了就要马上纠正，根据需要修改树的结构，通过维持树的特征，保证树的平衡。

8.1          红-黑树的特征

节点都有颜色

每一个节点或者是黑色或者是红色。

在插入和删除的过程中，要遵守保持这些颜色的不同排列的规则

1.       每一个节点不是红色就是黑色；

2.       根总是黑色的；

3.       如果节点是红色，则它的子节点必须是黑色的；

4.       从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。

8.2          红-黑树的效率

和一般的二叉搜索树类似，红黑树的查找，插入和删除的时间复杂度为O(logN)，额外的开销仅仅是每个节点的存储空间都稍微增加了一点，来存储红-黑的颜色。红-黑树的优点是对有序数据的操作不会慢到O(N)的时间复杂度。

9.   2-3-4树和外部存储

二叉树中，每个节点有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。2-3-4树非常有趣，它像红-黑树一样是平衡树，它的效率比红-黑树要差一些，但编程容易实现，学习2-3-4树可以更容易地理解B-树。

 

B-树是另一种多叉树，专门用在外部存储（通常是磁盘驱动器）中来组织数据。

 

9.1          2-3-4树

 

2-3-4树名字中的2、3和4的含义是指一个节点可能含有的子节点的个数。对非叶子节点来说有三种可能的情况：

l  有一个数据项的节点总是有两个子节点；

l  有两个数据项的节点总是有三个子节点；

l  有三个数据项的节点总是有四个子节点；

 

简而言之，非叶节点的子节点树总是比它含有的数据项数多1，这个重要的关系决定了2-3-4树的结构，比较来说，叶节点没有子节点，然而它可能含有2、3、4个数据项，空节点是不会存在的。

 

在2-3-4树中，不允许只有一个链接，有一个数据项的节点必须总是保持有两个链接，除非它是叶节点，在那种情况下没有链接。

 

树结构中很重要的一点就是它的链与自己数据项的关键字值之间的关系。二叉树中，所有关键字值比某个节点值小的节点都在这个节点左子节点为根的子树上，所有关键字值比某个节点值大的节点都在这个节点右子节点为根的子树上。2-3-4树中规则是一样的，还加上了一下几点：

l  根是child0的子树的所有子节点的关键字值小于key0；

l  根是child1的子树的所有子节点的关键字值大于key0小于key1；

l  根是child2的子树的所有子节点的关键字值大于key1小于key2；

l  根是child3的子树的所有子节点的关键字值大于key2；

 

注意树是平衡的，即使插入一列升序（或降序）排列的数据2-3-4树都能保持平衡。

9.1.1  2-3-4树的搜索

查找特定关键字值的数据项和在二叉树中的搜索例程相类似。从根开始，除非查找的关键字值是根，否则选择关键字值所在的合适范围，转向那个方向直到找到为止。

9.1.2  插入

新的数据项总是插在叶节点里，在树的最底层。如果插入到有子节点的节点里，子节点的编号就要发生变化以此来保持树的结构，这保证了节点的子节点比数据项多1。在2-3-4树中插入节点有时候比较简单，有时候相当复杂，无论哪种情况都是从查找适当的叶子节点开始的。

 

如果查找时没有碰到满节点时，插入很简单，找到合适的叶子节点后，只要把新数据插入进去便可以了；如果向下寻找要插入位置的路途中，节点已经满了，插入就变得复杂了。发生这种情况时，节点必须分裂，正是这种分裂过程保证了树的平衡（分裂过程比较复杂，暂不赘述，有兴趣的同学可以研究一下）。

9.1.3  效率

分析2-3-4树的效率比红-黑树要困难，但是还是可以从两者的等价性开始分析。查找过程中红-黑树每层都要访问一个节点，可能是查找已经存在的节点，也可能是插入一个新的节点，2-3-4树与红-黑树在这个方面是比较类似的，但是2-3-4树有个优势就是层数比红-黑树要短，在所有节点都满的情况下，2-3-4树的高度就大致在log(N+1)到log(N+1)/2之间，减少2-3-4树的高度可以使它的查找时间比红-黑树的短一些。

9.2          外部存储

2-3-4树是多叉树的例子，多叉树是指节点多于两个并且数据项多于一个。另一种多叉树，B-树，在外部存储器上的数据存储时有着很大的作用（外部存储指的是磁盘系统）。

 

到目前为止所讲过的数据结构都是假设数据存储在主存中（RAM，随机访问存储器）的，但是，大多数情况下要处理的数据项太大，不能都存储在主存中，这种情况需要另外一种存储方式：磁盘文件存储器。磁盘存储还有另外一个好处，持久性，但计算机断电时，主存中的数据会丢失，磁盘文件存储器断点后还可以保存数据；缺点就是要比主存慢得多。

 

在磁盘存储器中保存着大量的数据，怎样组织他们来实现快速查找、插入和删除呢？

 

计算机的主存按电子的方式工作，几微秒就可以访问一个字节。在磁盘存储器上存取要复杂得多，在旋转的磁盘上数据按照圆形的磁道排列，要访问磁盘驱动器上的某段数据，读写头要移动到正确的磁道，通过步进的电动机或类似的设备完成，这样的机械运动需要几毫秒。一旦找到正确的磁道，读写头必须要等待数据旋转到正确的位置，平均来说这还需要旋转半圈，读写头就位后，就可以进行实际的读/写操作了，这可能还需要几毫秒。因此，通常磁盘存取的速度大约是10毫秒，这比访问主存大概慢了10000倍（每年都会发展新技术来减少磁盘存取的时间，但是主存访问时间提升得远远超过了磁盘存取）。

 

磁盘驱动器每次最少读或者写一个数据块的数据，块的大小根据操作系统，磁盘驱动器的容量和其他因素组成，总是2的倍数。在读写操作时如果按照块的倍数来操作时效率最高的，通过组织软件使它每次操作一块数据，可以优化性能。

9.2.1  顺序有序排列

假设磁盘数据是顺序有序排列的，如果要查找某个记录，可以用二分查找方法，需要从读取一块记录中间位置的记录开始，现在处理的数据存储在磁盘上，因为每次磁盘存取都很耗时，所以更重要的是要注意访问多少次磁盘，而不是有多少独立的记录。

 

磁盘存取要比内存读取慢很多，但另一方面，一次访问一块，块数比记录数要少得多，假如31250块记录，取2的对数等于15次，理论上要读取磁盘数据15次。实际上这个数据还是要小一点，因为每块记录可能存储多条数据（假设是16条），一次可以读取16条记录，二分查找的开始阶段，内存中有多少条记录不会有很大的帮助，因为下一次存取会在较远的位置，但离下一条记录很近的时候，内存记录就非常有用了，因为它可能会直接存在这16条记录当中。

 

不幸的是，要在顺序有序排列的文件插入（或删除）一个数据项时的情况要遭得多，因为数据是有序的，这两个操作要平均移动一半的记录，因此要移动大概一半的块，这显然太不理想了。

 

顺序有序排列的另外一个问题是，如果它只有一个关键字，速度还比较快；比如文件是按照姓排序的，假设需要用地址簿中的电话号码方式查找，就不能用二分查找，因为数据时按照姓排序的，这就得查找整个文件，用顺序访问的方式一块一块地找，非常糟糕，所以需要寻找一种更有效的方式来保存磁盘中的数据。

9.2.2  B-树

怎样保存文件中的记录才能够快速地查找、插入和删除记录呢？树是组织内存数据的一个好方法，可以应用到外部存储的文件中来，但对于外部存储来说，需要用和内存数据不一样的树，这种树是多叉树，有点儿像2-3-4树，但每个节点有多个数据项，称它为B-树。

 

为什么每个节点有那么多的数据项呢？一次读或写一块的数据时的效率最高，在树中，包含数据的实体是节点。把一整块数据作为树的节点是比较合适的，这样读取一个节点可以在最短的时间里访问最大数据量的数据。

 

树中还需要保存节点间的链接（链接到其他块儿的，节点对应块），内存中的树里这些链接是引用，指向内存中其他部分的节点。在磁盘文件中的存储的树，链接是文件中的块儿的编号，可用int型的字段保存块号码，int可以保存20亿以上的块号码，基本上对大多数的文件都够用了。

 

在每个节点中数据是按照关键字顺序有序排列的，像2-3-4树一样。实际上，B-树的结构很像2-3-4树，只是每个节点有更多的数据项和更多的指向子节点的链接。B-树的阶数由节点拥有最多的节点数决定。

 

在记录中按照关键字查找和在内存的2-3-4树非常类似。首先，含有根的块儿读入到内存中，然后搜索算法开始在这15个节点中查找（或者块儿不满的话，有多少块就检查多少块儿），从0开始，但记录的关键字比较大时，需要找在这条记录和前一条记录之间的那个子节点。

 

尽可能让B-树节点满是非常重要的，这样每次存取磁盘时，读取整个节点，就可以获得最大数量的数据。

 

因为每个节点有那么多的记录，每层有那么多的节点，因此在B-树上的操作非常快，这里假设所有的数据都保存在磁盘上。在电话本的例子里有500000条记录，B-树中所有的节点至少是半满的，所有每个节点至少有8个记录和9个子节点的链接。树的高度因此比N以9为底的对数，N是500000，结果为5972，这样树的高度大概为6层，使用B-树只需要6次访问磁盘就可以在有500000条记录的文件中找到任何记录了，每次访问10毫秒，需要花费60毫秒的时间，这比顺序有序排列的文件中二分查找要快得多。

 

虽然B-树中的查找比在顺序有序排列的磁盘文件查找块，但是插入和删除操作才显示出B-树的最大优越性。

 

另一种加快文件访问速度的方法是用顺序有序排列存储记录但用文件索引连接数据。文件索引是由关键字-块对组成的列表，按关键字排序。索引中的记录根据某个条件顺序排列，磁盘上原来那些记录中可以按任何顺序有序排列，这就是说新记录可以简单地添加到文件末尾，这样记录可以按照时间排列。        

 

索引比文件中实际记录小得多，它甚至可以完全放在内存里。在本章中介绍的实例中，有500000条记录，每条的索引中的记录是32字节，这样索引大小是32×500000字节，即1600000字节(1.6M)，放在内存中没有任何问题，索引可以保存在磁盘中，数据库程序启动后读取到内存中，这样对索引的操作就可以直接在内存中完成了，每天结束时索引可以写回磁盘永久保存。应用将索引放在内存中的方法，使得操作电话本的文件比直接在顺序有序排列记录的文件中执行操作更快。

 

在索引文件中插入新数据项，要做两步，首先把这个数据项整个记录插入到主文件中去，然后把关键字和包括新数据项存储的块号码的记录插入到索引中。

 

如果索引是顺序有序排列的，要插入新数据项，平均需要移动一半的索引记录。当然可以使用更复杂的方法在内存中保存索引，例如保存成二叉树，2-3-4树，或红-黑树，这些方法都大大地减少了插入和删除的时间。这种情况下把索引存在内存中的方法都比文件顺序有序排列的方法快得多，有时比B-树都要快。

 

索引方法的一个优点是多级索引，同一个文件可以创建不同关键字的索引。在一个索引中关键字可以是姓，另一个索引中的关键字可以是地址，索引和文件比起来很小，所以它不会大量地增加数据存储量。

 

如果索引太大不能放在内存中，就需要按照块分开存储在磁盘上，对大文件来说把索引保存成B-树是很合适的，主文件中记录可以存成任何合适的顺序。

 

对于外部文件来说，归并排序是外部数据排序的首选方法，这是因为这种方法比起其他大部分排序方法来说，磁盘访问更多地涉及临近的记录而不是文件的随机部分。

 

第一步，读取一块，它的记录在内部排序，然后把排完序的块写回到磁盘中，下一块儿也同样排序并写回到磁盘中，直到所有的块内部都有序为止；

 

第二步，读取两个有序的块，合并成一个两块的有序的序列，再把它们写回到磁盘中，下次把每两块序列合成四块儿的序列。这个过程继续下去，直到所有成对的块都合并了为止。每次，有序的长度增长一倍，直到整个文件有序。

10.         哈希表

哈希表是一种数据结构，可以提供快速的插入和查找操作。第一次接触哈希表时，它的优点多得让人难以置信，不论哈希表有多少数据，插入和删除只需要常量级的时间，即O(1)的时间。哈希表运算得非常快，在计算机程序中，如果需要在一秒钟查找上千条记录，通常使用哈希表。哈希表的速度明显比较比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也容易。

 

哈希表也有一些缺点，它是基于数组的，数组创建后难于扩展。某些哈希表被基本填满时，性能下降地非常严重；而且，也没有一种简便的方法可以以任何一种顺序（比如从小到大）遍历表中的数据项，如果需要这种能力，只能选择其他数据结构。

 

然而，如果不需要有序遍历数据，而且可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。

 

假设使用数组作为数据存储结构，如果知道数组下标，要访问特定的数组数据数据项非常方便也非常快。增加一个新项很快，只需要把它插在最后一个数据项的后面，使用基于数组的数据库，使得存储数据块且非常简单，很吸引人，但是关键字必须组织得非常好，能够直接查找到数组下标以便查找到该数据项。

10.1    哈希化

经典使用的例子是字典，如果想要把一本英文字典的每个单词，从a到zyzzyva，都写入到计算机内存，以便快速读写，那么哈希表是一个不错的选择。

 

如何把单词转换成数组下标？把单词每个字符的代码求和（a=0,b=1,z=26），如果是cats，转换的下标为43，如果用这样的方法，a转换成0，字典中最后一个单词是zzzzzzzzzz(10个z)，所有字符编码的和是26×10=260，因此，单词编码的范围是0到260，不幸的是，词典中有50000个单词，没有足够的下标来索引那么多的单词，每个数组数据项大概要存储192个单词；如果用幂的连乘，27个字符，最终结果是，最终结果可能会7000000000，这个过程确实可以创造出独一无二的整数，但是结果非常巨大。内存中的数组根本不会有这么多的单元。第一种方法下标太小，第二种方法下标又太大。

 

现在需要一种压缩方法，把数位幂的连乘系统中得到的巨大的整数范围压缩到可接受的数组范围内。

 

但是如果把所有的字典数据都放在数组中，如果只有50000个单词，可能会假设这个数组大概就有这么多空间。但实际上，需要多一倍的空间容纳这些单词。所以最终需要容量为100000的数组，把0到7000000000的范围，压缩到0到100000，有一种简单的方法是取余，smallNumber = largeNumber % smallRange，用类似的方法把表示单词的唯一的数字压缩成数组下标，这是一种哈希函数。

 

但是，把巨大的数字空间压缩成较小的数字空间，必然要付出代价，即不能保证每个单词都映射到数组的空白单元。假设在数组中要插入一个新的数据项，通过哈希函数得到其下标后，发现那个单元已经有一个数据项，因为这两个数据项哈希化得到的下标完全相同，这种情况就是冲突。

 

冲突的可能性会导致哈希化方法无法实施，实际上，可以通过其他方式解决这个问题。但冲突发生时，一个方法是通过系统的另一个方法找到数组的一个空位，并把这个数据项填入，而不再使用哈希函数得到的数组下标，这个方法叫做开发地址法；第二种方法是创建一个存放一个单词链表的数组，数组内不直接存储单词。这样，但发生冲突时，新的数据项直接接到这个数组下标所指的链表中，这种方法叫做链地址法。

10.2    开放地址法

在开放地址法中，若数据不能直接放在由哈希函数计算出来的数组下标所指的单元时，就需要寻找数组的其他位置。

10.2.1              线性探测

线性探测中，线性地查找空白单元，如果5421是要插入数据的位置，它已经被占用了，那么就使用5422，然后5433，以此类推，数组下标一直递增，直到找到空位，这就叫线性探测，因为它沿着数组的下标一步一步地顺序查找空白单元。

 

当哈希表变得太满时，一个选择是扩展数组。在Java中，数组有固定的大小，而且不能扩展。编程时只能另外创建一个新的更大的数组，然后把旧数据的所有内容插入到新的数组中去。

 

哈希函数根据数组大小计算给点数据项的位置，所以这些数据项不能再放到新数组和老数组相同的位置上，因此不能简单地从一个数组向另一个数组拷贝数据。需要按照顺序遍历数组，然后执行insert向新数组中插入数据项，这叫做重新哈希化，这是一个非常耗时的过程，但是如果数组要进行扩展，这个过程是必要的。

 

扩展后的数组是原来的两倍，事实上，因为数组的容量最好应该是一个质数，新数组的长度应该是两倍多一点，计算新数组的容量是重新哈希化的一部分。

10.2.2              二次探测

在开放地址法中的线性探测会发生聚集（连续使用的数组单元），一旦聚集形成，就会变得越来越大。那些哈希化的落在聚集范围内的数据项，都要一步一步地移动，并且插在聚集的最后，因此使得聚集变得更大，聚集越大，增长地越快。

        

已填入哈希表的数据项和表长的比率叫做装填因子，当装填因子不太大时，聚集分布地比较连贯，哈希表的某个部分可能包含大量的聚集，而另一个部分还很稀疏，聚集降低了哈希表的性能。

 

二次探测是防止聚集产生的一种尝试，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。在线性探测中，如果哈希函数计算的原始下标是x，线性探测是x+1,x+2,x+3，以此类推。而在二次探测中，探测的过程是x+1,x+4,x+9,x+16,以此类推。

 

但二次探测的搜索变长时，好像它变得越来越绝望。第一次，查找相邻的单元。如果这个单元被占用，它认为这里可能有一个小的聚集，所以，它尝试距离为4的单元，如果这里也被占用，认为这里有个更大的聚集，然后尝试距离为9的单元，如果这也被占用，它感到一丝恐慌，跳到距离为16的单元，但哈希表几乎填满时，它会歇斯底里地跨越整个数组空间。

 

二次探测消除了在线性探测中产生的聚集问题，这种问题叫做原始聚集。然后，二次探测产生了另外一种，更细的聚集问题。之所以会发生，是因为所有映射到同一个位置的关键字在寻找空位时，探测的单元都是一样的。

10.2.3              再哈希法

为了消除原始聚集和二次聚集，可以使用另外一种方法：再哈希法。二次聚集产生的原因是，二次探测的算法产生的探测序列步长总是固定的：1，4，9，16，依此类推。

 

现在需要的一种方法是产生一种依赖关键字的探测序列，而不是每个关键字都一样，那么不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。方法是把关键字用不同的哈希函数再做一次哈希化，用这个结果作为步长。经验说明，第二个哈希函数必须具备以下特点：

• 和第一个哈希函数不同；

• 不能输出0（否则将没有步长：每次探测都是原地踏步，算法陷入死循环）。

 

使用开放地址策略时，探测序列通常用再哈希法生成。

10.3    链地址法

开放地址法中，通过在哈希表中再寻找一个空位解决冲突问题。另一个方法是在哈希表每个单元设置链表。某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加到链表中，不需要在元素的数组中寻找空位。

 

 

 

 

链地址法在概念上比开放地址法中的几种探测策略都要有效且简单，然而代码会比其它的长，因为必须包含链表机制。

 

链地址法中的装填因子与开放地址法的不同，在链地址法中，需要在有N个单元的数组中装入N个或更多的数据项；因此装填因子一般为1，或比1大，这没有问题，因为某些位置包含的链表中包含两个或两个以上的数据项。

 

当然，如果链表中有许多项，存取的时间就会变长，找到初始的单元需要O(1)的时间级，而搜索链表的时间与M成正比，M为链表包含的平均项数，即O(M)的时间级，因此不希望链表太满。

10.4    哈希函数

好的哈希函数很简单，所以能够快速计算，哈希表的主要优点是它的速度。如果哈希函数运行缓慢，速度就会降低。哈希函数中有很多乘法和除法是不可取的（Java或C++语言中有位操作，例如除以2的倍数，使得每位都向右移动，这种操作很有用）。

 

所谓完美的哈希函数把每个关键字都映射到表中不同的位置，只有在关键字组织得异乎寻常的好，且它的范围足够小，可以直接用于数组下标的时候，这种情况才可能出现。哈希函数需要把较大的关键字值范围压缩成较小的数组下标的范围。

 

压缩关键字字段，要把每个位都计算在内。而且，校验和应该舍弃，因为它没有提供任何有用的信息，在压缩中是多余的，各种调整位的技术都可以用来压缩关键字的不同字段。关键字的每个字段都应该在哈希函数中有所反映，关键字提供的数据越多，哈希化后越可能覆盖整个下标范围。

 

关于哈希函数的窍门是找到既简单又快的哈希函数，而且去掉关键字中的无用数据，并尽量使用所有的数据。通常，哈希函数包含对数组容量的取模操作，如果关键字不是随机分布的，不论使用什么哈希化系统都应该要求数组容量为质数。

10.5    哈希化的效率

在哈希表中执行插入和查询操作可以达到O(1)的时间级，如果没有发生冲突，只需要使用一次哈希函数和数组的引用，就可以插入一个新数据项或找到一个已存在的数据项。这是最小的存取时间级。

 

如果发生冲突，存取时间就依赖后来的探测深度，因此一次单独的查找或插入时间与探测的长度成正比，这里还要加到哈希函数的执行时间。

 

平均探测长度（以及平均存取时间）取决于装填因子（表中项数和表长的比率）。随着装填因子变大，探测长度也越来越长。

11.         堆

前面介绍了优先级队列，它是对最小（最大）关键字的数据项提供便利访问的数据结构。优先级队列可以用于计算机的任务调度，在计算机中某些程序和活动需要比其他的程序和活动先执行，因此要给它们分配更高的优先级。

 

优先级队列是一种抽象数据类型，它提供了删除最大（最小）关键字值的数据项的方法，插入数据项的方法，和其他操作，优先级队列可以用不同的内部结构实现。优先级队列可以用有序数组来实现，这种做法的问题是，尽管删除最大数据项的时间复杂度为O(1)，但是插入还是需要较长的O(N)的方法，这是因为必须移动数组中平均一半的数据项以插入新的数据项，并在插入后数组依然有序。

 

本节中介绍优先级队列中的另一种结构：堆。堆是一种树，由它实现的优先级队列的插入和删除时间复杂度都是O(logN)，尽管这样删除的时间变慢了一些，但是插入的时间快多了。但速度非常重要，且很多插入操作时，可以选择堆来实现优先级队列。

 

• 堆是有如下特点的二叉树：

• 它是完全二叉树，这也就是说，除了树的最后一层节点不需要是满的，其他每一层从左到右都完全是满的；

• 它常常是用一个数组来实现的；

• 堆中的每一个节点都满足堆的条件，也就是说每一个节点的关键字都大于（或等于）这个节点的子节点的关键字。

 

 

 

堆是完全二叉树的事实说明了堆的数组中没有“洞”，从下标0到N-1，每个数据单元都有数据项。本节中假设最大的关键字在根节点上，基于这种堆的优先级队列是降序的优先级队列。

 

堆和二叉搜索树相比是弱序的，在二叉搜索树中所有节点的左子孙的关键字都小于右子孙的关键字。这说明一个二叉搜索树中通过一个简单的算法就可以按序遍历节点。在堆中，按序遍历节点是困难的，因为堆中的组织规则比二叉搜索树的组织规则弱。对于堆来说，只要求沿着从根到叶子的每条路径，节点都是降序排列的。

 

由于堆是弱序的，所以一些操作是困难的或者是不可能的。除了不支持遍历以外，也不能在堆上便利地查找指定关键字，因为在查找的过程中，没有足够的信息来决定选择通过节点的两个节点中哪一个走向下一层，它也不能在少至O(logN)的时间内删除一个指定关键字的节点，因为没有办法能够找到这个节点。

 

因此，堆的这种组织似乎非常接近无序，不过对于快速移除最大节点的操作以及快速插入节点的操作，这种顺序已经足够了，这些操作是使用堆作为优先级队列时所需的所有操作。

11.1    移除节点

移除是指删除关键字最大的节点，这个节点是根节点，所以移除是非常容易的，根在堆数组中的索引总是0。

 

但是问题是，一旦移除了根节点，树就不再是完全的；数组里就有了一个空的数据单元。这个“洞”必须要填上，可以把数组中所有数据项都向前移动一个单元，但是还有快得多的方法，下面就是移除最大节点的步骤：

1.       移走根；

2.       把最后一个节点移动到根的位置；

3.       一直向下筛选这个节点，直到它在一个大于它的节点之下，小于它的节点之上为止。

 

 

向上或者向下筛选一个节点是指沿着一条路径一步步移动此节点，和它前面的节点交换位置，每一步都检查它是否处在了合适的位置。

 

11.2    插入节点

插入节点是非常容易的，插入使用向上筛选，而不是向下筛选。节点初始时插入到数组中最后一个空着的单元中，数组容量大小增一。但这样会破坏堆的条件，如果新插入的节点大于它新得到的父节点时，就会发生这种情况。因为父节点在堆的底端，它可能很小，所以新节点就显得比较大。因此，需要向上筛选新节点，直到它在一个大于它的节点之下，在一个小于它的节点之上。

 

向上筛选的算法比向下筛选的算法相比来说简单，因为它不用比较两个子节点的关键字大小。节点只有一个父节点，目标节点只要和它的父节点换位即可。如果先移除一个节点再插入相同的一个节点，结果并不一定是恢复成原来的堆。一组给定的节点可以组成很多合法的堆，这取决于节点插入的顺序。

11.3    堆操作的效率

对有足够多数据项的堆来说，向上筛选和向下筛选算法算是堆操作中最耗时的部分。这两个算法都是沿着一条路径重复地向上或向下移动节点，所需的复制操作和堆的高度有关系。

11.4    基于树的堆

也可以基于真正的树来实现堆，这棵树可以是二叉树，但不会是二叉搜索树，它的有序规则不是那么强。它也是一棵完全树，没有空缺的节点，称这样的树为树堆。

 

关于树堆的一个问题是找到最后的一个节点，移除最大数据项的时候是需要找到这个节点，因为这个节点将要插入到已移除的根的位置（然后再向下筛选）。同时也需要找到的一个空节点，因为它是插入新节点的位置。由于不知道它们的值，况且它不是一棵搜索树，不能直接查找到这两个节点，这就需要使用节点的标号的算法了，关键是取模（%）操作。

 

树堆操作的时间复杂度为O(logN)，因为基于数组的堆操作的大部分时间都消耗在向上筛选和向下筛选的操作上了，操作的时间和树的高度成正比。

11.5    堆排序

堆数据结构的效率使它引出一种出奇简单，但却很有效率的排序算法，称为堆排序。

 

堆排序的基本思想是使用普通的insert()例程在堆中插入全部无序的数据项，然后重复用remove()例程，就可以按顺序移除所有数据项。因为插入和删除方法操作的时间复杂度都是O(logN)，并且每个方法都必须要执行N次，所以整个排序操作需要O(N*logN)时间，这和快速排序一样，但是它不如快速排序快，部分原因是向下筛选中的循环的操作比快速排序里循环的操作要多。

 

尽管它要比快速排序略慢，但它比快速排序优越的一点是它对初始数据的分布不敏感。在关键字值按某种排列顺序的情况下，快速排序运行的时间复杂度可以降低到O（N^2）级，然而堆排序对任意排列的数据，其排序的时间复杂度都是O(N*logN)。

12.         数据结构的应用场合

12.1    通用的数据结构

12.1.1              数组，链表，树，哈希表

对于一个给定的问题，这些通用的数据结构中哪一个是合适的呢？下图给出一个大致的解法：

 

 

12.1.2              数组

当存储和操作数据时，在大多数情况下数组是首先应该考虑的结构。数组在下列情况下很有用：

•  数据量较小。

• 数据量的大小事先可预测。

 

如果插入速度很重要的话，可以使用无序数组。如果查找数组很重要的话，使用有序数组并用二分查找。数组元素的删除总是很慢，这是由于为了填充空出来的单元，平均半数以上要被移动。在有序数组中的遍历是很快的，而无序数组中不支持这种功能。

 

使用集合（Collection）是一种当数据太满时可以自己扩充空间的数组，集合可以应用于数据量不可预知的情况下，然而在向量扩充时，要将旧的数据拷贝到一个新的空间中，这一过程会造成程序明显的周期性暂停。

12.1.3              链表

如果需要存储的数据量不能预知或者需要频繁地插入删除数据元素时，考虑使用链表。但有新的元素加入时，链表就开辟新的所需要的空间，所以它甚至可以占满几乎所有的内存，在删除过程中没有必要像数组那样填补“空洞”。

 

在一个无序的链表中，插入是相当快的，查找或删除却很慢（尽管比数组的删除快一些），因此与数组一样，链表最好也应用于数据量相对较小的情况。对于编程而言，链表比数组复杂，但它比树或哈希表简单。

12.1.4              二叉搜索树

当确认数组和链表过慢时，二叉树是最先应该考虑的结构。树可以提供快速的O(logN)级的插入、查找和删除。遍历的时间复杂度是O(N)级的，这是任何数据结构遍历的最大值。对于遍历一定范围内的数据可以很快地访问出数据的最大值和最小值。

 

对于程序来说，不平衡的二叉树要比平衡的二叉树简单地多，但不幸的是，有序数据能将它的性能降低到O(N)级，不比一个链表好多少。然而如果可以保证数据是随机进入的，就不需要使用平衡二叉树。

 

12.1.5              平衡树

在众多平衡树中，我们讨论了红-黑树和2-3-4树，它们都是平衡树并且无论输入数据是否有序，它们都能保证性能为O(logN)。然而对于编程来说，这些平衡树都是很有挑战性的，其中最难的是红-黑树。它们也因为用了附加存储而产生额外消耗，对系统或多或少有些影响。

 

如果利用树的商用类可以降低编程的复杂性，有些情况下，选择哈希表比平衡树要好，即便当数据有序时，哈希表的性能也不降低。

12.1.6              哈希表

哈希表在数据存储结构中速度最快。哈希表通常用于拼写检查器和作为计算机编译器中的符号表，在这些应用中，程序必须在很短的时间内检查上千的词或符号。

 

哈希表对数据插入的顺序并不敏感，因此可以取代平衡树，但哈希表的编程却比平衡树简单多了。哈希表需要额外的存储空间，尤其是对于开放地址法。因为哈希表用数组作为存储结构，所以必须预先精确地知道待存储的数据量。

 

用链地址法处理冲突的哈希表是最健壮的解决方法.若能精确地知道数据量，在这种情况下用开放地址法编程最简单，因为不需要用到链表类。

 

哈希表并不能提供任何形式的有序遍历，或对最大最小值元素进行存取。如果这些功能重要的话，使用二叉搜索树更加合适。

 

 

12.2    专用的数据结构

12.2.1              栈

栈用在只对最后被插入数据项访问的时候，它是一个后进先出（LIFO）的结构。

 

栈往往通过数组或者链表实现，通过数组实现很有效率，因为最后被插入的数据总是在数组的最后，这个位置的数据很容易被删除。栈的溢出有可能出现，但当数组的大小被合理地规划好之后，溢出并不常见，因为栈很少会拥有大量的数据。

12.2.2              队列

队列用在只对最先被插入数据项访问的时候，它是一个先进先出（FIFO）的结构。

 

同栈相比，队列同样可以用数组和链表来实现。这两种方法都非常效率。数组需要附加的程序来处理队列在尾部回绕的情况。链表必须是双端的，这样才能从一端插入到另一端删除。用数组还是链表来实现队列的选择是通过数据量是否可以被很好地预测来决定的。如果知道有多少数据量的话，就是用数组；否则就使用链表。

12.2.3              优先级队列

优先级队列用在只对访问最高优先级数据项的时候有用，优先级队列可以用有序数组或堆来实现，向有序数组中插入数据是很慢的，但是删除很快。使用堆来实现优先级队列，插入和删除数据的时间复杂度均为O(logN)。 当插入速度不重要时，可以使用数组或双端链表。当数据量可以被预测时，使用数组；当数据量未知时，使用链表。如果速度很重要时，使用堆更好一些。

 

12.3    排序

当选择数据结构时，可以先尝试一种较慢但简单的排序，如插入排序。

 

插入排序对几乎已经已排好顺序的文件很有效，如果没有太多的元素处于乱序的位置上，操作的时间复杂度大约在O(N)级。

 

如果插入排序显得很慢，下一步可以尝试希尔排序。它很容易实现，并且使用起来不会因为条件不同而性能变化巨大。

 

只有当希尔排序变得很慢时，才应该选择那些更复杂但更快速的排序方法：归并排序、堆排序或快速排序。归并排序需要辅助存储空间，堆排序需要有一个堆的数据结构，前两者都比快速排序在某些程度上慢，所以当需要最短的排序时间时经常使用快速排序。

 

然而，快速排序在处理非随机顺序的数据时性能不太可靠，因为它的速度可能会蜕化成级。对于那些有可能是非随机性的数据来说，堆排更加可靠。

 


 
 

 

12.4    外部存储

前面的讨论都是假设数据被存放在了内存中，然而数据量大到内存中容不下时，只能被存到外部存储空间，它们被经常称为磁盘文件。

 

12.4.1              顺序存储

通过指定关键字进行搜索的最简单的方法是随机存储记录然后顺序读取。新的记录可以简单地插入在文件的最后，已删除的记录可以标记为已删除，或将记录顺次移动来填补空缺。

 

就平均而言，查找和删除会涉及读取半数的块，所以顺序存储并不是很快，时间复杂度为O(N)，但是对于小量数据来说它仍然是令人满意的。

12.4.2              索引文件

当使用索引文件时，速度会明显地提升。在这种方法中关键字的索引和相应块的号数被存放在内存中，当通过一个特殊的关键字访问一条记录时，程序会向索引询问。索引提供这个关键字的块号数，然后只需要读取这一个块，仅耗费O(1)级的时间。

 

可以使用不同种类的关键字来做多种索引，只要索引数量能在内存的存储范围之内，这种方法表现得很好；通常索引文件存储在磁盘中，只有在需要时才复制到内存中。

 

索引文件的缺点是必须先创建索引，这有可能对磁盘上的文件进行顺序读取，所以创建索引是很慢的。同样当记录被加入到文件中时索引还需要更新。

12.4.3              B-树

B-树是多叉树，通常用于外部存储，树中的节点对应于磁盘中的块。同其他树一样，通过算法来遍历树，在每一层上读取一个块。B-树可以在O(logN)级的时间内进行查找，插入和删除。这是相当快的，并且对于大文件也非常有效，但是它的编程很繁琐。

 

如果可以占用一个文件通常大小两倍以上的外部存储空间的话，外部哈希会是一个很好的选择。它同索引文件一样有着相同的存储时间O(1)，但它可以对更大的文件进行操作。

 

  

 

12.4.4              虚拟内存

有时候可以通过操作系统的虚拟内存能力来解决磁盘存取的问题，而不需要通过编程。

 

如果读取一个大小超过主存的文件，虚拟内存系统会读取合适主存大小的部分并将其它存储在磁盘上。当访问文件的不同部分时，它们会自动从磁盘读取并防止到内存中。

 

可以对整个文件使用内部存储的算法，使它们好像同时在内存中一样，当然，这样的操作比整个文件在内存中的速度要慢得多，但是通过外部存储算法一块块地处理文件的话，速度也是一样的慢。不要在乎文件的大小适合放在内存中，在虚拟内存的帮助下验证算法工作得好坏是有益的，尤其是对那些比可用内存大不了多少的文件来说，这是一个简单的解决方案。

 

 

评论

1 楼 ruize 2016-10-26  

首先，谢谢分享
其次，给博主一个建议，希望博主将以上程序测试运行成功后在发布，有些是存在错误的
再次，非常感谢分享，收货颇多！