据说牛得一塌糊涂的哈希（Hash）列表 - DelphiHash.pas(50)

据听说排队买iPad人群中，有人买到手后就把iPad砸了，并把砸iPad的视频传到了网上，有很多人不理解，问他们既然只是想把iPad砸了，为什么还要排队赶早？这些人回答：iPad不是叫苹果吗？我们才是正真了解iPad的，是苹果，当然要尝试榨汁才是最合适的。橙子是不是也可以榨汁？哈哈我现在在一台AMD双核2.8G电脑上，上面帖子里的数据，由于受电脑限制，只能做9万次循环的测试，下面我要看看做999万次的测试结果会怎么样：Time Elapsed Testeach Compare loop 9999999each Effect loop 100Result := (SUM(100)(for each Compare TimeElapsed)) / 100-------------------------------------1) General Compare: 1611-------------------------------------2) JB_AND_SB Compare: 1576-------------------------------------3) Memory Compare: 1585-------------------------------------呼~~~，好长的时间。但结果在我的意料中：看着SB，实际非常JB的JB_AND_SB函数大获全胜。内存比较函数也超越第一项字符串比较函数，获得第二名。这次内存比较函数的进步，得益于AMD的HT3.0超高内存带宽的优势，这个带宽，整整比Intel的高了一倍多（从这里也可以看出，AMD与Intel相比，虽然使用了更高带宽，但实际效果并没有成倍上升）。当然，这里只是一个测试。虽然我们已经知道JB_AND_SB函数性能不错，但是在写代码中，我仍然不会选择它，原因很简单，s1=s2 无论是看着还是写着，都是清晰明了的，既然s1=s2性能也已经非常不错了，没有理由换成一个性能可能更好，但好得甚为有限的另外的函数，更何况 Delphi 自带的运行时库函数，稳定性是由所有 Delphi 爱好者和使用者、做了无数次义务小白鼠后确定下来的，质量无疑更有保证。这就是我宁愿使用 s1=s2 ，而不使用 JB_AND_SB 的原因。

呵呵，是的。老是看不到有营养的帖子了。对上面函数的写法做个说明：1）全部比较不使用function，而使用procedure，为的是让返回的结果不能直接参与运算。2）全部函数增加inline编译标志，为的是尽量不因为手写代码导致多次call调用，如果不使用内联，人类习惯与计算机习惯的差异方面，肯定就直接输给用asm写成的代码了。3）在书面函数可能的范围下，尽量不犯常规优化错误。

汗了，我没表达清楚。。。我是说这句慢了if Result^.Key = Key then
Exit然后，我的意思是让Resut.Key换个N个hash键值代替，而不是使用其实函数计算后再比较。一： THashKeyValue = array [0..3] of Cardinal;
TKeyValuePair = record Next: PKeyValuePair;
//Key: AnsiString;
// 去掉key,使用下列数据类型 hashKey: THashKeyValue;
value: Integer;
end;
二：然后在Add时：function GetHashKeyValue(buf: PChar;
len: Integer): THashKeyValue;
begin
result[0] := hash1function(...);
result[1] := hash2function(...);
result[2] := hash3function(...);
result[3] := hash4function(...);
end;
procedure TAnsiStringHashList.Add(const Key: AnsiString;
const Value: integer);var ix: integer;
hash: THashKeyValue;
Bucket: PKeyValuePair;
begin
hash := GetHashKeyValue(PChar(Key), Length(Key));
ix := hash[0] mod Cardinal(BucketSize);
New(Bucket);
Lock;
try Bucket^.hashKey := hash;
Bucket^.Value := Value;
Bucket^.Next := Buckets[Hash];
Buckets[Hash] := Bucket;
Inc(FCount);
finally Unlock;
end;
end;
三：在Find函数中，使用THashKeyValue类型进行比较，而不是Key: string的字符串的比较为啥用N个hash键值比较，就是因为如果一个字串/内容，如果N次hash都是一样，则认为该内容是一样的，N越大，冲突的机率越小，一般弄到三个基本不会重复，这个看具体情况或场合。BTW：hash表，在Add的时候，应该作一次Find操作，检查现有的hashlist是否存在该key，如存在，则Result = -1，表示已存在。当然，也不算BUG，但对于写hash表的处理而言，要的就是Add一个唯一索引值的效果，如不需要，也无所谓。

