Are dictionaries the same as hashtables?

[cnb]

Are dictionaries the same as hashtables?

[Martin Marcher]

On 2008-08-26 00:32:20, cnb wrote:

Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

PS: your sig was *a bit* longer than you question. please don't do
that...

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iQIVAwUBSLO0KNjk1vit/YR7AQLAxhAAotF4xEbquq1C+fnVU93PhETiotFSw/ni
r32njO5MPu2ecyY4eOxGshzw6P2ez1i9K3Yk8bpm89FrsZeqnr dDhh8xFo7CKFjX
DeoBVE3x6jo4Q9iTvNpF6tUHCAgyxVuaV/F+Hz9mNdaJ5o+xxG474429Pumn1N4W
m5X4wk5BtIj1nV7R4xh+jOFDXFShSoCZBwyVGB+MIZUsQhAt4q N9MSuO3lhmNgtD
Eo03CVpdqiKcxqS77xnHIR8TtgahLyRAosMBenNCe5ELE7CALk VU/v4oNI+4G3Ju
n0mfkZA2iqWulcJD3QAdYwImFlXrlLYg6Y5OMvL/Tm4729htsvGBPZD0DSrR0rQs
tjgRIljhv3BwKoxsk/UUx2glbUShjEfgCimIePKmuSh7jN+CuCVsgaRj5zYGiCVQ
gintIQaiFheqjkpSfkRtLqBQBbLwzCS86Bzc++I0m+IENxExvu E3AY4Lmt5dVCAT
ox8TubGe50xgomWr9ms/szri9u5qYuUWzC2ByjUVauuGAQxHwQUQvjCBFM9TI6bc
do+TMTY8qJhb/qsW3TlX5HagW/Cn+jw+xwP8b+xeMNXAEA/Q3dwSKFTx1s5NwGg6
vvjwEdPooq3k2XEQFXZq12CUn0FYjhUAzwR/06JG6muAR0YEMHKGeqcuamuEKeU/
2VBXpaqVkPY=
=7TsX
-----END PGP SIGNATURE-----

[cnb]

On Aug 26, 9:43*am, Martin Marcher <[e-mail]:

On 2008-08-26 00:32:20, cnb wrote:

Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

PS: your sig was *a bit* longer than you question. please don't do
that...

*signature.asc
< 1KViewDownload

my what?

[John Machin]

On Aug 26, 5:43*pm, Martin Marcher <[e-mail]:

On 2008-08-26 00:32:20, cnb wrote:

Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

Please clarify: (1) Nothing in where? In the Python dictionary
implementation? (2) What do you mean by "sane collision handling"?
What do you mean by "simply overwriting"?

TIA,
John

[Diez B. Roggisch]

Martin Marcher wrote:

On 2008-08-26 00:32:20, cnb wrote:

>Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

