Memory efficiency: One large dictionary or a dictionary of smaller dictionaries?

by

Three suggestions:

  1. Use one dictionary.
    It’s easier, it’s more straightforward, and someone else has already optimized this problem for you. Until you’ve actually measured your code and traced a performance problem to this part of it, you have no reason not to do the simple, straightforward thing.

  2. Optimize later.
    If you are really worried about performance, then abstract the problem make a class to wrap whatever lookup mechanism you end up using and write your code to use this class. You can change the implementation later if you find you need some other data structure for greater performance.

  3. Read up on hash tables.
    Dictionaries are hash tables, and if you are worried about their time or space overhead, you should read up on how they’re implemented. This is basic computer science. The short of it is that hash tables are:

    • average case O(1) lookup time
    • O(n) space (Expect about 2n, depending on various parameters)

    I do not know where you read that they were O(n^2) space, but if they were, then they would not be in widespread, practical use as they are in most languages today. There are two advantages to these nice properties of hash tables:

    1. O(1) lookup time implies that you will not pay a cost in lookup time for having a larger dictionary, as lookup time doesn’t depend on size.
    2. O(n) space implies that you don’t gain much of anything from breaking your dictionary up into smaller pieces. Space scales linearly with number of elements, so lots of small dictionaries will not take up significantly less space than one large one or vice versa. This would not be true if they were O(n^2) space, but lucky for you, they’re not.

    Here are some more resources that might help:

    • The Wikipedia article on Hash Tables gives a great listing of the various lookup and allocation schemes used in hashtables.
    • The GNU Scheme documentation has a nice discussion of how much space you can expect hashtables to take up, including a formal discussion of why “the amount of space used by the hash table is proportional to the number of associations in the table”. This might interest you.

    Here are some things you might consider if you find you actually need to optimize your dictionary implementation:

    • Here is the C source code for Python’s dictionaries, in case you want ALL the details. There’s copious documentation in here:
    • Here is a python implementation of that, in case you don’t like reading C.
      (Thanks to Ben Peterson)
    • The Java Hashtable class docs talk a bit about how load factors work, and how they affect the space your hash takes up. Note there’s a tradeoff between your load factor and how frequently you need to rehash. Rehashes can be costly.

Leave a Comment