查找（Search）就是根据给定的某个值，在查找表中确定个其关键字等于给定值的数据元素（或记录）。在计算机应中，查找是常的基本运算，例如编译程序中符号表的查找。先说明个概念：
由同类型的数据元素（或记录）构成的集合
数据元素中某个数据项的值，称为键值。
可唯地标识某个数据元素或记录的关键字。
需和指定key进较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找度。对于含有n个数据元素的查找表，查找成功的平均查找度为：ASL=PiCi的和。Pi：查找表中第i个数据元素的概率。Ci：找到第i个数据元素时已经较过的次数。
查找表按照操作式可分为：
1.静态查找表（StaticSearchTable）:
只做查找操作的查找表。它的主要操作是：
2.动态查找表（DynamicSearchTable）：
在查找的同时进插或删除等操作：查找时插数据；查找时删除数据按照查找表是否有序分为序查找和有序查找：序查找：被查找数列有序序均可；有序查找：被查找数列必须为有序数列。
、序表查找
1.说明：
顺序查找适合于存储结构为顺序存储或链接存储的线性表。
2.基本思想：
顺序查找也称为线形查找，属于序查找算法。从数据结构线形表的端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
3.算法分析：
三、有序表查找
查找表中的数据必须按照某个主键进某种排序！
3.1分查找
说明：元素必须是有序的，如果是序的则要先进排序操作。
基本思想：也称为折半查找，属于有序查找算法。给定值k先与中间结点的关键字较，中间结点把线性表分成两个表，若相等则查找成功；若不相等，再根据k与该中间节点关键字的较结果确定下步查找哪个字表，这样递归进，知道查找到或查找结束发现表中没有这样的结点。
注意：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，次排序后不再发变化，折半查找能得到不错的效率。但对于需要频繁执插或删除操作的数据集来说，维护有序的排序会带来不的作量，那就不建议使。
3.2插值查找
在介绍插值查找之前，先考虑个新问题，为什么上述算法定要是折半，不是折四分之或者折更多呢？打个，在英字典查“apple”，你下意识翻开字典是翻前的书还是后的书呢？如果再让你查“zoo”，你怎么查？很显然，这绝对不会是从中间开始查起，是有定的的往前或往后翻。同样的，如要在取值范围1~10000之间100个元素从到均匀分布的数组中查找5，我们然会从数组下标较的开始查找。经过上的分析，折半查找这种查找式，不是适应的（也就是说是傻式的）。分查找中查找点计算如下：
mid=(low+high)/2，即mid=low+(highlow)/2
通过类，我们可以将查找的点改进为如下：
也就是将上述的例参数1/2改进为适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了较次数。
基本思想：基于分查找算法，将查找点的选择改进为适应选择，可以提查找效率。当然，插值查找也属于有序查找。
注意：对于表较，关键字分布较均匀的查找表来说，插值查找算法的平均性能折半查找要好的多。反之，数组中如果分布常不均匀，那么插值查找未必是很合适的选择。
3.3斐波那契查找
在介绍斐波那契查找算法之前，我们先介绍下和它很紧密相连并且家都熟知的个概念——分割。例称为分割，是指事物各部分间定的数学例关系，即将整体分为，较部分与较部分之等于整体与较部分之，其值约为1：0.618。0.618倍公认为是最具有审美意义的例数字，这个数值的作不仅仅体现在诸如绘画、雕塑、乐、建筑等艺术领域，且在管理、程设计等有着不可忽视的作。因此被称为分割。家记不记得斐波那契数列：1，1，2，3，5，8，13，21，34，55，89......（从第三个数开始，后每个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的值会越来越接近0.618，利这个特性，我们就可以将例运到查找技术中。
基本思想：也是分查找的种提升算法，通过运例的概念在数列中选择查找点进查找，提查找效率。同样地，斐波那契查找也属于种有序查找算法。相对于折半查找，般将待较的key值与第mid=（low+high）/2位置的元素进较，较结果分为三种情况：
斐波那契查找和折半查找很相似，它是根据斐波那契序列的特点对有序表进分割的。他要求开始表中记录的个数为某个斐波那契1，即n=F(k)1开始将k值与第F(k-1)位置的记录进较（即mid=low+F(k-1)-1），较结果也分为三种
1.相等，mid位置的元素即为所求
2.大于，low=mid+1，k-=2：
说明：low=high+1说明待查找的元素在[mid+1,high]范围内，k-=2说明范围[mid,high]内的元素个数为n(F(k1))=Fk1F(k1)=FkF(k1)1=f(k2)1个，所以可以递归地应斐波那契查找。
3.小于，high=mid-1，k-=1:
说明：low=mid+1，说明待查找的元素在[0,mid+1]范围内，k-=1说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应斐波那契查找；
总结：分查找的mid运算是加法与除法，插值查找则是复杂的四则运算，斐波那契查找只是最简单的加减运算。在海量数据的查找中，这种细微的差别可能会影响最终的查找效率。因此，三种有序表的查找法本质上是分割点的选择不同，各有优劣，应根据实际情况进选择。
四、线性索引查找
对于海量的序数据，为了提查找速度，般会为其构造索引表。索引就是把个关键字与他相对应的记录进关联的过程。个索引由若个索引项构成，每个索引项少包含关键字和其对应的记录在存储器中的位置等信息。索引按照结构可以分为：线性索引、树形索引和多级索引。
线性索引：将索引项的集合通过线性结构来组织，也叫索引表；
线性索引可分为：稠密索引、分块索引和倒排索引。
指的是在线性索引中，为数据集合中的每个记录都建个索引项
这其实就相当于给序的集合，建了张有序的线性表，其索引项定是按照关键码进有序的排列。这也相当于把查找过程中需要的排序作给提前做了。
分块查找称索引顺序查找，是顺序查找的种改进法。
算法思想：将n个数据元素“按块有序”划分为m块（m 算法流程：先选取各块中的最关键字构成个索引表；查找分为两个部分：先对索引表进分查找或顺序查找，以确定待查记录在哪块中；然后，在已确定的块中顺序法进查找。 这其实是有序查找和序查找的种中间状态或者说妥协状态。因为数据量过，建完整的稠密索引耗时耗，占资源过多；但如果不做任何排序或索引，那么遍历的查找也法接受，只能这种，做定程度的排序或索引。分块索引的效率遍历查找的O(n)要些，但与分查找的O(logn)还是要差不少。 不是由记录来确定属性值，是由属性值来确定记录的位置，这种被称为倒排索引。其中记录号表存储具有相同关键字的所有记录的地址或引（可以是指向记录的指针或该记录的主关键字）。倒排索引是最基础的搜索引擎技术。 算法（二）：哈希表 、哈希表的基本概念 哈希表（HashTable）是种特殊的数据结构，它最的特点就是可以快速实现查找、插和删除。因为它独有的特点，Hash表经常被来解决数据问题，也因此被的程序员所睐。我们知道，数组的最特点就是：寻址容易，插和删除困难；链表正好相反，寻址困难，插和删除操作容易。那么如果能够结合两者的优点，做出种寻址、插和删除操作同样快速容易的数据结构，那该有多好。这就是哈希表创建的基本思想，实际上哈希表也实现了这样的个“夙愿”，哈希表就是这样个集查找、插和删除操作于身的数据结构。 也叫散列表，是根据关键码值（key-value）直接进访问的数据结构，也就是我们常到的map。 也称为是散列函数，是Hash表的映射函数，它可以把任意度的输变换成固定度的输出，该输出就是哈希值。哈希函数能使对个数据序列的访问过程变得更加迅速有效，通过哈希函数，数据元素能够被很快的进定位。 设计出个简单、均匀、存储利率的散列函数是散列技术中最关键的问题。但是，般散列函数都临着冲突的问题。两个不同的关键字，由于散列函数值相同，因被映射到同表位置上。该现象称为冲突(Collision)或碰撞。发冲突的两个关键字称为该散列函数的同义词(Synonym)。最理想的解决冲突的法是安全避免冲突。要做到这点必须满两个条件： 其是|U|≤m，其是选择合适的散列函数。 、哈希表的实现法 我们之前说了，哈希表是个集查找、插和删除操作于身的数据结构。那这么完美的数据结构到底是怎么实现的呢？哈希表有很多种不同的实现法，为了实现哈希表的创建，这些所有的法都离不开两个问题——“定址”和“解决冲突”。 在这，我们通过详细地介绍哈希表最常的法——取余法（定值）+拉链法（解决冲突），来起窥探下哈希表强的优点。取余法家定不会感觉陌，就是我们经常说的取余数的操作。拉链法是什么，“拉链”说了就是“链表数组”。啥是“链表数组”啊？为了更好地解释“链表数组”，我们下图进解释：图中的主部分是个顺序存储结构数组，但是有的数组元素为空，有的对应个值，有的对应的是个链表，这就是“链表数组”。如数组0的位置对应个链表，链表有两个元素“496”和“896”，这说明元素“496”和“896”有着同样的Hash地址，这就是我们上边介绍的“冲突”或者“碰撞”。但是“链表数组”的存储式很好地解决了Hash表中的冲突问题，发冲突的元素会被存在个对应Hash地址指向的链表中。实际上，“链表数组”就是个指针数组，每个指针指向个链表的头结点，链表可能为空，也可能不为空。 那我们就起看看Hash表是如何根据“取余法+拉链法”构建的吧。将所有关键字为同义词的结点链接在同个链表中。若选定的散列表度为m，则可将散列表定义为个由m个头指针组成的指针数组T[0..m1]。凡是散列地址为i的结点，均插到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因α可以于1，但般均取α≤1。 举例说明拉链法的执过程，设有组关键字为(26，36，41，38，44，15，68，12，6，51)，取余法构造散列函数，初始情况如下图所示： 最终结果如下图所示： 理解了Hash表的创建，那根据建的Hash表进查找就很容易被理解了。查找操作，如果理解了插和删除，查找操作就较简单了，令待查找的关键字是x，也可分为种情况： 1）x所属的Hash地址未被占，即不存在与x相同的Hash地址关键字，当然也不存在x了； 2）x所属的Hash地址被占了，但它所存的关键不属于这个Hash地址，与1）相同，不存在与x相同Hash地址的关键字； 3）x所属的Hash地址被占了，且它所存的关键属于这个Hash地址，即存在与x相同Hash地址的关键字，只是不知这个关键字是不是x，需要进步查找。由此可，Hash表插、删除和插操作的效率都相当的。 思考个问题： 如果关键字是字符串怎么办？我们怎么根据字符串建Hash表？通常都是将元素的key转换为数字进散列，如果key本身就是整数，那么散列函数可以采keymodtablesize（要保证tablesize是质数）。在实际作中经常字符串作为关键字，例如身姓名、职位等等。这个时候需要设计个好的散列函数进程处理关键字为字符串的元素。有以下种处理法： 法1：将字符串的所有的字符的ASCII码值进相加，将所得和作为元素的关键字。此法的缺点是不能有效的分布元素，例如假设关键字是有8个字构成的字符串，散列表的度为10007。字最的ASCII码为127，按照法1可得到关键字对应的最数值为127×8=1016，也就是说通过散列函数映射时只能映射到散列表的槽0-1016之间，这样导致部分槽没有到，分布不均匀，从效率低下。 法2：假设关键字少有三个字构成，散列函数只是取前三个字进散列。该法只是取字符串的前三个字符的ASCII码进散列，最的得到的数值是2851，如果散列的度为10007，那么只有28%的空间被到，部分空间没有到。因此如果散列表太，就不太适。 法3：借助Horner's规则，构造个质数（通常是37）的多项式，（常的巧妙，不知道为何是37）。计算公式为:key[keysizei1]37i,0≤i 三、哈希表定址与解决冲突 3.1哈希表“定址的法” 其实常的“定址”的法有“五种”： 1).直接定址法： 很容易理解，key=Value+C；这个“C"是常量。Value+C其实就是个简单的哈希函数。 2).除法取余法： key=value%C 3).数字分析法： 这种蛮有意思，如有组value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。 4).平取中法 5).折叠法： 3.2哈希表“解决冲突”的法 Hash表解决冲突的法主要有以下种： 1)链接地址法： 将哈希值相同的数据元素存放在个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采线性查找法。 2)开放定址法： 如果两个数据元素的哈希值相同，则在哈希表中为后插的数据元素另外选择个表项。当程序查找哈希表时，如果没有在第个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到个符合查找要求的数据元素，或者遇到个空的表项。线性探测带来的最问题就是冲突的堆积，你把别预定的坑占了，别也就要像你样去找坑。改进的办法有次探测法和随机数探测法。开放地址法包括线性探测、次探测以及双重散列等法。其中线性探测法示意图如下 散列过程如下图所示： 3)再散列函数法： 3.3哈希表“定址”和“解决冲突”之间的权衡 虽然哈希表是在关键字和存储位置之间建了对应关系，但是由于冲突的发，哈希表的查找仍然是个和关键字较的过程，不过哈希表平均查找度顺序查找要得多，分查找也。 查找过程中需和给定值进较的关键字个数取决于下列三个因素：哈希函数、处理冲突的法和哈希表的装填因。 哈希函数的"好坏"先影响出现冲突的频繁程度，但如果哈希函数是均匀的，则般不考虑它对平均查找度的影响。对同组关键字，设定相同的哈希函数，但使不同的冲突处理法，会得到不同的哈希表，它们的平均查找度也不同。般情况下，处理冲突法相同的哈希表，其平均查找度依赖于哈希表的装填因α。显然，α越，产冲突的机会就越；但α过，空间的浪费就过多。通过选择个合适的装填因α，可以将平均查找度限定在个范围内。总之，哈希表“定址”和“解决冲突”之间的权衡决定了哈希表的性能。 四、实现Hashmap 综上所述，我们对这个Hash容器的基本要求应该有如下点： 算法（三）：排序 、冒泡排序（BubbleSort） 1.1思想 冒泡排序(bubblesort)：每个回合都从第个元素开始和它后的元素较，如果它后的元素更的话就交换，直重复，直到这个元素到了它能到达的位置。每次遍历都将剩下的元素中最的那个放到了序列的“最后”(除去了前已经排好的那些元素)。注意检测是否已经完成了排序，如果已完成就可以退出了。 1.2代码 1.3时空复杂度 冒泡排序的关键字较次数与数据元素的初始状态关。第趟的较次数为n-1，第i趟的较次数为n-i，第n-1趟（最后趟）的较次数为1，因此冒泡排序总的较次数为n(n1)/2； 冒泡排序的数据元素移动次数与序列的初始状态有关。在最好的情况下，移动次数为0次；在最坏的情况下，移动次数为n(n1)/2； 、选择排序（SelectionSort） 2.1思想 每个回合都选择出剩下的元素中最的那个，选择的法是先默认第元素是最的，如果后的元素它的话，那就更新剩下的最的元素值，找到剩下元素中最的之后将它放到合适的位置就了。和冒泡排序类似，只是找剩下的元素中最的式不同已。 2.2代码 2.3时空复杂度 对具有n个数据元素的序列进排序时，选择排序需要进n1趟选择。进第i趟选择时，后已经有i1个数据元素排好序，第i趟从剩下的ni+1个数据元素中选择个关键字最的数据元素，并将它与第i个数据元素交换，这样即可使后的i个数据元素排好序。选择排序的关键字较次数与序列的初始状态关。对n个数据元素进排序时，第趟的较次数为n1，第i趟的较次数是n1次，第n1趟（最后趟）的较次数是1次。因此，总的较次数为n(n1)/2；选择排序每趟都可能移动次数据元素，其总的移动次数与序列的初始状态有关。当序列已经排好序时，元素的移动次数为0。当每趟都需要移动数据元素时，总的移动次数为n1; 三、插排序（InsertionSort） 3.1思想 对具有n个数据元素的序列进排序时，插排序需要进n1趟插。进第j（1≤j≤n1）趟插时，前已经有j个元素排好序了，第j趟将aj+1插到已经排好序的序列中，这样即可使前的j+1个数据排好序。 3.2代码 3.3时空复杂度 四、希尔排序（ShellSort） 4.1思想 希尔排序，也称递减增量排序算法，实质是分组插排序。由DonaldShell于1959年提出。希尔排序是稳定排序算法。希尔排序的基本思想是：将数组列在个表中并对列分别进插排序，重复这过程，不过每次更的列（步更了，列数更少了）来进。最后整个表就只有列了。将数组转换表是为了更好地理解这算法，算法本身还是使数组进排序。 例如，假设有这样组数[13149433822559946523452773253910]，如果我们以步为5开始进排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样： 然后我们对每列进排序： 将上述四数字，依序接在起时我们得到：[10147325231327943339255994658245]。这时10已经移正确位置了，然后再以3为步进排序： 排序之后变为： 最后以1步进排序（此时就是简单的插排序了）。 4.2代码 上源码的步的选择是从n/2开始，每次再减半，直为0。步的选择直接决定了希尔排序的复杂度。 五、归并排序（MergeSort） 5.1思想 典型的是路合并排序，将原始数据集分成两部分(不定能够均分)，分别对它们进排序，然后将排序后的数据集进合并，这是典型的分治法策略。 5.2代码 5.3时空复杂度 六、快速排序（QuickSort） 6.1思想 快速排序是图灵奖得主C.R.AHoare于1960年提出的种划分交换排序。它采了种分治的策略，通常称其为分治法（Divide-and-ConquerMethod）；分治法的基本思想：将原问题分解为若个规模更但结构与原问题相似的问题。递归地解这些问题，然后将这些问题组合为原问题的解。利分治法可将快速排序分为三步： 6.2代码 6.3时空复杂度 七、堆排序（HeapSort） 7.1思想 堆排序在topK问题中使较频繁。堆排序是采叉堆的数据结构来实现的，虽然实质上还是维数组。堆（叉堆）可以视为棵完全的叉树，完全叉树的个“优秀”的性质是，除了最底层之外，每层都是满的，这使得堆可以利数组来表示（普通的叉树通常链表作为基本容器表示），每个结点对应数组中的个元素。 如下图，是个堆和数组的相互关系 对于给定的某个结点的下标i，可以很容易的计算出这个结点的结点、孩结点的下标： 叉堆具有以下性质： 【提问】堆是怎么调整的，介绍顶堆和顶堆； 堆排序的原理如下： 步骤： 1）构造最堆（Build_Max_Heap）： 若数组下标范围为0~n，考虑到单独个元素是根堆，则从下标n/2开始的元素均为根堆。于是只要从n/2-1开始，向前依次构造根堆，这样就能保证，构造到某个节点时，它的左右树都已经是根堆。 2）堆排序（HeapSort）： 由于堆是数组模拟的。得到个根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最堆调整的递归运算。第次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最堆调整。第次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最堆调整。重复该操作直heap[0]和heap[1]交换。由于每次都是将最的数并到后的有序区间，故操作完后整个数组就是有序的了。 3）最堆调整（Max_Heapify）： 该法是提供给上述两个过程调的。的是将堆的末端节点作调整，使得节点永远于节点。 7.2代码 7.3时空复杂度 堆排序在建堆和调整堆的过程中会产较的开销，在元素少的时候并不适。但是，在元素较多的情况下，还是不错的个选择。尤其是在解决诸如“前n的数”类问题时，乎是选算法。 、桶排序 桶排序(Bucketsort)或所谓的箱排序的原理是将数组分到有限数量的桶，然后对每个桶再分别排序（有可能再使别的排序算法或是以递归式继续使桶排序进排序），最后将各个桶中的数据有序的合并起来。排序过程： 设有数组array=[29,25,3,49,9,37,21,43]，那么数组中最数为49，先设置5个桶，那么每个桶可存放数的范围为：0~9、10~19、20~29、30~39、40~49，然后分别将这些数放所属的桶，如下图： 然后，分别对每个桶的数进排序，或者在将数放桶的同时插排序进排序。最后，将各个桶中的数据有序的合并起来，如下图： 九、各种排序法的时空复杂度 算法（四）：深度优先搜索和度优先搜索 BFS和DFS是两种分重要的搜索算法，BFS适合查找最优解，DFS适合查找是否存在解(或者说能找到任意个可解)。这两种算法即可以解决部分树和图的问题。 、深度优先搜索（DFS） 1.1介绍 图的深度优先搜索（DepthFirstSearch），和树的先序遍历较类似。它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点V出发，先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直图中所有和V有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选个未被访问的顶点作起始点，重复上述过程，直图中所有顶点都被访问到为。显然，深度优先搜索是个递归的过程。 1.2图解 1.2.1向图的深度优先搜索 下以“向图”为例，来对深度优先搜索进演示。 对上的图G1进深度优先遍历，从顶点A开始。 第1步：访问A 第2步：访问（A的邻接点）C。在第步访问A之后，接下来应该访问的是A的邻接点，即“C/D/F”中的个。但在本的实现中，顶点ABCDEFG是按照顺序存储，C在“D和F的前，因此，先访问C。” 第3步：访问（C的邻接点）B。在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中个(A已经被访问过，就不算在内)。由于B在D之前，先访问B。 第4步：访问(C的邻接点)D。在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另个邻接点D。 第5步：访问(A的邻接点)F。前已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另个邻接点F。 第6步：访问(F的邻接点)G。 第7步：访问(G的邻接点)E。 因此访问顺序是：。A=>C=>=>B=>D=>F=>G=>E 1.2.2有向图的深度优先搜索 下以“有向图”为例，来对深度优先搜索进演示 对上的图G2进深度优先遍历，从顶点A开始。 第1步：访问A。 第2步：访问B。在访问了A之后，接下来应该访问的是A的出边的另个顶点，即顶点B。 第3步：访问C。在访问了B之后，接下来应该访问的是B的出边的另个顶点，即顶点C,E,F。在本实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。 第4步：访问E。接下来访问C的出边的另个顶点，即顶点E。 第5步：访问D。接下来访问E的出边的另个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。 第6步：访问F。接下应该回溯"访问A的出边的另个顶点F"。 第7步：访问G。 因此访问顺序是：A=>B=>C=>E=>D=>F=>G 、度优先搜索（BFS） 2.1介绍 度优先搜索算法（BreadthFirstSearch），称为“宽度优先搜索”或“横向优先搜索”，简称BFS。它的思想是：从图中某顶点V出发，在访问了V之后依次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问”，直图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选个未曾被访问的顶点作为新的起始点，重复上述过程，知道图中所有顶点都被访问到为。换句话说，度优先搜索遍历图的过程是以V为起点，由近远，依次访问和V有路径相同且路径度为1、2、3......的顶点。 2.2图解 2.2.1向图的度优先搜索 下以“向图”为例，来对度优先搜索进演示。还是以上的图G1为例进说明。 第2步：依次访问C,D,F。在访问了A之后，接下来访问A的邻接点。前已经说过，在本实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前，因此，先访问C。再访问完C之后，再依次访问D,F。 第3步：依次访问B,G。在第2步访问完C,D,F之后，再依次访问它们的邻接点。先访问C的邻接点B，再访问F的邻接点G。 第4步：访问E。在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。 因此访问顺序是：A=>C=>D=>F=>B=>G=>E 2.2.2有向图的度优先搜索 下以“有向图”为例，来对度优先搜索进演示。还是以上的图G2为例进说明。 第2步：访问B。 第3步：依次访问C,E,F。在访问了B之后，接下来访问B的出边的另个顶点，即C,E,F。前已经说过，在本实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。 第4步：依次访问D,G。在访问完C,E,F之后，再依次访问它们的出边的另个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。 因此访问顺序是：A=>B=>C=>E=>F=>D=>G 算法（五）：最短路算法 最短路径问题是图论研究中的个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题-即已知起始结点，求最短路径的问题。适合使Dijkstra算法。确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径向反转的确定起点的问题。确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。全局最短路径问题-求图中所有的最短路径。适合使Floyd-Warshall算法。 、Dijkstra算法 1.1算法思想 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，于计算个节点到其他所有节点的最短路径。主要特点是以起始点为中向外层扩展，直到扩展到终点为。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描述： 在向图G=(V,E)中，假设每条边E[i]的度为w[i]，找到由顶点V0到其余各点的最短路径。（单源最短路径）算法思想：设G=(V,E)是个带权有向图，把图中顶点集合V分成两组，第组为已求出最短路径的顶点集合（S表示，初始时S中只有个源点，以后每求得条最短路径,就将加到集合S中，直到全部顶点都加到S中，算法就结束了），第组为其余未确定最短路径的顶点集合（U表示），按最短路径度的递增次序依次把第组的顶点加S中。在加的过程中，总保持从源点v到S中各顶点的最短路径度不于从源点v到U中任何顶点的最短路径度。此外，每个顶点对应个距离，S中的顶点的距离就是从v到此顶点的最短路径度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径度。 适条件与限制： 有向图和向图都可以使本算法，向图中的每条边可以看成相反的两条边。来求最短路的图中不能存在负权边。(可以利拓扑排序检测) 1.2算法步骤 Dijkstra算法找出以A为起点的单源最短路径步骤如下 1.3代码实现 以"邻接矩阵"为例对迪杰斯特拉算法进说明。 MatrixUDG是邻接矩阵对应的结构体。mVexs于保存顶点，mEdgNum于保存边数，mMatrix则是于保存矩阵信息的维数组。例如，mMatrix[i][j]=1，则表示"顶点i(即mVexs[i])"和"顶点j(即mVexs[j])"是邻接点；mMatrix[i][j]=0，则表示它们不是邻接点。 、Floyd算法 Dijkstra很优秀，但是使Dijkstra有个最的限制，就是不能有负权边。Bellman-Ford适于权值可以为负、权值为负的回路的图。这Dijkstra算法的使范围要。 2.1算法思想 Floyd算法是个经典的动态规划算法。通俗的语来描述的话，先我们的标是寻找从点i到点j的最短路径。从动态规划的度看问题，我们需要为这个标重新做个诠释（这个诠释正是动态规划最富创造的精华所在）；从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每个节点k，我们检查Dis(i,k)+Dis(k,j) 2.2算法步骤 初始状态：S是记录各个顶点间最短路径的矩阵。 2.3代码实现 以"邻接矩阵"为例对弗洛伊德算法进说明，对于"邻接表"实现的图在后会给出相应的源码。 算法（六）：布隆过滤器 、引 、常规思路与局限 如果想判断个元素是不是在个集合，般想到的是将集合中所有元素保存起来，然后通过较确定。链表、树、散列表（叫哈希表，Hashtable）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越。同时检索速度也越来越慢。数组链表树、平衡叉树、TrieMap(红树)哈希表；虽然上描述的这种数据结构配合常的排序、分搜索可以快速效的处理绝部分判断元素是否存在集合中的需求。但是当集合的元素数量够，如果有500万条记录甚1亿条记录呢？这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容，旦数据量过，消耗的内存也会呈现线性增，最终达到瓶颈。有的同学可能会问，哈希表不是效率很吗？查询效率可以达到O(1)。但是哈希表需要消耗的内存依然很。使哈希表存储亿个垃圾email地址的消耗？哈希表的做法：先，哈希函数将个email地址映射成8字节信息指纹；考虑到哈希表存储效率通常于50%（哈希冲突）；因此消耗的内存：8*2*1亿字节=1.6G内存，普通计算机是法提供如此的内存。这个时候，布隆过滤器（BloomFilter）就应运。 三、哈希函数 哈希函数的概念是：将任意的数据转换成特定的数据的函数，转换后的数据称为哈希值或哈希编码。个应是Hashtable（散列表，也叫哈希表），是根据哈希值(Keyvalue)直接进访问的数据结构。也就是说，它通过把哈希值映射到表中个位置来访问记录，以加快查找的速度。下是个典型的hash函数/表示意图： 可以明显的看到，原始数据经过哈希函数的映射后成为了个个的哈希编码，数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。哈希函数有以下两个特点： 缺点：哈希表的空间效率还是不够。如果哈希表存储亿个垃圾邮件地址，每个email地址对应8bytes,哈希表的存储效率般只有50%，因此个email地址需要占16bytes.因此亿个email地址占1.6GB，如果存储亿个emailaddress则需要上百GB的内存。除是超级计算机，般的服务器是法存储的。所以要引下的BloomFilter。 四、布隆过滤器（BloomFilter） 4.1原理 布隆过滤器（BloomFilter）的核实现是个超的位数组和个哈希函数。假设位数组的度为m，哈希函数的个数为k 以上图为例，具体的操作流程： 假设集合有3个元素{x,y,z}，哈希函数的个数为3。先将位数组进初始化，将每个位都设置为0。对于集合的每个元素，将元素依次通过3个哈希函数进映射，每次映射都会产个哈希值，这个值对应位数组上的个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的法将W通过哈希映射到位数组上的3个点。如果3个点的其中有个点不为1，则可以判断该元素定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。 注意：此处不能判断该元素是否定存在集合中，可能存在定的误判率。从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。 4.2添加与查询 1)布隆过滤器添加元素 将要添加的元素给k个哈希函数； 得到对应于位数组上的k个位置； 将这k个位置设为1； 2)布隆过滤器查询元素 将要查询的元素给k个哈希函数；得到对应于位数组上的k个位置； 如果k个位置有个为0，则肯定不在集合中； 如果k个位置全部为1，则可能在集合中； 4.3优点 4.4缺点 但是布隆过滤器的缺点和优点样明显。误算率是其中之。随着存的元素数量增加，误算率随之增加。但是如果元素数量太少，则使散列表矣。误判补救法是：再建个的名单，存储那些可能被误判的信息。另外，般情况下不能从布隆过滤器中删除元素.我们很容易想到把位数组变成整数数组，每插个元素相应的计数器加1,这样删除元素时将计数器减掉就可以了。然要保证安全地删除元素并非如此简单。先我们必须保证删除的元素的确在布隆过滤器.这点单凭这个过滤器是法保证的。另外计数器回绕也会造成问题。 4.5实例 可以快速且空间效率的判断个元素是否属于个集合； 来实现数据字典，或者集合求交集。 算法（七）：致性哈希 、Hash算法 致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义： 假设个简单的场景： 有4个cache服务器（后简称cache）组成的集群，当个对象object传集群时，这个对象应该存储在哪个cache呢？ 种简单的法是使映射公式：Hash(object)%4； 这个算法就可以保证任何object都会尽可能随机落在其中个cache中。切运正常。然后考虑以下情况：由于流量增，需要增加台cache，共5个cache。这时，映射公式就变成Hash(object)%5。有个cache服务器down掉，变成3个cache。这时，映射公式就变成Hash(object)%3。 、致性Hash算法 2.1环形Hash空间 按照常的hash算法来将对应的key哈希到个具有2^32次个桶的空间中，即$0$(2{32})-1的数字空间中。现在我们可以将这些数字头尾相连，想象成个闭合的环形。如下图 2.2数据映射 现在我们将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值，然后散列到Hash环上。如下图： 2.3机器映射 在采致性哈希算法的分布式集群中将新的机器加，其原理是通过使与对象存储样的Hash算法将机器也映射到环中（般情况下对机器的hash计算是采机器的IP或者机器唯的别名作为输值），然后以顺时针的向计算，将所有对象存储到离最近的机器中。假设现在有NODE1，NODE2，NODE3三台机器，通过Hash算法得到对应的KEY值，映射到环中，其示意图如下： 通过上图可以看出对象与机器处于同哈希空间中，这样按顺时针转动object1存储到了NODE1中，object3存储到了NODE2中，object2、object4存储到了NODE3中。在这样的部署环境中，hash环是不会变更的，因此，通过算出对象的hash值就能快速的定位到对应的机器中，这样就能找到对象真正的存储位置了。 2.4机器的删除与添加 普通hash求余算法最为不妥的地就是在有机器的添加或者删除之后会照成量的对象存储位置失效，这样就的不满单调性了。下来分析下致性哈希算法是如何处理的。 2.4.1节点（机器）的删除 以上的分布为例，如果NODE2出现故障被删除了，那么按照顺时针迁移的法，object3将会被迁移到NODE3中，这样仅仅是object3的映射位置发了变化，其它的对象没有任何的改动。如下图： 2.4.2节点（机器）的添加 如果往集群中添加个新的节点NODE4，通过对应的哈希算法得到KEY4，并映射到环中，如下图： 通过按顺时针迁移的规则，那么object2被迁移到了NODE4中，其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析，致性哈希算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说是常合适的，避免了量数据迁移，减小了服务器的的压。 2.5平衡性 根据上的图解分析，致性哈希算法满了单调性和负载均衡的特性以及般hash算法的分散性，但这还并不能当做其被泛应的原由，因为还缺少了平衡性。下将分析致性哈希算法是如何满平衡性的。hash算法是不保证平衡的，如上只部署了NODE1和NODE3的情况（NODE2被删除的图），object1存储到了NODE1中，object2、object3、object4都存储到了NODE3中，这样就照成了常不平衡的状态。 2.6虚拟节点 其实，理论上，只要cache够多，每个cache在圆环上就会够分散。但是在真实场景，cache服务器只会有很少，所以，在致性哈希算法中，为了尽可能的满平衡性，其引了虚拟节点的概念。“虚拟节点”（virtualnode）是实际节点（机器）在hash空间的复制品（replica），个实际节点（机器）对应了若个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在hash空间中以hash值排列。以上只部署了NODE1和NODE3的情况（NODE2被删除的图）为例，之前的对象在机器上的分布很不均衡，现在我们以2个副本（复制个数）为例，这样整个hash环中就存在了4个虚拟节点，最后对象映射的关系图如下： 根据上图可知对象的映射关系： 通过虚拟节点的引，对象的分布就较均衡了。那么在实际操作中，真正的对象查询是如何作的呢？对象从hash到虚拟节点到实际节点的转换如下图： “虚拟节点”的hash计算可以采对应节点的IP地址加数字后缀的式。 例如假设NODE1的IP地址为192.168.1.100。 引“虚拟节点”前，计算cacheA的hash值： Hash(“192.168.1.100”); 引“虚拟节点”后，计算“虚拟节”点NODE1-1和NODE1-2的hash值：Hash(“192.168.1.100#1”);//NODE1-1 Hash(“192.168.1.100#2”);//NODE1-2 算法（八）：simhash 随着信息爆炸时代的来临，互联上充斥着着量的近重复信息，有效地识别它们是个很有意义的课题。例如，对于搜索引擎的爬系统来说，收录重复的是毫意义的，只会造成存储和计算资源的浪费；同时，展示重复的信息对于户来说也并不是最好的体验。造成近重复的可能原因主要包括：镜像站；内容复制；嵌告；计数改变；少量修改； 个简化的爬系统架构如下图所示： 事实上，传统较两个本相似性的法，多是将本分词之后，转化为特征向量距离的度量，如常的欧距离、海明距离或者余弦度等等。两两较固然能很好地适应，但这种法的个最的缺点就是，法将其扩展到海量数据。例如，试想像Google那种收录了数以亿互联信息的型搜索引擎，每天都会通过爬的式为的索引库新增数百万，如果待收录每条数据都去和库的每条记录算下余弦度，其计算量是相当恐怖的。我们考虑采为每个web档通过hash的式成个指纹（fifingerprint）。传统的加密式hash，如md5，其设计的的是为了让整个分布尽可能地均匀，输内容哪怕只有轻微变化，hash就会发很地变化。我们理想当中的哈希函数，需要对乎相同的输内容，产相同或者相近的hashcode，换句话说，hashcode的相似程度要能直接反映输内容的相似程度。很明显，前所说的md5等传统hash法满我们的需求。、simhash的原理 simhash是localitysensitivehash（局部敏感哈希）的种。Google就是基于此算法实现件查重的。simhash算法的主要思想是降维，将维的特征向量映射成个f-bit的指纹(fifingerprint)，通过较两篇章的f-bit指纹的HammingDistance来确定章是否重复或者度近似。 我们假设有以下三段本： 使传统hash可能会产如下的结果： 使simhash会应该产类似如下的结果: 海明距离的定义，为两个进制串中不同位的数量。上述三个本的simhash结果，其两两之间的海明距离为(p1,p2)=4，(p1,p3)=16以及(p2,p3)=12。事实上，这正好符合本之间的相似度，p1和p2间的相似度要远于与p3的。如何实现这种hash算法呢？图解如下： 算法过程概如下： 三、海明距离 当我们算出所有doc的simhash值之后，需要计算docA和docB之间是否相似的条件是：A和B的海明距离是否于等于n，这个n值根据经验般取值为3,那海明距离怎么计算呢？进制串A和进制串B的海明距离就是AxorB后进制中1的个数。 simhash本质上是局部敏感性的hash，和md5之类的不样。正因为它的局部敏感性，所以我们可以使海明距离来衡量simhash值的相似度。 算法（九）：倒排索引 、倒排索引 倒排索引（invertedindex），也常被称为反向索引、置档案或反向档案，是种索引法，被来存储在全搜索下某个单词在个档或组档中存储位置的映射。它是档检索系统中最常的数据结构。有两种不同的倒排索引形式： 我们就能得到下的反向件索引： 检索的条件"what","is"和"it"将对应这个集合：{0,1}∩{0,1,2}∩{0,1,2}={0,1}； 对相同的字，我们得到后这些完全反向索引，有档数量和当前查询的单词结果组成的成对数据。同样，档数量和当前查询的单词结果都从零开始。所以，"banana":{(2,3)}就是说"banana"在第三个档T2，且在第三个档的位置是第四个单词(地址为3)。 如果我们执短语搜索"whatisit"我们得到这个短语的全部单词各的结果所在档为档0和档1。但是这个短语检索的连续的条件仅仅在档1得到。有了这个索引系统，搜索引擎可以很便地响应户的查询，如户输查询词“banana”，搜索系统查找倒排索引，从中可以读出包含这个单词的档，这些档就是提供给户的搜索结果，利单词频率信息、档频率信息即可以对这些候选搜索结果进排序，计算档和查询的相似性，按照相似性得分由到低排序输出，此即为搜索系统的部分内部流程。 、单词词典 2.1哈希加链表 这种词典结构主要由两个部分构成：主体部分是哈希每个哈希表项保存个指针，指针指向冲突链表，在冲突链表，相同哈希值的单词形成链表结构。之所以会有冲突链表，是因为两个不同单词获得相同的哈希值，如果是这样，在哈希法被称做是次冲突，可以将相同哈希值的单词存储在链表，以供后续查找。 在建索引的过程中，词典结构也会相应地被构建出来。如在解析个新档的时候，对于某个在档中出现的单词T，先利哈希函数获得其哈希值，之后根据哈希值对应的哈希表项读取其中保存的指针，就找到了对应的冲突链表。如果冲突链表已经存在这个单词，说明单词在之前解析的档已经出现过。如果在冲突链表没有发现这个单词，说明该单词是次碰到，则将其加冲突链表。通过这种式，当档集合内所有档解析完毕时，相应的词典结构也就建起来了。在响应户查询请求时，其过程与建词典类似，不同点在于即使词典没出现过某个单词，也不会添加到词典内。 以图1-7为例，假设户输的查询请求为单词3，对这个单词进哈希，定位到哈希表内的2号槽，从其保留的指针可以获得冲突链表，依次将单词3和冲突链表内的单词较，发现单词3在冲突链表内，于是找到这个单词，之后可以读出这个单词对应的倒排列表来进后续的作，如果没有找到这个单词，说明档集合内没有任何档包含单词，则搜索结果为空 2.2树形结构 B树（或者B+树）是另外种效查找结构，如图是个B树结构示意图。B树与哈希式查找不同，需要字典项能够按照排序（数字或者字符序），哈希式则须数据满此项要求。B树形成了层级查找结构，中间节点于指出定顺序范围的词典项存储在哪个树中，起到根据词典项较进导航的作，最底层的叶节点存储单词的地址信息，根据这个地址就可以提取出单词字符串。 算法（十）：海量数据处理 、何谓海量数据处理？ 、从Set、Map谈到hashtable、hash_map/hash_set 般来说，STL容器分为两种 所谓关联式容器，类似关联式数据库，每笔数据或每个元素都有个键值（key）和个实值（value），即所谓的Key-Value（键-值对）。当元素被插到关联式容器中时，容器内结构（RB-Tree、hashtable）便依照其键值，以某种特定规则将这个元素放置于适当位置。包括在关联式数据库中，如，在MongoDB内，档（document）是最基本的数据组织形式，每个档也是以Key-Value(键-值对)的式组织起来。个档可以有多个Key-Value组合，每个Value可以是不同的类型，如String、Integer、List等等。"name":"July","Sex":"male","age":23； 2.1关联式容器之集合：set/map/multimap/multimap set，同map样，所有元素都会根据元素的键值动被排序，因为set、map两者的所有操作，都是调RB-tree的操作为，不过，值得注意的是，两者都不允许两个元素有相同的键值。不同的是，set的元素不像map那样可以同时拥有实值（value）和键值（key），set元素的键值就是实值，实值就是键值，map的所有元素都是pair，同时拥有实值（value）和键值（key），pair的第个元素被视为键值，第个元素被视为实值。于multiset、multimap，他们的特性及法和set、map完全相同，唯的差别就在于它们允许键值重复，即所有的插操作基于RB-tree的insert_equal()insert_unique()。 2.2关联式容器之映射表：hash_set/hash_map/hash_multiset/hash_multimap hash_set/hash_map，两者的切操作都是基于hashtable之上。hash_set同set样，同时拥有实值和键值，且实值就是键值，键值就是实值，hash_map同map样，每个元素同时拥有个实值(value)和个键值(key)，所以其使式，和上的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不具备动排序功能。为什么因为hashtable没有动排序功能。于hash_multiset/hash_multimap的特性与上的multiset/multimap完全相同，唯的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable（multiset/multimap，上说了，底层实现机制是RB-tree），所以它们的元素都不会被动排序，不过也都允许键值重复。 所以，综上，说了，什么样的结构决定其什么样的性质，因为set/map/multiset/multimap都是基于RB-tree之上，所以有动排序功能，hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有动排序功能，于加个前缀multi_就是允许键值重复已。 三、处理海量数据问题之六把密钥 (1)海量志数据，提取出某访问 既然是海量数据处理，那么可想知，给我们的数据那就定是海量的。针对这个数据的海量，我们如何着呢对的，就是分治之/hash映射+hash统计+堆/快速/归并排序，说了，就是先映射，后统计，最后排序： 1.分治之/hash映射：针对数据太，内存受限，只能是：把件化成(取模映射)件，即16字针：化，各个击破，缩规模，逐个解决2.hash统计：当件转化了件，那么我们便可以采常规的Hashmap(ip，value)来进频率统计。 3.堆/快速排序：统计完了之后，便进排序(可采取堆排序)，得到次数最多的IP； 具体论，“先是这天，并且是访问百度的志的IP取出来，逐个写到个件中。注意到IP是32位的，最多有2^32个IP。同样可以采映射的法，如%1000，把整个件映射为1000个件，再找出每个件中出现频率最的IP（可以采Hash_map对那1000个件中的所以IP进频率统计，然后依次找出各个件中频率最的那个IP）及相应的频率。然后再在这1000个最的IP中，找出那个频率最的IP，即为所求。 (3)有个1G的件，每是个词，词的不超过16字节，内存限制时1M。返回频数最的100个词。 由上那两个例题，分治之+hash统计+堆/快速排序这个套路，我们已经开始有了屡试不爽的感觉。下，再拿道再多多验证下。请看此第3题：是件很，是内存受限，咋办还能怎么办呢还是： 1.分治之/hash映射：顺序读件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个件（记为x0,x1,…x4999）中。这样每个件概是200k左右。如果其中的有的件超过了1M，还可以按照类似的法继续往下分，直到分解得到的件的都不超过1M。 2.hash统计：对每个件，采trie树、hash——map等统计每个件中出现的词以及相应的频率。 3.堆、归并排序：取出出现频率最的100个词（可以含100个结点的最堆），并把100个词及相应的频率存件，这样得到了5000个件。最后就是把这5000个件进归并（类似于归并排序）的过程了。 (4)海量数据分布在100台电脑中，想个办法效统计出这批数据的TOP10。如果每个数据元素只出现次，且只出现在某台机器中，那么可以采取以下步骤统计出现次数TOP10的数据元素： 1.堆排序：在每台电脑上求出TOP10，可以采包含10个元素的堆完成（TOP10，最堆，TOP10，最堆，如求TOP10，我们先取前10个元素调整成最堆，如果发现，然后扫描后的数据，并与堆顶元素较，如果堆顶元素，那么该元素替换堆顶，然后再调整为最堆。最后堆中的元素就是TOP10）。 2.求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利上类似的法求出TOP10就可以了。但如果同个元素重复出现在不同的电脑中呢，如下例所述：就拿2台机器求top2的情况来说，第台：a(50)、b(50)、c(49)、d(49)、e(0)、e(0)，第台：a(0)、b(0)、c(49)、d(49)、e(50)、f(50)，这个时候，你可以有两种法： i.遍历遍所有数据，重新hash取摸，如此使得同个元素只出现在单独的台电脑中，然后采上所说的法，统计每台电脑中各个元素的出现次数找出TOP10，继组合100台电脑上的TOP10，找出最终的TOP10。 ii.暴求解：直接统计统计每台电脑中各个元素的出现次数，然后把同个元素在不同机器中的出现次数相加，最终从所有数据中找出TOP10。 (5)有10个件，每个件1G，每个件的每存放的都是户的query，每个件的query都可能重复。要求你按照query的频度排序。 1.hash映射：顺序读取10个件，按照hash(query)%10的结果将query写到另外10个件（记为）中。这样新成的件每个的约也1G（假设hash函数是随机的）。 2.hash统计：找台内存在2G左右的机器，依次对hash_map(query,query_count)来统计每个query出现的次数。注：hash_map(query,query_count)是来统计每个query的出现次数，不是存储他们的值，出现次，则count+1。 3.堆/快速/归并排序：利快速/堆/归并排序按照出现次数进排序。将排序好的query和对应的query_cout输出到件中。这样得到了10个排好序的件。对这10个件进归并排序（内排序与外排序相结合）。除此之外，此题还有以下两个法： 1.般query的总量是有限的，只是重复的次数较多已，可能对于所有的query，次性就可以加到内存了。这样，我们就可以采trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。 2.与案1类似，但在做完hash，分成多个件后，可以交给多个件来处理，采分布式的架构来处理（如MapReduce），最后再进合并。 其实本质上还是分治之的思想，重在“分”的技巧上！适范围：第k，中位数，不重复或重复的数字基本原理及要点：因为元素范围很，不能利直接寻址表，所以通过多次划分，逐步确定范围，然后最后在个可以接受的范围内进。可以通过多次缩，双层只是个例。 (1)2.5亿个整数中找出不重复的整数的个数，内存空间不以容纳这2.5亿个整数。有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为28个区域(如单个件代表个区域)，然后将数据分离到不同的区域，然后不同的区域在利bitmap就可以直接解决了。也就是说只要有够的磁盘空间，就可以很便的解决。 (2)5亿个int找它们的中位数。 这个例上那个更明显。先我们将int划分为2^16个区域，然后读取数据统计落到各个区域的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第数刚好是中位数。然后第次扫描我们只统计落在这个区域中的那些数就可以了。实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第数，在将该区域分成2^20个区域，然后确定是区域的第数，然后区域的数的个数只有2^20，就可以直接利directaddrtable进统计了。 适范围：可以来实现数据字典，进数据的判重，或者集合求交集; 基本原理及要点：对于原理来说很简单，位数组+k个独hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不持删除个已经插的关键字，因为该关键字对应的位会牵动到其他的关键字。所以个简单的改进就是countingBloomfifilter，个counter数组代替位数组，就可以持删除了。还有个较重要的问题，如何根据输元素个数n，确定位数组m的及hash函数个数。当hash函数个数k=(ln2)(m/n)时错误率最。在错误率不于E的情况下，m少要等于才能表示任意n个元素的集合。但m还应该更些，因为还要保证bit数组少半为0，则m>=nlg(1/E)lge概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。举个例我们假设错误率为0.01，则此时m应概是n的13倍。这样k概是8个。注意这m与n的单位不同，m是bit为单位，n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的度都是有很多bit的。所以使bloomfifilter内存上通常都是节省的。 扩展：Bloomfifilter将集合中的元素映射到位数组中，k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Countingbloomfifilter（CBF）将位数组中的每位扩展为个counter，从持了元素的删除操作。SpectralBloomFilter（SBF）将其与集合元素的出现次数关联。SBF采counter中的最值来近似表示元素的出现频率。 附：Bitmap介绍 所谓的Bit-map就是个bit位来标记某个元素对应的Value，Key即是该元素。由于采了Bit为单位来存储数据，因此在存储空间，可以节省。如果说了这么多还没明什么是Bit-map，那么我们来看个具体的例，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这假设这些元素没有重复）。那么我们就可以采Bit-map的法来达到排序的的。要表示8个数，我们就只需要8个Bit（1Bytes），先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，如下图 然后遍历这5个元素，先第个元素是4，那么就把4对应的位置为1（可以这样操作p+(i/8)|(0×01<<(i%8))当然了这的操作涉及到Big-ending和Little-ending的情况，这默认为Big-ending）,因为是从零开始的，所以要把第五位置为，如下图： 然后再处理第个元素7，将第位置为1,，接着再处理第三个元素，直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下： 然后我们现在遍历遍Bit区域，将该位是的位的编号输出（2，3，4，5，7），这样就达到了排序的的。 可进数据的快速查找，判重，删除，般来说数据范围是int的10倍以下。问题实例1: 在2.5亿个整数中找出不重复的整数，注，内存不以容纳这2.5亿个整数。案1：采2-Bitmap（每个数分配2bit，00表示不存在，01表示出现次，10表示多次，11意义）进，共需内存2^32*2bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。 案2：也可采与第1题类似的法，进划分件的法。然后在件中找出不重复的整数，并排序。然后再进归并，注意去除重复的元素。 问题实例2: 给40亿个不重复的unsignedint的整数，没排过序的，然后再给个数，如何快速判断这个数是否在那40亿个数当中？ 案1：位图/Bitmap的法，申请512M的内存，个bit位代表个unsignedint值。读40亿个数，设置相应的bit位，读要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。 1）Trie树 适范围：数据量，重复多，但是数据种类，可以放内存; 基本原理及要点：实现式，节点孩的表示式 扩展：压缩实现 问题实例 2）数据库索引 适范围：数据量的增删改查 基本原理及要点：利数据的设计实现法，对海量数据的增删改查进处理； 3）倒排索引(Invertedindex) 适范围：搜索引擎，关键字查询 基本原理及要点：为何叫倒排索引？种索引法，被来存储在全搜索下某个单词在个档或者组档中的存储位置的映射。 适范围：数据的排序，去重; 基本原理及要点：外排序的归并法，置换选择败者树原理，最优归并树; 适范围：数据量，但是数据种类可以放内存 基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。 问题实例: 算法（十一）：总结 AVL树是平衡二叉查找树，增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中心，将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转。同理左旋是以某个节点为中心，将它沉入当前左子节点的位置，而让当前的右子节点作为新树的根节点，也称为逆时针旋转。 红黑树在本质上还是二叉查找树，它额外引入了5个约束条件： ①节点只能是红色或黑色。 ②根节点必须是黑色。 ③所有NIL节点都是黑色的。 ④一条路径上不能出现相邻的两个红色节点。 ⑤在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。 红黑树的平衡性不如AVL树，它维持的只是一种大致的平衡，不严格保证左右子树的高度差不超过1。这导致节点数相同的情况下，红黑树的高度可能更高，也就是说平均查找次数会高于相同情况的AVL树。 B树中每个节点同时存储key和data，而B+树中只有叶子节点才存储data，非叶子节点只存储key。InnoDB对B+树进行了优化，在每个叶子节点上增加了一个指向相邻叶子节点的链表指针，形成了带有顺序指针的B+树，提高区间访问的性能。 B+树的优点在于： ①由于B+树在非叶子节点上不含数据信息，因此在内存页中能够存放更多的key，数据存放得更加紧密，具有更好的空间利用率，访问叶子节点上关联的数据也具有更好的缓存命中率。 ②B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而B树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。但是B树也有优点，由于每个节点都包含key和value，因此经常访问的元素可能离根节点更近，访问也更迅速。 排序可以分为内部排序和外部排序，在内存中进行的称为内部排序，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序。 内部排序包括比较排序和非比较排序，比较排序包括插入/选择/交换/归并排序，非比较排序包括计数/基数/桶排序。 插入排序包括直接插入/希尔排序，选择排序包括直接选择/堆排序，交换排序包括冒泡/快速排序。 每一趟将一个待排序记录按其关键字的大小插入到已排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。 publicvoidinsertionSort(int[]nums){for(inti=1;i 把记录按下标的一定增量分组，对每组进行直接插入排序，每次排序后减小增量，当增量减至1时排序完毕。 每次在未排序序列中找到最小元素，和未排序序列的第一个元素交换位置，再在剩余未排序序列中重复该操作直到所有元素排序完毕。 将待排序记录看作完全二叉树，可以建立大根堆或小根堆，大根堆中每个节点的值都不小于它的子节点值，小根堆中每个节点的值都不大于它的子节点值。 以大根堆为例，在建堆时首先将最后一个节点作为当前节点，如果当前节点存在父节点且值大于父节点，就将当前节点和父节点交换。在移除时首先暂存根节点的值，然后用最后一个节点代替根节点并作为当前节点，如果当前节点存在子节点且值小于子节点，就将其与值较大的子节点进行交换，调整完堆后返回暂存的值。 比较相邻的元素，如果第一个比第二个大就进行交换，对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，每一轮排序后末尾元素都是有序的，针对n个元素重复以上步骤n-1次排序完毕。 publicvoidbubbleSort(int[]nums){for(inti=0;i 首先选择一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，一部分全部小于等于基准元素，一部分全部大于等于基准元素，再按此方法递归对这两部分数据进行快速排序。 基本原理：应用分治法将待排序序列分成两部分，然后对两部分分别递归排序，最后进行合并，使用一个辅助空间并设定两个指针分别指向两个有序序列的起始元素，将指针对应的较小元素添加到辅助空间，重复该步骤到某一序列到达末尾，然后将另一序列剩余元素合并到辅助空间末尾。