判断一个元素是否在一个集合中

出自http://community.csdn.net/Expert/TopicView1.asp?id=3660145
QuickKeyBoard()

这样的问题在noi教学中属于基础问题，当你要看一个元素是否在一个集合中时，利用Hash散列表的效率最高。代码我已经写好了，复杂度：5000+5000。delphi5下经过:
program AB5000;
{$APPTYPE CONSOLE}数组

const
  MaxVal = 30000;dom

var
  a, b: array [0..5000] of Integer;
  d: array [0..MaxVal-1] of Byte;
  i: Integer;函数

begin
  // 向数组a,b中填入随机数据。
  Randomize;
  for i:=0 to 5000 do
  begin
    a[i] := Random(MaxVal);
    b[i] := Random(MaxVAl);
  end;ui

  // 清空Hash表
  FillChar(d, 30000*Sizeof(Byte), 0);
  // 构造数组a的Hash表
  for i:=0 to 5000 do
    Inc(d[a[i] mod MaxVal]);
  // 在数组a的Hash表中查找数组b的元素
  for i:=0 to 5000 do
    if d[b[i] mod MaxVal]<>0 then
      Write(b[i], ' ');
  Writeln;
  Readln;
end.
若是是字符串数组的话，那么，改变一下Hash函数便可。我上面用的Hash函数是“求余数”，对于字符串，能够考虑使用执行链接格式(ELF)Hash函数，代码以下：
function ELFHash(var s: String): Integer;
var
  g, h, i: LongWord;
begin
  h := 0;
  for i:=1 to Length(s) do
  begin
    h := h shl 4 + Ord(s[i]);
    g := h and $f0000000;
    if g <> 0 then
     h := h xor (g shr 24);
    h := h and (not g);
  end;
  ELFHash := h mod M;
end;
这个Hash函数最先用于Unix系统的文件系统，对长短字符串都颇有效，对不一样的s，冲突的几率很是的小。其中的M是Hash表的大小。
.net