正则表达式(Regular Expression)测试程序【续】

/**正则表达式的分组
    * group
    */
/*
    Pattern p = Pattern.compile("(\\d{3,5})([a-z]{2})");//分组，使用()，此处把数字和字母分组。一共有3组，正则表达式本身就是一组
    String s = "123aa-34345bb-234cc-00";
    Matcher m = p.matcher(s);
    while(m.find()) {
       p(m.group(1));//group,内容为正则表达式所匹配的字符串，组号即第n个左小括号,输入第几组就打印选中的那个组的内容
   //m.group()则直接打印所有组内容
    }
*/

/** Reluctant quantifiers限定词 勉强限定词
    * ?? 一个或没有
    *? 零个或更多
    * +? 一个或更多
    * {n}? 正好n个
    * {n,}? 至少n个
    * {n,m}? 至少n最多m
*/
/**Possesive quantifiers独占性限定词
    * ?+ 意义同上
    *+ Greedy,Reluctant,Possessive这三种quantifiers区别：它们都是匹配到了就停止
    * ++ Greedy，看到{n,m}就直接吞入m个字符，再与正则表达式匹配，匹配不上则往外吐一个再匹配
    * {n}+ Reluctant，看到{n,m}就吞入n个字符，再匹配，匹配不上则再吞一个字符
    * {n,}+ Possesive，独占的，与Greedy类似，一次吞m个，只是不往外吐
    * {n,m}+
*/
/*
    Pattern p = Pattern.compile(".{3,10}+[0-9]");
    String s = "aaaa5bbbb68";
    Matcher m = p.matcher(s);
    if(m.find())
       p(m.start() + "-" + m.end());
    else
       p("not match!");
*/

正则表达式(Regular Expression)测试程序

import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class RegExp {
  public static void main(String[] args) {
  /* p("abc".matches("..."));//可以匹配，一个点代表一个字符
    p("a8729a".replaceAll("\\d", "-"));//把数字全替换为横线,\\d代表一位数字
    Pattern p = Pattern.compile("[a-z]{3}");//匹配三个字符，每个都是a-z
    Matcher m = p.matcher("fgh");
    p(m.matches());*/
    // p("fgh".matches("[a-z]{3}"));//上边三句可合并为这一句

  /**Greedy quantifiers 贪婪限定符，默认
    * 初步认识 . * + ?即meta characters
    * . 一个字符
    * ? 一个或零个
    * * 零个或多个
    * + 一个或多个
    * [n] 正好n个
    * [n,]最少n个
    * [n,m]至少n个最多m个
    */
    /* p("a".matches("."));
    p("aaaa".matches("a*"));
    p("aaaa".matches("a+"));
    p("aaaa".matches("a?"));
    p("".matches("a*"));//零宽度匹配 zero length matches。空串匹配
    p("".matches("a?"));
    p("".matches("a+"));
    p("1231231425346234".matches("\\d{3,100}"));//至少3个之多100个，且都是数字
    p("192.168.0.aaa".matches("\\d{1,3}\\.\\d{1,3}\\.\\d{1,3}\\.\\d{1,3}"));
    p("192".matches("[0-2][0-9][0-9]"));//一个中括号内是匹配一个字符
    */

    /**
      * ^取反
      * -代表范围
      * |代表或者
      * &&代表并且
      */
    /* p("a".matches("[abc]"));
    p("a".matches("[^abc]"));
    p("A".matches("[a-zA-Z]"));
    p("A".matches("[a-z]|[A-Z]"));
    p("A".matches("[a-z[A-Z]]"));//或的另一个写法
    p("R".matches("[A-Z&&[RFG]]"));//交集，取A-Z与RFG集合交集的部分，其实就是RFG
    */

    /**
      *\d digit
      *\D non-digit
      *\s a whitespace character:如[ \t\n\x0B\f\r] 不可见的符号
      *\S a non-whitespace character
      *\w a word character: [a-zA-Z_0-9]包括下划线
      *\W a non-word character
      */
    /*p(" \n\r\t".matches("\\s{4}"));
    p(" ".matches("\\S"));
    p("a_8".matches("\\w{3}"));
    p("abc888&^%".matches("[a-z]{1,3}\\d+[&^#%]+"));
    p("\\".matches("\\\\"));//匹配一个\必须用两个\\
    */

    /**
      * POSIX Style
      * POSIX (Portable Operating System Interface based on uniX)
      * 以 unix 操作系统为基础的可携带操作系统界面
      * 以 unix 操作系统为基础的操作系统标准
      */
    /*p("a".matches("\\p{Lower}"));//很少这样写，不推荐
      */

    /**
      * boundary 边界匹配
      * ^位于中括号里代表取反，在中括号外代表一行的起始位置
      * $结尾
      * \b word boundary
      * \B non-word boundary
      */
    /*p("hello sir".matches("^h.*"));
    p("hello sir".matches(".*ir$"));
    p("hello sir".matches("^h[a-z]{1,3}o\\b.*"));
    p("hellosir".matches("^h[a-z]{1,3}o\\b.*"));

    */

    /**whilte lines 空白行
      * 此处空白行代表有空格的行。行开头就是换行符的不算作本例的空白行
      */

    /*p(" \n".matches("^[\\s【开头是空白字符】&&[^\\n]]【并且不是换行符】*\\n$【末尾跟着换行符】"));
    // " \n"即一个空白行
      */
}

  public static void p(Object o) {
    System.out.println(o);
  }
}

