Developing a hash table in Go

Strictly speaking, a hash table is a data structure that stores one or more key and value pairs and uses the hashFunction of the key to compute an index into an array of buckets or slots, from which the correct value can be retrieved. Ideally, the hashFunction should assign each key to a unique bucket, provided that you have the required number of buckets.

A good hashFunction must be able to produce a uniform distribution of hash values because it is inefficient to have unused buckets or big differences in the cardinalities of the buckets. Additionally, the hashFunction should work consistently and output the same hash value for identical keys because otherwise it would be impossible to find the information you want! If you think that hash tables are not that useful, handy, or clever, you should consider the following: when a hash table has n keys and k buckets, its search speed goes from O (n) for a linear search to O (n/k)! Although the improvement might look small, you should realize that for a hash array with only 20 slots, the search time would be reduced by 20 times! This makes hash tables good for applications such as dictionaries or any other analogous application where you have to search lots of data. Although using lots of buckets increases the complexity and the memory usage of your program, there are times when it is worth it.

The following figure shows the graphical representation of a simple hash table with 10 buckets. It is not difficult to understand that the hashFunction is the modulo operator:

Although the presented version of a hash table uses numbers because they are a little easier to implement and understand, you can use any data type you want as long as you can find an appropriate hashFunction to process your input. The source code of hash.go will be presented in three parts.

The first one is the following:

package main 
 
import ( 
   "fmt" 
) 
 
type Node struct { 
   Value int 
   Next  *Node 
} 
 
type HashTablestruct { 
   Table map[int]*Node

 
   Size  int 
} 

The Node struct definition is taken from the implementation of the linked list you saw earlier. The reason for using a map for the Table variable instead of a slice is that the index of a slice can only be a natural number, whereas the key of a map can be anything.

The second part contains the following Go code:

func hashFunction(i, size int) int { 
   return (i % size) 
} 
 
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 
} 
 
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() 
         } 
   } 
}

Note here that the traverse() function is using the Go code from linkedList.go in order to traverse the elements of each bucket in the hash table. Additionally, note that the insert function does not check whether or not a value already exists in the hash table in order to save book space, but this is not usually the case. Also, for reasons of speed and simplicity, new elements are inserted at the beginning of each list.

The last part contains the implementation of the main() function:

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

Executing hash.go will generate the following output, which proves that the hash table is working as expected:

$ go run hash.go
Number of spaces: 10
89 -> 79 -> 69 -> 59 -> 49 -> 39 -> 29 -> 19 -> 9 ->
86 -> 76 -> 66 -> 56 -> 46 -> 36 -> 26 -> 16 -> 6 ->
92 -> 82 -> 72 -> 62 -> 52 -> 42 -> 32 -> 22 -> 12 -> 2 ->
94 -> 84 -> 74 -> 64 -> 54 -> 44 -> 34 -> 24 -> 14 -> 4 ->
85 -> 75 -> 65 -> 55 -> 45 -> 35 -> 25 -> 15 -> 5 ->
87 -> 77 -> 67 -> 57 -> 47 -> 37 -> 27 -> 17 -> 7 ->
88 -> 78 -> 68 -> 58 -> 48 -> 38 -> 28 -> 18 -> 8 ->
90 -> 80 -> 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10 -> 0 ->
91 -> 81 -> 71 -> 61 -> 51 -> 41 -> 31 -> 21 -> 11 -> 1 ->
93 -> 83 -> 73 -> 63 -> 53 -> 43 -> 33 -> 23 -> 13 -> 3 ->

If you execute hash.go multiple times, you will see that the order the lines are printed in will vary. This happens because the output of range hash.Table found in the traverse() function cannot be predicted, which happens because Go has an unspecified return order for hashes.