View source for Epita: Algo: Course: Info-Spe: Hashing methods

A '''hash function''' is any algorithm that maps data of variable length to data of a fixed length. The values returned by a hash function are called '''hash values, hash codes, hash sums, checksums''' or '''simply hashes'''.
<br/>

== hash principle ==
Let '''''E''''' be a set of names, assume the key is the name itself and that we compute for each item '''''x''''' of the set '''''E''''', a natural number ''h('''x''')'' called '''hash value''' lying between '''''0''''' and '''''8''''' processed as follows :

* Give to the letter '''''a, b, c, ..., z''''' their own ordinal value, that is to say '''''1, 2, 3, ..., 26'''''
* Add together the letter's values of the key
* Add to this number the length (the number of letters) of the key 
* Compute the remainder of the latter value when it was divided by '''''9''''' ''h('''x'''), to obtain the hash value ''h('''x''') <math>\in</math> ['''0,8''']'' 
<br/>

For the set '''''E''' = { '''nathalie, caroline, arnaud, reda, mathieu, jerome, nicolas''' }'', we will obtain the following values :
<br/>
<br/>

{| border="0" cellpadding="5" align="center"
| align="right" | 
|
{| border="0" cellpadding="5" align="center"
| align="right" | ''h('''nathalie''')''
| align="right" | = (70+8) mod 9 
| align="right" | = 6 
|-
| align="right" | ''h('''caroline''')''
| align="right" | = (77+8) mod 9 
| align="right" | = 4
|-
| align="right" | ''h('''arnaud''')''
| align="right" | = (59+6) mod 9
| align="right" | = 2 
|-
| align="right" | ''h('''reda''')''
| align="right" | = (28+4) mod 9
| align="right" | = 5
|-
| align="right" | ''h('''mathieu''')''
| align="right" | = (77+7) mod 9 
| align="right" | = 3 
|-
| align="right" | ''h('''jerome''')''
| align="right" | = (66+6) mod 9
| align="right" | = 0
|-
| align="right" | ''h('''nicolas''')''
| align="right" | = (73+7) mod 9
| align="right" | = 8
|+ '''Valeurs de hachage'''
|}
| align="left" | 
|
{| border="1" cellpadding="5" align="center"
| align="right" | 0
| align="right" | jerome 
|-
| align="right" | 1
|-
| align="right" | 2 
| align="right" | arnaud 
|-
| align="right" | 3
| align="right" | mathieu
|-
| align="right" | 4
| align="right" | caroline
|-
| align="right" | 5
| align="right" | reda 
|-
| align="right" | 6
| align="right" | nathalie
|-
| align="right" | 7
|-
| align="right" | 8
| align="right" | nicolas
|+ '''Associated Hash Table'''
|}
|+ '''Table 1. Hashing of ''E'' (Values and hash table)'''
|}
<br/>
<br/>

The table 1 presents the associated hash table to the previous example. We can see that the restriction of '''''h''''' to '''''E''''' is injective (''perfect hash function''). That is to say that all items '''''x''''' of the set '''''E''''' can be stored in the table and <math>O(1)</math> accesses are required to perform a search in the worst case.

