<commit_before>Hash Table
==========

.. code:: C

    #include "libstephen/ht.h"

-  `Header
   (master) <https://github.com/brenns10/libstephen/blob/master/inc/libstephen/ht.h>`__
-  `Implementation
   (master) <https://github.com/brenns10/libstephen/blob/master/src/hashtable.c>`__

The hash table associates keys with values. It uses a "hash" to
determine the location of a key inside an array, and uses that to
achieve nearly constant time lookup. A hash table needs enough memory to
ensure that the table is about half empty, in order to work properly.
So, the table basically trades off memory for access speed.

Infrastructure
--------------

Hash tables need a good deal more infrastructure than a simple list
needs. A list can store values without knowing or caring about their
type. On the other hand, a hash table needs to know the data type of its
keys for these reasons: \* Hashing! A hash function takes a key and
produces a number, which can hopefully be used to index into the table.
You need to know the data type in order to come up with a good hash
table. \* Equality testing! A hash function is bound to have collisions.
So, a hash table needs to be able to check whether keys are equal, and
that means knowing the type of the keys.

To handle this, the hash table takes function pointers of two different
types. The first is called ``HASH_FUNCTION``:

.. code:: C

    typedef unsigned int (*HASH_FUNCTION)(DATA toHash);
    unsigned int my_hash(DATA toHash) {
      //compute hash value
      return hash_value;
    }
<commit_msg>Fix doc/tutorial/hashtable.rst list formatting.<commit_after>Hash Table
==========

.. code:: C

    #include "libstephen/ht.h"

-  `Header
   (master) <https://github.com/brenns10/libstephen/blob/master/inc/libstephen/ht.h>`__
-  `Implementation
   (master) <https://github.com/brenns10/libstephen/blob/master/src/hashtable.c>`__

The hash table associates keys with values. It uses a "hash" to
determine the location of a key inside an array, and uses that to
achieve nearly constant time lookup. A hash table needs enough memory to
ensure that the table is about half empty, in order to work properly.
So, the table basically trades off memory for access speed.

Infrastructure
--------------

Hash tables need a good deal more infrastructure than a simple list
needs. A list can store values without knowing or caring about their
type. On the other hand, a hash table needs to know the data type of its
keys for these reasons:

- Hashing! A hash function takes a key and produces a number, which can
  hopefully be used to index into the table.  You need to know the data type in
  order to come up with a good hash table.
- Equality testing! A hash function is bound to have collisions.  So, a hash
  table needs to be able to check whether keys are equal, and that means knowing
  the type of the keys.

To handle this, the hash table takes function pointers of two different
types. The first is called ``HASH_FUNCTION``:

.. code:: C

    typedef unsigned int (*HASH_FUNCTION)(DATA toHash);
    unsigned int my_hash(DATA toHash) {
      //compute hash value
      return hash_value;
    }

{'fraction_non_alphanumeric': 0.07875516036837091, 'fraction_numerical': 0.0025404890441409972, 'mean_word_length': 3.5718432510885343, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6581727', 'n_tokens_mistral': 887, 'n_tokens_neox': 858, 'n_words': 447}