<commit_before>.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata:: Improved Collision Resolution
   :author: <NAME>
   :prerequisites:
   :topic: Hashing
   :short_name: HashCImproved
   :exercises: 

.. _HashFunc:

.. include:: JSAVheader.rinc

Improved Collision Resolution
=============================

Linear Probing by Steps
-----------------------

How can we avoid primary clustering?
One possible improvement might be to use linear probing,
but to skip slots by some constant :math:`c` other than 1.
This would make the probe function
:math:`\textbf{p}(K, i) = ci`,
and so the :math:`i` th slot in the probe sequence will be
:math:`\textbf{h}(K) + ic) \mod M`.
In this way, records with adjacent home positions will not follow the
same probe sequence.
For example, if we were to skip by twos, then our offsets from the home
slot would be 2, then 4, then 6, and so on.

One quality of a good probe sequence is that it will cycle through
all slots in the hash table before returning to the home position.
Clearly linear probing (which "skips" slots by one each time) does this.
Unfortunately, not all values for <i>c</i> will make this happen.
For example, if :math:`c = 2` and the table contains an even number of
slots, then any key whose home position is in an even slot will have
a probe sequence that cycles through only the even slots.
Likewise, the probe sequence for a key whose home position is in an
odd slot will cycle through the odd slots.
Thus, this combination of table size and linear probing constant
effectively divides the records into two sets stored in two
disjoint sections of the hash table.
So long as both sections of the table contain the same number of records,
this is not really important.
However, just from chance it is likely that one section will become
fuller than the other, leading to more collisions and poorer
performance for those records.
The other section would have fewer records, and thus better
performance.
But the overall system performance will be degraded,
as the additional cost to the side that is more full outweighs the
improved performance of the less-full side.

Constant :math:`c` must be relatively prime to :math:`M` to generate a
linear probing sequence that visits all slots in the table
(that is, :math:`c` and :math:`M` must share no factors).
For a hash table of size :math:`M = 10`, if :math:`c`
is any one of 1, 3, 7, or 9,
then the probe sequence will visit all slots for any key.
When :math:`M = 11`, any value for :math:`c` between 1 and 10 generates a
probe sequence that visits all slots for every key.

.. TODO::
   :type: Slideshow

   This applet shows one performance effect of using a collision resolution
   method that generates disjoint tables.
   The graph shows the probability that an insert operation will fail as the
   hash table fills up.
   When the probe function visits every slot of the table, insertion can
   never fail unless the hash table is full.
   But if the probe function does not visit every slot (such as when the
   step size for linear probing is 2 and the table size is even), then
   it is possible for one of the sub-tables to become full before the entire
   table is full.
   In this graph, the step size is always 2.

Consider the situation where :math:`c = 2` and we wish to insert a record
with key :math:`k_1` such that
:math:`\textbf{h}(k_1) = 3`.
The probe sequence for  :math:`k_1` is 3, 5, 7, 9, and so on.
If another key :math:`k_2` has home position at slot 5,
then its probe sequence will be 5, 7, 9, and so on.
The probe sequences of :math:`k_1` and :math:`k_2`
are linked together in a manner that contributes to clustering.
In other words, linear probing with a value of :math:`c > 1` does not
solve the problem of primary clustering.
We would like to find a probe function that does not link
keys together in this way.
We would prefer that the probe sequence for :math:`k_1`
after the first step on the sequence should not be identical to the
probe sequence of :math:`k_2`.
Instead, their probe sequences should diverge.

.. avembed:: Exercises/Sorting/HashingLinearStepProbePRO.html
   :showbutton: hide
   :title: Linear Probing by Steps Exercise

Pseudo-Random Probing
---------------------