To know if an item '''''x''''' is in '''''E''''', it is sufficient to compute the table index '''''v''' = h('''x''')''.
<br/>

  '''if''' ''v'' = ''1'' '''or''' ''v'' = ''7'' '''then''' 
     ''x'' is not in ''E''
  '''else''' 
     we compare ''x'' with the item which is at the index ''v''
     '''if ''' ''x'' = ''y'' '''then''' 
        ''x'' is in '''''E''''',
     '''if''' ''x''' <math>\neq</math> ''y'' '''then''' 
        ''x'' is not in ''E''


''<u>Remark :</u> Obviously, it is necessary to be able to recognize an "empty" box or not.''
<br/>

If you want to add an item '''''x''''' which has the same hash value as another item '''''y''''' already present in the table, '''''h''''' is no longer injective ('''''x''' <math>\neq</math> '''y''''' and '''''v''' = h('''x''') = h('''y''')''). We call this situation a '''''primary collision''''' between '''''x''''' and '''''y''''' at the slot '''''v'''''.

Later we will see the techniques for resolving the conflict created by collisions. In this case, the fonction no longer gives access to a lone item but to a small group of them.

The set '''''E''''' has been "hashed". This is why the name is ''hash function''.

We use the the hashing methods when we have to store the items of a set belonging to a big universe '''''U'''''. The ''hash function '''h''''' maps the universe '''''U''''' into the slots of ''hash table '''T[0..m-1]''''' where the size '''''m''''' of the hash table is typically much less than the size of '''''U'''''. The hash function reduces the range of array indices and hence the size of the array. Instead of a size of '''''U''''', the array can have size '''''m'''''.  

For each key '''''x''''' of the set, ''h('''x''')'' (''hash value'') gives the index of '''''x''''' within the hash table. It allows us to search, insert or delete it. The choice of the hash function is essential, and must be :

* uniform: It should uniformly distribute the set of keys in the hash table,
* easy and fast to compute: The aim is not to weaken the method by a long and tedious calculation,
* Consistent: equal keys must produce the same hash value.

As a result, the design of a hash function is a complex and fastidious issue.

Anyway, and as good as this function might be, we can not avoid collisions. Therefore, we need to know how to manage them. There are, for this purpose, two kinds of methods that we will see later, the methods '''''collision resolution by chaining''' (indirect methods)'' and '''''open adressing collision resolution''' (direct methods)''.

<br/>

=== Hash functions ===
We now give some principles of construction of a hash function. These are mixable together. We assume for what follows that the keys are represented in memory by a sequence of bits interpreted as integers (natural numbers).

''<u>Remark :</u> The advantage of using a sequence of bits is that there is no calculation needed to interprete the value as a natural number.''

We must reduce the obtained values to the interval ''['''1,m''']'' or ''['''0,m-1''']'' ( it is often easier to start with '''''0''''' ).

For simplicity's sake, we will use characters coded on 5 bits and in increasing progression, that is to say :

 A=00001$, B=00010, C=00011, ..., Z=11010

For example : 

 BUZZ=00010101011101011010

Therefore, the goal is to build the following function ''h'':
 <math>h\ :\ \{0,1\}^{*} \rightarrow [0,m-1]</math>
set to a bit sequence in a range of '''''m''''' integers.

<br/>

==== Extraction method ====
This method involves extracting a certain number of bits. If '''''p''''' bits are extracted, the interval is reduced to:
 <math>[0,2^{p}-1]</math>.

For example, perform the extraction of <span style="color:#FF8C00;">bits 2, 7, 12 and 17</span> starting at left and completing with zeros. That gives:

<br/>

{| border="1" cellpadding="5" align="center"
| align="left" | NAT 
| align="left"  | 0<span style="color:#FF8C00;">'''''1'''''</span>1100<span style="color:#FF8C00;">'''''0'''''</span>0011<span style="color:#FF8C00;">'''''0'''''</span>100
| align="left"  | 1000
| align="left"  | 8
|-
| align="left" | CARO
| align="left"  | 0<span style="color:#FF8C00;">'''''0'''''</span>0110<span style="color:#FF8C00;">'''''0'''''</span>0011<span style="color:#FF8C00;">'''''0'''''</span>01001<span style="color:#FF8C00;">'''''1'''''</span>11
| align="left"  | 0001
| align="left"  | 1
|-
| align="left" | REDA
| align="left"  | 1<span style="color:#FF8C00;">'''''0'''''</span>0100<span style="color:#FF8C00;">'''''0'''''</span>1010<span style="color:#FF8C00;">'''''0'''''</span>10000<span style="color:#FF8C00;">'''''0'''''</span>01
| align="left"  | 0000
| align="left"  | 0
|-
| align="left" | KRIS
| align="left"  | 0<span style="color:#FF8C00;">'''''1'''''</span>0111<span style="color:#FF8C00;">'''''0'''''</span>0100<span style="color:#FF8C00;">'''''1'''''</span>00110<span style="color:#FF8C00;">'''''0'''''</span>11
| align="left"  | 1010
| align="left"  | 10
|+ '''Table 2. Extraction method.'''
|}

<br/>

It's obviously very easy to implement on a computer and in the case of <math>m = 2^p</math>, the obtained word of '''''p''''' bits gives directly an index value in the hash table.

The problem is that the partial use of the key does not give good results. Indeed, a good hash function must use every bit of the key representation. It is well suited in the case where the data is known in advance or when certain bits of the coding are not material.

<br/>

==== Compression method====
In this method, we use every bit of the key representation that is cut into sub-words of an equal number of bits that are combined with a bit operator. We could use the '''''AND''''' or '''''OR''''', but they always give values that are lower (''ET'') or higher (''OR'') than the original values. For this reason, we prefer using '''''XOR''' (exclusive OR)''. For this example, we will use sub-words of '''''5''''' bits, which gives:

<br/>

{| border="1" cellpadding="5" align="center"
| align="left" | h(NAT)
| align="left" | 01110 xor 00001 xor 10100
| align="left" | 11011
| align="left" | 27
|-
| align="left" | h(CARO)
| align="left" | 00011 xor 00001 xor 10010 xor 01111
| align="left" | 11111
| align="left" | 31
|-
| align="left" | h(REDA)
| align="left" | 10010 xor 00101 xor 00100 xor 00001
| align="left" | 10010
| align="left" | 18
|-
| align="left" | h(KRIS)
| align="left" | 01011 xor 10010 xor 01001 xor 10011
| align="left" | 00011
| align="left" | 3
|+ '''Table 3. Compression method'''.
|}

<br/>

The problem with this method comes when you ''"hash"'' the same way all anagrams of a key, for example:

 h(REDA) = 10010 xor 00101 xor 00100 xor 00001 = 10010 = 18
 h(READ) = 10010 xor 00101 xor 00001 xor 00100 = 10010 = 18

In this case, it is because the key is cut to the character definition limit ('''''5''''' bits). That said, we can always introduce an offset that solves the problem. Simply rotate the bits to the right, the first character of '''''1''''' bit, the second '''''2''''', etc. Which gives:

 h(REDA) = 01001 xor 01001 xor 10000 xor 00010 = 10010 = 18
 h(READ) = 01001 xor 01001 xor 00100 xor 01000 = 01100 = 12

The example given is reduced to keys of '''''5''''' bits, but the interest is to encode the final representation on the size of a memory word.

<br/>

==== Division method====
This method consists to calculate the remainder of the key value divided by '''''m'''''. Assume '''''m = 23''''' and we <span style="color:#FF8C00;">'''''use the previous compression values of the keys'''''</span>, we will obtain :

<br/>

{| border="1" cellpadding="5" align="center"
| align="left" | NAT = 011100000110100
| align="left" | h(NAT) = <span style="color:#FF8C00;">'''''27'''''</span> mod 23 = 4
|-
| align="left" | CARO = 00011000011001001111
| align="left" | h(CARO) = <span style="color:#FF8C00;">'''''31'''''</span> mod 23 = 8
|-
| align="left" | REDA = 10010001010010000001
| align="left" | h(REDA) = <span style="color:#FF8C00;">'''''18'''''</span> mod 23 = 18
|-
| align="left" | KRIS = 01011100100100110011
| align="left" | h(KRIS) = <span style="color:#FF8C00;">'''''3'''''</span> mod 23  = 3
|+ '''Table 4. Division method.'''
|}

<br/>

This is very easy to calculate, but if '''''m''''' is even, all even key (resp. odd) will go in even indices (resp. odd). The same is true if '''''m''''' has small dividers. The solution is to take a prime '''''m'''''. But then again, there may be problems of accumulation.

<br/>

==== Multiplication method====
let <math>\theta</math> be a real number, such that '''''0''''' < <math>\theta</math> < '''''1''''', then we construct the following hash function:

 <math>h(e)=\lfloor\ ((x\ *\ \theta)\ mod\ 1)\ *\ m\ \rfloor</math>

First, we multiply the key '''''x''''' by <math>\theta</math> and extract the fractional part of the result. Then we multiply this value by '''''m''''' (size of the hash table) and take the floor of the result. That will give for <math>\theta</math> = '''''0.5987526325, m=27''''' and <span style="color:#FF8C00;">'''''the use of the previous compression values of the keys'''''</span>:

<br/>

{| border="1" cellpadding="5" align="center"
| align="left" | h(NAT)
| align="left" | <math>\lfloor((</math><big><span style="color:#FF8C00;">''''' 27 '''''</span></big><math>\ *\ 0,5987526325)\ mod\ 1)\ *\ 27\rfloor</math>
| align="left" | <math>4</math>
|-
| align="left" | h(CARO)
| align="left" | <math>\lfloor((</math><big><span style="color:#FF8C00;">''''' 31 '''''</span></big><math>\ *\ 0,5987526325)\ mod\ 1)\ *\ 27\rfloor</math>
| align="left" | <math>15</math>
|-
| align="left" | h(REDA)
| align="left" | <math>\lfloor((</math><big><span style="color:#FF8C00;">''''' 18 '''''</span></big><math>\ *\ 0,5987526325)\ mod\ 1)\ *\ 27\rfloor</math>
| align="left" | <math>20</math>
|-
| align="left" | h(KRIS)
| align="left" | <math>\lfloor((</math><big><span style="color:#FF8C00;">''''' 3 '''''</span></big><math>\ *\ 0,5987526325)\ mod\ 1)\ *\ 27\rfloor</math>
| align="left" | <math>21</math>
|+ '''Table 5. Multiplication method.'''
|}

<br/>

An advantage of the multiplication method is that the value of '''''m''''' is not critical. We typically choose it to be a power of 2 <math>(m=2^p for some integer p)</math>, since we can easily implement the function on most computers. Although this method works with any value of the constant <math>\theta</math>, it works better with some value than with others. We should avoid taking <math>\theta</math> values too close to '''''0''''' or '''''1''''' to avoid accumulation at the ends of the hash table. The optimal choice depends on characteristics of the data being hashed, but...

Curiously :D, both values <math>\theta</math> that are statistically the most uniform, suggested by Knuth, are :

 <math>\theta\ =\ \frac{\sqrt{5}-1}{2}\ \simeq\ 0.6180339887</math><br/>
 <math>\theta\ =\ 1\ -\ \frac{\sqrt{5}-1}{2}\ \simeq\ 0.3819660113</math>


'''''<u>Conclusion :</u> There is no universal hash function. Each function must be adapted to the data it handles and to the application that manages them. We will not forget that it must also be consistent and fast.'''''

<br/>

== Collision resolutions ==
We assume for what follows that we have a uniform and adequate function hash. Then several possible solutions are available to us to resolve collisions.

<br/>

=== By chaining (''indirect methods'') ===
In such methods, the elements that collide are chained together. Either outside of the table ('''hashing with separate chaining''') or, in an overflow area ('''coalesced hashing'''), if dynamic allocation is not possible (''this is rarely seen'').

<br/>

==== hashing with separate chaining ====
As we said, with this method, the elements are chained together outside the hash table. Each box in the hash table contains a pointer directed at the head of the [[Epita:Algo:Course:Sup-Info:Elementary_Data_Structures#Pointer_implementation_of_Lists|list]] of all stored items that hash to this box.

For the following example values:

{| border="1" cellpadding="5" align="center"
| align="right" | <big>items</big>
| align="left" | <math>X_{1}</math>
| align="left" | <math>X_{2}</math>
| align="left" | <math>X_{3}</math>
| align="left" | <math>X_{4}</math>
| align="left" | <math>X_{5}</math>
| align="left" | <math>X_{6}</math>
| align="left" | <math>X_{7}</math>
| align="left" | <math>X_{8}</math>
| align="left" | <math>X_{9}</math>
| align="left" | <math>X_{10}</math>
| align="left" | <math>X_{11}</math>
| align="left" | <math>X_{12}</math>
| align="left" | <math>X_{13}</math>
| align="left" | <math>X_{14}</math>
| align="left" | <math>X_{15}</math>
|-
| align="right" | <big>hash values</big>
| align="center" | <math>1</math>
| align="center" | <math>3</math>
| align="center" | <math>5</math>
| align="center" | <math>2</math>
| align="center" | <math>1</math>
| align="center" | <math>3</math>
| align="center" | <math>1</math>
| align="center" | <math>7</math>
| align="center" | <math>4</math>
| align="center" | <math>5</math>
| align="center" | <math>3</math>
| align="center" | <math>6</math>
| align="center" | <math>3</math>
| align="center" | <math>9</math>
| align="center" | <math>2</math>
|+ '''Table 6. Example of values for separate chaining.'''
|}

<br/>

We would have the following hash table '''''th''''':

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:separatechaininghash.png | ''Collision resolution by chaining'']]
|}

<br/>

''<u>Remark:</u> Items in collision could be represented in other forms (trees, etc.), but there is no interest in doing that because if the distribution is uniform and adapted (our premise) to the data set, the number of collisions should not exceed 5, which in search terms (even sequentially: D) is quite "tolerable/acceptable".''

<br/>

===== Search =====

Search is simple to implement: it is sufficient to calculate, for the searched element, its hash value, and then to compare each element of the collided elements list (on it) to determine whether it is the one you are looking for.

<br/>

===== Insertion =====

For insertion there are two possibilities :

* Seeking the element to be added, and if it does not exist, insert it at the end of the collision list (we are already at the end of the list after the search). The interest is to keep short lists without redundancy of elements,
* insert at first place in the list of collisions. The advantage is that there is no prior search, thus saving time. The problem is to extend the list of collision (due to the redundancy of elements).

<br/>

===== Deletion =====

As for the insertion, there are two possibilities, the choice depends on the previous choice made for insertion:

* Search for the item to delete and if it exists, delete it,
* Search for all possible instances of the item to be deleted and, optionally, deletion. The main drawback is always having to browse the entire list of collisions.

<br/>

==== Coalesced hashing ====
If dynamic memory allocation is not possible, it is necessary to link the elements together within the hash table. Each slot of the latter has got two fields: an item and a link (usually integer) representing the index of the table where the element in collision is.

The principle is to split the hash table (of size '''''m''''') in two zones:

* one '''''primary hashing zone''''' of '''''p''''' elements,
* one '''''reserve area''''' of '''''r''''' elements allowing the user to manage the collisions.

The Constraints are, first to have '''''m=p+r''''' greater than or equal to the number of items in the collection to "hash", and second to have a link element, for each index (hash value) within the hash table.

When an item is positionned and its primary hash value reaches an empty box in the main area, it is placed there, otherwise it is placed in the reserve area and the relationship of collision is updated.

''<u>Remark :</u> The reserve area is always used in decreasing order of indices.''

<br/>

With '''''p=6''''' and '''''r=3''''', for the following values of example:

{| border="1" cellpadding="5" align="center"
| align="right" | <big>éléments</big>
| align="left" | <math>X_{1}</math>
| align="left" | <math>X_{2}</math>
| align="left" | <math>X_{3}</math>
| align="left" | <math>X_{4}</math>
| align="left" | <math>X_{5}</math>
| align="left" | <math>X_{6}</math>
| align="left" | <math>X_{7}</math>
| align="left" | <math>X_{8}</math>
|-
| align="right" | <big>hash values</big>
| align="center" | <math>1</math>
| align="center" | <math>3</math>
| align="center" | <math>1</math>
| align="center" | <math>3</math>
| align="center" | <math>4</math>
| align="center" | <math>2</math>
| align="center" | <math>1</math>
| align="center" | <math>6</math>
|+ '''Table 7. Example of values for hashing with reserve area.'''
|}

<br/>

we would have the following hash table '''''th''''':

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:hashingwithreservearea.png | ''Hash table with reserve area'']]
|}

<br/>

''<u>Remark:</u> In this case, the hash value is no longer calculated on '''m''', but on '''p'''.''

As we can see, the difficulty lies in the choice of the size of the reserve area. In the previous example, if we wanted to add an element whose primary hash value is '''''1, 2, 3, 4''''' or '''''6''''', it would collide with another element already present in the table and we would be unable to find a place insofar as the reserve area is already full.

The problem is the following :

* If the reserve area is too small, it is filled too quickly and the use of the table is incomplete,
* If the reserve area is too large, the dispersion effect is lost and extrapolation would give a linked list (which is of no interest).

In this case, a solution is to no longer consider a reserve area, using '''''m''''' at a  maximum value and manage primary hash collisions as if there was a reserve area (starting from the maximum index and going up).

The drawback is that this creates collisions that are not due to the coincidence of the primary hash values. These are called '''''secondary collisions'''''.

<br/>

Using this principle and '''''m=17''''', for the following example values:

<br/>

{| border="1" cellpadding="5" align="center"
| align="right" | <big>éléments</big>
| align="left" | <math>X_{1}</math>
| align="left" | <math>X_{2}</math>
| align="left" | <math>X_{3}</math>
| align="left" | <math>X_{4}</math>
| align="left" | <math>X_{5}</math>
| align="left" | <math>X_{6}</math>
| align="left" | <math>X_{7}</math>
| align="left" | <math>X_{8}</math>
| align="left" | <math>X_{9}</math>
| align="left" | <math>X_{10}</math>
| align="left" | <math>X_{11}</math>
| align="left" | <math>X_{12}</math>
| align="left" | <math>X_{13}</math>
| align="left" | <math>X_{14}</math>
| align="left" | <math>X_{15}</math>
|-
| align="right" | <big>valeurs de hachage</big>
| align="center" | <math>1</math>
| align="center" | <math>3</math>
| align="center" | <math>5</math>
| align="center" | <math>2</math>
| align="center" | <math>1</math>
| align="center" | <math>3</math>
| align="center" | <math>1</math>
| align="center" | <math>17</math>
| align="center" | <math>4</math>
| align="center" | <math>5</math>
| align="center" | <math>3</math>
| align="center" | <math>14</math>
| align="center" | <math>3</math>
| align="center" | <math>9</math>
| align="center" | <math>2</math>
|+ '''Table 8. Example of values for coalesced hashing.'''
|}

<br/>

we would have the following hash table '''''th''''':

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:coalescedhashing.png | ''Table of coalesced hashing'']]
|}

<br/>

''<u>Remark :</u> We directly use the index values for the collision link.''

As you can see in the previous example, when inserting <math>x_{8}</math> primary hash value '''''17''''', we see that its place is already used to manage the collision of <math>x_{5}</math> on <math>x_{1}</math>. Indeed, these two elements have the same primary hash value ('''''1'''''). We solve the problem by putting <math>x_{8}</math> at the first free slot in going up ('''''14''''') and it is linked to its theoretical box ('''''17'''''). In this case, lists of hash values '''''1''''' and '''''17''''' merge, like others thereafter. This phenomenon explains the origin of the name coalesced hashing.

''<u>Culture :</u><br/>   Coalesce; come together to form one mass or whole (Oxford Dictionnary)<br/>   Origin: mid 16th century: from Latin coalescere "grow together", from co- (from cum "with") + alescere "grow up" (from alere "nourish")''


===== Algorithms =====

For algorithms that follow, the type of data used is as follows:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    m = ...                       <span style="color:#00FF00;">/* Size of hash table */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...               <span style="color:#00FF00;">/* Definition of type of element */</span>
    t_elt = '''record'''                <span style="color:#00FF00;">/* Definition of type t_elt */</span>
       t_element elt
       integer   lien
    '''end record''' t_elt<br/>
    t_tabhash = m t_elt           <span style="color:#00FF00;">/* Definition of the hash table */</span><br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tabhash th


'''<big>Searching</big>'''

Search is simple to implement: it is sufficient to calculate, for the searched element, its hash value, and then to compare each element following the list, using the link, to find the specified element or to find the link to zero.

''<u>Remark:</u> we do not waste too much time, since we do not traverse the merged list of collisions from the first element of the first list, but directly from the primary hash value index that we are looking for.''

We will write a boolean function that returns "true" if the element exists and "false" otherwise. For this we will use two external functions:

  * '''''h''' (hashing function)''
  * '''''isempty''' (boolean function returning true if a box is empty)''

Function prototypes of '''''h''''' and '''''isempty''''':

 '''Algorithm function''' h : integer  <span style="color:#00FF00;">/* between 1 and m */</span>
 '''Local parameters'''
    t_element x<br/>
 '''Algorithm function''' isempty : boolean
 '''Local parameters'''
    t_tabhash th
    integer   i

Then the '''search''' algorithm is:

 '''Algorithm function''' search_coalescedHashing : boolean
 '''Local parameters'''
    t_tabhash th
    t_element x
 '''Variables'''
    integer i
 '''Begin'''
    i <math>\leftarrow</math> h(x)  <span style="color:#00FF00;">/* calculation of the primary hash value */</span>
    '''if''' isempty(th,i) '''then'''
        '''return'''(False)
    '''endif'''
    '''while''' th[i].elt<>x '''and''' th[i].lien<>0 '''do'''
        i <math>\leftarrow</math> th[i].lien
    '''endwhile'''
    '''return'''(th[i].elt=x)
 '''End algorithm function''' search_coalescedHashing
<br/>

'''<big>Insertion</big>'''

We will use the same functions as for search. The algorithm will also use a variable '''''r''' (reserve index)'' which will locate the first slot available (''empty'') in going up. That gives:

 '''Algorithm function''' insert_coalescedHashing : boolean
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer r, i
 '''Begin'''
    i <math>\leftarrow</math> h(x)                 <span style="color:#00FF00;">/* calculation of the primary hash value */</span>
    r <math>\leftarrow</math> m                    <span style="color:#00FF00;">/* initialization of the reserve area slot */</span>
    '''if''' isempty(th,i) '''then'''     <span style="color:#00FF00;">/* insertion of the element */</span>
        th[i].elt <math>\leftarrow</math> x
        th[i].lien <math>\leftarrow</math> 0
        '''return'''(True)
    '''endif'''
    '''while''' th[i].elt<>x and th[i].lien<>0 '''do'''
        i <math>\leftarrow</math> th[i].lien
    '''endwhile'''
    '''if''' th[i].elt=x '''then'''      <span style="color:#00FF00;">/* element already present */</span>
        '''return'''(True)
    '''endif'''
    '''while''' r>=1 '''and''' not(isempty(th,r)) '''do'''     <span style="color:#00FF00;">/* search of the first empty box in the reserve area*/</span>
        r <math>\leftarrow</math> r-1
    '''endwhile'''
    '''if''' r>=1 '''then'''
        th[i].Lien <math>\leftarrow</math> r       <span style="color:#00FF00;">/* update the link with the last item */</span>
        th[r].Elt <math>\leftarrow</math> x        <span style="color:#00FF00;">/* in the list of collision on the primary hash value */</span>
        th[r].Lien <math>\leftarrow</math> 0
        '''return'''(True)
    '''endif'''
    '''return'''(False)            <span style="color:#00FF00;">/* full table (no way;))*/</span>
 '''End algorithm function''' insert_coalescedHashing

''<u>Remarks :</u>'' 
* ''the only case of a false return is due to a full table.''
* ''we could memorize '''r''' to start systematically from the last slot used for the reserve. In this case, you must keep the search of an 'empty' box. Indeed, it may have had direct insertions of elements (on primary hash value) at the end of table.''
<br/>

'''<big>Deletion</big>'''

Except for the separate chaining, it is quite complicated to manage the deletion. Indeed, with the coalesced hashing, deleting an element requires us to eventually shift all those that are linked to it. Its absence can split two collisions lists.

For example, imagine that in the table in figure 8, we remove the element <math>x_{x7}</math> located in the the slot of index '''''15'''''. Then it should shift <math>x_{x8}</math> and <math>x_{x12}</math>. In this case, <math>x_{x12}</math> would end up directly in its own primary hash value box that would separate its own collision list of the collision lists of hash value '''''1''''' and '''''17''''', which would be always linked.

In fact it is preferable in this case not to remove the element, but to create a new process for declaring a box not as '''empty''', but as '''free'''. A box may then take three state: '''empty''', '''free''' or '''occupied'''.

We could then add to the function '''''isempty''''' (previously declared) the functions '''''isfree''''' and '''''isoccupied''''', but it is more advisable to create just one function which tests the three possible states of a box.

These states are specified by an enumerated type  as follows:

 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_state = (empty, free, occupied)             <span style="color:#00FF00;">/* Definition of different states of a box */</span>

Therefore a slight modification of the hash table definition is necessary in order to integrate states of each slot, which gives:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    m = ...                       <span style="color:#00FF00;">/* Size of the hash table */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...               <span style="color:#00FF00;">/* Definition of the type of elements */</span>
    t_elt = '''record'''                <span style="color:#00FF00;">/* Definition du type t_elt */</span>
       <span style="color:#FFA500;">t_state   state</span>           <span style="color:#00FF00;">/* State of the box */</span>
       t_element elt
       integer   link
    '''end record''' t_elt<br/>
    t_tabhash = m t_elt           <span style="color:#00FF00;">/* Definition of the hash table */</span><br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tabhash th

That allows us to specify the function '''''is''''' as follows:

 '''Algorithm function''' is : boolean
 '''Local parameters'''
    t_tabhash th
    integer   i
    t_state   state
 '''Begin'''
    '''return'''(th[i].state=state)     <span style="color:#00FF00;">/* Comparison of the box state to this one of transmitted parameter */</span>
 '''End algorithm function''' is

Then the '''search''' function becomes :

 '''Algorithm function''' search_coalescedHashing : integer
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer i
 '''Begin'''
    i <math>\leftarrow</math> h(x)                     <span style="color:#00FF00;">/* calculation of the primary hash value */</span>
    '''while''' not(is(th,i,empty)) '''and''' not(is(th,i,occupied) '''and''' th[i].elt=x)  '''do'''
       '''if''' th[i].link<>0 '''then'''
          i <math>\leftarrow</math> th[i].link         <span style="color:#00FF00;">/* even if the box is free*/</span>
       '''else'''
          break
       '''endif'''
    '''endwhile'''
    '''if''' (is(th,i,occupied) '''and''' th[i].elt=x) '''then'''
       '''return'''(i)
    '''else'''
       '''return'''(0)
    '''endif'''
 '''End algorithm function''' search_coalescedHashing

''<u>Remark:</u> the function has become '''integer''' and returns the index value of the searched element if it is found otherwise it is '''0'''.''

The '''delete''' function consists in searching for the element and, if  it exists, changing its box state to ''"free"'', it will directly use the '''search''' function. It should be noted that this '''boolean''' function will return '''''True''''' if the element existed and has been removed and '''''false''''' if not, which gives:

 '''Algorithm function''' delete_coalescedHashing : boolean
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer  i
 '''Begin'''
    i <math>\leftarrow</math> search_coalescedHashing(th,x)    <span style="color:#00FF00;">/* recovery of the box index contening x if it exists, '''0''' if not*/</span>
    '''if''' i>0 '''then'''
       th[i].state <math>\leftarrow</math> free
    '''endif'''
    '''return'''(i>0)
 '''End algorithm function''' delete_coalescedHashing

In this way, the links are not destroyed and there is no need to rebuild the hash table from the beginning (or at least since the creation of '''''x''''').
To conclude, we need to give the version of the '''insert''' fucntion algorithm including the management of boxes '''''freed''''', which gives:

 '''Algorithm function''' insert_coalescedHashing : boolean
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer r, i, lib
 '''Begin'''
    i <math>\leftarrow</math> h(x)                                         <span style="color:#00FF00;">/* calculation of the primary hash value */</span>
    '''if''' is(th,i,vide) '''then'''                             <span style="color:#00FF00;">/* insertion of the element */</span>
       th[i].elt <math>\leftarrow</math> x
       th[i].link <math>\leftarrow</math> 0
       th[i].state <math>\leftarrow</math> occupied
       '''return'''(True)
    '''endif'''
    lib <math>\leftarrow</math> 0                                          <span style="color:#00FF00;">/* search for the element x */</span>
    '''while''' th[i].link<>0 '''do'''
       '''if''' is(th,i,free) '''and''' lib=0 '''then'''    
          lib <math>\leftarrow</math> i                                    <span style="color:#00FF00;">/* memorizing of the first free box encountered */</span>
       '''endif'''   
       '''if''' is(th,i,occupied) '''and''' th[i].elt=x '''then'''
          break
       '''endif'''
       i <math>\leftarrow</math> th[i].link                                <span style="color:#00FF00;">/* even if the box is free */</span>
    '''endwhile'''
    '''if''' lib=0 '''then'''                                     <span style="color:#00FF00;">/* no free box encountered */</span>
       '''if''' is(th,i,occupied) '''and''' th[i].elt=x '''then'''      <span style="color:#00FF00;">/* element already présent */</span>
           '''return'''(True)
       '''endif'''
       r <math>\leftarrow</math> m                                         <span style="color:#00FF00;">/* initialization of the reserve area box */</span>
       '''while''' r>=1 '''and''' not(is(th,r,vide)) '''do'''           <span style="color:#00FF00;">/* search for the first empty box in the reserve area*/</span>
          r <math>\leftarrow</math> r-1
       '''endwhile'''
       '''if''' r>=1 '''then'''
          th[i].link <math>\leftarrow</math> r                             <span style="color:#00FF00;">/* update the link with the last item */</span>
          th[r].elt <math>\leftarrow</math> x                              <span style="color:#00FF00;">/* in the list of collision on the primary hash value  */</span>
          th[r].link <math>\leftarrow</math> 0
          th[r].state <math>\leftarrow</math> occupied
          '''return'''(True)
       '''else'''
          '''return'''(False)                             <span style="color:#00FF00;">/* full table (no way;))*/</span>
       '''endif'''
    '''else'''
       th[lib].elt <math>\leftarrow</math> x                               <span style="color:#00FF00;">/* list of collision on the primary hash value */</span>
       th[lib].state <math>\leftarrow</math> occupied
       '''if''' is(th,i,occupied) '''andt''' th[i].elt=x '''then'''      <span style="color:#00FF00;">/* element already present */</span>
          th[i].state <math>\leftarrow</math> free
       '''endif'''   
       '''return'''(True)
    '''endif'''
 '''End algorithm function''' insert_coalescedHashing

''<u>Remark :</u> The variable '''lib''' is used to memorize the first free box encountered during the search for the element. This eventually will allows us to move forward the element '''x''' in the list of collision if it already existed. As a reminder, a free box is a box that was occupied by an element that has been deleted in the meantime.''
<br/>

===Open Adressing (direct methods)===
In such methods, the links no longer exist. The advantage is being able to use their memory space for other elements. The problem is to manage the collisions between elements. The solution is obtained by calculation inside of the table. As for the coalesced hashing, '''''m''''' must be greater or equal to the number of elements to place.

The solution is based on a ''probe sequence function'':

 <math>\begin{matrix}probe &: &E &\rightarrow &\{1, 2, \ldots, m\}^{m} \\  &: &x &\rightarrow &(probe_{1}(x), probe_{2}(x), \ldots, probe_{m}(x)) \end{matrix}</math><br/>
 with <br/>
     <math>\forall\ i \in \{1,\ldots,m\}\quad probe_{i}(x) \in \{1,\ldots,m\}</math><br/>
 and<br/>
     <math>if\ i \neq j\ then\ probe_{i}(x) \neq probe_{j}(x)</math>.

=====Algorithms=====

For algorithms that follow, the type of data used is as follows:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    m = ...                       <span style="color:#00FF00;">/* Size of the hash table */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...               <span style="color:#00FF00;">/* Definition of type of elements */</span>
    t_tabhash = m t_element       <span style="color:#00FF00;">/* Definition of hash table */</span><br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tabhash th


'''<big>Searching</big>'''

When looking for an element '''''x''''' in the hash table, we successively explore the slots corresponding to the successive trials until we find '''''x''''' or an '''"empty"''' box. Indeed, if '''''x''''' existed, it would be placed in the '''"empty"''' box.

We will write an integer function that returns the slot index of the element if it exists and '''''0''''' if not. For this we will use three external functions:

  * '''''h''' (hashing function)''
  * '''''probe''' (probe sequence function)''
  * '''''isempty''' (boolean function returning true if a box is empty)''

Function prototypes of '''''h''''', '''''probe''''' and '''''isempty''''':

 '''Algorithm function''' h : integer  <span style="color:#00FF00;">/* between 1 and m */</span>
 '''Local parameters'''
    t_element x<br/>
 '''Algorithm function''' probe : integer  <span style="color:#00FF00;">/* between 1 and m */</span>
 '''Local parameters'''
    integer   i                      <span style="color:#00FF00;">/* probe number (between 1 and m) */</span>
    t_element x<br/>
 '''Algorithm function''' isempty : boolean
 '''Local parameters'''
    t_tabhash th
    integer   i

Then the '''search''' algorithm is:

 '''Algorithm function''' search_directHashing : integer
 '''Local parameters'''
    t_tabhash th
    t_element x
 '''Variables'''
    integer  i, v                  <span style="color:#00FF00;">/* i is the probe number, v is the probe value */</span>
 '''Begin'''
    i <math>\leftarrow</math> 1            
    '''while''' i<=m '''do'''
       v <math>\leftarrow</math> probe(i,x)            <span style="color:#00FF00;">/* calculation of the ith probe */</span>
       '''if''' isempty(th,v) '''or''' th[v]=x '''then'''
          Break
       '''endif'''
       i <math>\leftarrow</math> i+1
    '''endwhile'''
    '''if''' th[v]=x '''then'''
         '''return'''(v)
    '''else'''
        '''return'''(0)
    '''endif'''
 '''End algorithm function''' search_directHashing


'''<big>Insertion</big>'''

The procedure is the same as for research. Only when one comes across an ''"empty"'' box, do we add the element in this box. The algorithm is globally the same. As it starts with a research phase, we keep the same external functions.

We will therefore write an integer function that returns the index number if the element exists after trying to insert (''if it's been created or if it already existed'') and '''''0''''' if not (full table). The '''insertion''' algorithm is:

 '''Algorithm function''' insert_directHashing : boolean
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer  i, v                  <span style="color:#00FF00;">/* i is the probe number, v is the probe value */</span>
 '''Begin'''
    i <math>\leftarrow</math> 1            
    '''while''' i<=m '''do'''
       v <math>\leftarrow</math> probe(i,x)             <span style="color:#00FF00;">/* calculation of the ith probe */</span>
       '''if''' isempty(th,v) '''or''' th[v]=x '''then'''
          Break
       '''endif'''
       i <math>\leftarrow</math> i+1
    '''endwhile'''
    '''sif''' th[v]=x '''then'''
         '''return'''(v)
    '''else'''
       '''if''' isempty(th,v) '''then'''
          th[v] <math>\leftarrow</math> x
          '''return'''(v)
       '''else'''
          '''return'''(0)
       '''endif'''
    '''endif'''
 '''End algorithm function''' insert_directHashing

''<u>Remarks :</u>'' 
* ''It might be wise to check that the table is not full before you start looking. That said, with <math>m \geqslant n</math>, it is improbable that happens.
* ''Using '''search_directHashing''' in '''insert_directHashing''' is possible, but not very interesting considering the simplicity of the search algorithm. Remember that a function call will take more time than the code "inline".''


'''<big>Deletion</big>'''

We have shown that deletion generated a problem of data reorganization. We will keep the solution used for the coalesced hashing. We will use the definition of '''box states''' as well as the function '''is''' which will use the following declarations:


 <span style="color:#0000FF;">'''Constants'''</span><br/>
    m = ...                       <span style="color:#00FF00;">/* Size of the hash table */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...               <span style="color:#00FF00;">/* Definition of the type of elements */</span>
    t_elt = '''record'''                <span style="color:#00FF00;">/* Definition du type t_elt */</span>
       <span style="color:#FFA500;">t_state   state</span>           <span style="color:#00FF00;">/* State of the box */</span>
       t_element elt
    '''end record''' t_elt<br/>
    t_tabhash = m t_elt           <span style="color:#00FF00;">/* Definition of the hash table */</span><br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tabhash th

Then the '''search''' function becomes:

 '''Algorithm function''' search_directHashing : integer
 '''Local parameters'''
    t_tabhash th
    t_element x
 '''Variables'''
    integer  i, v                  <span style="color:#00FF00;">/* i is the probe number, v is the probe value */</span>
 '''Begin'''
    i <math>\leftarrow</math> 1            
    '''while''' i<=m '''do'''
       v <math>\leftarrow</math> probe(i,x)            <span style="color:#00FF00;">/* calculation of the ith probe */</span>
       '''if''' is(th,v,empty) '''or''' (is(th,v,occupied) '''and''' th[v].elt=x) '''then'''
          Break
       '''endif'''
       i <math>\leftarrow</math> i+1
    '''endwhile'''
    '''if''' is(th,v,occupied) '''and''' th[v].elt=x '''then'''
       '''return'''(v)
    '''else'''
       '''return'''(0)
    '''endif'''
 '''End algorithm function''' search_directHashing

The '''deletion''' procedure only searches for '''''x''''' and sets its state as ''"free"'', so:

 '''Algorithm procedure''' delete_directHashing
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer  v                     <span style="color:#00FF00;">/* v is the value of the good probe else '''0''' */</span>
 '''Begin'''
    v <math>\leftarrow</math> search_directHashing(th,x)
    '''if''' v>0 '''then'''
        th[v].state <math>\leftarrow</math> free
    '''endif'''
 '''End algorithm procedure''' delete_directHashing

To conclude, it left to give the version of the function '''insert''' algorithm including the management of boxes '''''freed''''', that gives:
 
 '''Algorithm function''' insert_directHashing : boolean
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer  i, v, lib             <span style="color:#00FF00;">/* i is the probe number, v is the probe value, lib the 1st free box */</span>
 '''Begin'''
    i <math>\leftarrow</math> 1            
    lib <math>\leftarrow</math> 0
    '''while''' i<=m '''do'''
       v <math>\leftarrow</math> probe(i,x)             <span style="color:#00FF00;">/* calculation of the ith probe */</span>
       '''if''' is(th,v,empty) '''then'''
          Break
       '''endif'''
       '''if''' is(th,v,occupied) '''and''' th[v].elt=x '''then'''
          '''return'''(v)
       '''endif'''
       '''if''' is(th,v,free) '''and''' lib=0 '''then'''
          lib <math>\leftarrow</math> v
       '''endif'''
       i <math>\leftarrow</math> i+1
    '''endwhile'''
    '''if''' is(th,v,empty) '''then'''
       '''if''' lib=0 '''then'''
          th[v].elt <math>\leftarrow</math> x
          th[v].state <math>\leftarrow</math> occupied
          '''return'''(v)
       '''else'''
          th[lib].elt <math>\leftarrow</math> x
          th[lib].state <math>\leftarrow</math> occupied
          '''return'''(lib)
       '''endif'''
    '''else'''
       '''return'''(0)
    '''endif'''
 '''End algorithm function''' insert_directHashing

''<u>Remark :</u> As for the '''''coalesced hashing''''', this algorithm could be modified as follows: as soon as there is a ''"free"''' box or an ''"empty"'' box '''''x''''' is inserted. If at the end '''''x''''' is detected and the insertion has been made, it is deleted. The interest is to put '''''x''''' as near as possible to its first trial hash value, and thus reduce the time for the next search.''

