Computer systems often use inscrutable identifiers where people would normally use a name. For example, imagine a computer system for managing patients in a hospital. This system would need to maintain a list of appointments, and it would be useful for the hospital’s reception staff to be able to tell arriving patients where to go for their appointment. So the system would need to know about things such as buildings and departments—radiography, physiotherapy, and so on.

The system will usually have some sort of unique identifier for entities such as these in order to avoid ambiguity and ensure data integrity. But users of the system will most likely want to know that an appointment is in the Dr. Marvin Munroe Memorial Building, rather than, say, the building with ID 49. So the user interface will need to convert the ID to text.

The information about which ID corresponds to which building typically belongs in a database, or possibly a configuration file. You wouldn’t want to bake the list into a big switch statement in the code, as that would make it hard to support multiple customers, and would also need a new software release anytime a building is built or renamed.

The user interface could just look up the name in the database every time it needs to display an appointment’s information, but there are a few problems with this. First, the computer running the UI might not have access to the database—if the UI is written as a client-side application in WPF or Windows Forms, there’s a good chance that it won’t—a lot of companies put databases behind firewalls that restrict access even on the internal network. And even if it did, making a request to the server for each ID-based field takes time—in a form with several such fields, you could easily end up causing a noticeable delay. And this would be unnecessary for data that’s not expected to change from day to day.

A dictionary can provide a better solution here. When the application starts up, it can load a dictionary to go from an ID to a name. Translating an ID to a displayable name then becomes as simple as this:

string buildingName = buildingIdToNameMap[buildingId];

As for how you would load this dictionary in the first place, that’ll depend on where the data is stored. Whether it’s coming from a file, a database, a web service, or somewhere else, you can use LINQ to initialize a dictionary—we’ll see how to do that in “Dictionaries and LINQ.”

Dictionaries are often used to cache information that is slow to fetch or create. Information can be placed in a dictionary the first time it is loaded, allowing an application to avoid that cost the next time the information is required. For example, suppose a doctor is with a patient, and wants to look at information regarding recent tests or medical procedures the patient has undergone. This will typically involve requesting records from some server to describe these patient encounters, and you might find that the application can be made considerably more responsive by keeping hold of the records on the client side after they have been requested so that they don’t have to be looked up again and again as the doctor scrolls through a list of records.

This is a very similar idea to the lookup usage we described earlier, but there are two important differences. First, caches usually need some sort of policy that decides when to remove data from the cache—if we add every record we load into the cache and never clear out old ones, the cache will consume more memory over time, slowing the program down, which is the opposite of the intended effect. The appropriate policy for removing items from a cache will be application-specific. In a patient record viewing application, the best approach might be to clear the cache as soon as the doctor starts looking up information for a new patient, since that suggests the doctor has moved on to a new appointment and therefore won’t be looking at the previous patient’s details anytime soon. But that policy works only because of how this particular system is used—other systems may require other mechanisms. Another popular heuristic is to set an upper limit on either the number of entries or the total size of the data in a cache, and to remove items based on when they were last retrieved.

The second difference between using a dictionary to cache data rather than to look up preloaded data is that in caching scenarios, the data involved is often more dynamic. A list of known countries won’t change very often, but patient records might change while in use, particularly if the patient is currently in the hospital. So when caching copies of information locally in a dictionary, you need to have some way of dealing with the fact that the information in the cache might be stale. (For example, although caching patient records locally would be useful, your application might need to deal with the possibility that new test results become available while the patient is with the doctor.) As with removal policy, detection of stale data requires application-specific logic.

For example, some data might never change—accounting data usually works this way, because even when data is discovered to be incorrect, it’s not usually modified. Legal auditing requirements usually mean you have to fix problems by adding a new accounting record that corrects the old one. So for this sort of entry, you know that a cache of any given record will never be stale. (Newer records might exist that supersede the cached record you have, but the cache of that record will still be consistent with whatever is in the database for that entry.)

Sometimes it might be possible to perform a relatively cheap test to discover whether the cached record is consistent with the information on a server. HTTP supports this—a client can send a request with an If-Modified-Since header, containing the date at which the cached information was known to be up-to-date. If the server has no newer information, it sends a very short reply to confirm this, and will not send a new copy of the data. Web browser caches use this to make web pages you’ve previously visited load faster, while ensuring that you always see the most recent version of the page.

But you may simply have to guess. Sometimes the best staleness heuristic available to you might be something such as “If the cached record we have is more than 20 minutes old, let’s get a fresh copy from the server.” But you need to be careful with this approach. Guesswork can sometimes lead to a cache that offers no useful performance improvements, or which produces data that is too stale to be useful, or both.

Regardless of the precise details of your cache removal and staleness policies, the approach will look something like Example 9-5. (The Record type in this example is not a class library type, by the way. It’s just for illustration—it would be the class for whatever data you want to cache.)

class RecordCache
{
    private Dictionary<int, Record> cachedRecords =
        new Dictionary<int, Record>();

