I am coding a word-processing that there is so much array access(static array, no changes at run-time). I am hasing the string and then check if there is in my array(lookup). But what is a good implementation of it? I am doing by the simple way. Checking value per value if match to my hash input. Ideas to make it fastest?

I am currently checking:

if loop unroling will make really different.
if disorderly array is really slow than a sorted
I'II go to see if vectorization will be fine in this case.

do you recommend it? better,how do you implement this algorith?

here's current routine(it's returns into EAX the index of hash in array or a negative value,if don't any):



array is:



Thanks in advance.

I am on x86/32bit machine. Runnning Linux. But not really matter. The algorith has no(and shouldn't) OS-specific.

You should use the (hash_value mod array.size) as an index of the array instead of searching, that way you get O(1) access instead of the O(n) you have now.

If you have collisions you'll need to store in the array pointers to lists (or make each array entry hold several entries if that solves the issue). Also google for perfect hashing which is suitable for static arrays.

there are lot of ways to implement it. but essentially as Loco suggested.
a simple one
http://code.google.com/p/x64lab/source/browse/develop/ide/wspace.asm
line 2534 for utf-16 directory. you allocate the table on the stack, etc.etc, accordinng the number of bits you need (choos it carefully!)
look at the sdbm hash, good for general purpose.

here some macros i wrote (my improvement on it tested exstensively works without doubt better on labels L_00000, directory, and english dictionary)
http://code.google.com/p/x64lab/source/browse/develop/macro/mrk_macrow.inc
line 519,550

Cheers,

If you can't build hash tables, because of some reason, you can try to keep the array sorted and use binary search. It will speed the things up.

1) you're linearly scanning a table of hash values - you don't have a hash-table. O(n) lookup speed is bad.
2) checking for table end with byte(0) instead of dword(0) seems potentially dangerous.
3) as already mentioned, if your hash-table is static, you really should google perfect hashing - if it's suitable for your scenario, you get true O(1) lookups.
4) if for some reason you can't/won't do a true hash-table, at least sort the input values and use a binary search, that gives you O(log n) lookup speed (i.e. searching the entire DWORD space would require a worst-case of 32 iterations to find your item).

ths is becoming a very useful thread, i think it's time to post this instructional
links if i dint it yet, http://home.comcast.net/~bretm/hash/

Cheers,

I needed that for education!
I know "by guts" what is a hash, but this article going into much needed details.
Thanks.

http://reflector.webtropy.com/default.aspx/Net/Net/3@5@50727@3053/DEVDIV/depot/DevDiv/releases/whidbey/netfxsp/ndp/clr/src/BCL/System/Collections/Hashtable@cs/1/Hashtable@cs

The C#.NET HashTable source code is fairly educational. The Insert and ContainsKey methods especially.

reading above about the load factor, i would like to point out now that
collisions rate should be solved keeping this points as reference:

a) the hash function
b) the scheme
c) the context

a)
the hash function generate values from inputs.
those values may collide. here a graph, not much readable imho,
about how the function works:
http://www.fantasy-coders.de/projects/gh/html/x435.html


b)
the scheme is about the way you manage the table in memory,
because you have got some collisions coming from a good/bad a)
also deallocation/reallocation in order to increase/decrease/sort
free slots (buckets). this scheme for example,
http://en.wikipedia.org/wiki/Cuckoo_hashing
or linear probing

the focus here is on the birthday's paradox
http://en.wikipedia.org/wiki/Birthday_problem


c)
the context is the last but not least. because one thing is
hashing an english dictionary, one other thing is hashing
programmer's labels and symbols, where you may have
symbols like j,m,n,o,j1,j2 etc.
i cannot find the link of a valuable explanation about python using
a clever and elegant scheme on numbers and variables.
but here an implementation of the function:
http://stackoverflow.com/questions/793761/built-in-python-hash-function

Cheers,