The various techniques of ''direct hashing'' are characterized by the choice of the of the probe sequence function. This latter gives a serie of '''''m''''' slots in the hash table. There are at most '''''m!''''' different slots in the table, but most methods use much less. In the '''''linear probing''''', for example, we see that the sequence of available boxes of an element depends only on the value of primary hash (''1st try''). ''This implies that there are only '''m''' different sequences in the hash table.''
<br/>

=====Linear probing=====
The linear probing works as follows: when there is a collision (when we hash to a table index '''''v''''' that is already occupied with a key different from the search key), then we just check the next entry in the table (by incrementing the index) '''''v+1'''''. If we reach the end ('''''m<sup>th</sup>''''' box), we wrap back to the beginning of the table ('''''1<sup>st</sup>''''').

Call '''''Modplus''''' this circular progression and note it <math>a \oplus b</math>

Using a uniform hashing function '''''h''''', the probe sequence will be:

 <math>probe_{1}(x)=h(x) </math><br/>
 <math>probe_{2}(x)=h(x) \oplus 1</math><br/>
 ...<br/>
 <math>probe_{i}(x)=h(x) \oplus i-1</math><br/>
 ...<br/>
 <math>probe_{m}(x)=h(x) \oplus m-1</math>

Using this principle and '''''m=11''''', for the following example of values:

<br/>

{| border="1" cellpadding="5" align="center"
| align="right" | <big>elements</big>
| align="left" | <math>X_{1}</math>
| align="left" | <math>X_{2}</math>
| align="left" | <math>X_{3}</math>
| align="left" | <math>X_{4}</math>
| align="left" | <math>X_{5}</math>
| align="left" | <math>X_{6}</math>
| align="left" | <math>X_{7}</math>
| align="left" | <math>X_{8}</math>
| align="left" | <math>X_{9}</math>
|-
| align="right" | <big>hashing values</big>
| align="center" | <math>10</math>
| align="center" | <math>3</math>
| align="center" | <math>5</math>
| align="center" | <math>11</math>
| align="center" | <math>4</math>
| align="center" | <math>3</math>
| align="center" | <math>1</math>
| align="center" | <math>10</math>
| align="center" | <math>2</math>
|+ '''Tableau 9. Example values for the linear probing.'''
|}

<br/>

We will have the following hash table '''''th''''':

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:linearprobing.png | ''Linear probing hash table'']]
|}


''<u>Remarks :</u>''
* ''Elements which have the same primary hashing value have the same probe sequence.''
* ''Long runs of occupied slots tend to get longer.''


An advantage of this technique is there is no need for the conception of a probe sequence function. Indeed, it is sufficient, to replace the first try by a call to the hash function and the other ones by <math>v \oplus 1</math> in the algorithms.

