The Go code of hashTable.go, which will be presented in five parts, will help clarify many things about hash tables.

The first part of hashTable.go is as follows:

package main 
 
import ( 
    "fmt" 
) 
 
const SIZE = 15 
 
type Node struct { 
    Value int 
    Next  *Node 
} 

In this part, you can see the definition of the node of the hash table, which, as expected, is defined using a Go structure. The SIZE constant variable holds the number of buckets of the hash table.

The second segment from hashTable.go is shown in the following Go code:

type HashTable struct { 
    Table map[int]*Node 
    Size  int 
} 
 
func hashFunction(i, size int) int { 
    return (i % size) 
} 

In this code segment, you can see the implementation of the hash function used in this particular hash. The hashFunction() uses the modulo operator. The main reason for choosing the modulo operator is because this particular hash table has to cope with integer values. If you were dealing with strings or floating-point numbers, then you should have used a different logic in your hash function.

The actual hash is stored in a HashTable structure that has two fields. The second field is the size of the hash table, and the first field is a map that associates an integer with a linked list (*Node). As a result, this hash table will have as many linked lists as the number of its buckets. This also means that the nodes of each bucket of the hash table will be stored in linked lists. You will learn more about linked lists in a little while.

The third code portion of hashTable.go is as follows:

func insert(hash *HashTable, value int) int { 
    index := hashFunction(value, hash.Size) 
    element := Node{Value: value, Next: hash.Table[index]} 
    hash.Table[index] = &element 
    return index 
} 

The insert() function is called for inserting elements into the hash table. Note that the current implementation of the insert() function does not check for duplicate values.

The fourth part of hashTable.go comes next:

func traverse(hash *HashTable) { 
    for k := range hash.Table { 
        if hash.Table[k] != nil { 
            t := hash.Table[k] 
            for t != nil { 
                fmt.Printf("%d -> ", t.Value) 
                t = t.Next 
            } 
            fmt.Println() 
        } 
    } 
} 

The traverse() function is used for printing all of the values in the hash table. The function visits each one of the linked lists of the hash table and prints the stored values, linked list by linked list.

The last code portion of hashTable.go is as follows:

func main() { 
    table := make(map[int]*Node, SIZE) 
    hash := &HashTable{Table: table, Size: SIZE} 
    fmt.Println("Number of spaces:", hash.Size) 
    for i := 0; i < 120; i++ { 
        insert(hash, i) 
    } 
    traverse(hash) 
}

In this part of the code, you create a new hash table named hash using the table variable, which is a map that holds the buckets of the hash table. As you already know, the slots of a hash table are implemented using linked lists. The main reason for using a map to hold the linked lists of a hash table instead of a slice or an array is that the keys of a slice or an array can only be positive integers, while the keys of a map can be almost anything you need.

Executing hashTable.go will produce the following output:

$ go run hashTable.go
Number of spaces: 15
108 -> 93 -> 78 -> 63 -> 48 -> 33 -> 18 -> 3 ->
109 -> 94 -> 79 -> 64 -> 49 -> 34 -> 19 -> 4 ->
117 -> 102 -> 87 -> 72 -> 57 -> 42 -> 27 -> 12 ->
119 -> 104 -> 89 -> 74 -> 59 -> 44 -> 29 -> 14 ->
111 -> 96 -> 81 -> 66 -> 51 -> 36 -> 21 -> 6 ->
112 -> 97 -> 82 -> 67 -> 52 -> 37 -> 22 -> 7 ->
116 -> 101 -> 86 -> 71 -> 56 -> 41 -> 26 -> 11 ->
114 -> 99 -> 84 -> 69 -> 54 -> 39 -> 24 -> 9 ->
118 -> 103 -> 88 -> 73 -> 58 -> 43 -> 28 -> 13 ->
105 -> 90 -> 75 -> 60 -> 45 -> 30 -> 15 -> 0 ->
106 -> 91 -> 76 -> 61 -> 46 -> 31 -> 16 -> 1 ->
107 -> 92 -> 77 -> 62 -> 47 -> 32 -> 17 -> 2 ->
110 -> 95 -> 80 -> 65 -> 50 -> 35 -> 20 -> 5 ->
113 -> 98 -> 83 -> 68 -> 53 -> 38 -> 23 -> 8 ->
115 -> 100 -> 85 -> 70 -> 55 -> 40 -> 25 -> 10 ->  

This particular hash table is perfectly balanced because it has to deal with continuous numbers that are placed in a slot according to the results of the modulo operator. Real-world problems might not generate such convenient results!

Note that if you execute hashTable.go several times, you will most likely get an output where the lines are in a different order, because the way that Go outputs the key and value pairs of a map is totally random!