Re: Dictionary Keys question

On Jan 30, 7:02 pm, FireNWater <kho...@xxxxxxxxx> wrote:
Thank you for the explanation. . . I think I now have a (foggy)
understanding of hash tables. It seems to be a way to create order
(an index) out of disorder (random numbers or characters) behind the
scenes. .

The key thing to realize is, quite simply, don't rely on order in a
dictionary. If you do, bad things can happen. The underlying
implementation is not important to know.

But if you really do want to know, let me correct you here, and give a
perhaps clearer explanation (if not, there's no need to read any
further):

The 'order' that your speaking of is not implemented by the hash
*table*, per se, but rather by the hash function, which returns an
integer (the hash code).

The hash table takes the hash code and calculates where in its list to
place the object (as explained before, using modulo to shrink the
integer into the range of the list). If multiple items end up in the
same list, they are placed into a kind of linked list, with each node
containing an object and pointing to the next. Of course, if too many
objects end up in the same bucket, the efficiency of finding an object
in the hash table reduces to that of a linked list, so hash functions
are generally implemented to ensure a unique number (or as unique as
possible) to every object.

Python dictionaries are hash tables that automatically grow as space
is needed. While integers in the range of the list will never change
location unless the list shrinks, larger hash codes can move around
quite apparently randomly. Space available is also a factor, as others
have found out on this list. The order of a dictionary *is*
determined, but factors involved in deciding that order may appear
surprisingly mundane, and certainly variable across runs of your
program.
.

Relevant Pages

  • Mutable objects which define __hash__ (was Re: Why are tuples immutable?)
    ... The actual rule dictionaries use when deciding whether or not to allow a key is ... simply 'can I hash it?'. ... > nothing wrong with using such mutable objects as keys. ... # Mutate some value in mylist ...
    (comp.lang.python)
  • Re: Why is dictionary.keys() a list and not a set?
    ... convenient and usually well-understood way of describing which builtin ... > but semantics suffers greatly. ... dictionaries. ... object is hashable if calling hash on that object returns an integer. ...
    (comp.lang.python)
  • Re: Mutable objects which define __hash__ (was Re: Why are tuples immutable?)
    ... > A second time a key may be hashed is when it is used as a lookup key. ... hash, that seems to be a performance gain that is independent of the dictionary ... mutables keys or list entries, ... Dictionaries or sets are a nice way to do that, ...
    (comp.lang.python)
  • Re: Hashed password secure?
    ... > Consider the way that a typical password hash attack program works. ... > the salt, and then it hashes the dictionary once for each unique salt value ... So the attacker has to hash the dictionary 2^16 ... want to not store his dictionaries, he'd have to try on average half his ...
    (sci.crypt)
  • Re: Order of tuples in dict.items()
    ... I suppose it *is* possible for Python to change its hash function ... the very nature of hash tables is that they are dependent on the ... identical dictionaries in the same order when iterated over (of course, ... Keeping a list of keys *in the order they are added* is not the same as ...
    (comp.lang.python)