For the search algorithm that would give:

 '''Algorithm function''' search_linearProbing : integer
 '''Global parameters'''
    t_tabhash th
 '''Local parameters'''
    t_element x
 '''Variables'''
    integer  i, v, lib             <span style="color:#00FF00;">/* i is the probe number, v is the probe value, lib is the 1st free box */</span>
 '''Begin'''
    i <math>\leftarrow</math> 1            
    lib <math>\leftarrow</math> 0
    v <math>\leftarrow</math> h(x)                     <span style="color:#00FF00;">/* calculation of the 1st probe */</span>
    '''while''' i<=m '''do'''
       '''if''' is(th,v,empty) '''or''' (is(th,v,occupied) '''and''' th[v].elt=x) '''then'''
          Break
       '''endif'''
       '''if''' is(th,v,free) '''and''' lib=0 '''then'''
          lib <math>\leftarrow</math> v
       '''endif'''
       i <math>\leftarrow</math> i+1                    
       v <math>\leftarrow</math> v '''mod''' m + 1                 <span style="color:#00FF00;">/* calculation of the ith probe */</span>
    '''endwhile'''
    '''if''' lib=0 '''then'''
       '''if''' i>m '''then'''                      <span style="color:#FF0000;">/* not found and full table => problem */</span>
          '''return'''(0)
       '''else'''
          '''if''' is(th,v,empty) '''then'''        <span style="color:#00FF00;">/* not found */</span>
             '''return'''(0)
          '''else'''                         <span style="color:#00FF00;">/* found on v at the ith probe */</span>
             '''return'''(v)
          '''endif'''
       '''endif'''
    '''else'''
       '''if''' i>m '''or''' is(th,v,empty) '''then'''    <span style="color:#00FF00;">/* not found */</span>
          '''return'''(0)
       '''else'''
          th[lib].elt <math>\leftarrow</math> x
          th[lib].state <math>\leftarrow</math> occupied
          th[v].state <math>\leftarrow</math> free
          '''return'''(lib)
       '''endif'''
    '''endif'''
 '''End algorithm function''' search_linearProbing