有了这个基础后，那么每次去比较的操作就是THashKeyValue: array [0..X] of Cardinal的比较。我相信：这个比较时间，基本可以忽略。当Add时，就将计算出来的hashKey保存起来，这样，下次Add/Find的时候，只是计算了一次SrcKey的hash值，而不是将已存在的hash列表所有的键盘都计算一次。其实这个也算不上什么大问题，只在hash的广度合适，它的深度不高，基本不会出慢的情况。之前我刚开始测试hash表的情况，也是直接用string = string进行检测，后来发现深度在X时，速度就慢下来了，add，10W条记录就要2-3s，后来才发现这问题的。才找了N多资料，后来google了到一篇文章（具体叫啥忘了，只记得关键字：暴雪，hash，冲突，一而再，再而三的机率基本是XXX。。。忘了），才用起这方法来了。其实N=2已经够用了。呵呵。

噢，明白你的意思了。N=2 通常是够用了，=4 更保险、心理感觉会好些。在建立Hash表的时候就执行这些操作，是一个不错的思路，但里面涉及到一些具体的应用场合，比如重复键是否在数据源存在、重复键取舍原则等等。一般Hash应用环境里，通常是首先调试Hash函数，该函数本身，要求在常量时间内完成应用环境下的哈希生成，然后调试深度广度比，这个调整与哈希函数本身的离散均匀度也有关系。所以，我觉得即使在Add时处理重复键（直接返回或者用新值替换），本身也应该是在常量时间内完成，而不应该明显变慢，因为我觉得这个是由Hash这个架构特色决定并保证的呀。

最后介绍一下 TAnsiStringHashList 类中 Assign 和 AssignTo 方法里的二个思路。当发生 Assign （AssignTo）行为的时候，我们会判断 Assign 的目标，在发现实际上是二个 TAnsiStringHashList 需要进行分派数据时，针对 Hash 实际的工作价值，Assign 可以有二个行为：1）将源Hash表里的数据，完整地复制到目标Hash表里。这个就是我上面代码中贴出的情况。通过这样的完整复制，二个Hash表完全独立，可以各自做自己希望的操作。缺点是复制需要时间，尤其Hash表通常用在极大数量检索上，这种复制产生的复制时间是非常巨大的，内存耗费也是非常巨大的。但是，Hash表通常是用来干什么的？最常用的是用来快速Key/Value检索。基于Hash这种特殊的工作目的，真的有必要完整地复制数据吗？这个我就不知道了，也许会有人需要这种复制。但是更多时候我们可能仅仅是需要另开一个线程来协助检索。这种情况下，完全可以做到让数据共享。这就是下面的二：2）源和目标数据共享。方法很简单，由于Hash表的 Buckets 是一个最大为 BucketSize 的数组，那么我们只要利用 Move 函数，将这个数组里的数据挪到新的数组里就可以了。这种 Move 操作可以瞬间完成，内存的占用也只有一个 Buckts 数组，与思路一里花费巨大内存的情况完全不同。完成以后，新生成的 Hash 表就可以协助对原有数据进行检索了。这是非常高效的。 if Source is TAnsiStringHashList then
begin
Self.FUseLock := TAnsiStringHashList(Source).FUseLock;
TAnsiStringHashList(Source).Lock;
Self.Lock;
try Self.BucketSize := TAnsiStringHashList(Source).BucketSize;
SetLength(Self.Buckets, Self.BucketSize);
Move(TAnsiStringHashList(Source).Buckets, Self.Buckets, Self.BucketSize);
Self.FCount :=TAnsiStringHashList(Source).FCount;
finally Self.Unlock;
TAnsiStringHashList(Source).Unlock;
end;
end;
但是请注意了，这样一来，二个实例的任何一个都不能执行 Clear 动作了，因为数据是共享的，任何一方执行 Clear ，另一方也再也拿不到数据了，甚至按照目前我帖子里的写法，二个实例的任何一个都不能释放，因为任何一个释放，一定会在 Destroy 方法里调用 Clear ....... 汗....吧滴、吧滴、吧滴...也许需要一个引用计数....

留个名吧，地质那小子在哪抄的诗呀！感谢谢小雨哥，加油，DELPHI是无所不能的！建义开个专栏，DELPHI无所不能，把其他语言实现的功能，在DELPHI中写出更美的代码！