    public Record GetRecord(int recordId)
    {
        Record result;
        if (cachedRecords.TryGetValue(recordId, out result))
        {
            // Found item in cache, but is it stale?
            if (IsStale(result))
            {
                result = null;
            }
        }

        if (result == null)
        {
            result = LoadRecord(recordId);
            // Add newly loaded record to cache
            cachedRecords[recordId] = result;
        }
        DiscardAnyOldCacheEntries();

        return result;
    }

    private Record LoadRecord(int recordId)
    {
        ... Code to load the record would go here ...
    }

    private bool IsStale(Record result)
    {
        ... Code to work out whether the record is stale would go here ...
    }

    private void DiscardAnyOldCacheEntries()
    {
        ... Cache removal policy code would go here ...
    }
}

Notice that this code does not use the indexer to look up a cache entry. Instead, it uses a method called TryGetValue. You use this when you’re not sure if the dictionary will contain the entry you’re looking for—in this case, the entry won’t be present the first time we look it up. (The dictionary would throw an exception if we use the indexer to look up a value that’s not present.) TryGetValue returns true if an entry for the given key was found, and false if not. Notice that its second argument uses the out qualifier and it uses this to return the item when it’s found, or a null reference when it’s not found.

Another common use for a dictionary is when you want something that works like a property, but where the set of available properties is not necessarily fixed. For example, WCF is designed to send and receive messages over a wide range of network technologies, each of which may have its own unique characteristics. So WCF defines some normal properties and methods to deal with aspects of communication that are common to most scenarios, but also provides a dictionary of dynamic properties to handle transport-specific scenarios.

For example, if you are using WCF with HTTP-based communication, you might want your client code to be able to modify the User-Agent header. This header is specific to HTTP, and so WCF doesn’t provide a property for this as part of its programming model, because it wouldn’t do anything for most network protocols. Instead, you control this with a dynamic property, added via the WCF Message type’s Properties dictionary, as Example 9-6 shows.

Message wcfMessage = CreateMessageSomehow();

HttpRequestMessageProperty reqProps = new HttpRequestMessageProperty();
reqProps.Headers.Add(HttpRequestHeader.UserAgent, "my user agent");

wcfMessage.Properties[HttpRequestMessageProperty.Name] = reqProps;

The final common scenario we’ll look at for dictionaries is to provide efficient storage for a sparse array. A sparse array is indexed by an integer, like a normal array, but only a tiny fraction of its elements contain anything other than the default value. For a numeric element type that would mean the array is mostly zeros, while for a reference type it would be mostly nulls.

As an example of where this might be useful, consider a spreadsheet. When you create a new spreadsheet, it appears to be a large expanse of cells. But it’s not really storing information for every cell. I just ran Microsoft Excel, pressed Ctrl-G to go to a particular cell and typed in $XFD$1000000, and then entered a value for that cell. This goes to the 16,384th column (which is as wide as Excel 2007 can go), and the 1 millionth row. Yet despite spanning more than 16 billion cells, the file is only 8 KB. And that’s because it doesn’t really contain all the cells—it only stores information for the cells that contain something.

The spreadsheet is sparse—it is mostly empty. And it uses a representation that makes efficient use of space when the data is sparse.

If you try to create a rectangular array with 16,384 columns and 1 million rows, you’ll get an exception as such an array would go over the .NET 4 upper size limit for any single array of 2 GB. A newly created array always contains default values for all of its elements, so the information it contains is always sparse to start with—sparseness is a characteristic of the data, rather than the storage mechanism, but the fact that we simply cannot create a new, empty array this large demonstrates that a normal array doesn’t store sparse information efficiently.

There is no built-in type designed specifically for storing sparse data, but we can use a dictionary to make such a thing. Example 9-7 uses a dictionary to provide storage for a single-dimensional sparse array of double elements. It uses long as the index argument type to enable the array to grow to a logical size that is larger than would be possible with an int, which tops out at around 2.1 billion.

class SparseArray
{
    private Dictionary<long, double> nonEmptyValues =
                                         new Dictionary<long, double>();

    public double this[long index]
    {
        get
        {
            double result;
            nonEmptyValues.TryGetValue(index, out result);
            return result;
        }
        set
        {
            nonEmptyValues[index] = value;
        }
    }
}

Notice that this example doesn’t bother to check the return value from TryGetValue. That’s because when it fails to find the entry, it sets the result to the default value, and in the case of a double, that means 0. And 0 is what we want to return for an entry whose value has not been set yet.

The following code uses the SparseArray class:

SparseArray big = new SparseArray();
big[0] = 123;
big[10000000000] = 456;

Console.WriteLine(big[0]);
Console.WriteLine(big[2]);
Console.WriteLine(big[10000000000]);

This sets the value of the first element, and also the element with an index of 10 billion—this simply isn’t possible with an ordinary array. And yet it works fine here, with minimal memory usage. The code prints out values for three indexes, including one that hasn’t been set. Here are the results:

123
0
456

Reading the value that hasn’t been set returns the default value of 0, as required.