vector的用法

线性结构中的顺序表有三种，向量，栈和队列
栈和队列在很多数据结构的书中都有论述到。唯独向量这一种顺序表很少
现在记录下vector的用法

/*
*-----------------------------------------
*先来C++，有关Vector类
*-----------------------------------------
*/
vector 抽象容器类型之一（还有list和deque等），与其他几中容器类型不同的是它高效支持随机访问其中的元素。
使用vector，首先必须调用头文件(#include )

它的声明和初始化是这样的
vector <类型名> 变量名
vector vi = ( 10 , 1 ) //初始化为10个元素的vector，每个元素都为1

push_back()的用法是将元素插入vector容器的最尾部
举个例子
vector vi;
int a[4] = { 0, 1, 2, 3};
for ( int i = 0; i<=4; ++i )
vi.push_back(a[i]);

此时vi就是0 1 2 3
如果改成
vi.push_front( a[i] );
vi就是 3 2 1 0


/*///////vector方法列表/////
1.toString()
2.reset(x,y)//重新赋值例如:myv.reset(2,3);
3.getclone()//复制.例如myv2=myv1.getclone();
4.eqV(v)//是否相等例如if(v1.eqv(v2)){};
5.addV(v),addVNew(v)和minusV(v),minusVNew(v)//加法减法v1.addV(v2);v3=v1.addVNew(v2);
6. scaleV(n)和scaleVNew(n)//伸长.见上
7.getLength()和setLength(n)//a=v1.getLength();v1.setLength(30);
8.getAngle()和setAngle(n)//得到与设置角度.
9.rot(n)和rotNew(n)//旋转
10.dot(v)//内积x=v1.dot(v2)
11.angleBetween(v)//得到夹角例如x=v1.angleBetween(v2);
*/


class vector {
var x:Number;
var y:Number;
// 用于返回属性值的方法
function toString():String {
return ("["+x+","+y+"]");
}
//改变属性值的方法.
function reset(getx:Number, gety:Number):Void {
x = getx;
y = gety;
}
//克隆向量.与mx不同//!!!!!!
function getclone():vector {
return new vector(x, y);
}
//比较相等否.
function eqV(getVector:vector):Boolean {
return (x == getVector.x && y == getVector.y);
}
//向量加法.
function addV(getVector:vector):Void {
x += getVector.x;
y += getVector.y;
}
//向量加法得到新向量.
function addVNew(getVector:vector):vector {
return new vector(x+getVector.x, y+getVector.y);
}
//向量减法
function minusV(getVector:vector):Void {
x -= getVector.x;
y -= getVector.y;
}
//向量减法得到新向量.
function minusVNew(getVector:vector):vector {
return new vector(x-getVector.x, y-getVector.y);
}
//向量缩放
function scaleV(n:Number):Void {
x *= n;
y *= n;
}
//向量缩放得到新向量.
function scaleVNew(n:Number):vector {
return new vector(x*n, y*n);
}
//得到向量的长度
function getLength():Number {
return Math.sqrt(x*x+y*y);
}
//设置向量长度
function setLength(len:Number):Void {
var r = this.getLength();
if (r) {
this.scaleV(len/r);
} else {
this.x = len;
}
}
//得到向量角度
function getAngle():Number {
return (180/Math.PI)*Math.atan2(y, x);
}
//设置向量角度
function setAngle(angle:Number):Void {
var r = this.getLength();
var tem = angle*(Math.PI/180);
x = r*Math.cos(tem);
y = r*Math.sin(tem);
}
//旋转.
function rot(angle:Number):Void {
var r = this.getLength();
var tem = angle*(Math.PI/180);
var ca = Math.cos(tem);
var sa = Math.sin(tem);
var rx = x*ca-y*sa;
var ry = x*sa+y*ca;
x = rx;
y = ry;
}
//旋转并得到新向量.
function rotNew(angle:Number):vector {
var v = new vector(x, y);
v.rotate(angle);
return v;
}
//内积
function dot(v:vector):Number {
return x*v.x+y*v.y;
}
//法向量计算省略.可以用rotateNew(90)得到.
//垂直验证省略.用(v1.dot(v2)==0)判断垂直.
//向量夹角.得到向量夹角绝对值.
function angleBetween(v:vector):Number {
var tem = this.dot(v);
return (180/Math.PI)*Math.acos(tem/(this.getLength()*v.getLength()));
}
// 构造函数
function vector(getx:Number, gety:Number) {
x = getx;
y = gety;
}
}

/*
*---------------------------------------
*另一个示范vector用法的c程序段
*来自C编程思想
*---------------------------------------
*/

#include < string.h >
#include < iostream.h >
#include < fstream.h >
#include < vector.h >
using namespace std;

int main() {
vector v;
ifstream in("Fillvector.cpp");
string line;
while(getline(in, line))
v.push_back(line); // Add the line to the end
// Add line numbers:
for(int i = 0; i < v.size(); i++)
cout << i << ": " << v[i] << endl;
} ///:~

getline获得文件的一行

int main() {
vector words;
ifstream in("GetWords.cpp");
string word;
while(in >> word)
words.push_back(word);
for(int i = 0; i < words.size(); i++)
cout << words[i] << endl;
} ///:~

while(in >> word)是以空格（space）为分割符来分割的

百度一面未果的师兄写的···

我投的是商务引擎研发工程师，后来才知道是百度的核心技术职位。笔试有3道题目，第一道是有Ｎ（N〉10000）个集合，每个集合有Ｍ个词，每个集合有集合号，现在有个待查找的词序列，返回词所在的集合号。我当时的想法是查找无非有两种好方法，一种是折半，一种是HASH。词没有联系，只能用HASH了。第二道把两个有序的序列，排列成整体有序的序列，我用的是两个折半。
今天的面试感觉发挥不是很好，先自我介绍了一下，主要是项目和获奖情况。然后让我写蜜网项目的architecture,感觉讲得不是很到位。面试官对我做得项目也不是很感兴趣。然后开始Ｃ＋＋基础问答，诸如拷贝构造函数作用，缺省拷贝构造函数危害，虚函数作用，指针和引用。缺省拷贝构造函数危害没有答上来，其他的都还勉强。然后是一道证明题，快速排序的时间复杂度，并证明。这个就基本不会了。第一道程序题很简单，写出字符串逆序输出的代码。我很快就写完了，然后面试官就叫我在自己的程序里找错误，费了九牛二虎之力终于把错误找完了，纸上写程序真的不习惯。第二道题，ｖｅｃｔｏｒ类，包括构造函数，插入，查找。。。我就答不上来了，STL只用过LIST。还有一道题，在ｌｏｇ文件，包括时间　网址　关键字，统计每个关键字的出现次数。我的想法是用二叉树，面试官点了一下头，应该思路是对的，然后面试官接着问如果这个ｌｏｇ文件数据是海量，内存装不下，怎么办。我就不知道怎么回答了。还有一道智力题，大概计算一下下面那条马路的车流量，说出你的思路。我的想法是高峰时段观察5-10分钟，低谷时段考察5-10分钟，平常时段考察5-10分钟，然后加权平均


【swetter想说的话】
当时笔试百度的时候做的是和这位师兄一样的题，只是那时候的数据结构很弱，因此连个一面的机会都没有。后来为了准备微软的笔试，恶补了几天数据结构，C++后的STL也是猛看，现在再看一面的题，C++基础基本没问题，缺省拷贝构造函数的危害就在于它是浅拷贝，不小心就会造成RUNTIME ERROR。第一道程序题将字符串逆序输出，其实就可以使用STL中的vector容器，这是可置换的，使用一个迭代器，和rbegin(),rend()函数就可以轻松搞定。vector类的构造函数，插入，查找。。。只要会用向量类，这个不难。。log文件那个就不行了，哎，数据结构还需要继续加强。。。不然找不到工作啊，加油加油

时间复杂度的计算

一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 请判断下列关系是否成立： （1） f(n)=O(g(n)) （2） g(n)=O(f(n)) （3） h(n)=O(n^1.5) （4） h(n)=O(nlgn) 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。
◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
◆ （2）成立。与上同理。
◆ （3）成立。与上同理。
◆ （4）不成立。由于当n→∞时n^1.5比nlgn递增的快，所以h(n)与nlgn的比值不是常数，故不成立。 2、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0 while(i (2) x=n; // n>1 while (x>=(y+1)*(y+1)) y++; 解答：T(n)=n1/2 ，T(n)=O(n1/2)， 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。 (3) x=91; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; 解答： T(n)=O(1)， 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。

【典藏】列函数与散列表（哈希函数、哈希表、Hash函数、Hash表）

散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)。

一、散列表的概念 
1、散列表 
　 设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。
　 散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。其中：
　 ① h：U→{0，1，2，…，m-1} ，通常称h为散列函数(Hash Function)。散列函数h的作用是压缩待处理的下标范围，使待处理的|U|个值减少到m个值，从而降低空间开销。
　 ② T为散列表(Hash Table)。
　 ③ h(K i )(K i ∈U)是关键字为K i 结点存储地址(亦称散列值或散列地址)。
　 ④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing)

