? 特点
? 简单、常用，可与上述几种方法结合使用
? p的选取很重要；p选的不好，容易产生同义词
? 随机数法
? 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) ? 适于关键字长度不等的情况
? 选取哈希函数，考虑以下因素：
? 计算哈希函数所需时间 ? 关键字长度
? 哈希表长度（哈希地址范围） ? 关键字分布情况 ? 记录的查找频率
冲突处理
冲突：是指由关键字得到的Hash地址上已有其他记录。 冲突处理 ：
为出现哈希地址冲突的关键字寻找下一个哈希地址。 好的哈希函数可以减少冲突，但很难避免冲突。
常见的冲突处理方法有： 开放地址法 再哈希法 链地址法
公共溢出区法
排序：
直接插入排序
把未排序的元素一个一个和已排序的元素作对比，确定插入的位置然后插入到有序的序列中。
void Direct_Insert_Sort(DataType R[], int n){
//将记录序列R按关键字作升序排列，降序排列类似 //记录从第一个位置开始存储，R[0]作为监视哨 for(i=2; i<=n;++i){
if(R[i].key R[j+1]=R[j]; //从有序部分最后一个位置开始向前查找插入位置 R[j+1]=R[0]; //将记录插入到正确位置 } } } 折半插入排序 把未排序的元素，通过对已排序的元素进行折半查找，查找出相应的位置，然后把需要排序的元素插入到已排序的序列中。 void Binary_Insert_Sort(DataType R[], int n){ for(i=2; i<=n; ++i){ // 从第二个位置处的记录开始排序 R[0]=R[i]; //R[0]为监视哨，保存待插入的元素 low=1; high=i-1; //插入位置的初始区间 while(low<=high){ //while循环确定插入位置 mid=(low+high)/2; if(R[0].key>R[mid].key) low=mid+1; //插入位置在前半部份 else high=mid-1; //插入位置在后半部分 } for(j=i-1; j>=high+1; j--) //向后移动数据 R[j+1]=R[j]; R[high+1]=R[0]; //将记录插入到正确位置 } } 性能分析 折半插入排序过程中，每次在确定插入位置时，采用二分的办法，需要比较的次数至多为 log2(n+1) ，总共需要n-1趟，因此，整个排序过程需要比较的次数为O(nlog2n)。而数据的移动次数和直接插入排序算法相同，也为O(n2)。 希尔排序 冒泡排序 快速排序 归并排序和基数排序等排序算法 图： ? 无向图（Undigraph） G=(V, E) 其中，V同有向图的顶点，E为顶点之间的边集合 ? 有向图（Digragh） G=（V，E） 其中，V为图的顶点集合 E为顶点之间的弧集合