0

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

我目前正在检查：

如果我使用循环展开，它会让这变得非常不同。如果我使用无序数组，它比有序数组慢很多。我会去看看在这种情况下矢量化是否会很好。

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

这是当前例程（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
4

1 回答 1

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.

编辑：哈希数组的起始地址可以输入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.

    ...
于 2013-02-18T22:00:05.507 回答