Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

Re: why use a hash instead of an array

by davido (Archbishop)
on Jun 11, 2013 at 18:57 UTC ( #1038325=note: print w/replies, xml ) Need Help??

in reply to why use a hash instead of an array

Hashes provide constant time lookups by key as opposed to constant time lookups by index. Imagine if your dictionary were 0: Apple, 1: Ball, 2: Cat, 3: Dog. Find the word at index #2. That's done in constant time. Now find for me Cat. You have to either do a linear search, or a binary search to find it (linear time, or log2(n) time. You would never remember that 4200 is Quagmire, so you end up doing time-consuming searches a lot.

Now let's organize your dictionary like this: "Apple: A fruit. Ball: A toy. Cat: A skittish animal. Dog: A loyal animal. ..... Quagmire: A difficult situation". Quick, find if Quagmire is in the dictionary. Wow, we just did it in constant time (no searching), using a hash.

That turns out to be really, REALLY useful. We're not always just looking up words in dictionaries. We're referring to attributes in objects, we're manipulating sets, we're memoizing and caching, and we're even implementing variable systems (Perl's package globals reside in a glorified hash, internally).

In computer science one would look at hashes as yet another datastructure. And for many problems, selecting the right data structure is 9/10ths of the solution. As you get into programming, I recommend getting a good introductory book on data structures and algorithms. I wish I had a suggestion for you. Mastering Algorithms with Perl is probably a little advanced at this point, and it's getting a little old too. But start looking at, well, what is an array, and what are its characteristics? What is a linked list, and what are its characteristics? Binary Tree, Hash, and so on.


Replies are listed 'Best First'.
Re^2: why use a hash instead of an array
by AnomalousMonk (Chancellor) on Jun 12, 2013 at 01:55 UTC

    While it is aimed, I think, more at the intermediate programmer, chromatic's freely downloadable Modern Perl might be a good beginners intro to Perl. And while I can't recommend Wikipedia as a beginners resource because it gets rather CS-ish rather quickly, all the topics davido mentioned and more are there and may serve as useful points of departure to more accessible on-line resources: array; linked list; binary tree; hash, or associative array; ...

    And you are always welcome at The Monastery Gates.

Re^2: why use a hash instead of an array
by DarrenSol (Acolyte) on Jun 13, 2013 at 15:01 UTC
    jeez. i did a web search and went through a number of the pages that came up, but didn't find a reason why to use a hash that's as quick and clear as your quagmire example. thanks.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1038325]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (9)
As of 2017-09-19 20:54 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (229 votes). Check out past polls.