- Hash tables are an implementation technique used to implement
- mapping between objects. Assuming a good hashing function is used,
- they provide near-constant-time access and storing of information.
- Duplicate keys are not allowed.
-
- This file defines the following entry points: hash_table_new
- creates a hash table, and hash_table_destroy deletes it.
- hash_table_put establishes a mapping between a key and a value.
- hash_table_get retrieves the value that corresponds to a key.
- hash_table_contains queries whether a key is stored in a table at
- all. hash_table_remove removes a mapping that corresponds to a
- key. hash_table_map allows you to map through all the entries in a
- hash table. hash_table_clear clears all the entries from the hash
- table.
-
- The number of mappings in a table is not limited, except by the
- amount of memory. As you add new elements to a table, it regrows
- as necessary. If you have an idea about how many elements you will
- store, you can provide a hint to hash_table_new().
-
- The hashing and equality functions depend on the type of key and
- are normally provided by the user. For the special (and frequent)
- case of using string keys, you can use the pre-canned
- make_string_hash_table(), which provides an efficient string
- hashing function, and a string equality wrapper around strcmp().
-
- When specifying your hash and test functions, make sure the
- following holds true:
-
- - The test function returns non-zero for keys that are considered
- "equal", zero otherwise.
-
- - The hash function returns a number that represents the
- "distinctness" of the object. In more precise terms, it means
- that for any two objects that test "equal" under the test
- function, the hash function MUST produce the same result.
-
- This does not mean that each distinct object must produce a
- distinct value, only that non-distinct objects must produce the
- same values! For instance, a hash function that returns 0 for
- any given object is a perfectly valid (albeit extremely bad) hash
- function. A hash function that hashes a string by adding up all
- its characters is another example of a valid (but quite bad) hash
- function.
-
- The above stated rule is quite easy to enforce. For example, if
- your testing function compares strings case-insensitively, all
- your function needs to do is lower-case the string characters
- before calculating a hash. That way you have easily guaranteed
- that case differences will not result in a different hash.
-
- - If you care about performance, choose a hash function with as
- good "spreading" as possible. A good hash function will react to
- even a small change in its input with a completely different
- resulting hash. Finally, don't make the hash function itself
- overly slow, because you'll be incurring a non-negligible
- overhead to reads and writes to the hash table.
+ Hash tables are a technique used to implement mapping between
+ objects with near-constant-time access and storage. The table
+ associates keys to values, and a value can be very quickly
+ retrieved by providing the key. Fast lookup tables are typically
+ implemented as hash tables.
+
+ The entry points are
+ hash_table_new -- creates the table.
+ hash_table_destroy -- destroys the table.
+ hash_table_put -- establishes or updates key->value mapping.
+ hash_table_get -- retrieves value of key.
+ hash_table_get_pair -- get key/value pair for key.
+ hash_table_contains -- test whether the table contains key.
+ hash_table_remove -- remove the key->value mapping for key.
+ hash_table_map -- iterate through table mappings.
+ hash_table_clear -- clear hash table contents.
+ hash_table_count -- return the number of entries in the table.
+
+ The hash table grows internally as new entries are added and is not
+ limited in size, except by available memory. The table doubles
+ with each resize, which ensures that the amortized time per
+ operation remains constant.
+
+ By default, tables created by hash_table_new consider the keys to
+ be equal if their pointer values are the same. You can use
+ make_string_hash_table to create tables whose keys are considered
+ equal if their string contents are the same. In the general case,
+ the criterion of equality used to compare keys is specified at
+ table creation time with two callback functions, "hash" and "test".
+ The hash function transforms the key into an arbitrary number that
+ must be the same for two equal keys. The test function accepts two
+ keys and returns non-zero if they are to be considered equal.