LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Is using a variant variable the best way, or a good one, to implement the C++ hash map type?

Solved!
Go to solution

Hello,

 

I was searching a method to use a hash map in labview to improve the computing time of my program. Since there isn't a hash map object in labview I've used a variant as a map. Is this a good way to do it?

 

Thanks in advanced!

0 Kudos
Message 1 of 3
(5,738 Views)
Solution
Accepted by topic author marccj

Please read point 5 in the following link: http://zone.ni.com/devzone/cda/pub/p/id/1495


CLA CTAChampionI'm attending the GLA Summit!
Subscribe to the Test Automation user group: UK Test Automation Group
0 Kudos
Message 2 of 3
(5,735 Views)

It totally depends on the use-case. If the use case would be that you have a large finit set of elements I would say no. The only thing you need is a good hashing algorithm to compute the hash. Further you need to tackle how you handle hashing collisions.

 

From the link:

Many applications require that large datasets be stored such that individual elements can quickly be retrieved using a unique identifier—this is commonly known as a lookup table, hash table, or map. A simple array is often used for this purpose, but retrieving a value can be an inefficient process, as it requires a linear search through the array.

 

This statement is just plain wrong, because retrieving a value from a array implemented as a hash table does not take a linear search, O(n), you only need to compute the index from where the value is stored which can be done in constant time, O(1), however taking collisions into acount this gives you a average of O(1 + n/k), where k is the size of the hash table. When n approaches k more hash collisions will occure. When n = k then the hash table is full. When n > k you have overflow, but you can still solve this using several approaches, http://en.wikipedia.org/wiki/Hash_table#Collision_resolution. You are however right that at some point when n approaches k that more and more collisions will ocure and finaly will surpase the timing of a array implemented as a red-black tree, variant, which has a average timing of O(log n).

 

When you know the array size will be a fixed size, n, or around n a hash table is very very usefull. A good rule of thumb is then to choose a array size of n*2. Further when all the keys (not to confuse with index, index != key) are know beforehand you can implement perfect hashing enabling constant time lookup.

0 Kudos
Message 3 of 3
(5,719 Views)