http://www.perlmonks.org?node_id=996977


in reply to Hash tables, are they really what we see?

To a very large extent just let Perl do its thing. Stuff that programmers do often Perl has been optimised to do fast. Almost always a list or tree in other languages is a solution to an intermediate problem which you can solve directly using Perl's hash or dynamic array structures.

A Perl hash is an associative array which stores values that are accessed using keys. Under the hood the key turns into a "hash" (hence the name of the structure) which Perl is very quick at looking up. The whole point of a hash type data structures is that the lookup is fast (due to the hash magic) and finding something isn't there is just as fast as finding it is there. The time in both cases is essentially a small constant time. The trick is that the key gets turned by a hashing function into an index into a hash table so (simplifying greatly) the time to find (or not find) an entry is the time the hash function takes plus the time to index into the table - a short and almost constant time. Hashes are generally the answer to problems you might solve using trees in other languages.

Perl is very time efficient at managing dynamic arrays that can be easily used in the ways you might want to use linked lists. In particular Perl's arrays are fast for adding and removing blocks of elements at each end and are pretty fast for adding and removing blocks of elements elsewhere in arrays. Under the hood Perl does clever stuff with linked lists, but you don't need to know that.

True laziness is hard work

Replies are listed 'Best First'.
Re^2: Hash tables, are they really what we see?
by heatblazer (Scribe) on Oct 03, 2012 at 06:29 UTC

    Thank you for the reply. I`ll let it as it is.