The ideal probe function would select the next position on the probe
sequence at random from among the unvisited slots; that is, the probe
sequence should be a random permutation of the hash table positions.
Unfortunately, we cannot actually select the next position in the
probe sequence at random, because we would not be able to duplicate
this same probe sequence when searching for the key.
However, we can do something similar called
:dfn:`pseudo-random probing`.
In pseudo-random probing, the :math:`i` th slot in the probe sequence is
:math:`(\textbf{h}(K) + r_i) \mod M`
where :math:`r_i` is the :math:`i` th value in a random permutation
of the numbers from 1 to :math:`M-1`.
All insertions and searches use the same sequence of random numbers.
The probe function would be
:math:`\textbf{p}(K, i) = \textbf{Perm}[i-1]`
where **Perm** is an array of length :math:`M-1` containing a
random permutation of the values from 1 to :math:`M - 1`.

.. TODO::
   :type: Slideshow

   As you select values to insert, be sure to trigger collision resolution
   enough times to get an understanding of how pseudo-random probing works.
   Try hitting the "reset" button, and see how the random permutation being
   used will change.

.. avembed:: Exercises/Sorting/HashingPseudoRandomProbePRO.html
   :showbutton: hide
   :title: Pseudo-Random Probing Exercise


Quadratic Probing
-----------------

Another probe function that eliminates
primary clustering is called
:dfn:`quadratic probing`.
Here the probe function is some quadratic function
:math:`\textbf{p}(K, i) = c_1 i^2 + c_{2}i + c_3`
for some choice of constants :math:`c_1`, :math:`c_2`,
and  :math:`c_3`.

The simplest variation is :math:`\textbf{p}(K, i) = i^2`
(i.e., :math:`c_1 = 1`, :math:`c_2 = 0`, and
:math:`c_3 = 0`).
Then the :math:`i` th value in the probe sequence would be
:math:`(\textbf{h}(K) + i^2) \mod M`.
Under quadratic probing, two keys with different home
positions will have diverging probe sequences.
For example, given a hash table of size :math:`M = 101`, assume
for keys :math:`k_1` and :math:`k_2` that
and :math:`\textbf{h}(k_1) = 30` and 
:math:`\textbf{h}(k_2) = 29`.
The probe sequence for :math:`k_1` is 30,
then 31, then 34, then 39.
The probe sequence for :math:`k_2` is 29,
then 30, then 33, then 38.
Thus, while :math:`k_2` will probe to :math:`k_1`'s
home position as its second choice, the two keys' probe sequences
diverge immediately thereafter.

.. TODO::
   :type: KA

   Try inserting numbers for yourself, and demonstrate how the probe
   sequences for diverge by inserting these numbers into a table of size
   16: 0, 16, 32, 15, 31.

Unfortunately, quadratic probing has the disadvantage that typically
not all hash table slots will be on the probe sequence.
Using :math:`\textbf{p}(K, i) = i^2`
gives particularly inconsistent results.
For many hash table sizes, this probe function will cycle through a
relatively small number of slots.
If all slots on that cycle happen to be full, this means that the
record cannot be inserted at all!
For example, if our hash table has three slots, then records that hash
to slot 0 can probe only to slots 0 and 1 (that is, the probe sequence
will never visit slot 2 in the table).
Thus, if slots 0 and 1 are full, then the record cannot be inserted
even though the table is not full!
A more realistic example is a table with 105 slots.
The probe sequence starting from any given slot will only visit 23
other slots in the table.
If all 24 of these slots should happen to be full, even if other slots
in the table are empty, then the record cannot be inserted because the
probe sequence will continually hit only those same 24 slots.

.. TODO::
   :type: KA or slideshow

   Now go back up to the applet above. Pick some hash table size, and try
   to insert values that all hash to the same slot. See how they follow a
   probe sequence that will not fill the table.
   Try to 'fill the probe sequence' such that a record cannot be
   inserted into the table, even though the table is not full.

Fortunately, it is possible to get good results from quadratic probing
at low cost.<commit_msg>Added quadratic probing KA exercise to RST<commit_after>.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata:: Improved Collision Resolution
   :author: <NAME>
   :prerequisites:
   :topic: Hashing
   :short_name: HashCImproved
   :exercises: 

