Best way to hash a dictionary

[Miki Tebeka]

Hello All,

I need to store dictionary as dictionary keys, and do it efficiently
(which means using native types).
Currently there are 3 ways I can think of: 
1. Using a sorted tuple of dictionary items
2. Using a sorted string from the dictioary items
3. Using a string from the dicionary items (AFAIK this is a bug)

>From my test #1 is the fastet. (See below)
Any other suggestions (are there immutable dictionaries?)?

10x.
Miki

--- h.py ---
#!/usr/bin/env python

def tuple_tag(h):
    items = h.items()
    items.sort()
    return tuple(items)

def str_tag(h):
    # Buggy
    return str(h)

def sorted_str_tag(h):
    items = h.items()
    items.sort()
    return str(items)

def test(hf, times):
    h = {}
    k = {}
    while times > 0:
        k[times] = times
        key = hf(k)
        h[key] = times
        assert(h[key] == times)
        times -= 1

if __name__ == '__main__':
    from sys import argv, exit
    from os.path import basename
    
    def usage():
        print 'usage: %s -t|-s|-ss [TIMES]' % basename(argv[0])
        exit (1)

    if len(argv) not in [2, 3]:
        usage()

    if argv[1] == '-t':
        hf = tuple_tag
    elif argv[1] == '-s':
        hf = str_tag
    elif argv[1] == '-ss':
        hf = sorted_str_tag
    else:
        usage()

    try:
        times = long(argv[2])
    except ValueError:
        usage()
    except IndexError:
        times = 1000

    test(hf, times)
    print '* Done'
--- h.py ---
[09:40] $time h.py -t
* Done
real 2.87
user 2.77
sys 0.05
[09:41] $time h.py -s
* Done
real 3.16
user 2.77
sys 0.04
[09:41] $time h.py -ss
* Done
real 4.40
user 4.36
sys 0.03