Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #16431 > unrolled thread

Re: order independent hash?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: order independent hash? Peter Otten <__peter__@web.de> - 2011-11-30 13:47 +0100
    Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 07:35 -0800
    Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 07:35 -0800
      Re: order independent hash? Dave Angel <d@davea.name> - 2011-12-01 10:52 -0500
        Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 08:17 -0800
        Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 08:17 -0800
      Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-02 03:18 +1100
        Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 20:29 -0800
          Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-02 16:00 +1100
            Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 21:48 -0800
              Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-05 00:40 +1100
            Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 21:48 -0800
              Re: order independent hash? Roel Schroeven <rschroev_nospam_ml@fastmail.fm> - 2011-12-04 14:41 +0100
                Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 07:39 -0800
                  Re: order independent hash? Ian Kelly <ian.g.kelly@gmail.com> - 2011-12-04 10:41 -0700
                    Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 10:06 -0800
                      Re: order independent hash? Ian Kelly <ian.g.kelly@gmail.com> - 2011-12-04 13:13 -0700
                        Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 15:17 -0800
                        Re: order independent hash? Matt Joiner <anacrolix@gmail.com> - 2011-12-05 10:21 +1100
                        Re: order independent hash? Ian Kelly <ian.g.kelly@gmail.com> - 2011-12-04 16:24 -0700
                          Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 16:52 -0800
                            Re: order independent hash? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-12-05 02:00 +0000
                          Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 16:52 -0800
                            Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-05 12:59 +1100
                            Re: order independent hash? Ethan Furman <ethan@stoneleaf.us> - 2011-12-04 18:08 -0800
                              Re: order independent hash? Ben Finney <ben+python@benfinney.id.au> - 2011-12-05 15:52 +1100
                            Re: order independent hash? Matt Joiner <anacrolix@gmail.com> - 2011-12-05 14:02 +1100
                          Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-06 21:24 -0800
                          Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-06 21:24 -0800
                        Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 15:17 -0800
                          Re: order independent hash? Terry Reedy <tjreedy@udel.edu> - 2011-12-04 19:28 -0500
                    Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-04 10:06 -0800
            Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-02 10:53 +0100
              Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-02 03:48 -0800
              Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-02 09:00 -0800
              Re: order independent hash? Terry Reedy <tjreedy@udel.edu> - 2011-12-02 16:40 -0500
                Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-04 14:55 +0100
                  Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-05 01:08 +1100
                    Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-07 14:28 +0100
                      Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-07 09:48 -0800
                  Re: order independent hash? Tim Chase <python.list@tim.thechases.com> - 2011-12-04 12:57 -0600
                    Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-08 10:30 +0100
                      Re: order independent hash? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-12-09 11:27 +0000
                        Re: order independent hash? Hrvoje Niksic <hniksic@xemacs.org> - 2011-12-09 17:51 +0100
                          Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-10 04:13 +1100
                        Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-11 10:58 +1100
                        Re: order independent hash? Chris Angelico <rosuav@gmail.com> - 2011-12-11 11:17 +1100
                        Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-11 14:04 +1100
          Re: order independent hash? Lie Ryan <lie.1296@gmail.com> - 2011-12-05 00:29 +1100
        Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-01 20:29 -0800
        Re: order independent hash? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-12-02 04:33 +0000

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#16633

On Monday, December 5, 2011 7:24:49 AM UTC+8, Ian wrote:
> On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> >> Please explain what you think a hash function is, then.  Per
> >> Wikipedia, "A hash function is any algorithm or subroutine that maps
> >> large data sets to smaller data sets, called keys."
> >>
> >> > Are you miss-leading the power of true OOP ?
> >>
> >> I have no idea what you are suggesting.  I was not talking about OOP at all.
> >
> > In python the (k,v) pair in a dictionary k and v can be  both an objects.
> > v can be a tuple or a list.  There are some restrictions on k to be an
> >  hashable type in python's implementation. The key is used to compute the position of the pair to be stored in a  hash table. The hash function maps key k to the position in the hash table. If k1!=k2 are both  mapped to the same
> > position, then something has to be done to resolve this.
> 
> I understand how dicts / hash tables work.  I don't need you to
> explain that to me.  What you haven't explained is why you stated that
> a hash function that operates on objects is not a hash function, or
> what you meant by "misleading the power of true OOP".

If v is a tuple or a list then a dictionary in python can replace a bi-directional list or a tree under the assumption that the hash which  accesses values stored in a  much faster way  when well implemented.  

[toc] | [prev] | [next] | [standalone]

#16636

Dihedral, you're back to double posting. Please stop. Send to the mailing 
list, or to the newsgroup, it doesn't matter. But don't send to both.

Further comments below.


On Sun, 04 Dec 2011 16:52:14 -0800, 88888 Dihedral wrote:

> If v is a tuple or a list then a dictionary in python can replace a
> bi-directional list or a tree under the assumption that the hash which 
> accesses values stored in a  much faster way  when well implemented.

No it can't.

The keys in a hash tables are unordered. You get an order when you 
iterate over them, but that order is arbitrary.

Keys in a list or tree are ordered. E.g. collections.OrderedDict 
remembers the order that keys are added. If Python were to replace 
OrderedDicts with dicts, it would break code.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#16634

On Monday, December 5, 2011 7:24:49 AM UTC+8, Ian wrote:
> On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> >> Please explain what you think a hash function is, then.  Per
> >> Wikipedia, "A hash function is any algorithm or subroutine that maps
> >> large data sets to smaller data sets, called keys."
> >>
> >> > Are you miss-leading the power of true OOP ?
> >>
> >> I have no idea what you are suggesting.  I was not talking about OOP at all.
> >
> > In python the (k,v) pair in a dictionary k and v can be  both an objects.
> > v can be a tuple or a list.  There are some restrictions on k to be an
> >  hashable type in python's implementation. The key is used to compute the position of the pair to be stored in a  hash table. The hash function maps key k to the position in the hash table. If k1!=k2 are both  mapped to the same
> > position, then something has to be done to resolve this.
> 
> I understand how dicts / hash tables work.  I don't need you to
> explain that to me.  What you haven't explained is why you stated that
> a hash function that operates on objects is not a hash function, or
> what you meant by "misleading the power of true OOP".

If v is a tuple or a list then a dictionary in python can replace a bi-directional list or a tree under the assumption that the hash which  accesses values stored in a  much faster way  when well implemented.  

[toc] | [prev] | [next] | [standalone]

#16635

On 12/05/2011 11:52 AM, 88888 Dihedral wrote:
> On Monday, December 5, 2011 7:24:49 AM UTC+8, Ian wrote:
>> On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
>> <dihedr...@googlemail.com>  wrote:
>>>> Please explain what you think a hash function is, then.  Per
>>>> Wikipedia, "A hash function is any algorithm or subroutine that maps
>>>> large data sets to smaller data sets, called keys."
>>>>
>>>>> Are you miss-leading the power of true OOP ?
>>>>
>>>> I have no idea what you are suggesting.  I was not talking about OOP at all.
>>>
>>> In python the (k,v) pair in a dictionary k and v can be  both an objects.
>>> v can be a tuple or a list.  There are some restrictions on k to be an
>>>   hashable type in python's implementation. The key is used to compute the position of the pair to be stored in a  hash table. The hash function maps key k to the position in the hash table. If k1!=k2 are both  mapped to the same
>>> position, then something has to be done to resolve this.
>>
>> I understand how dicts / hash tables work.  I don't need you to
>> explain that to me.  What you haven't explained is why you stated that
>> a hash function that operates on objects is not a hash function, or
>> what you meant by "misleading the power of true OOP".
>
> If v is a tuple or a list then a dictionary in python can replace a bi-directional list or a tree under the assumption that the hash which  accesses values stored in a  much faster way  when well implemented.

trying not to be rude, but the more you talk, the more I"m convince that 
you're trolling. Welcome to my killfile.

[toc] | [prev] | [next] | [standalone]

#16637

Lie Ryan wrote:
> On 12/05/2011 11:52 AM, 88888 Dihedral wrote:
>> On Monday, December 5, 2011 7:24:49 AM UTC+8, Ian wrote:
>>> On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
>>> <dihedr...@googlemail.com>  wrote:
>>>>> Please explain what you think a hash function is, then.  Per
>>>>> Wikipedia, "A hash function is any algorithm or subroutine that maps
>>>>> large data sets to smaller data sets, called keys."
>>>>>
>>>>>> Are you miss-leading the power of true OOP ?
>>>>>
>>>>> I have no idea what you are suggesting.  I was not talking about 
>>>>> OOP at all.
>>>>
>>>> In python the (k,v) pair in a dictionary k and v can be  both an 
>>>> objects.
>>>> v can be a tuple or a list.  There are some restrictions on k to be an
>>>>   hashable type in python's implementation. The key is used to 
>>>> compute the position of the pair to be stored in a  hash table. The 
>>>> hash function maps key k to the position in the hash table. If 
>>>> k1!=k2 are both  mapped to the same
>>>> position, then something has to be done to resolve this.
>>>
>>> I understand how dicts / hash tables work.  I don't need you to
>>> explain that to me.  What you haven't explained is why you stated that
>>> a hash function that operates on objects is not a hash function, or
>>> what you meant by "misleading the power of true OOP".
>>
>> If v is a tuple or a list then a dictionary in python can replace a 
>> bi-directional list or a tree under the assumption that the hash 
>> which  accesses values stored in a  much faster way  when well 
>> implemented.
> 
> trying not to be rude, but the more you talk, the more I"m convince that 
> you're trolling. Welcome to my killfile.

I think he's a bot, and he's been in my killfile for a while now.

~Ethan~

[toc] | [prev] | [next] | [standalone]

#16639

Ethan Furman <ethan@stoneleaf.us> writes:

> Lie Ryan wrote:

> > trying not to be rude, but the more you talk, the more I"m convince
> > that you're trolling. Welcome to my killfile.
>
> I think he's a bot, and he's been in my killfile for a while now.

Having a ludicrous name doesn't help, and is part of what dropped them
into my kill file.

Maybe when they give a human-friendly name, and drop the insistence on
being right rather than learning something, they can emerge from some of
our kill files.

-- 
 \       “We jealously reserve the right to be mistaken in our view of |
  `\      what exists, given that theories often change under pressure |
_o__)              from further investigation.” —Thomas W. Clark, 2009 |
Ben Finney

[toc] | [prev] | [next] | [standalone]

#16638

Yes. I sent a mail earlier asking such and it was bounced. I'm one
email from also blocking this fellow.

On Mon, Dec 5, 2011 at 12:59 PM, Lie Ryan <lie.1296@gmail.com> wrote:
> On 12/05/2011 11:52 AM, 88888 Dihedral wrote:
>>
>> On Monday, December 5, 2011 7:24:49 AM UTC+8, Ian wrote:
>>>
>>> On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
>>> <dihedr...@googlemail.com>  wrote:
>>>>>
>>>>> Please explain what you think a hash function is, then.  Per
>>>>> Wikipedia, "A hash function is any algorithm or subroutine that maps
>>>>> large data sets to smaller data sets, called keys."
>>>>>
>>>>>> Are you miss-leading the power of true OOP ?
>>>>>
>>>>>
>>>>> I have no idea what you are suggesting.  I was not talking about OOP at
>>>>> all.
>>>>
>>>>
>>>> In python the (k,v) pair in a dictionary k and v can be  both an
>>>> objects.
>>>> v can be a tuple or a list.  There are some restrictions on k to be an
>>>>  hashable type in python's implementation. The key is used to compute
>>>> the position of the pair to be stored in a  hash table. The hash function
>>>> maps key k to the position in the hash table. If k1!=k2 are both  mapped to
>>>> the same
>>>> position, then something has to be done to resolve this.
>>>
>>>
>>> I understand how dicts / hash tables work.  I don't need you to
>>> explain that to me.  What you haven't explained is why you stated that
>>> a hash function that operates on objects is not a hash function, or
>>> what you meant by "misleading the power of true OOP".
>>
>>
>> If v is a tuple or a list then a dictionary in python can replace a
>> bi-directional list or a tree under the assumption that the hash which
>>  accesses values stored in a  much faster way  when well implemented.
>
>
> trying not to be rude, but the more you talk, the more I"m convince that
> you're trolling. Welcome to my killfile.
>
> --
> http://mail.python.org/mailman/listinfo/python-list



-- 
ಠ_ಠ

[toc] | [prev] | [next] | [standalone]

#16767

On Monday, December 5, 2011 7:24:49 AM UTC+8, Ian wrote:
> On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> >> Please explain what you think a hash function is, then.  Per
> >> Wikipedia, "A hash function is any algorithm or subroutine that maps
> >> large data sets to smaller data sets, called keys."
> >>
> >> > Are you miss-leading the power of true OOP ?
> >>
> >> I have no idea what you are suggesting.  I was not talking about OOP at all.
> >
> > In python the (k,v) pair in a dictionary k and v can be  both an objects.
> > v can be a tuple or a list.  There are some restrictions on k to be an
> >  hashable type in python's implementation. The key is used to compute the position of the pair to be stored in a  hash table. The hash function maps key k to the position in the hash table. If k1!=k2 are both  mapped to the same
> > position, then something has to be done to resolve this.
> 
> I understand how dicts / hash tables work.  I don't need you to
> explain that to me.  What you haven't explained is why you stated that
> a hash function that operates on objects is not a hash function, or
> what you meant by "misleading the power of true OOP".

Do you  forget the memory management of a dictionary in Python that has 
to be linked for a dynamical growing and shrinking number of (k,v) pairs 
in a long period of time?

Avoiding the true non-trivial part in any implementation or use of a dictionary  is miss leading ? 

Probing too deep in the stack or occupying too much in the heap is not
bug free?

[toc] | [prev] | [next] | [standalone]

#16768

On Monday, December 5, 2011 7:24:49 AM UTC+8, Ian wrote:
> On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> >> Please explain what you think a hash function is, then.  Per
> >> Wikipedia, "A hash function is any algorithm or subroutine that maps
> >> large data sets to smaller data sets, called keys."
> >>
> >> > Are you miss-leading the power of true OOP ?
> >>
> >> I have no idea what you are suggesting.  I was not talking about OOP at all.
> >
> > In python the (k,v) pair in a dictionary k and v can be  both an objects.
> > v can be a tuple or a list.  There are some restrictions on k to be an
> >  hashable type in python's implementation. The key is used to compute the position of the pair to be stored in a  hash table. The hash function maps key k to the position in the hash table. If k1!=k2 are both  mapped to the same
> > position, then something has to be done to resolve this.
> 
> I understand how dicts / hash tables work.  I don't need you to
> explain that to me.  What you haven't explained is why you stated that
> a hash function that operates on objects is not a hash function, or
> what you meant by "misleading the power of true OOP".

Do you  forget the memory management of a dictionary in Python that has 
to be linked for a dynamical growing and shrinking number of (k,v) pairs 
in a long period of time?

Avoiding the true non-trivial part in any implementation or use of a dictionary  is miss leading ? 

Probing too deep in the stack or occupying too much in the heap is not
bug free?

[toc] | [prev] | [next] | [standalone]

#16630

On Monday, December 5, 2011 4:13:01 AM UTC+8, Ian wrote:
> On Sun, Dec 4, 2011 at 11:06 AM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> >> If you want to talk about ways to use dicts, please start a different
> >> thread for it.  As has been pointed out several times now, it is
> >> off-topic for this thread, which is about hash *functions*.
> >
> > A hash that can hash objects is not a hash function at all.
> 
> Please explain what you think a hash function is, then.  Per
> Wikipedia, "A hash function is any algorithm or subroutine that maps
> large data sets to smaller data sets, called keys."
> 
> > Are you miss-leading the power of true OOP ?
> 
> I have no idea what you are suggesting.  I was not talking about OOP at all.

In python the (k,v) pair in a dictionary k and v can be  both an objects. 
v can be a tuple or a list.  There are some restrictions on k to be an
 hashable type in python's implementation. The key is used to compute the position of the pair to be stored in a  hash table. The hash function maps key k to the position in the hash table. If k1!=k2 are both  mapped to the same
position, then something has to be done to resolve this.     


  
 

[toc] | [prev] | [next] | [standalone]

#16632

On 12/4/2011 6:17 PM, 88888 Dihedral wrote:

> In python the (k,v) pair in a dictionary k and v can be  both an objects.
> v can be a tuple or a list.

In Python, everything is an object. *tuple* and *list* are subclasses of 
*object*. The value v for a dict can be any object, and must be an object.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#16622

A hash that can hash objects is not a trivial hash function  

On Monday, December 5, 2011 1:41:14 AM UTC+8, Ian wrote:
> On Sun, Dec 4, 2011 at 8:39 AM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> > Thanks for your comments. Are we gonna talk about the way to implement a hash
> > table or the use of a hash table in programming?
> 
> Implementing a hash table is not very relevant on a list about Python,
> which already has them built into the language; and any pure Python
> implementation would be uselessly slow.
> 
> If you want to talk about ways to use dicts, please start a different
> thread for it.  As has been pointed out several times now, it is
> off-topic for this thread, which is about hash *functions*.

A hash that can hash objects is not a hash function at all.
Are you miss-leading the power of true OOP ?

[toc] | [prev] | [next] | [standalone]

#16536

Chris Angelico <rosuav@gmail.com> writes:

>> The hash can grow with (k,v) pairs accumulated in the run time.
>> An auto memory management mechanism is required for a hash of a non-fixed size of (k,v) pairs.
>
> That's a hash table

In many contexts "hash table" is shortened to "hash" when there is no
ambiguity.  This is especially popular among Perl programmers where the
equivalent of dict is called a hash.

> Although strictly speaking, isn't that "Python dicts are implemented
> as hash tables in CPython"? Or is the hashtable implementation
> mandated?

It's pretty much mandated because of the __hash__ protocol.

[toc] | [prev] | [next] | [standalone]

#16540

On Friday, December 2, 2011 5:53:47 PM UTC+8, Hrvoje Niksic wrote:
> Chris Angelico <ros...@gmail.com> writes:
> 
> >> The hash can grow with (k,v) pairs accumulated in the run time.
> >> An auto memory management mechanism is required for a hash of a non-fixed size of (k,v) pairs.
> >
> > That's a hash table
> 
> In many contexts "hash table" is shortened to "hash" when there is no
> ambiguity.  This is especially popular among Perl programmers where the
> equivalent of dict is called a hash.
> 
> > Although strictly speaking, isn't that "Python dicts are implemented
> > as hash tables in CPython"? Or is the hashtable implementation
> > mandated?
> 
> It's pretty much mandated because of the __hash__ protocol.

A hash table  definitely can replace a bi-directional list. 
But this is for applications or languages like C. 
In python hash is a build in type. Perl's lazy way of programming is famous. 

[toc] | [prev] | [next] | [standalone]

#16556

On Friday, December 2, 2011 5:53:47 PM UTC+8, Hrvoje Niksic wrote:
> Chris Angelico <ros...@gmail.com> writes:
> 
> >> The hash can grow with (k,v) pairs accumulated in the run time.
> >> An auto memory management mechanism is required for a hash of a non-fixed size of (k,v) pairs.
> >
> > That's a hash table
> 
> In many contexts "hash table" is shortened to "hash" when there is no
> ambiguity.  This is especially popular among Perl programmers where the
> equivalent of dict is called a hash.
> 
> > Although strictly speaking, isn't that "Python dicts are implemented
> > as hash tables in CPython"? Or is the hashtable implementation
> > mandated?
> 
> It's pretty much mandated because of the __hash__ protocol.

I agree with you. When a hash is inserted with (k,v1) and then (k,v2) 
such that  v1!=v2, there are several possibilities to handle this situation 
in programming:

1. v2 just replaces v1 with or without a message
2. the programmer can delete the (k,v1) entry and then insert a (k, (v1,v2))
entry.
3. the programmer initializes a tuple of (v1,v2), and then delete the (k,v1)
entry to be replaced by a (k,(v1,v2)) entry.

Hashes of hashes are really powerful in Python to be used to build a relational
DB of thousands of thousands of objects or records in a piece of cake.

A similar hash library in C is to be used everywhere is not difficult at all.

    

[toc] | [prev] | [next] | [standalone]

#16572

On 12/2/2011 4:53 AM, Hrvoje Niksic wrote:
> Chris Angelico<rosuav@gmail.com>  writes:
>
>>> The hash can grow with (k,v) pairs accumulated in the run time.
>>> An auto memory management mechanism is required for a hash of a non-fixed size of (k,v) pairs.
>>
>> That's a hash table
>
> In many contexts "hash table" is shortened to "hash" when there is no
> ambiguity.  This is especially popular among Perl programmers where the
> equivalent of dict is called a hash.
>
>> Although strictly speaking, isn't that "Python dicts are implemented
>> as hash tables in CPython"? Or is the hashtable implementation
>> mandated?
>
> It's pretty much mandated because of the __hash__ protocol.

Lib Ref 4.8. Mapping Types — dict
"A mapping object maps hashable values to arbitrary objects."

This does not say that the mapping has to *use* the hash value ;-).
Even if it does, it could use a tree structure instead of a hash table. 
But hash tables seem to work well for general purposes,

"Mappings are mutable objects."
(This would change if a frozendict were added.)

especially when additions and deletions are needed.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#16608

Terry Reedy <tjreedy@udel.edu> writes:

>> [Hashing is] pretty much mandated because of the __hash__ protocol.
>
> Lib Ref 4.8. Mapping Types — dict
> "A mapping object maps hashable values to arbitrary objects."
>
> This does not say that the mapping has to *use* the hash value ;-).
> Even if it does, it could use a tree structure instead of a hash
> table.

An arbitrary mapping doesn't, but reference to the hash protocol was in
the context of implementation constraints for dicts themselves (my
response quotes the relevant part of Chris's message).  If a Python
implementation tried to implement dict as a tree, instances of classes
that define only __eq__ and __hash__ would not be correctly inserted in
such a dict.  This would be a major source of incompatibility with
Python code, both in the standard library and at large.

[toc] | [prev] | [next] | [standalone]

#16609

2011/12/5 Hrvoje Niksic <hniksic@xemacs.org>:
> If a Python
> implementation tried to implement dict as a tree, instances of classes
> that define only __eq__ and __hash__ would not be correctly inserted in
> such a dict.

Couldn't you just make a tree of hash values? Okay, that's probably
not the most useful way to do things, but technically it'd comply with
the spec.

ChrisA

[toc] | [prev] | [next] | [standalone]

#16782

Chris Angelico <rosuav@gmail.com> writes:

> 2011/12/5 Hrvoje Niksic <hniksic@xemacs.org>:
>> If a Python implementation tried to implement dict as a tree,
>> instances of classes that define only __eq__ and __hash__ would not
>> be correctly inserted in such a dict.
>
> Couldn't you just make a tree of hash values? Okay, that's probably
> not the most useful way to do things, but technically it'd comply with
> the spec.

That's a neat idea.  The leaves of the tree would contain a list of
items with the same hash, but that's what you effectively get with a
linear-probe hash table anyway.

As you said, not immediately useful, but one could imagine the technique
being of practical use when implementing Python or a Python-compatible
language in a foreign environment that supports only tree-based
collections.

[toc] | [prev] | [next] | [standalone]

#16786

On Wednesday, December 7, 2011 9:28:40 PM UTC+8, Hrvoje Niksic wrote:
> Chris Angelico <ros...@gmail.com> writes:
> 
> > 2011/12/5 Hrvoje Niksic <hni...@xemacs.org>:
> >> If a Python implementation tried to implement dict as a tree,
> >> instances of classes that define only __eq__ and __hash__ would not
> >> be correctly inserted in such a dict.
> >
> > Couldn't you just make a tree of hash values? Okay, that's probably
> > not the most useful way to do things, but technically it'd comply with
> > the spec.
> 
> That's a neat idea.  The leaves of the tree would contain a list of
> items with the same hash, but that's what you effectively get with a
> linear-probe hash table anyway.
> 
> As you said, not immediately useful, but one could imagine the technique
> being of practical use when implementing Python or a Python-compatible
> language in a foreign environment that supports only tree-based
> collections.

The heap as the root that could be divided like a tree of nodes to be used
is funny. There are many ways to implement the heap manager in SW. 
 

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.python

csiph-web