A dictionary--an object of the CFDictionary type--is a hashing-based collection whose keys for accessing its values are arbitrary, program-defined pieces of data (or pointers to data). Although the key is usually a string (or, in Core Foundation, a CFString object), it can be anything that can fit into the size of a pointer--an integer, a reference to a Core Foundation object, even a pointer to a data structure (unlikely as that might be). The keys of dictionaries are unlike the keys of the other collection objects in that, conceptually, they are also contained by the collection along with the values. Dictionaries are primarily useful for holding and organizing data that can be labeled, such as values extracted from text fields in the user interface.
In Core Foundation, a dictionary differs from an array in that the key used to access a particular value in the dictionary remains the same as values are added to or removed from the dictionary--that is, until a value associated with a particular key is replaced or removed. In an array, the key (that is, the index) that is used to retrieve a particular value can change over time as values are added to or deleted from the array. Also, unlike an array, a dictionary does not put its values in any order. To enable later retrieval of a value, the key of the key-value pair should be constant (or be treated as constant); if the key changes after being used to put a value in the dictionary, the value might not be retrievable. The keys of a dictionary form a set; in other words, keys are guaranteed to be unique in a dictionary.
Although a customization of the CFDictionary type might not use hashing and a hash table for storage of the values, the keys require both a function that generates hash codes and a function that tests for equality of two keys based on their hash codes. These two functions together must maintain the invariant that
if equal(X,Y) then hash(X) == hash(Y)
Although the converse of this logic is not generally true, the contrapositive is required by Boolean logic:
if hash(X) != hash(Y), then !equal(X,Y)
If the
hash
and
equal
key callbacks are
NULL
, the key is used as a pointer-sized integer and pointer equality is used. For best performance, you should try to provide a
hash
callback that computes sufficiently dispersed hash codes for the key set.
The access time for a value in a CFDictionary object is guaranteed to be at worst
O(log N)
for any implementation, but is often
O(1)
(constant time). Insertion or deletion operations are typically in constant time as well, but are
O(N*log N)
in the worst cases. It is faster to access values through a key than accessing them directly. Dictionaries tend to use significantly more memory than a array with the same number of values.