[Tutor] object representation

Alan Gauld alan.gauld at btinternet.com
Thu Mar 4 09:50:53 CET 2010

"spir" <denis.spir at gmail.com> wrote

> Does this mean that the associative arrays representing objects are
> implemented like python dicts, thus hash tables?

Yes, in fact I think they are Python dicts - although I've never actually
looked at the source to confirm that.

> I was wondering about the question because I guess the constraints
> are quite different:
> * Dict keys are of any type, including heterogeneous (mixed).
> Object keys are names, ie a subset of strings.

The keys must be immutable but ...
the object keys are a perfect subset of the generic dict.

> * Object keys are very stable, typically they hardly change;
> usually only values change. Dicts often are created empty and fed in a 
> loop.

The normal case is as you say but you can if you with create an empty
object and then later add attributes - in a loop if you wish.

> * Objects are small mappings: entries are explicitely written in code 
> (*).
> Dicts can be of any size, only limited by memory; they are often fed
> by computation.

But again the object usage is just a subset of the generic.

> * In addition, dict keys can be variables, while object keys rarely
> are: they are literal constants (*).

variables in Python are just names that efer to objects.
When you use a variable as a key to a dict you really use
the value of the variable.

>>> d = {}
>>> x = 42
>>> d[x] = 66
>>> d[42]
>>> d[x]
>>> x = 5
>>> d[x]
Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
KeyError: 5

It is the value of x that is the key not 'x'. If you change the value of x
it ceases to be a valid key of the dict.

> So, I guess the best implementations for objects and dicts may
> be quite different. i wonder about alternatives for objects,

They could be different and perhaps optimised but I don't think
they are. Pythons dicts are already pretty efficient. They form
the backbone of almost everything in Python not just objects.

> in particuliar trie and variants: http://en.wikipedia.org/wiki/Trie,
> because they are specialised for associative arrays which keys are 
> strings.

> PS: Would someone point me to typical hash funcs for string keys,
> and the one used in python?

Wikipedia for generic and the source for Python?


Alan Gauld
Author of the Learn to Program web site

More information about the Tutor mailing list