- Hash tables are an implementation technique used to implement
- mapping between objects. Provided a good hashing function is used,
- they guarantee constant-time access and storing of information.
- Duplicate keys are not allowed.
-
- The basics are all covered. 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_exists 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 are normally provided by the
- user. For the special (and frequent) case of hashing strings, you
- can use the pre-canned make_string_hash_table(), which provides the
- string hashing function from the Dragon Book, and a string equality
- wrapper around strcmp().
-
- When specifying your own 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.
-
- 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 changes in case will not result in a different hash.
-
- - (optional) Choose the hash function to get 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 your hash function extremely slow, because
- you're then defeating the purpose of hashing.
+ 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.