forum > Hash performance
Alexander Feb 28 at 09:08
How does Hash works when i'm trying to get an element? ( http://haxe.org/api/hash )
Does it iterate through all elements looking for provided key? Or does it use another algorithm?
Since i'm new to haxe, i don't know how to make performance tests for such things yet. So maybe someone can explain me how does hash work on different platforms? 8)
Justin L Mills Mar 01 at 15:19
Alexander Mar 01 at 19:38
Ok, thanx. I'll try
Mike Robinson Mar 16 at 18:42
The key idea of any hash-table implementation, in whatever language or language system, is that the key is transformed by some mathematical process into a number that permits only some subset of the table's total contents to be searched for in quest of a particular key. Once "the appropriate filing-cabinet drawer" has been chosen, the computer still must search through the contents of "that drawer," perhaps one-by-one, searching for an exact key match. But time is saved because it knows it doesn't have to search any other drawer in the same filing cabinet. You really can't make "blanket" statements about a hash-table, though, because actual performance depends entirely on the actual statistical distribution of the actual key-values at any particular time. The only thing you can say with any confidence is that, "it probably is an improvement, and likely to be a considerable improvement, over not using a hash table at all."
Mike Robinson Mar 16 at 18:44
... "and by the way, it's cheap." You get a lot of bang for the buck, most of the time, and at very minimal cost. Trees and other esoteric data structures require a lot more care-and-feeding (even if those duties are handled "for" you...).
ryan May 10 at 22:22
Hashes are good, but they come with the problem of collisions.
For a number of cases, Tries do the job much better: