散列一般也叫哈希。散列表也叫哈希表。本位将介绍散列表的基本知识、一致性哈希、哈希碰撞攻击及Java里的哈希实现。
散列表是普通数组概念的推广，在最坏情况下查找一个元素需要O(n)，在一些合理假设下，查找一个元素的期望时间为O(1)。
在散列表中，不是直接把关键字用作数组下标，而是根据关键字计算出下标。
散列函数：作用就是根据关键字计算出数组下标。
碰撞（collision）：多个关键字映射到同一个数组下标位置。
槽：一般把散列表的数组的一个存储单元（元素）叫做槽。
简单一致性散列：（Simple uniform hashing）假设任何元素散列到m个槽中的每一个的可能性是相同的，且与其他元素已被散列到什么位置上独立无关，这个假设称为简单一致性散列。
写出一个O(n)时间的非递归过程，输出给定的含n个节点的二叉树中每个结点的关键字，要求只能使用除树本身以外固定量的额外存储空间，而且在过程中不能修改该树，哪怕只是暂时的。
树的遍历可以分为广度优先和深度优先两种形式。
树的遍历可以分为先根遍历、中序遍历、后序遍历。前中后是以父节点在遍历中的顺序为根据的。
由于只能使用固定量的额外存储空间，所以，没法构建队列或栈来进行遍历 或 用变量标记哪些结点是已输出的。由于不能修改树，也没法在树上做标记。所以，结点是否已输出只能在遍历过程中判断，也就需要遍历的算法能够区分出已输出和未输出的。
如果采用广度优先的方式，先输出父结点后，由于没有足够的空间来存储对子树的引用，树可以说是变为两棵独立的树，这个方式应该是不可行的。
如果采用深度优先的方式，以中序遍历为例，总是按左子树、父结点、右子树的顺序遍历，那么当右子树遍历完后，说明父结点及其所有子树都遍历完成了，可以这样往上处理父结点的父结点。而判断右子树是否遍历完成可以通过：当前遍历完成的结点是否是父结点的右结点来完成。这种方法是可行的。
当结点p及其子树都遍历完成后，需要向上查找第一个未遍历的右子树（parent = p.parent）：
p == parent.rChild，当前遍历是子树是右子树，需要继续往上查找；这里的堆不是编程语言里的堆，是一种数据结构。
堆像一棵倒立的满二叉树，每个节点最多有两个直接子节点。最上面的节点称为根节点，没有子节点的节点称为叶子节点，有子节点的节点称为分支节点。
堆有大顶堆和小顶堆之分。大顶堆是指分支节点大于它的所有子节点，堆里最大元素是根节点；小顶堆是指分支节点小于它的所有子节点，堆里最小元素是根节点。
堆排序是借助堆数据结构进行排序的一种高效算法，它的平均时间复杂度是O(n*lg(n))。
堆排序的核心是构建和维持堆。
实现时要注意的是：
以数组第一个节点（序号为0）为根，方便计算叶子节点。
大多数算法介绍都是以1为数组的起始下标的，左右叶子节点的计算分别为：lchild=2*parent; rchild =2*parent+1；而实际编程语言大多数都是以0为起始下标的，所以子节点计算需要调整为：lchild=2*parent+1; rchild=2*parent+2；因为根节点是0，导致根节点的左子树与根节点相同而出错。
构建是从底向上逐层构建堆，从最后一层的分支节点（ len(arr)/2 ）开始构建堆。
从堆顶取出最大元素与最后一个堆元素交互后，堆的大小减1。所以堆在排序过程中是逐渐缩小的，但根总是第一个元素，所以可以利用之前也构建好的堆，只需要调整一棵子树。
继续阅读
快速排序也是基于分治模式的，对于规模为n的数组，最坏情况运行时间是O(n^2)，平均运行时间是O(lg(n))。
对数组A[p…r]排序的分治过程的三个步骤：
从上面的步骤可以看到，快速排序的关键在划分子数组，且每次划分都产生一个元素，它所在的位置就是它最终的位置。
继续阅读
合并排序是基于分治思想的：
1. 如果数组足够小，直接对数组进行排序。
2. 否则，把数组划分为两个子数组，分别进行合并排序，然后合并两个有序的子数组为有序数组。
进行合并操作的复杂度为O(n)，由于每次把数组分为2个子数组，需要进行lg(n)次合并，所以时间复杂度为O(n*lg(n))，。
每次合并都需要与两个子数组长度和 大小的数组，所以空间复杂度为O(n)。
记录插入排序及其改进算法、希尔排序、冒泡排序，及插入排序与冒泡排序的对比。
继续阅读