.. _HashFunc:

.. include:: JSAVheader.rinc

Improved Collision Resolution
=============================

Linear Probing by Steps
-----------------------

How can we avoid primary clustering?
One possible improvement might be to use linear probing,
but to skip slots by some constant :math:`c` other than 1.
This would make the probe function
:math:`\textbf{p}(K, i) = ci`,
and so the :math:`i` th slot in the probe sequence will be
:math:`\textbf{h}(K) + ic) \mod M`.
In this way, records with adjacent home positions will not follow the
same probe sequence.
For example, if we were to skip by twos, then our offsets from the home
slot would be 2, then 4, then 6, and so on.

One quality of a good probe sequence is that it will cycle through
all slots in the hash table before returning to the home position.
Clearly linear probing (which "skips" slots by one each time) does this.
Unfortunately, not all values for <i>c</i> will make this happen.
For example, if :math:`c = 2` and the table contains an even number of
slots, then any key whose home position is in an even slot will have
a probe sequence that cycles through only the even slots.
Likewise, the probe sequence for a key whose home position is in an
odd slot will cycle through the odd slots.
Thus, this combination of table size and linear probing constant
effectively divides the records into two sets stored in two
disjoint sections of the hash table.
So long as both sections of the table contain the same number of records,
this is not really important.
However, just from chance it is likely that one section will become
fuller than the other, leading to more collisions and poorer
performance for those records.
The other section would have fewer records, and thus better
performance.
But the overall system performance will be degraded,
as the additional cost to the side that is more full outweighs the
improved performance of the less-full side.

Constant :math:`c` must be relatively prime to :math:`M` to generate a
linear probing sequence that visits all slots in the table
(that is, :math:`c` and :math:`M` must share no factors).
For a hash table of size :math:`M = 10`, if :math:`c`
is any one of 1, 3, 7, or 9,
then the probe sequence will visit all slots for any key.
When :math:`M = 11`, any value for :math:`c` between 1 and 10 generates a
probe sequence that visits all slots for every key.

.. TODO::
   :type: Slideshow

   This applet shows one performance effect of using a collision resolution
   method that generates disjoint tables.
   The graph shows the probability that an insert operation will fail as the
   hash table fills up.
   When the probe function visits every slot of the table, insertion can
   never fail unless the hash table is full.
   But if the probe function does not visit every slot (such as when the
   step size for linear probing is 2 and the table size is even), then
   it is possible for one of the sub-tables to become full before the entire
   table is full.
   In this graph, the step size is always 2.

Consider the situation where :math:`c = 2` and we wish to insert a record
with key :math:`k_1` such that
:math:`\textbf{h}(k_1) = 3`.
The probe sequence for  :math:`k_1` is 3, 5, 7, 9, and so on.
If another key :math:`k_2` has home position at slot 5,
then its probe sequence will be 5, 7, 9, and so on.
The probe sequences of :math:`k_1` and :math:`k_2`
are linked together in a manner that contributes to clustering.
In other words, linear probing with a value of :math:`c > 1` does not
solve the problem of primary clustering.
We would like to find a probe function that does not link
keys together in this way.
We would prefer that the probe sequence for :math:`k_1`
after the first step on the sequence should not be identical to the
probe sequence of :math:`k_2`.
Instead, their probe sequences should diverge.

.. avembed:: Exercises/Sorting/HashingLinearStepProbePRO.html
   :showbutton: hide
   :title: Linear Probing by Steps Exercise

Pseudo-Random Probing
---------------------

The ideal probe function would select the next position on the probe
sequence at random from among the unvisited slots; that is, the probe
sequence should be a random permutation of the hash table positions.
Unfortunately, we cannot actually select the next position in the
probe sequence at random, because we would not be able to duplicate
this same probe sequence when searching for the key.
However, we can do something similar called
:dfn:`pseudo-random probing`.
In pseudo-random probing, the :math:`i` th slot in the probe sequence is
:math:`(\textbf{h}(K) + r_i) \mod M`
where :math:`r_i` is the :math:`i` th value in a random permutation
of the numbers from 1 to :math:`M-1`.
All insertions and searches use the same sequence of random numbers.
The probe function would be
:math:`\textbf{p}(K, i) = \textbf{Perm}[i-1]`
where **Perm** is an array of length :math:`M-1` containing a
random permutation of the values from 1 to :math:`M - 1`.