The term "collision" is rather well defined when talking about associative
arrays using hashing (which python's dicts are): it means that two distinct
keys produce the same hash-value, leading to a bucket collision. And of
course python deals with that sanely, and creates a list of objects inside
the bucket which is traversed and comparison is used to determine which
actual value to retrieve.

Python does not have a "one key maps to a list of values"-semantics - which
I consider the sane choice...

However, you can have that using the defaultdict for example:

listdict = defaultdict(list)

listdict[key].append(value)

Diez

[Ben Finney]

cnb <ci**********@yahoo.sewrites:

Are dictionaries the same as hashtables?

The 'dict' type in Python has certain behaviour, as specified in the
language reference. In CPython they are implemented as hash tables,
but I don't recall anything that specifies they *must* be implemented
that way.

So my answer would be "maybe, but don't count on it". Write your
program to the specified behaviour of the language, not to the
underlying implementation.

--
\ “With Lisp or Forth, a master programmer has unlimited power |
`\ and expressiveness. With Python, even a regular guy can reach |
_o__) for the stars.� —Raymond Hettinger |
Ben Finney

[John Machin]

On Aug 26, 7:36 pm, "Diez B. Roggisch" <[e-mail]:

Martin Marcher wrote:

On 2008-08-26 00:32:20, cnb wrote:

Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

The term "collision" is rather well defined when talking about associative
arrays using hashing (which python's dicts are): it means that two distinct
keys produce the same hash-value, leading to a bucket collision. And of
course python deals with that sanely, and creates a list of objects inside
the bucket which is traversed and comparison is used to determine which
actual value to retrieve.

I see neither buckets nor lists in the CPython svn trunk version of
dictobject.c and IIRC it's been using open addressing for a very long
time.

[Diez B. Roggisch]

John Machin wrote:

On Aug 26, 7:36 pm, "Diez B. Roggisch" <[e-mail]:

>Martin Marcher wrote:

On 2008-08-26 00:32:20, cnb wrote:
Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

The term "collision" is rather well defined when talking about
associative arrays using hashing (which python's dicts are): it means
that two distinct keys produce the same hash-value, leading to a bucket
collision. And of course python deals with that sanely, and creates a
list of objects inside the bucket which is traversed and comparison is
used to determine which actual value to retrieve.

I see neither buckets nor lists in the CPython svn trunk version of
dictobject.c and IIRC it's been using open addressing for a very long
time.

I don't know the exact names of the involved structures - I named them
liberally from my understanding of how associative arrays based on hashing
are implemented. But the below code shows that hash-collisions can occur
without corrupting data, while OTOH of course degenerating the lookup from
usually O(1) to O(n). Try playing around with it, commenting out the proper
hashing of the key will lead to great performance enhancements.

Diez

import pprint

class StupidThing(object):

def __init__(self, key):
self.key = key
def __hash__(self):
#return hash(self.key)
return 1
def __cmp__(self, other):
return cmp(self.key, other.key)
def __repr__(self):
return "<%s>" % self.key
d = {}

for a in xrange(1000):
d[StupidThing(str(a))] = a

pprint.pprint(d)

[Martin]

On Tue, Aug 26, 2008 at 9:52 AM, cnb <ci**********@yahoo.sewrote:

On Aug 26, 9:43 am, Martin Marcher <[e-mail]:

>On 2008-08-26 00:32:20, cnb wrote:

Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

PS: your sig was *a bit* longer than you question. please don't do
that...

signature.asc
< 1KViewDownload

my what?

Hehe,

it was *my* sig... i was using some old box with a mut config that
still had the fortune script in it... sorry.

Anyway what I meant by collision handling was:

$ python
Python 2.5.2 (r252:60911, Jul 31 2008, 17:31:22)
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.

>>l = {}
l

{}

>>l["a"] = 12
l["b"] = 13
l

{'a': 12, 'b': 13}

>>l["a"] = "This is a collision"
l

{'a': 'This is a collision', 'b': 13}

>>>

As you see position "a" is simply overwritten. Probably "sane" doesn't
really apply because how could the python creators possibly know
whether I just want to overwrite the value or indeed want some form of
collision handling (talk about lists vs. trees with there
subforms...)...

If one would want that he/she/it could still subclass dict and do more magic.

/martin

--
http://www.xing.com/profile/Martin_Marcher

You are not free to read this message,
by doing so, you have violated my licence
and are required to urinate publicly. Thank you.

[Cameron Laird]

In article <6h************@mid.uni-berlin.de>,
Diez B. Roggisch <de***@nospam.web.dewrote:

>Martin Marcher wrote:

>On 2008-08-26 00:32:20, cnb wrote:

>>Are dictionaries the same as hashtables?

[Fredrik Lundh]

Martin Marcher wrote:

>Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

are you sure you know what "collision handling" means in this context?

</F>

[Fredrik Lundh]

Diez B. Roggisch wrote:

I don't know the exact names of the involved structures - I named them
liberally from my understanding of how associative arrays based on hashing
are implemented. But the below code shows that hash-collisions can occur
without corrupting data

http://en.wikipedia.org/wiki/Open_addressing

"Open addressing, or closed hashing, is a method of collision resolution
in hash tables. With this method a hash collision is resolved by
probing, or searching through alternate locations in the array (the
probe sequence) until either the target record is found, or an unused
array slot is found, which indicates that there is no such key in the
table."

</F>

[Diez B. Roggisch]

Cameron Laird wrote:

In article <6h************@mid.uni-berlin.de>,
Diez B. Roggisch <de***@nospam.web.dewrote:

>>Martin Marcher wrote:

>>On 2008-08-26 00:32:20, cnb wrote:
Are dictionaries the same as hashtables?

.
.
.

>>Python does not have a "one key maps to a list of values"-semantics -
which I consider the sane choice...

However, you can have that using the defaultdict for example:

listdict = defaultdict(list)

listdict[key].append(value)

Diez

? I'm lost. As I understand your terms, Python's dictionaries
map keys to objects, but you would prefer that Python's
dictionaries map keys only to lists of values. That *sounds*
like a complexification, at best. Are you trying to make a
point about implementation aligning with semantics?

The OP seems to want that (or at least sees it as one of two viable design
choices), see his other answer in this thread.

I certainly *don't* agree with that, I merely pointed out that python comes
with means to easily create such a data-structure in the case it is needed.

Diez

[Chris Mellon]

On Tue, Aug 26, 2008 at 11:12 AM, Fredrik Lundh <fr*****@pythonware.comwrote:

Martin Marcher wrote:

>>Are dictionaries the same as hashtables?

Yes, but there is nothing in there that does sane collision handling
like making a list instead of simply overwriting.

are you sure you know what "collision handling" means in this context?

I think the confusion comes from thinking that dictionaries are
(really) hash tables and thus that things like collision handling are
exposed to the user of the data structure. In this sense, no,
dictionaries are *not* hash tables. They are mappings of keys to
values, and they use hash tables as part of their implementation.

[Cameron Laird]

In article <6h************@mid.uni-berlin.de>,
Diez B. Roggisch <de***@nospam.web.dewrote:

>Cameron Laird wrote:

>In article <6h************@mid.uni-berlin.de>,
Diez B. Roggisch <de***@nospam.web.dewrote:

>>>Martin Marcher wrote:

On 2008-08-26 00:32:20, cnb wrote:
Are dictionaries the same as hashtables?

.
.
.

>>>Python does not have a "one key maps to a list of values"-semantics -
which I consider the sane choice...

However, you can have that using the defaultdict for example:

listdict = defaultdict(list)

listdict[key].append(value)

Diez

? I'm lost. As I understand your terms, Python's dictionaries
map keys to objects, but you would prefer that Python's
dictionaries map keys only to lists of values. That *sounds*
like a complexification, at best. Are you trying to make a
point about implementation aligning with semantics?

The OP seems to want that (or at least sees it as one of two viable design
choices), see his other answer in this thread.

I certainly *don't* agree with that, I merely pointed out that python comes
with means to easily create such a data-structure in the case it is needed.

Diez

Oh! Thanks for clearing *that* up; I certainly had a different
impression.

To the original poster then: please be aware that the values of
Python's dictionaries not only can be any first-class objects,
but it's quite common--quite common in *my* code, anyway--for
dictionaries to range over lists, tuples, functions, other
dictionaries, and more. Python needn't change to allow you to
write any of this.