哈希表中的搜索哈希

Question

我使用大量的数组访问（静态数组，在运行时没有更改）编写一个字处理代码。我对字符串进行哈希处理，然后检查数组（查找）是否存在。但是，它的良好实施是什么？我正在以简单的方式做。如果匹配我的散列输入，则检查每个值的值。想法使其最快？

我目前检查：

如果我使用循环展开它将使这真的不同。 如果我使用无序数组，它比排序数组慢很多。 我会去看看在这种情况下矢量化是否正常。

你有什么建议？或者更好的是，你将如何实现这个算法？

这里的当前例程（它的返回到EAX散列阵列的索引或负值时，如果没有匹配）：

Index_of: 
push edx 
push ecx 
push ebx 
mov ecx,123456   ;hash example. in the real code,it's set by a routine. 
xor ebx,ebx 
mov eax,array 
.LOOP1: 
     cmp [eax],ecx   ;match hash? 
     je .FOUND 
     cmp byte [eax],0 
     je .NOTFOUND 
     add ebx,1 
     add eax,4 
     jmp .LOOP1 
.NOTFOUND: 
     neg eax 
     jmp .DONE 
.FOUND: 
     mov eax,ebx 
.DONE: 
pop ebx 
pop ecx 
pop edx 
ret 

阵列是：

; hashs for examples 
array: 
dd 33389990 
dd 1234567 
dd 81919191 
dd 938383737 
0 

Answer 1

的想法散列表是将值作为散列键的函数而不循环。

如果你能有一个永远不能返回一个值，你可以做这样的事情：

; first fill the hash table with values, and with invalid values for the rest. 
; for an example, I assume here hash table of 0x1000000h = 16777216d bytes. 
; 0xFFFFFFFFF marks no match and 0xFFFFFFFE marks hash collision. 

; first fill the hash table with "no match" values. 

    mov ecx,(16777216/4) 
    mov eax,0xFFFFFFFF 
    mov edi,hash_array 
    rep stosd 

; here set the values you want to return into the hash table. 
; for hash collisions write 0xFFFFFFFE, and handle hash collision in the 
; hash collision handling code. 

; here we have some hash function that outputs 123456d with some input string. 

编辑：中hash数组的起始地址可以在eax输入，所以它不是硬编码。

mov eax,hash_array    ; the start address of the hash array 
    mov ecx,123456     ; example hash 
    call @get_value_from_hash_table ; call to get the value from hash table 

    ... 

编辑：ecx必须以4被缩放如果散列值的双字。

@get_value_from_hash_table: 
    mov eax,[eax+4*ecx] 
    cmp eax,0xFFFFFFE 
    ja @no_match ; 0xFFFFFFFF ; no match 
    je @hash_collision  ; hash collision 

    ; match, no hash collisions, no jumps needed. 

    ... 

@hash_collision: 
    ; handle hash collision here, the best way depends on your data. 

    ... 

@no_match: 
    ; handle no match here. 

    ...