in reply to Hash and Array

If your question is, and I'm way out on a limb here trying to interpret your question:

Can you correctly describe a hash as being implemented an array of pointers internally

then the answer is a qualified "Yes and No":)

In essence, a hash consists of a (c-style) array of pointers, with each pointer leading to a structure that contains two further pointers. One pointing to the key for element, and the other to value. When an element is accessed, the characters that make up the key are munged (Tech. term:) mathematically by some algorithm to yield an index into the array. The pointer in this location leads to the structure and thence the value (and a copy of the key).

If the array where infinite in size, and the munging (hashing) algorithm were perfect, that would enough, but in the real world infinite arrays don't exist and hashing algorithms are imperfect except for special cases of highly tailored algorithms for specific, limited key sets., so the has to be extra logic, flags and pointers to deal with collisions.

See Gisle Aas' PerlGuts Illustrated for the most accessible description of perls internals I've encountered (you'll need to scroll down a ways or search for "RITER, EITER" to find the description of Perls hashes. It also includes a really excellent picture of their layout HV.PNG.

My apologies in advance if I misinterpreted your question, but a mention of PerlGuts Illustrated and Gisle's generosity in making it available is worth it anyway.

Examine what is said, not who speaks.
1) When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
2) The only way of discovering the limits of the possible is to venture a little way past them into the impossible
3) Any sufficiently advanced technology is indistinguishable from magic.
Arthur C. Clarke.

Replies are listed 'Best First'.
Re: Re: Hash and Array
by donno20 (Sexton) on Apr 28, 2003 at 03:44 UTC
    The idea strike to my mind when I encounter this 
    use Data::Dumper;
$hash{keya} ;
$hash{keyb} ;
$hash{keyc} ;

$hash{keya}{1} = "fooA";
$hash{keya}{2} = "barA";
$hash{keyb}{1} = "fooB";
$hash{keyb}{2} = "barB";
$hash{keyc}{1} = "fooC";
$hash{keyc}{2} = "barC";

print Dumper (\%hash);

__output__

$VAR1 = {
          'keya' => {
                      '1' => 'fooA',
                      '2' => 'barA'
                    },
          'keyb' => {
                      '1' => 'fooB',
                      '2' => 'barB'
                    },
          'keyc' => {
                      '1' => 'fooC',
                      '2' => 'barC'
                    }
        };

    [download]
    Let this is case 1. I assigned 2 values to each key (keya, keyb, keyc). Note that $hash{keya}{1} also a hash itself, so I supposed $hash{keya} is pointed to an array of pointers, which in turn pointed to $hash{keya}{1} and $hash{keyb}{2} respectively. And $hash{keya}{1} pointed to value "fooA" ultimately.
    However, in case 2, which I initialize hash like this: 
    use Data::Dumper;
$hash{keya} = "";
$hash{keyb} = "";
$hash{keyc} = "";

$hash{keya}{1} = "fooA";
$hash{keya}{2} = "barA";
$hash{keyb}{1} = "fooB";
$hash{keyb}{2} = "barB";
$hash{keyc}{1} = "fooC";
$hash{keyc}{2} = "barC";

print Dumper (\%hash);

__output__

$VAR1 = {
          'keya' => '',
          'keyb' => '',
          'keyc' => ''
        };

    [download]
    As you notice $hash (keya, keyb, keyc) is as its initialize value, not pointed to each {1} and {2} repectively. $hash{keya}{1} is still exist if you print it out. But $hash{keya} cannot access $hash{keya}{1} anymore.
    Hence I deduced that hash is an array of pointer. ^_^, up to here, I have no concrete evidence or proof, that why I put up my query here to ask for advice. Hope can share with you guys.
    Regards,
    donno20 ^_^
[reply]
[d/l]
[select]

      If you were using strict, you would see why the results from your second program is different from those of the first. 

      C:\test>type test.pl
#! perl -slw
use strict;
use Data::Dumper;

my %hash;

$hash{keya} = "";
$hash{keyb} = "";
$hash{keyc} = "";

$hash{keya}{1} = "fooA";
$hash{keya}{2} = "barA";
$hash{keyb}{1} = "fooB";
$hash{keyb}{2} = "barB";
$hash{keyc}{1} = "fooC";
$hash{keyc}{2} = "barC";

print Dumper (\%hash);

C:\test>test
Can't use string ("") as a HASH ref while "strict refs" in use at C:\t
+est\test.pl line 11.

      [download]

      In the first program, when you initialise the keys keya, keyb, and keyc in the %hash, you are implicitly initialising them to undef.

      In the second program, you are explicitly initialising them to a null string "".

      In the first, when you do

      $hash{keya}{1} = "fooA";

      you are attempting to assign a value to the key 1, in the anonymous hash that is pointed at by the reference held in the keya element of %hash, which doesn't exist! Whilst keya exists, it is set to undef.

      Seeing this, the compiler does the DWIM that perl does so well, and decides to autovivify (create implicitly), an anonymous hash, with a key of 1, assign "fooA" to that key, and then assign a reference to that anonymous hash as the value of $hash{keya}.

      Result: It did what you thought it would do, even though it did much more than you probably thought in order to do it.

      However, in the second program, when perl encounters the same line, it discovers that not only does the keya key exists in %hash, but that the value of that key is already set (to a null string).

      At this point, it knows that it can neither use that null string as a reference to an anonymous hash (hence the error listed under strict) nor can it legitimately overwrite the null string with a reference to an anonymous hash as that would be implicitly destroying the value that you had explicitly assigned.

      With strict enabled, it not only refuses to overwrite your explicitly assigned data, it yells that it has done so.

      Without strict, it still doesn't do the assignment, but just doesn't say anything. You didn't ask it to tell you, so it assumes that you know what you are doing and keeps stum.

      The net result is that in the second program, lines 6 through 11 do absolutely nothing.

      Examine what is said, not who speaks.
      1) When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
      2) The only way of discovering the limits of the possible is to venture a little way past them into the impossible
      3) Any sufficiently advanced technology is indistinguishable from magic.
      Arthur C. Clarke.
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom