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 1 of 3  [1] 2 3  Next page →

#16431 — Re: order independent hash?

Neal Becker wrote:

> I like to hash a list of words (actually, the command line args of my
> program) in such a way that different words will create different hash,
> but not sensitive to the order of the words.  Any ideas?

You mean a typical python hash value which would be /likely/ to differ for 
different lists and /guaranteed/ to be equal for equal lists is not good 
enough? Because that would be easy:

args = sys.argv[1:]
hash(tuple(sorted(args))) # consider duplicate args
hash(frozenset(args)) # ignore duplicate args

[toc] | [next] | [standalone]

#16499

On Wednesday, November 30, 2011 8:47:13 PM UTC+8, Peter Otten wrote:
> Neal Becker wrote:
> 
> > I like to hash a list of words (actually, the command line args of my
> > program) in such a way that different words will create different hash,
> > but not sensitive to the order of the words.  Any ideas?
> 
> You mean a typical python hash value which would be /likely/ to differ for 
> different lists and /guaranteed/ to be equal for equal lists is not good 
> enough? Because that would be easy:
> 
> args = sys.argv[1:]
> hash(tuple(sorted(args))) # consider duplicate args

I knew a hash can replace a bi-directional linked list.
The value  can be a multi-field string  to be parsed for further actions. 
Is this what you are asking?

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

#16500

On Wednesday, November 30, 2011 8:47:13 PM UTC+8, Peter Otten wrote:
> Neal Becker wrote:
> 
> > I like to hash a list of words (actually, the command line args of my
> > program) in such a way that different words will create different hash,
> > but not sensitive to the order of the words.  Any ideas?
> 
> You mean a typical python hash value which would be /likely/ to differ for 
> different lists and /guaranteed/ to be equal for equal lists is not good 
> enough? Because that would be easy:
> 
> args = sys.argv[1:]
> hash(tuple(sorted(args))) # consider duplicate args

I knew a hash can replace a bi-directional linked list.
The value  can be a multi-field string  to be parsed for further actions. 
Is this what you are asking?

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

#16501

On 12/01/2011 10:35 AM, 88888 Dihedral wrote:
> On Wednesday, November 30, 2011 8:47:13 PM UTC+8, Peter Otten wrote:
>> Neal Becker wrote:
>>
>>> I like to hash a list of words (actually, the command line args of my
>>> program) in such a way that different words will create different hash,
>>> but not sensitive to the order of the words.  Any ideas?
>> You mean a typical python hash value which would be /likely/ to differ for
>> different lists and /guaranteed/ to be equal for equal lists is not good
>> enough? Because that would be easy:
>>
>> args = sys.argv[1:]
>> hash(tuple(sorted(args))) # consider duplicate args
> I knew a hash can replace a bi-directional linked list.
> The value  can be a multi-field string  to be parsed for further actions.
> Is this what you are asking?
A hash is a number, so I don't see how it can replace any kind of linked 
list.  Perhaps you're thinking of some other language.

-- 

DaveA

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

#16502

On Thursday, December 1, 2011 11:52:46 PM UTC+8, Dave Angel wrote:
> On 12/01/2011 10:35 AM, 88888 Dihedral wrote:
> > On Wednesday, November 30, 2011 8:47:13 PM UTC+8, Peter Otten wrote:
> >> Neal Becker wrote:
> >>
> >>> I like to hash a list of words (actually, the command line args of my
> >>> program) in such a way that different words will create different hash,
> >>> but not sensitive to the order of the words.  Any ideas?
> >> You mean a typical python hash value which would be /likely/ to differ for
> >> different lists and /guaranteed/ to be equal for equal lists is not good
> >> enough? Because that would be easy:
> >>
> >> args = sys.argv[1:]
> >> hash(tuple(sorted(args))) # consider duplicate args
> > I knew a hash can replace a bi-directional linked list.
> > The value  can be a multi-field string  to be parsed for further actions.
> > Is this what you are asking?
> A hash is a number, so I don't see how it can replace any kind of linked 
> list.  Perhaps you're thinking of some other language.
> 
> -- 
> 
> DaveA

A long number of a varied length allowed but   can interpreted by the programmer. 

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

#16504

On Thursday, December 1, 2011 11:52:46 PM UTC+8, Dave Angel wrote:
> On 12/01/2011 10:35 AM, 88888 Dihedral wrote:
> > On Wednesday, November 30, 2011 8:47:13 PM UTC+8, Peter Otten wrote:
> >> Neal Becker wrote:
> >>
> >>> I like to hash a list of words (actually, the command line args of my
> >>> program) in such a way that different words will create different hash,
> >>> but not sensitive to the order of the words.  Any ideas?
> >> You mean a typical python hash value which would be /likely/ to differ for
> >> different lists and /guaranteed/ to be equal for equal lists is not good
> >> enough? Because that would be easy:
> >>
> >> args = sys.argv[1:]
> >> hash(tuple(sorted(args))) # consider duplicate args
> > I knew a hash can replace a bi-directional linked list.
> > The value  can be a multi-field string  to be parsed for further actions.
> > Is this what you are asking?
> A hash is a number, so I don't see how it can replace any kind of linked 
> list.  Perhaps you're thinking of some other language.
> 
> -- 
> 
> DaveA

A long number of a varied length allowed but   can interpreted by the programmer. 

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

#16503

On Fri, Dec 2, 2011 at 2:52 AM, Dave Angel <d@davea.name> wrote:
> On 12/01/2011 10:35 AM, 88888 Dihedral wrote:
>> I knew a hash can replace a bi-directional linked list.
>> The value  can be a multi-field string  to be parsed for further actions.
>> Is this what you are asking?
>
> A hash is a number, so I don't see how it can replace any kind of linked
> list.  Perhaps you're thinking of some other language.

A hashtable is a form of data structure that involves hashing values
(ie calculating hashes for them) and storing them for easier retrieval
than a simple linked list offers. That may be what you're thinking of.

ChrisA

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

#16523

On Friday, December 2, 2011 12:18:29 AM UTC+8, Chris Angelico wrote:
> On Fri, Dec 2, 2011 at 2:52 AM, Dave Angel <d...@davea.name> wrote:
> > On 12/01/2011 10:35 AM, 88888 Dihedral wrote:
> >> I knew a hash can replace a bi-directional linked list.
> >> The value  can be a multi-field string  to be parsed for further actions.
> >> Is this what you are asking?
> >
> > A hash is a number, so I don't see how it can replace any kind of linked
> > list.  Perhaps you're thinking of some other language.
> 
> A hashtable is a form of data structure that involves hashing values
> (ie calculating hashes for them) and storing them for easier retrieval
> than a simple linked list offers. That may be what you're thinking of.
> 
> ChrisA

I clear my point a hash is a collection of (key, value) pairs that have
well defined methods and behavior to be used in programming. 

The basic operations of a hash normally includes the following:

1. insertion of a (key, value) pair  into the hash
2. deletion of a (key, value) from the hash
3. inquiring  a hash by a key to retrieve the value if the (key, value) 
pair available in the hash. If no key matched, the hash will return 
a not found result. 

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. 

Some implementations of a hash might pose some restrictions of k and v
for some reasons. But in object programming k and v can be objects
to be manipulated by the programmer.  

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

#16526

On Fri, Dec 2, 2011 at 3:29 PM, 88888 Dihedral
<dihedral88888@googlemail.com> wrote:
> I clear my point a hash is a collection of (key, value) pairs that have
> well defined methods and behavior to be used in programming.
>
> The basic operations of a hash normally includes the following:
>
> 1. insertion of a (key, value) pair  into the hash
> 2. deletion of a (key, value) from the hash
> 3. inquiring  a hash by a key to retrieve the value if the (key, value)
> pair available in the hash. If no key matched, the hash will return
> a not found result.
>
> 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 - think of a Python dictionary:

On Fri, Dec 2, 2011 at 3:33 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Python dicts are hash tables.

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

Cryptography and data verification use hashing too (look at the
various historic hashing algorithms - CRC, MD5, SHA, etc). The concept
of a hash is a number (usually of a fixed size) that is calculated
from a string or other large data type, such that hashing the same
input will always give the same output, but hashing different input
will usually give different output. It's then possible to identify a
large object solely by its hash, as is done in git, for instance; or
to transmit both the data and the hash, as is done in message
protection schemes (many archiving programs/formats include a hash of
the uncompressed data). These have nothing to do with (key,value)
pairs, but are important uses of hashes.

ChrisA

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

#16529

On Friday, December 2, 2011 1:00:10 PM UTC+8, Chris Angelico wrote:
> On Fri, Dec 2, 2011 at 3:29 PM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> > I clear my point a hash is a collection of (key, value) pairs that have
> > well defined methods and behavior to be used in programming.
> >
> > The basic operations of a hash normally includes the following:
> >
> > 1. insertion of a (key, value) pair  into the hash
> > 2. deletion of a (key, value) from the hash
> > 3. inquiring  a hash by a key to retrieve the value if the (key, value)
> > pair available in the hash. If no key matched, the hash will return
> > a not found result.
> >
> > 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 - think of a Python dictionary:
> 
> On Fri, Dec 2, 2011 at 3:33 PM, Steven D'Aprano
> <steve+comp....@pearwood.info> wrote:
> > Python dicts are hash tables.
> 
> Although strictly speaking, isn't that "Python dicts are implemented
> as hash tables in CPython"? Or is the hashtable implementation
> mandated? Anyway, near enough.
>

 
> Cryptography and data verification use hashing too (look at the
> various historic hashing algorithms - CRC, MD5, SHA, etc). The concept
> of a hash is a number (usually of a fixed size) that is calculated
> from a string or other large data type, such that hashing the same
> input will always give the same output, but hashing different input
> will usually give different output. It's then possible to identify a
> large object solely by its hash, as is done in git, for instance; or
> to transmit both the data and the hash, as is done in message
> protection schemes (many archiving programs/formats include a hash of
> the uncompressed data). These have nothing to do with (key,value)
> pairs, but are important uses of hashes.
> 
> ChrisA

If one tries to insert a (k,v1) and then a (k,v2) pair into a
hash with v1 not equals V2, what could happen in your understanding of
a hash?

A hash function is different from a hash or so called a hash table in
my post. 
 
If the hash collision rate is not specified, then  it is  trivial to write a hash function with the conditions you specified. A hash function applied to a set of data items only  is of very limited use at all.
 
A hash stores (k,v) pairs specified in the run time with auto memory
management build in is not a simple hash function to produce data signatures only clearly in my post.   

What I said a hash which is lifted as a basic type in python  is called a dictionary in python. 

It is called a map in c++'s generics library. 

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

#16606

On 12/02/2011 04:48 PM, 88888 Dihedral wrote:
> On Friday, December 2, 2011 1:00:10 PM UTC+8, Chris Angelico wrote:
>> On Fri, Dec 2, 2011 at 3:29 PM, 88888 Dihedral
>> <dihedr...@googlemail.com>  wrote:
>>> I clear my point a hash is a collection of (key, value) pairs that have
>>> well defined methods and behavior to be used in programming.
>>>
>>> The basic operations of a hash normally includes the following:
>>>
>>> 1. insertion of a (key, value) pair  into the hash
>>> 2. deletion of a (key, value) from the hash
>>> 3. inquiring  a hash by a key to retrieve the value if the (key, value)
>>> pair available in the hash. If no key matched, the hash will return
>>> a not found result.
>>>
>>> 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 - think of a Python dictionary:
>>
>> On Fri, Dec 2, 2011 at 3:33 PM, Steven D'Aprano
>> <steve+comp....@pearwood.info>  wrote:
>>> Python dicts are hash tables.
>>
>> Although strictly speaking, isn't that "Python dicts are implemented
>> as hash tables in CPython"? Or is the hashtable implementation
>> mandated? Anyway, near enough.
>>
>
>
>> Cryptography and data verification use hashing too (look at the
>> various historic hashing algorithms - CRC, MD5, SHA, etc). The concept
>> of a hash is a number (usually of a fixed size) that is calculated
>> from a string or other large data type, such that hashing the same
>> input will always give the same output, but hashing different input
>> will usually give different output. It's then possible to identify a
>> large object solely by its hash, as is done in git, for instance; or
>> to transmit both the data and the hash, as is done in message
>> protection schemes (many archiving programs/formats include a hash of
>> the uncompressed data). These have nothing to do with (key,value)
>> pairs, but are important uses of hashes.
>>
>> ChrisA
>
> If one tries to insert a (k,v1) and then a (k,v2) pair into a
> hash with v1 not equals V2, what could happen in your understanding of
> a hash?

Don't try to argue, in English, `hash != hash` is true; it's just a 
typical occurence of homonyms. Just because they have the same name 
doesn't mean hash (function) has to have somewhat similar properties to 
hash (table).

> A hash function is different from a hash or so called a hash table in
> my post.

Indeed.

> If the hash collision rate is not specified, then  it is  trivial to write a hash function with the conditions you specified. A hash function applied to a set of data items only  is of very limited use at all.

It's trivial indeed, but a hashtable couldn't exist without hash 
function. And without a good hash function, a hash table's performance 
may degrade into O(n) access/insertion/deletion.

> A hash stores (k,v) pairs specified in the run time with auto memory
> management build in is not a simple hash function to produce data signatures only clearly in my post.
>
> What I said a hash which is lifted as a basic type in python  is called a dictionary in python.
>
> It is called a map in c++'s generics library.

Putting aside all these, it's pretty obvious from the beginning that OP 
was referring to hash functions, not hash tables.

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

#16530

On Friday, December 2, 2011 1:00:10 PM UTC+8, Chris Angelico wrote:
> On Fri, Dec 2, 2011 at 3:29 PM, 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> > I clear my point a hash is a collection of (key, value) pairs that have
> > well defined methods and behavior to be used in programming.
> >
> > The basic operations of a hash normally includes the following:
> >
> > 1. insertion of a (key, value) pair  into the hash
> > 2. deletion of a (key, value) from the hash
> > 3. inquiring  a hash by a key to retrieve the value if the (key, value)
> > pair available in the hash. If no key matched, the hash will return
> > a not found result.
> >
> > 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 - think of a Python dictionary:
> 
> On Fri, Dec 2, 2011 at 3:33 PM, Steven D'Aprano
> <steve+comp....@pearwood.info> wrote:
> > Python dicts are hash tables.
> 
> Although strictly speaking, isn't that "Python dicts are implemented
> as hash tables in CPython"? Or is the hashtable implementation
> mandated? Anyway, near enough.
>

 
> Cryptography and data verification use hashing too (look at the
> various historic hashing algorithms - CRC, MD5, SHA, etc). The concept
> of a hash is a number (usually of a fixed size) that is calculated
> from a string or other large data type, such that hashing the same
> input will always give the same output, but hashing different input
> will usually give different output. It's then possible to identify a
> large object solely by its hash, as is done in git, for instance; or
> to transmit both the data and the hash, as is done in message
> protection schemes (many archiving programs/formats include a hash of
> the uncompressed data). These have nothing to do with (key,value)
> pairs, but are important uses of hashes.
> 
> ChrisA

If one tries to insert a (k,v1) and then a (k,v2) pair into a
hash with v1 not equals V2, what could happen in your understanding of
a hash?

A hash function is different from a hash or so called a hash table in
my post. 
 
If the hash collision rate is not specified, then  it is  trivial to write a hash function with the conditions you specified. A hash function applied to a set of data items only  is of very limited use at all.
 
A hash stores (k,v) pairs specified in the run time with auto memory
management build in is not a simple hash function to produce data signatures only clearly in my post.   

What I said a hash which is lifted as a basic type in python  is called a dictionary in python. 

It is called a map in c++'s generics library. 

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

#16607

Op 2011-12-02 6:48, 88888 Dihedral schreef:
> A hash stores (k,v) pairs specified in the run time with auto memory 
> management build in is not a simple hash function to produce data
> signatures only clearly in my post.
> 
> What I said a hash which is lifted as a basic type in python  is
> called a dictionary in python.
> 
> It is called a map in c++'s generics library.

Not exactly: a C++ std::map uses a tree structure (which is why it keeps
the keys sorted). C++ STL also has std::hash_map which, as the name
implies, does use a hash table implementation.

-- 
The saddest aspect of life right now is that science gathers knowledge
faster than society gathers wisdom.
  -- Isaac Asimov

Roel Schroeven

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

#16618

On Sunday, December 4, 2011 9:41:19 PM UTC+8, Roel Schroeven wrote:
> Op 2011-12-02 6:48, 88888 Dihedral schreef:
> > A hash stores (k,v) pairs specified in the run time with auto memory 
> > management build in is not a simple hash function to produce data
> > signatures only clearly in my post.
> > 
> > What I said a hash which is lifted as a basic type in python  is
> > called a dictionary in python.
> > 
> > It is called a map in c++'s generics library.
> 
> Not exactly: a C++ std::map uses a tree structure (which is why it keeps
> the keys sorted). C++ STL also has std::hash_map which, as the name
> implies, does use a hash table implementation.
> 
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? 

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

#16620

On Sun, Dec 4, 2011 at 8:39 AM, 88888 Dihedral
<dihedral88888@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*.

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

#16621

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]

#16625

On Sun, Dec 4, 2011 at 11:06 AM, 88888 Dihedral
<dihedral88888@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.

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

#16627

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]

#16628

Duh. What's the point you're trying to make?

On Mon, Dec 5, 2011 at 10:17 AM, 88888 Dihedral
<dihedral88888@googlemail.com> wrote:
> 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.
>
>
>
>
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list



-- 
ಠ_ಠ

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

#16629

On Sun, Dec 4, 2011 at 4:17 PM, 88888 Dihedral
<dihedral88888@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".

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web