''<u>Remarks :</u>''
* ''The algorithm takes into account the possibility of removing the items and therefore the three possible states of the hash table boxes. This allows two things in the case of searching:''
** ''differentiate the case '''not find''' from the case '''not found and full table'''''
** ''move the founded element to a free slot encountered in its previous trials''
* ''This is of course a simplifiable "rough draft" :)''

<br/>

=====Double hashing=====
The linear probing suffers from a problem known as '''primary clustering''' due to the buildup of long runs of occupied slots. The probability that a buildup of '''''k''''' elements in a table of size '''''m''''' gets longer at the next insertion is equal to <math>\frac{k+2}{m}</math>. 

We must therefore try to disperse a few more collided items. We can then imagine the following probe sequence function:

 <math>probe_{i}(x)=h(x) \oplus k(i-1)</math>

where '''''k''''' is a fixed integer.

To obtain the '''''m''''' hash values during the sequence of '''''m''''' probes, it is necessary that '''''k''''' and '''''m''''' are coprime (''mutually prime'').  In fact, it does not really solve the element buildup problem, but these will occur every '''''k''''' slots. To avoid this, it would been preferable that the increment ('''''k''''') depend on the element '''''x'''''.

Then we introduce a second hash function '''''d''''' ('''''double hashing''''') and the probe sequence becomes:

 <math>probe_{i}(x)=h(x) \oplus d(x)(i-1)</math>

