hash table

[Kevin_Price]

Here's an llb of a version of my hash table (LV v7.1).  You'll have to decide for yourself if it's worth the effort to decipher -- it's only sparsely commented.

-Kevin P.

[DFGray]

A better solution is two 1D arrays - one containing your key and the other your value.  Using 1D arrays allows you to efficiently search for your key using the Search 1D Array primitive.  The output of this then allows you to rapidly index your value.  If the search doesn't find anything, you also know that (get a -1 output from the search) and can take appropriate action.  You can modify the two arrays fairly easily with the array VIs.  If you will be modifying the hash table, don't store it in a global.  Race conditions can cause you all sorts of problems.  Use a LV2 style global (probably best for this type of problem) or a single element queue.

Note that Kevin's example above is a LV2 style global.

Message Edited by DFGray on 08-28-2006 08:47 AM

[Kevin_Price]

Yeah, 'Search 1D Array' is pretty quick, but on average you'll have to look at 1/2 the array elements before you find the one you're looking for.  With hashing, you'll have to perform the hash computation, but can then generally index straight to the corresponding element.  In the event of the occasional hash "collision" (two different input strings map to the same numeric hash value), you'll look at another element or two.

The tradeoff is to compare the time needed to index and compare many array elements vs. the time needed to compute a hash value (and the non-negligible difficulty of implementing the additional code).  Hashing mainly becomes attractive for large collections where lookup time needs to be optimized.

I tend to think of hashing as applying primarily to strings, but with a little creativity it could also be applied to other chunks of bytes such as custom cluster datatypes.  Hmmmm....

-Kevin P.

[DFGray]

I've always been too lazy to create a real hash table, but since you conveniently provided one, I might try some benchmarks.  I have never created a list large enough to make the extra code worth the effort (I don't think - the benchmarks will tell).  Thanks for the code!

[Odd_Modem]

I think this vi might show that variant attribute lookups exhibit hash table-esque performance. I varied the table size from 10K members to 100K members and the average lookup time varied from 4us to 6us. Personally, I just use it as a hash table regardless of the performance, since it is a tool for solutions.