加入混战 呵呵 d2010 那个高手帮我改改这个function MyProcedure(a,b:string):boolean;asmpushad cmp eax,0 je @@exit cmp edx,0 je @@exit mov ecx,eax-4 cmp ecx,edx-4 jne @@exit mov esi,eax mov edi,edx cld rep cmpsw je @@ok @@exit: mov result,false jmp @@leave @@ok: mov result,true @@leave: popadend;
procedure TForm1.FormCreate(Sender: TObject);var a,b:string;
begin
a:='ab草D';
b:='ab草D';
if myprocedure(a,b) then
caption:='ok' else
caption:='no'end;

rep cmpsw有这个，必慢!

楼上的楼上，呵呵，考试么？我将你的代码写清楚些，函数名也改得正式一些，注释也补上，写在下面，看看可以得几分：function WideStringCompare(a, b: WideString):Boolean;{$IFDEF PUREPASCAL}var i:integer;
pa,pbWORD;
// 或许写成 pa,pbWideChar 更贴切begin
Result := false;
if (Length(a) <> length(b)) or (Length(a) = 0) then
else
begin
pa := @a[1];
pb := @b[1];
i := length(a);
while pa^ = pb^do
begin
inc(pa);inc(pb);dec(i, 2);
if i < 1 then
begin
Result :=True;
break;
end;
end;
end;
end;
{$else
}asm pushad cmp eax,0 // a = '' je @@exit // goto @@exit cmp edx,0 // b ='' je @@exit // goto @@exit mov ecx,eax-4 // length(a) -> ecx cmp ecx,edx-4 // ecx - length(b) <> 0 jne @@exit // goto @@exit mov esi,eax // p1 = @a[1] mov edi,edx // p2 = @b[1] cld // dir + rep cmpsw // loop stepsize = 2, ++p1, ++p2, p1^ - p2^ je @@ok // = 0 goto @@ok@@exit: mov result,false // Result = 0 jmp @@leave@@ok: mov result,true // Result = 1@@leave: popadend;
{$ENDIF}不过这个 asm 写成的函数，依我估计，肯定比我上面用 JB_AND_SB 写成的函数慢。

呵呵，不是“强烈的自信”，是“百分百的事实”！假如你真的仔细参与了上面讨论，应该已经看到：JB_AND_SB 函数当中的循环步长是 Longword，就是说，每循环一次跨出 4 步，而你贴的 asm 代码的循环步长是 word，也就是每次循环跨 2 步！你说是一次跨 2 步快呢？还是一次跨 4 步快？从你的回复看，你的回答可能会让我们很吃惊的。因此，我在前面帖子里贴出了做 999 万次循环测试的结果，由于是高级语言代码，确实在有一倍跨步优势的情况下，针对 asm 仅有很微小的进步。但，毕竟是进步。

汗啊，确实 JB 函数输掉了。asm 的测试函数改写成这个帖子规定要求的测试函数格式如下：procedure asmCompare(s1, s2 :WideString;
var lresult: Boolean);asm pushad cmp eax,0 // a = '' je @@fail // goto @@fail cmp edx,0 // b ='' je @@fail // goto @@fail mov ecx,eax-4 // length(a) -> ecx cmp ecx,edx-4 // ecx - length(b) <> 0 jne @@fail // goto @@fail mov esi,eax // p1 = @a[1] mov edi,edx // p2 = @b[1] cld // dir + rep cmpsw // loop step size = 2, ++p1, ++p2, p1^ - p2^ je @@succ // = 0 goto @@succ@@fail: popad mov [ecx],0 // lresult = false jmp @@exit@@succ: popad mov [ecx],1 // lresult = true@@exit:end;
实测结果，很快！Time Elapsed Testeach Compare loop 99999each Effect loop 100Result := (SUM(100)(for each Compare TimeElapsed)) / 100-------------------------------------1) General Compare: 41-------------------------------------2) JB_AND_SB Compare: 41-------------------------------------3) Memory Compare: 43-------------------------------------4) asm Compare: 16 <-------- 就是这个，字符串比较用它吧-------------------------------------

hash 单元 晚上认真学习 画画指针流程图 害的我又下了 一遍 PASCAL数据结构（清华大学那本）

小雨 果然是难得的奇才啊 批准你进入 艾博龙 公司 编写DELPHI