Again each probe sequence must guarantee the '''''m''''' hash values. This requires the same criteria as above, that is to say that '''''m''''' and '''''d(x)''''' have to be coprime regardless of '''''x'''''. 

There are two ways to obtain that:

 * <math>m</math> is prime and <math>d \in [1, m-1]</math><br/>
 * <math>m=2^{p}</math> (it is even) and <math>d(x)</math> has to be odd for all <math>x</math>.<br/> 
   What can be obtained by having <math>d(x)=2d'(x)+1</math>, 
   where <math>d'(x)</math> is a fnction whose values are in <math>[0,2^{p-1}-1]</math>.

''<u>Remark:</u> We will not give the search, insertion and deletion algorithms insofar as the adaptation is very simple (replacement of initializations and of <math>v \leftarrow probe(i,x)</math> by <math>v \leftarrow v \oplus d(x)</math> ).''

<br/>

==Conclusion on hash methods==

* All these methods are well suited for static sets. They are roughly equivalent for a low occupancy rate.

* The coalesced hashing is the most effective method if the memory area reserved for the hashing must be fixed in advance (static data area).

* Linear probing is slower, but this method has the advantage of being extremely simple to implement.

* The double hashing is better than the linear probing, but it requires the computation of two hash functions (and their creation).

* Besides the separate chaining, they do not support deletions well, even with a marking system that significantly increases the search time.

* '''''The most powerful of these is undoubtedly the separate chaining.'''''

----
<small>''(Christophe "krisboul" Boullay)''</small>