What is a HASH TABLE when doing HASH JOIN?

Question

In HASH JOIN method of oracle, HASH TABLE will be built on one of the tables and other will be joined depending on the values in the hash table.

Could you please let me know what is Hash table? What is the structure of hash table? how will it be created?

Solution

A hash table is a table where you can store stuff by the use of a key. It is like an array but stores things differently

a('CanBeVarchar') := 1; -- A hash table

In oracle, they are called associative arrays or index by tables. and you make one like this:

TYPE aHashTable IS TABLE OF [number|varchar2|user-defined-types] INDEX BY VARCHAR2(30);
myTable aHashTable;

So, what is it? it's just a bunch of key-value pairs. The data is stored as a linked list with head nodes that group the data by the use of something called HashCode to find things faster. Something like this:

a    ->     b     ->    c
Any         Bitter      Class
Array       Bold        Count

Say you are storing random words and it's meaning (a dictionary); when you store a word that begins with a, it is stored in the 'a' group. So, say you want this myTable('Albatroz') := 'It's a bird', the hash code will be calculated and put in the A head node, where it belongs: just above the 'Any'. a, has a link to Any, which has a link to Array and so on.

Now, the cool thing about it is that you get fast data retreival, say you want the meaning of Count, you do this definition := myTable('Count'); It will ignore searching for Any, Array, Bitter, Bold. Will search directly in the C head node, going trhough Class and finally Count; that is fast!

Here a wikipedia Link: http://en.wikipedia.org/wiki/Hash_table

Note that my example is oversimplified read with a little bit of more detail in the link.

Read more details like the load factor: What happens if i get a LOT of elements in the a group and few in the b and c; now searching for a word that begins with a is not very optinmal, is it? the hash table uses the load factor to reorganize and distribute the load of each node, for example, the table can be converted to subgroups:

From this

a          b     ->    c
Any        Bitter      Class
Anode      Bold        Count
Anti       
Array
Arrays
Arrow

To this

an    ->   ar      b     ->    c
Any        Array   Bitter      Class
Anode      Arrays  Bold        Count
Anti       Arrow

Now looking for words like Arrow will be faster.