.. TODO::
   :type: Slideshow

   As you select values to insert, be sure to trigger collision resolution
   enough times to get an understanding of how pseudo-random probing works.
   Try hitting the "reset" button, and see how the random permutation being
   used will change.

.. avembed:: Exercises/Sorting/HashingPseudoRandomProbePRO.html
   :showbutton: hide
   :title: Pseudo-Random Probing Exercise


Quadratic Probing
-----------------

Another probe function that eliminates
primary clustering is called
:dfn:`quadratic probing`.
Here the probe function is some quadratic function
:math:`\textbf{p}(K, i) = c_1 i^2 + c_{2}i + c_3`
for some choice of constants :math:`c_1`, :math:`c_2`,
and  :math:`c_3`.

The simplest variation is :math:`\textbf{p}(K, i) = i^2`
(i.e., :math:`c_1 = 1`, :math:`c_2 = 0`, and
:math:`c_3 = 0`).
Then the :math:`i` th value in the probe sequence would be
:math:`(\textbf{h}(K) + i^2) \mod M`.
Under quadratic probing, two keys with different home
positions will have diverging probe sequences.
For example, given a hash table of size :math:`M = 101`, assume
for keys :math:`k_1` and :math:`k_2` that
and :math:`\textbf{h}(k_1) = 30` and 
:math:`\textbf{h}(k_2) = 29`.
The probe sequence for :math:`k_1` is 30,
then 31, then 34, then 39.
The probe sequence for :math:`k_2` is 29,
then 30, then 33, then 38.
Thus, while :math:`k_2` will probe to :math:`k_1`'s
home position as its second choice, the two keys' probe sequences
diverge immediately thereafter.

.. TODO::
   :type: KA

   Try inserting numbers for yourself, and demonstrate how the probe
   sequences for diverge by inserting these numbers into a table of size
   16: 0, 16, 32, 15, 31.


.. avembed:: Exercises/Sorting/HashingQuadraticProbePRO.html
   :showbutton: hide
   :title: Quadratic Probing Exercise

Unfortunately, quadratic probing has the disadvantage that typically
not all hash table slots will be on the probe sequence.
Using :math:`\textbf{p}(K, i) = i^2`
gives particularly inconsistent results.
For many hash table sizes, this probe function will cycle through a
relatively small number of slots.
If all slots on that cycle happen to be full, this means that the
record cannot be inserted at all!
For example, if our hash table has three slots, then records that hash
to slot 0 can probe only to slots 0 and 1 (that is, the probe sequence
will never visit slot 2 in the table).
Thus, if slots 0 and 1 are full, then the record cannot be inserted
even though the table is not full!
A more realistic example is a table with 105 slots.
The probe sequence starting from any given slot will only visit 23
other slots in the table.
If all 24 of these slots should happen to be full, even if other slots
in the table are empty, then the record cannot be inserted because the
probe sequence will continually hit only those same 24 slots.

.. TODO::
   :type: KA or slideshow

   Now go back up to the applet above. Pick some hash table size, and try
   to insert values that all hash to the same slot. See how they follow a
   probe sequence that will not fill the table.
   Try to 'fill the probe sequence' such that a record cannot be
   inserted into the table, even though the table is not full.

Fortunately, it is possible to get good results from quadratic probing
at low cost.
{'fraction_non_alphanumeric': 0.07943138961415724, 'fraction_numerical': 0.01392515230635335, 'mean_word_length': 3.982943047123446, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 0, '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': '4412085', 'n_tokens_mistral': 5054, 'n_tokens_neox': 4701, 'n_words': 2719}