simple pointer operations (newbe)

Discussion in 'Perl Misc' started by Dirk Lehmann, Feb 25, 2006.

  1. Dirk Lehmann

    Dirk Lehmann Guest

    Hello,

    In the following example I like to print out the array (@$b). But it don't
    works. Perl don't like converting the scalar (after incrementation) to a
    reference. How can I cast the scalar to a reference? (I know that their are
    other possibilities around to print out an array for this example.)

    ######
    use strict;

    my $b = [reverse(10..15)];
    my $buf = \($b->[0]);
    for(0..$#$b)
    {
    print "\$buf points to address $buf and their is $$buf\n"; #line 14 in
    runtime error
    $buf++;
    }
    ######

    output:
    ------
    $buf points to address SCALAR(0x22531c) and their is 15
    Can't use string ("2249501") as a SCALAR ref while "strict refs" in use at
    /home/[...]/Pointer2.pl line 14.
    ------

    Thanks, Dirk.
     
    Dirk Lehmann, Feb 25, 2006
    #1
    1. Advertising

  2. "Dirk Lehmann" <-berlin.de> wrote in
    news:dtpopf$5et$02$-online.com:

    > Subject: simple pointer operations (newbe)


    Perl is not C. No pointers. Just references.

    > How can I cast the scalar to a reference?


    You should not even want to.

    > (I know that their are other possibilities around to print
    > out an array for this example.)


    Then use those methods.

    > ######
    > use strict;


    use warnings;

    missing.

    Sinan
    --
    A. Sinan Unur <>
    (reverse each component and remove .invalid for email address)

    comp.lang.perl.misc guidelines on the WWW:
    http://mail.augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html
     
    A. Sinan Unur, Feb 25, 2006
    #2
    1. Advertising

  3. Dirk Lehmann

    Dirk Lehmann Guest

    "A. Sinan Unur" <> wrote in
    news:Xns977562F4C4479asu1cornelledu@127.0.0.1...
    > "Dirk Lehmann" <-berlin.de> wrote in
    > news:dtpopf$5et$02$-online.com:
    >
    >> How can I cast the scalar to a reference?

    >
    > You should not even want to.
    >


    Yes, I know that it is very critical to 'play' with pointers on this way ;)

    >
    >> ######
    >> use strict;

    >
    > use warnings;
    >


    It wasn't the complete code:

    ######
    #!/usr/local/bin/perl -w

    use strict;

    my $a = \12345;
    print "\$a points to address $a and their is $$a\n\n";

    my $b = [reverse(10..15)]; #equal to '$b = \(reverse(10..15))'
    print "\$b points to address $b and their is (@$b)\n";
    print "output with pointer operations:\n";
    my $buf = \($b->[0]);
    for(0..$#$b)
    {
    print "\$buf points to address $buf and their is $$buf\n";
    $buf++;
    }
    ######

    Sorry for my bad english,
    Dirk.
     
    Dirk Lehmann, Feb 25, 2006
    #3
  4. A. Sinan Unur wrote:
    > "Dirk Lehmann" <-berlin.de> wrote in
    > news:dtpopf$5et$02$-online.com:
    >
    > > How can I cast the scalar to a reference?

    >
    > You should not even want to.


    Just to expand on that it should be pointed out that (amongst several
    of things) Perl's arrays are of dynamic size. This means the storage of
    elements cannot be contiguous[1] in memory so even if you do drop into
    C and fiddle directly with an SV* (which is perfectly possible) then
    you still couldn't do pointer arithmetic to get from one element of an
    array to another.

    [1] They could be if they were relocatable, but then you couldn't
    meaningfully have pointers to them at all!
     
    Brian McCauley, Feb 25, 2006
    #4
  5. Dirk Lehmann

    Anno Siegel Guest

    Dirk Lehmann <-berlin.de> wrote in comp.lang.perl.misc:
    > "A. Sinan Unur" <> wrote in
    > news:Xns977562F4C4479asu1cornelledu@127.0.0.1...
    > > "Dirk Lehmann" <-berlin.de> wrote in
    > > news:dtpopf$5et$02$-online.com:
    > >
    > >> How can I cast the scalar to a reference?

    > >
    > > You should not even want to.
    > >

    >
    > Yes, I know that it is very critical to 'play' with pointers on this way ;)


    It's not critical, it's nonsense.

    When you increment a reference, Perl uses the reference address as an
    integer and increments that. If you were to re-interpret the incremented
    number as a memory address, that wouldn't even be correctly aligned on most
    machines. In any case it points to a random place in memory, there is
    no way of predicting what will be found there.

    Anno
    --
    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.
     
    Anno Siegel, Feb 25, 2006
    #5
  6. Dirk Lehmann

    Dirk Lehmann Guest

    "Brian McCauley" <> wrote in
    news:...
    >
    > A. Sinan Unur wrote:
    >> "Dirk Lehmann" <-berlin.de> wrote in
    >> news:dtpopf$5et$02$-online.com:
    >>
    >> > How can I cast the scalar to a reference?

    >>
    >> You should not even want to.

    >
    > Just to expand on that it should be pointed out that (amongst several
    > of things) Perl's arrays are of dynamic size. This means the storage of
    > elements cannot be contiguous[1] in memory so even if you do drop into
    > C and fiddle directly with an SV* (which is perfectly possible) then
    > you still couldn't do pointer arithmetic to get from one element of an
    > array to another.
    >


    Oooh, okay. I didn't know it.

    Thanks to all,
    Dirk.
     
    Dirk Lehmann, Feb 25, 2006
    #6
  7. "Dirk Lehmann" <-berlin.de> wrote in
    news:dtpr2b$cvo$01$-online.com:

    > "A. Sinan Unur" <> wrote in
    > news:Xns977562F4C4479asu1cornelledu@127.0.0.1...
    >> "Dirk Lehmann" <-berlin.de> wrote in
    >> news:dtpopf$5et$02$-online.com:
    >>
    >>> How can I cast the scalar to a reference?

    >>
    >> You should not even want to.
    >>

    >
    > Yes, I know that it is very critical to 'play' with pointers on this
    > way ;)


    Smiley notwithstanding, you missed my point about there not being any
    pointers in Perl. Only references.

    >>> ######
    >>> use strict;

    >>
    >> use warnings;
    >>

    >
    > It wasn't the complete code:
    >
    > ######
    > #!/usr/local/bin/perl -w
    >
    > use strict;
    >
    > my $a = \12345;
    >
    > print "\$a points to address $a and their is $$a\n\n";


    $a is now a reference. When you dereference it, you get the value it
    references. $a is not a pointer.

    > my $b = [reverse(10..15)]; #equal to '$b = \(reverse(10..15))'
    > print "\$b points to address $b and their is (@$b)\n";


    $b does not point to an address. It references the specific anonymous
    array you have created. Not to any of its elements, including the first
    element. Perl is not C.

    Sinan

    --
    A. Sinan Unur <>
    (reverse each component and remove .invalid for email address)

    comp.lang.perl.misc guidelines on the WWW:
    http://mail.augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html
     
    A. Sinan Unur, Feb 25, 2006
    #7
  8. Anno Siegel <-berlin.de> wrote:
    > Dirk Lehmann <-berlin.de> wrote in comp.lang.perl.misc:
    >> "A. Sinan Unur" <> wrote in
    >> news:Xns977562F4C4479asu1cornelledu@127.0.0.1...
    >> > "Dirk Lehmann" <-berlin.de> wrote in
    >> > news:dtpopf$5et$02$-online.com:
    >> >
    >> >> How can I cast the scalar to a reference?
    >> >
    >> > You should not even want to.
    >> >

    >>
    >> Yes, I know that it is very critical to 'play' with pointers on this way ;)

    >
    > It's not critical, it's nonsense.



    I assumed Dirk didn't get the translation to English quite right.

    I think he meant to say:

    I know that it is often criticized to 'play' with pointers this way.

    ie. he realizes the pitfalls of pointer arithmetic.



    Dirk,

    The way you said it might well be taken to mean:

    I know that it is essential to 'play' with pointers on this way

    Which is the meaning that I think prompted Anno's followup here.


    --
    Tad McClellan SGML consulting
    Perl programming
    Fort Worth, Texas
     
    Tad McClellan, Feb 25, 2006
    #8
  9. Dirk Lehmann wrote:
    > Hello,
    >
    > In the following example I like to print out the array (@$b). But it
    > don't works. Perl don't like converting the scalar (after
    > incrementation) to a reference.


    A reference _is_ a scalar already.

    > How can I cast the scalar to a
    > reference?


    Perl does not have casting. I think you are confusing programming languages.
    Perl references are much more advanced than pointers in those other
    languages and you don't do arithmetic on them.

    jue
     
    Jürgen Exner, Feb 25, 2006
    #9
  10. Dirk Lehmann wrote:
    > "A. Sinan Unur" <> wrote in
    > news:Xns977562F4C4479asu1cornelledu@127.0.0.1...
    >> "Dirk Lehmann" <-berlin.de> wrote in
    >> news:dtpopf$5et$02$-online.com:
    >>
    >>> How can I cast the scalar to a reference?

    >>
    >> You should not even want to.
    >>

    >
    > Yes, I know that it is very critical to 'play' with pointers on this
    > way ;)


    No, it is not critical.
    It is dangerous and plain stupid and therefore Perl doesn't support it.

    > my $a = \12345;
    > print "\$a points to address $a and their is $$a\n\n";


    References are not memory addresses and memory addresses are not references.
    Either get used to that or use a more low-level programming language where
    the programmer may be able to access the memory via pointers directly but in
    return is forced to implement all memmory allocation and garbage collection
    himself.

    jue
     
    Jürgen Exner, Feb 25, 2006
    #10
  11. Dirk Lehmann

    Dirk Lehmann Guest

    "Abigail" <> wrote in
    news:...
    > Dirk Lehmann (-berlin.de) wrote on MMMMDLXI September MCMXCIII
    > in <URL:news:dtpr2b$cvo$01$-online.com>:
    > :)
    > :) It wasn't the complete code:
    > :)
    > :) ######
    > :) #!/usr/local/bin/perl -w
    > :)
    > :) use strict;
    > :)
    > :) my $a = \12345;
    > :) print "\$a points to address $a and their is $$a\n\n";
    > :)
    > :) my $b = [reverse(10..15)]; #equal to '$b = \(reverse(10..15))'
    >
    > Eh, no.
    >
    > $ perl -wle '$b = [reverse (10 .. 15)]; print ref $b'
    > ARRAY
    > $ perl -wle '$b = \(reverse (10 .. 15)); print ref $b'
    > SCALAR
    >
    >
    >
    > Once again, Perl has references. Not pointers. And while the
    > stringification of a reference of an array contains a memory address,
    > and that memory address is indeed the address of the array, it's NOT the
    > address of the first element. It's the address of a struct (the array)
    > of which one element points to an array of pointers of structures
    > containing scalars.
    >
    > Perl is not C.
    >


    Okay, I think that I should learn much more about the differences between a
    pointer and a reference. I'm just at the beginning to understand references
    because the most introductions to Perl let references shown like a pointer
    and don't tell the reader what are the differences.

    Thanks and sorry for my bad english again,
    Dirk.
     
    Dirk Lehmann, Feb 25, 2006
    #11
  12. Dirk Lehmann wrote:
    > Okay, I think that I should learn much more about the differences
    > between a pointer and a reference. I'm just at the beginning to
    > understand references because the most introductions to Perl let
    > references shown like a pointer


    Which actually is correct. References do point to thingies, so they are
    pointers.

    > and don't tell the reader what are
    > the differences.


    Which only becomes a problem if you make assumptions based on you previous
    experience in other programming languages where "pointer" has a different
    and unfortunately overlapping meaning.

    It's like on airplanes the rudder and therefore stearing on the ground is
    controlled by foot pedals. Now, don't try to push the right pedal to make a
    right turn when you are in a car.

    jue
     
    Jürgen Exner, Feb 25, 2006
    #12
  13. Dirk Lehmann

    Dirk Lehmann Guest

    "Tad McClellan" <> wrote in
    news:...
    > Anno Siegel <-berlin.de> wrote:
    >> Dirk Lehmann <-berlin.de> wrote in comp.lang.perl.misc:
    >>> "A. Sinan Unur" <> wrote in
    >>> news:Xns977562F4C4479asu1cornelledu@127.0.0.1...
    >>> > "Dirk Lehmann" <-berlin.de> wrote in
    >>> > news:dtpopf$5et$02$-online.com:
    >>> >
    >>> >> How can I cast the scalar to a reference?
    >>> >
    >>> > You should not even want to.
    >>> >
    >>>
    >>> Yes, I know that it is very critical to 'play' with pointers on this way
    >>> ;)

    >>
    >> It's not critical, it's nonsense.

    >
    >
    > I assumed Dirk didn't get the translation to English quite right.
    >
    > I think he meant to say:
    >
    > I know that it is often criticized to 'play' with pointers this way.
    >
    > ie. he realizes the pitfalls of pointer arithmetic.
    >
    >
    >
    > Dirk,
    >
    > The way you said it might well be taken to mean:
    >
    > I know that it is essential to 'play' with pointers on this way
    >
    > Which is the meaning that I think prompted Anno's followup here.
    >
    >


    Ooh sorry,

    I surveyed this posting.

    I meant: I know that it is dangerous to use the pointer arithmetic because
    if you do a wrong calculation or do not check if you have left your data
    structure, you can points outside this. And it's very dangerous if an user
    overwrite items in your stack, for example a return-address! That's what I
    mean.

    But, now I know that you don't have this problem in Perl. ;)

    Dirk.
     
    Dirk Lehmann, Feb 25, 2006
    #13
  14. Dirk Lehmann wrote:
    > Okay, I think that I should learn much more about the differences between
    > a pointer and a reference. I'm just at the beginning to understand
    > references because the most introductions to Perl let references shown
    > like a pointer and don't tell the reader what are the differences.


    Hi,
    I'm pretty new to Perl but here's how I've understood this reference Vs
    pointer question:
    It is quite a common question and there are often misconceptions between the
    two. A friend of mine heavily disliked a particular language because not
    knowing references, he thought that the lack of pointers would be cripling
    (i.e. no linked lists or function pointers, for instance).

    Maybe it would help to think of references as a restricted form of pointers.
    Just like a pointer a reference points to an address in memory and in Perl
    has a type i.e. a reference to a scalar, array, hash or subroutine, for
    example. Again like pointers you can ask something for its memory address
    and assign this address to a reference. Given another reference you can also
    de-reference it get the thingy to which the reference is pointing, though
    you'll need to explicitly specify the dereferenced type you're expecting to
    get out. Other operations for references include the equality comparison,
    seeing if they point to the same thing, and asking for the type of the
    reference with the ref function. Stringgification of memory addresses to
    which the references point is also possible, but its only use seems to be as
    hash keys. Technically references like strings and numbers are one kind of
    scalar in addition to numbres and strings.

    Unlike pointers references don't support address arithmetic and when you
    come to think of it it is not truely necessary, either. But then again, you
    can index to an array of references, rather than dangerously dealing with
    the raw memory addresses. Similarly, in stead of using statically defined
    structs as in C, you've got the more dynamic hashtables, and references to
    hashes can easily be put in an array or a hash as values, for that matter.
    Lastly, note that unlike in C, the array notation is not simply syntactic
    sugar for pointer arithmetic.

    Hope this helps.

    --
    With kind regards Veli-Pekka Tätilä ()
    Accessibility, game music, synthesizers and programming:
    http://www.student.oulu.fi/~vtatila/
     
    Veli-Pekka Tätilä, Feb 26, 2006
    #14
  15. Abigail wrote:
    <snip>
    > You'r not doing anyone learning about references a favour by telling them
    > a reference has anything to do with memory locations. That's just an
    > implementation detail - one that could in principle change, without having
    > it any effect on the language level.

    Hmm now that I think of what you said, quite right. The reason why I started
    talking about memory addresses is that I didn't think abstractly enough and
    actually encountered pointers before references. So I often still think of
    references mostly as a neat subset of pointer functionality, my bad I guess.
    Conceptually, though, neither the concept of a memory address nor the size
    of the element to which you are refering to matters much as there's no
    arithmetic. Knowing that there are some similarrities between pointers and
    references might or might help the confused OP, I'm not sure.

    One question on references, even though it comes down to yet another
    implementation detail, <grin>:
    I said earlier that they support equality comparisons. Is the real memory
    address checked when you use the equals operator or does it simply compare
    the references after stringification? Does it matter, in case of references,
    whether the equals operator is numerical or string based? I'm a bit confused
    here myself, oh well.

    --
    With kind regards Veli-Pekka Tätilä ()
    Accessibility, game music, synthesizers and programming:
    http://www.student.oulu.fi/~vtatila/
     
    Veli-Pekka Tätilä, Feb 26, 2006
    #15
  16. Dirk Lehmann

    Anno Siegel Guest

    Abigail <> wrote in comp.lang.perl.misc:
    > Veli-Pekka Tätilä () wrote on MMMMDLXII
    > September MCMXCIII in <URL:news:dtt66s$4sn$>:


    [comparing references]

    > Yes and no. If you do a numeric compare, it compares memory addresses.
    > If you do a string compare, it compares the stringification. But that
    > doesn't really matter, in both cases, (in the absense of overload magic)
    > the result is true if, and only if the references are the same.
    >
    > If overload magic is present, all bets are off.


    Just blessing has an effect on stringification, even without overloading.
    Thus, through hash key stringification

    $hash{ $ref} = 1;
    bless $ref, 'gaga';
    $hash{ $ref};

    will access an undefined value unless $ref was blessed into "gaga" to
    begin with.

    It is true that a string comparison of two references is true if and only
    if the references are the same. The strings that are compared may not be
    the same each time.

    Anno
    --
    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.
     
    Anno Siegel, Feb 26, 2006
    #16
  17. Re: References as Hash Keys (Newbie) (Was: simple pointer operations (newbe))

    Anno Siegel wrote:
    <snip>
    > It is true that a string comparison of two references is true if and only
    > if the references are the same.

    I thought so, too, when stringification enters the picture they can be equal
    only when their types and addresses are exactly the same. But still, hmm,
    you cannot have references to two different types pointing to the same
    memory address, of course, so on second thought the address is a unique key
    alone.

    > The strings that are compared may not be the same each time.

    Is this because of possible garbage collection, or scalars growing or
    shrinking automagically? Hmm speaking of hash keys, my understanding based
    on some other languages is that they must depend on the object's state to be
    able to work consistantly. But if you use a stringified memory address and
    the address changes later on independent of the blessed thing's state, you
    cannot just dereference the same blessed thingy to reuse it as a key in
    indexing. Many other languages let you freely use objects or whatever else
    you like as hash keys. ARe there any workarounds for Perl? One possibility
    that came to mind would be to use Data::Dumper and compute a hash value
    based on the object's state. Can I somehow access Perl's internal hashing
    function for keys to hash my own data, similar to Java's hashCode method?

    I do realize Perl is not the same as Java, far from it. Still browsing the
    docs for the hashCode method for the Object class, I noticed this contract
    for hashing which might be widely applicable. Quoting JDK 5.0:

    - Whenever it is invoked on the same object more than once during an
    execution of a Java application, the hashCode method must consistently
    return the same integer, provided no information used in equals comparisons
    on the object is modified. This integer need not remain consistent from one
    execution of an application to another execution of the same application.

    Interesting, so the internal state may change and you're allowed to return
    the same hash code as long as the equality of the object, as far as the user
    goes, is not altered. Maybe my suggestion about simply dumping the blessed
    thingy's internals isn't wise after all.

    - If two objects are equal according to the equals(Object) method, then
    calling the hashCode method on each of the two objects must produce the same
    integer result.

    - It is not required that if two objects are unequal according to the
    equals(java.lang.Object) method, then calling the hashCode method on each of
    the two objects must produce distinct integer results. However, the
    programmer should be aware that producing distinct integer results for
    unequal objects may improve the performance of hashtables.

    Hmmm don't these last two statements contradict each other? At least on an
    initial read, the first seems to say that if two objects of the same Class
    return the same boolean for equals, you must return the same hash codes.
    However, the second one effectively mitigates the first by saying that if
    they produce different boolean values for equals, they don't have to produce
    different hashcodes. So as far as I can see, you cannot tell based on the
    hash code whether two objects are equal. The hash codes can be the same if
    they are and they can still be the same if they aren't. What's the use of
    being able to use objects as hash keys then? Perhaps I'm again missing
    something fundamental here.

    --
    With kind regards Veli-Pekka Tätilä ()
    Accessibility, game music, synthesizers and programming:
    http://www.student.oulu.fi/~vtatila/
     
    Veli-Pekka Tätilä, Feb 27, 2006
    #17
  18. Re: References as Hash Keys, Tree Structures (Newbie)

    Also sprach Uri Guttman:

    >>>>>> "TvP" == Tassilo v Parseval <> writes:

    >
    > TvP> Also sprach Veli-Pekka Tätilä:
    >
    > >> Umm yes, the equals method in the Java example applies to the
    > >> object to be hashed but the hash code returned by that object is
    > >> used as the index. Which naturally leads to the question, what are
    > >> hashed objects as keys good for if anything? So far I haven't been
    > >> able to think of any real good uses.

    >
    > TvP> Nowadays they are commonly used for the implementation of
    > TvP> inside-out objects. Whenever you want to associate some
    > TvP> additional data with an object, the ability to use it as hash-key
    > TvP> is useful.
    >
    > i use refs as hash keys in several places. one is to track a set of refs
    > where you want to be able to add/delete them. these are usually objects
    > but there is no reason they couldn't be regular refs. an example is an
    > event loop where you need to track live events and be able to find them
    > all. a hash of those objects as key and value is perfect for that.


    Interesting that you mention this scenario because this usage (keeping
    track of events and associated objects) was the very one I came across
    just recently. They used it for debugging purpose to see if any objects
    leaked which can be a pain to figure out in event-based programming.
    They used a weakened hash lest they interfere with the garbage
    collecting.

    > so just because someone can't see a good reason to use a certain idiom
    > doesn't mean they don't exist.


    Certainly not. :)

    > and i wouldn't call them hashed objects. a hash of objects (or refs) is
    > probably clearer and definitely more accurate.


    It's both ambiguous as 'hash' can mean the data-type (in Perl at least)
    or it can mean the return value of the hashing function applied to the
    object. I think we're both referring to the latter.

    Tassilo
    --
    use bigint;
    $n=71423350343770280161397026330337371139054411854220053437565440;
    $m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);
     
    Tassilo v. Parseval, Feb 27, 2006
    #18
  19. Dirk Lehmann

    Anno Siegel Guest

    Brian McCauley <> wrote in comp.lang.perl.misc:
    >
    > A. Sinan Unur wrote:
    > > "Dirk Lehmann" <-berlin.de> wrote in
    > > news:dtpopf$5et$02$-online.com:
    > >
    > > > How can I cast the scalar to a reference?

    > >
    > > You should not even want to.

    >
    > Just to expand on that it should be pointed out that (amongst several
    > of things) Perl's arrays are of dynamic size. This means the storage of
    > elements cannot be contiguous[1] in memory so even if you do drop into
    > C and fiddle directly with an SV* (which is perfectly possible) then
    > you still couldn't do pointer arithmetic to get from one element of an
    > array to another.


    That isn't true.

    A Perl array (see below) contains a C array (xav_alloc) that stores
    pointers (AV*) to the array elements. That C array is always contiguous
    (C doesn't have any other). If a (Perl-) array is extended, in general
    the C array must be copied to a new location. Pointer arithmetic on
    the array is entirely possible.

    Anno

    struct xpvav {
    char* xav_array; /* pointer to first array element */
    SSize_t xav_fill; /* Index of last element present */
    SSize_t xav_max; /* max index for which array has space */
    IV xof_off; /* ptr is incremented by offset */
    NV xnv_nv; /* numeric value, if any */
    MAGIC* xmg_magic; /* magic for scalar array */
    HV* xmg_stash; /* class package */

    SV** xav_alloc; /* pointer to beginning of C array of SVs */
    SV* xav_arylen;
    U8 xav_flags;
    };


    --
    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.
     
    Anno Siegel, Feb 27, 2006
    #19
  20. Re: References as Hash Keys (Newbie) (Was: simple pointer operations (newbe))

    Also sprach Veli-Pekka Tätilä:

    > I do realize Perl is not the same as Java, far from it. Still browsing the
    > docs for the hashCode method for the Object class, I noticed this contract
    > for hashing which might be widely applicable. Quoting JDK 5.0:


    [...]

    > - If two objects are equal according to the equals(Object) method, then
    > calling the hashCode method on each of the two objects must produce the same
    > integer result.
    >
    > - It is not required that if two objects are unequal according to the
    > equals(java.lang.Object) method, then calling the hashCode method on each of
    > the two objects must produce distinct integer results. However, the
    > programmer should be aware that producing distinct integer results for
    > unequal objects may improve the performance of hashtables.
    >
    > Hmmm don't these last two statements contradict each other? At least on an
    > initial read, the first seems to say that if two objects of the same Class
    > return the same boolean for equals, you must return the same hash codes.
    > However, the second one effectively mitigates the first by saying that if
    > they produce different boolean values for equals, they don't have to produce
    > different hashcodes. So as far as I can see, you cannot tell based on the
    > hash code whether two objects are equal. The hash codes can be the same if
    > they are and they can still be the same if they aren't. What's the use of
    > being able to use objects as hash keys then? Perhaps I'm again missing
    > something fundamental here.


    You are blurring the distinction between the key that is to be hashed
    and the result of this hashing, namely the hash code.

    You can build a hash where all keys are projected onto the same hash
    code and yet the hash remains functional. This is just going to be a
    terribly inefficient hash as each new key inserted produces a collision.

    Think of a hash as an array where a key/value pair is stored inside one
    of the array's element. Which element is going to be used is determined
    by the hash code. If a collision occurs because two different keys
    produce the same hash code, then some method of resolving this collision
    must be used. Usually, the array's elements are linked lists so that on
    each collision a new pair is pushed onto this list.

    A simple hash implemented in Perl would look like this:

    package Hash;

    use constant HASH_SEED => 1;

    sub hash {
    my ($self, $key) = @_;
    my $hc = HASH_SEED;
    $hc ^= ord $_ for split //, $key;
    return $hc % @$self;
    }

    sub new {
    my ($class, $size) = @_;
    my @ary; $#ary = ($size || 4) - 1;
    return bless \@ary => $class;
    }

    sub store {
    my ($self, $key, $value) = @_;
    my $code = $self->hash($key);

    # collision: check if key is already in hash
    if ($self->[$code]) {
    for (@{ $self->[$code] }) {
    if ($_->{key} eq $key) {
    # key in the hash: update value
    $_->{val} = $value;
    return;
    }
    }
    }
    # not yet in the hash
    push @{ $self->[$code] }, { key => $key, val => $value };
    }

    sub get {
    my ($self, $key) = @_;
    my $code = $self->hash($key);
    return if ! $self->[$code];
    for (@{ $self->[$code] }) {
    return $_->{val} if $_->{key} eq $key;
    }
    }

    It's not terribly smart as the array for the key/value pairs is never
    resized so the more elements you put in the slower it will get. And you
    can now use a hash with only two buckets and yet store an arbitrary
    amount of key/value pairs in them:

    use Data::Dumper;

    my $hash = Hash->new(2);

    my $c = 0;
    for (qw/foo bar 123 bla 567/) {
    $hash->store($_, $c++);
    }

    for (qw/foo bar 123 bla 567/) {
    print $hash->get($_), "\n";
    }

    print Dumper $hash;
    __END__
    foo => 0
    bar => 1
    123 => 2
    bla => 3
    567 => 4
    $VAR1 = bless( [
    [
    {
    'val' => 1,
    'key' => 'bar'
    },
    {
    'val' => 3,
    'key' => 'bla'
    }
    ],
    [
    {
    'val' => 0,
    'key' => 'foo'
    },
    {
    'val' => 2,
    'key' => '123'
    },
    {
    'val' => 4,
    'key' => '567'
    }
    ]
    ], 'Hash' );

    As you can see, the keys 'foo', '123' and '567' all had the same hash code
    which is why they ended up in the same array element.

    This also explains why it is more efficient to have two different keys
    have two different hash codes. When they have the same hash code, a
    collision happens and a linear list of key/value pairs first has to be
    searched to find the right pair.

    Tassilo
    --
    use bigint;
    $n=71423350343770280161397026330337371139054411854220053437565440;
    $m=-8,;;$_=$n&(0xff)<<$m,,$_>>=$m,,print+chr,,while(($m+=8)<=200);
     
    Tassilo v. Parseval, Feb 27, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jesus M. Salvo Jr.
    Replies:
    2
    Views:
    4,324
    robert
    Feb 11, 2006
  2. Replies:
    10
    Views:
    741
    Chris Torek
    Feb 4, 2005
  3. jimjim
    Replies:
    16
    Views:
    875
    Jordan Abel
    Mar 28, 2006
  4. Replies:
    4
    Views:
    1,329
    Fred Zwarts
    Jul 2, 2009
  5. arithmetic operations on pointer

    , Nov 25, 2013, in forum: C Programming
    Replies:
    29
    Views:
    268
    Tim Rentsch
    Dec 3, 2013
Loading...

Share This Page