2、散列表的冲突现象
（1）冲突 
　 两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。 
　 【例】上图中的k 2 ≠k 5 ，但h(k 2 )=h(k 5 )，故k 2 和K 5 所在的结点的存储地址相同。 
（2）安全避免冲突的条件 
　 最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件： 
     ①其一是|U|≤m 
     ②其二是选择合适的散列函数。这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。
（3）冲突不可能完全避免 
　   通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。 
（4）影响冲突的因素 
　 冲突的频繁程度除了与h相关外，还与表的填满程度相关。设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(Load Factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。

二、散列函数的构造方法 
1、散列函数的选择有两条标准：简单和均匀。
　   简单指散列函数的计算简单快速；均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。
2、常用散列函数
为简单起见，假定关键字是定义在自然数集合上。其它关键字可以转换到自然数集合上。 
（1）平方取中法 
　 具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。 
　 【例】将一组关键字(0100，0110，1010，1001，0111)平方后得 (0010000，0012100，1020100，1002001，0012321) ，若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。相应的散列函数用C实现很简单： 
     int Hash(int key){ //假设key是4位整数 
     key*=key； key/=100； //先求平方值，后去掉末尾的两位数
     return key％1000； //取中间三位数作为散列地址返回
    } 
（2）除余法 
　 该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m。该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。 
　 【例】若选m是关键字的基数的幂次，则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。 
　 【例】若关键字是十进制整数，其基为10，则当m=100时，159，259，359，…，等均互为同义词。 
（3）相乘取整法 
　 该方法包括两个步骤：首先用关键字key乘上某个常数A(0

 该函数的C代码为： 

     int Hash(int key){       double d=key *A； //不妨设A和m已有定义       return (int)(m*(d-(int)d))；//(int)表示强制转换后面的表达式为整数       }  （4）随机数法 　 选择一个随机函数，取关键字的随机函数值为它的散列地址，即h(key)=random(key)其中random为伪随机函数，但要保证函数值是在0到m-1之间。 （5）数字分析法  设有 n 个 d 位数，每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种符号出现的几率均等; 在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。 （6）基数转换法  将关键码值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。  （7）折叠法  有时关键码所含的位数很多，采用平方取中法计算太复杂，则可将关键码分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址，这方法称为折叠法。  （8）ELFhash字符串散列函数  ELFhash函数在UNIX系统V 版本4中的“可执行链接格式”( Executable and Linking Format，即ELF )中会用到，ELF文件格式用于存储可执行文件与目标文件。ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效，字符串中每个字符都有同样的作用，它巧妙地对字符的ASCII编码值进行计算，ELFhash函数对于能够比较均匀地把字符串分布在散列表中。

三、处理冲突的方法  　 通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0..m-1]中。  1、开放定址法  （1）开放地址法解决冲突的方法 　 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。注意：  ①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。  ②空单元的表示与具体的应用相关。  【例】关键字均为非负数时，可用"-1"来表示空单元，而关键字为字符串时，空单元应是空串。  　 总之：应该用一个不会出现的关键字来表示空单元。  （2）开放地址法的一般形式  　 开放定址法的一般形式为： h i =(h(key)+d i )％m 1≤i≤m-1.其中：  　 ①h(key)为散列函数，d i 为增量序列，m为表长。  　 ②h(key)是初始的探查位置，后续的探查位置依次是h l ，h 2 ，…，h m-1 ，即h(key)，h l ，h 2 ，…，h m-1 形成了一个探查序列。  　 ③若令开放地址一般形式的i从0开始，并令d 0 =0，则h 0 =h(key)，则有： h i =(h(key)+d i )％m 0≤i≤m-1.探查序列可简记为h i (0≤i≤m-1)。  （3）开放地址法堆装填因子的要求  　 开放定址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。  （4）形成探测序列的方法  　 按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。       ①线性探查法(Linear Probing)  该方法的基本思想是：将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：d，d+l，d+2，…，m-1，0，1，…，d-1 .即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。探查过程终止于三种情况：  　 (1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；  　 (2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；  　 (3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。  利用开放地址法的一般形式，线性探查法的探查序列为： h i =(h(key)+i)％m 0≤i≤m-1 //即d i =i  　 【例9.1】已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。 

解答:为了减少冲突，通常令装填因子α 　 用线性探查法解决冲突时，当表中i,i+1，…，i+k的位置上已有结点时，一个散列地址为i，i+1，…，i+k+1的结点都将插入在位置i+k+1上。把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积(Clustering)。这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间。若散列函数不好或装填因子过大，都会使堆积现象加剧。  　 【例】上例中，h(15)=2，h(68)=3，即15和68不是同义词。但由于处理15和同义词41的冲突时，15抢先占用了T[3]，这就使得插入68时，这两个本来不应该发生冲突的非同义词之间也会发生冲突。  　 为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找)，而应使探查序列跳跃式地散列在整个散列表中。       ②二次探查法(Quadratic Probing)  　 二次探查法的探查序列是：h i =(h(key)+i*i)％m 0≤i≤m-1 //即d i =i 2，即探查序列为d=h(key)，d+1 2 ，d+2 2 ，…，等。该方法的缺陷是不易探查到整个散列空间。     ③双重散列法(Double Hashing)  　 该方法是开放定址法中最好的方法之一，它的探查序列是：h i =(h(key)+i*h1(key))％m 0≤i≤m-1 //即d i =i*h1(key)，即探查序列为：d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。  　 该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。  注意：定义h1(key)的方法较多，但无论采用什么方法定义，都必须使h1(key)的值和m互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。  　 【例】 若m为素数，则h1(key)取1到m-1之间的任何数均与m互素，因此，我们可以简单地将它定义为：h1(key)=key％(m-2)+1  　 【例】对例9.1，我们可取h(key)=key％13，而h1(key)=key％11+1。  　 【例】若m是2的方幂，则h1(key)可取1到m-1之间的任何奇数。  2、拉链法  （1）拉链法解决冲突的方法  　 拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。  【例9.2】已知一组关键字和选定的散列函数和例9.1相同，用拉链法解决冲突构造这组关键字的散列表。 　　解答：不妨和例9.1类似，取表长为13，故散列函数为h(key)=key％13，散列表为T[0..12]。 注意：当把h(key)=i的关键字插入第i个单链表时，既可插入在链表的头上，也可以插在链表的尾上。这是因为必须确定key不在第i个链表时，才能将它插入表中，所以也就知道链尾结点的地址。若采用将新关键字插入链尾的方式，依次把给定的这组关键字插入表中，则所得到的散列表如下图所示。　（2）拉链法的优点 

　 与开放定址法相比，拉链法有如下几个优点：(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。  （3）拉链法的缺点  　 拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

四、散列表上的运算  散列表上的运算有查找、插入和删除。其中主要是查找，这是因为散列表的目的主要是用于快速查找，且插入和删除均要用到查找操作。  1、散列表类型说明：       #define NIL -1 //空结点标记依赖于关键字类型，本节假定关键字均为非负整数      #define M 997 //表长度依赖于应用，但一般应根据。确定m为一素数      typedef struct{ //散列表结点类型      KeyType key；      InfoType otherinfo； //此类依赖于应用      }NodeType；      typedef NodeType HashTable[m]； //散列表类型 2、基于开放地址法的查找算法  　 散列表的查找过程和建表过程相似。假设给定的值为K，根据建表时设定的散列函数h，计算出散列地址h(K)，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值K比较。若相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去，直到某个地址单元为空(查找失败)或者关键字比较相等(查找成功)为止。 （1）开放地址法一般形式的函数表示  int Hash(KeyType k，int i)  { //求在散列表T[0..m-1]中第i次探查的散列地址hi，0≤i≤m-1  //下面的h是散列函数。Increment是求增量序列的函数，它依赖于解决冲突的方法  return(h(K)+Increment(i))％m； //Increment(i)相当于是d i  } 若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的h(K)和Increment(i)可定义为：  int h(KeyType K){//用除余法求K的散列地址  return K％m；  }  int Increment(int i){ //用线性探查法求第i个增量d i  return i; //若用二次探查法，则返回i*i  }  （2）通用的开放定址法的散列表查找算法： int HashSearch(HashTable T，KeyType K，int *pos)  { //在散列表T[0..m-1]中查找K，成功时返回1。失败有两种情况：找到一个开放地址  //时返回0，表满未找到时返回-1。 *pos记录找到K或找到空结点时表中的位置  int i=0； //记录探查次数  do{  *pos=Hash(K，i)； //求探查地址hi  if(T[*pos].key==K) return l； //查找成功返回  if(T[*pos].key==NIL) return 0；//查找到空结点返回  }while(++i return -1； //表满且未找到时，查找失败  } //HashSearch  注意：上述算法适用于任何开放定址法，只要给出函数Hash中的散列函数h(K)和增量函数Increment(i)即可。但要提高查找效率时，可将确定的散列函数和求增量的方法直接写入算法HashSearch中。  3、基于开放地址法的插入及建表  　 建表时首先要将表中各结点的关键字清空，使其地址为开放的；然后调用插入算法将给定的关键字序列依次插入表中。插入算法首先调用查找算法，若在表中找到待插入的关键字或表已满，则插入失败；若在表中找到一个开放地址，则将待插入的结点插入其中，即插入成功。  void Hashlnsert(HashTable T，NodeTypene w)  { //将新结点new插入散列表T[0..m-1]中  int pos，sign；  sign=HashSearch(T，new.key，&pos)； //在表T中查找new的插入位置  if(!sign) //找到一个开放的地址pos  T[pos]=new； //插入新结点new，插入成功  else //插人失败  if(sign>0)  printf("duplicate key!")； //重复的关键字  else //sign<0 >m) //用开放定址法处理冲突时，装填因子α须不大于1  Error("Load factor>1")；  for(i=0;i T[i].key=NIL； //将各关键字清空，使地址i为开放地址  for(i=0;i Hashlnsert(T，A[i])；  } //CreateHashTable  4、删除  　 基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为NIL，而应该将其置为特定的标记DELETED。因此须对查找操作做相应的修改，使之探查到此标记时继续探查下去。同时也要修改插人操作，使其探查到DELETED标记时，将相应的表单元视为一个空单元，将新结点插入其中。这样做无疑增加了时间开销，并且查找时间不再依赖于装填因子。因此，当必须对散列表做删除结点的操作时，一般是用拉链法来解决冲突。  5、性能分析  　 插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。  　 虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。  （1）查找成功的ASL  　 散列表上的查找优于顺序查找和二分查找。  　 【例】在例9.1和例9.2的散列表中，在结点的查找概率相等的假设下，线性探查法和拉链法查找成功的平均查找长度分别为：  ASL=(1×6+2×2+3×l+9×1)/10=2.2 //线性探查法  ASL=(1×7+2×2+3×1)/10=1.4 //拉链法  　　当n=10时，顺序查找和二分查找的平均查找长度(成功时)分别为：  ASL=(10+1)/2=5.5 //顺序查找  ASL=(1×l+2×2+3×4+4×3)/10=2.9 //二分查找，可由判定树求出该值  （2） 查找不成功的ASL  　 对于不成功的查找，顺序查找和二分查找所需进行的关键字比较次数仅取决于表长，而散列查找所需进行的关键字比较次数和待查结点有关。因此，在等概率情况下，也可将散列表在查找不成功时的平均查找长度，定义为查找不成功时对关键字需要执行的平均比较次数。 　 【例】例9.1和例9.2的散列表中，在等概率情况下，查找不成功时的线性探查法和拉链法的平均查找长度分别为：  ASL unsucc =(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=59/13≈4.54  ASL unsucc =(1+0+2+1+0+1+1+0+0+0+1+0+3)/13≈10/13≈0.77  注意：  　 ①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。  　 ②散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找 长度。  　 ③ α的取值越小，产生冲突的机会就小，但α过小，空间的浪费就过多。只要α选择合适，散列表上的平均查找长度就是一个常数，即散列表上查找的平均时间为O(1)。  　 ④ 散列法与其他查找方法的区别  除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找，每次关键字的比较结果为"="或"!="两种可能，其平均时间为O(n)；其余的查找均是对有序集合的查找，每次关键字的比较有"="、"<"和">"三种可能，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O(lgn)。而散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。