Golang DSA Chapter 4 Part 2: Hash Tables and Hash Functions

Welcome back. In Part 1 we covered binary search trees and AVL trees. Now we’re finishing up Chapter 4 of “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi. This second half covers B-trees, B+ trees, tables, containers, circular linked lists, and hash functions.

Let’s get through it.

Wrapping Up AVL Trees

Before we move on, the book finishes the AVL tree section with a full working example. The main method creates an AVL tree, inserts some nodes, then removes a couple:

func main() {
    var treeNode *TreeNode
    fmt.Println("Tree is empty")
    var avlTree []byte
    avlTree, _ = json.MarshalIndent(treeNode, "", " ")
    fmt.Println(string(avlTree))

    fmt.Println("\n Add Tree")
    InsertNode(&treeNode, integerKey(5))
    InsertNode(&treeNode, integerKey(3))
    InsertNode(&treeNode, integerKey(8))
    InsertNode(&treeNode, integerKey(7))
    InsertNode(&treeNode, integerKey(6))
    InsertNode(&treeNode, integerKey(10))
    avlTree, _ = json.MarshalIndent(treeNode, "", " ")
    fmt.Println(string(avlTree))

    fmt.Println("\n Delete Tree")
    RemoveNode(&treeNode, integerKey(3))
    RemoveNode(&treeNode, integerKey(7))
    avlTree, _ = json.MarshalIndent(treeNode, "", " ")
    fmt.Println(string(avlTree))
}

A neat trick here: the book uses json.MarshalIndent to print the tree as JSON. It’s a simple way to visualize the tree structure without writing a custom print function. After inserting keys 5, 3, 8, 7, 6, and 10, the tree rebalances itself. Then removing keys 3 and 7 triggers more rebalancing. The whole point is that AVL trees always stay balanced no matter what you throw at them.

B+ Trees

B+ trees store keys and pointers to next-level nodes. When you search for something, the tree uses recursion to walk through adjacent node keys until it finds what you need.

Where do you see B+ trees in real life? Filesystems. They’re great for storage because they need fewer I/O operations to find a node. The term “fan-out” comes up here, which is just the number of child nodes any given node can point to.

Rudolf Bayer and Edward M. McCreight first described B+ trees in a technical paper. The key properties:

• Space usage is O(n)
• Insert, find, and remove operations are O(log_b n), where b is the order of the tree
• Block-oriented storage makes them good for disk-based data
• You can improve space efficiency with compression techniques

B+ trees belong to the family of multiway search trees. Think of them as trees that can have more than two children per node, which keeps the tree short and wide instead of tall and skinny.

B-Trees

B-trees are similar but different. In a B-tree, non-leaf nodes only have keys, and all the actual data lives in the leaves. The main purpose? Reducing disk accesses.

Knuth originally came up with the concept. Bayer and McCreight were the first to implement it. Some things to know about B-trees:

• They’re self-balancing and keep data sorted
• Every non-leaf node has at least n/2 child nodes (where n is the max children allowed)
• They handle multiple insertions and deletions well
• Used in real filesystems like HFS and Reiser4
• Space: O(n), Insert/Search/Delete: O(log n)

If you’re wondering what the practical difference is between B-trees and B+ trees: in a B+ tree, all data is in the leaf nodes and the leaves are linked together. In a B-tree, data can be in any node. B+ trees are usually better for range queries because you can just walk through the linked leaves.

T-Trees

The book gives T-trees a brief mention. A T-tree is a balanced structure that keeps both the index and the actual data in memory. They’re used in in-memory databases. The “T” refers to the shape of the node.

Each node has pointers to parent, left child, and right child, plus an ordered array of data pointers. T-trees are built on top of self-balancing binary search trees and are good for ordered scanning of data.

Tables

The book moves on to a simple table implementation in Go. Think of it like a basic database table: you have rows, columns, and a table name.

Here are the struct definitions:

type Table struct {
    Rows        []Row
    Name        string
    ColumnNames []string
}

type Row struct {
    Columns []Column
    Id      int
}

type Column struct {
    Id    int
    Value string
}

Nothing fancy. A Table has a name, column names, and rows. Each Row has an ID and a slice of Column values. Each Column has an ID and a string value.

The printTable function just loops through rows and columns:

func printTable(table Table) {
    var rows []Row = table.Rows
    fmt.Println(table.Name)
    for _, row := range rows {
        var columns []Column = row.Columns
        for i, column := range columns {
            fmt.Println(table.ColumnNames[i], column.Id, column.Value)
        }
    }
}

And the main method creates a “Customer” table with two rows of data (Id, Name, SSN columns). It’s a straightforward example of modeling tabular data with Go structs.

Symbol Tables

A quick section on symbol tables. They show up during program compilation. A symbol table stores the symbol’s name, location, and address. In Go, the gosym package gives you access to Go symbol and line number tables. Go binaries built with the GC compiler include these tables, which map program counters to line numbers.

This is more of a “good to know” section than a “you’ll build this yourself” section.

Containers and Circular Linked Lists

Go’s container package gives you access to heap, list, and ring data structures. The book focuses on the ring, which models a circular linked list.

A circular linked list is exactly what it sounds like: a list where the last node loops back to the first node. Here’s how you build one using Go’s container/ring package:

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    var integers []int
    integers = []int{1, 3, 5, 7}
    var circular_list *ring.Ring
    circular_list = ring.New(len(integers))
    var i int
    for i = 0; i < circular_list.Len(); i++ {
        circular_list.Value = integers[i]
        circular_list = circular_list.Next()
    }

You create a ring with ring.New(n) where n is the length. Then you fill it by moving through with Next(). To print all values, use the Do method:

    circular_list.Do(func(element interface{}) {
        fmt.Print(element, ",")
    })
    fmt.Println()

You can also go backwards with Prev():

    for i = 0; i < circular_list.Len(); i++ {
        fmt.Print(circular_list.Value, ",")
        circular_list = circular_list.Prev()
    }
    fmt.Println()

And jump forward by a specific number of steps with Move(n):

    circular_list = circular_list.Move(2)
    circular_list.Do(func(element interface{}) {
        fmt.Print(element, ",")
    })
    fmt.Println()
}

Circular linked lists are useful when you need to cycle through a collection repeatedly. Think round-robin scheduling or cycling through a playlist.

Hash Functions

The chapter ends with hash functions. These are used in cryptography and lots of other areas. Go gives you two main ways to create hashes: crc32 and sha256.

The book shows an example using sha256 with binary marshaling. Marshaling here means saving the internal state of a hash so you can resume it later. Here’s the example:

package main

import (
    "bytes"
    "crypto/sha256"
    "encoding"
    "fmt"
    "hash"
    "log"
)

func main() {
    const (
        example1 = "this is a example "
        example2 = "second example"
    )
    var firstHash hash.Hash
    firstHash = sha256.New()
    firstHash.Write([]byte(example1))

    var marshaler encoding.BinaryMarshaler
    var ok bool
    marshaler, ok = firstHash.(encoding.BinaryMarshaler)
    if !ok {
        log.Fatal("first Hash is not generated by encoding.BinaryMarshaler")
    }
    var data []byte
    var err error
    data, err = marshaler.MarshalBinary()
    if err != nil {
        log.Fatal("failure to create first Hash:", err)
    }

    var secondHash hash.Hash
    secondHash = sha256.New()
    var unmarshaler encoding.BinaryUnmarshaler
    unmarshaler, ok = secondHash.(encoding.BinaryUnmarshaler)
    if !ok {
        log.Fatal("second Hash is not generated by encoding.BinaryUnmarshaler")
    }
    if err := unmarshaler.UnmarshalBinary(data); err != nil {
        log.Fatal("failure to create hash:", err)
    }

    firstHash.Write([]byte(example2))
    secondHash.Write([]byte(example2))
    fmt.Printf("%x\n", firstHash.Sum(nil))
    fmt.Println(bytes.Equal(firstHash.Sum(nil), secondHash.Sum(nil)))
}

What’s happening here: you hash the first string, then marshal (save) the hash state. You create a second hash and unmarshal (restore) that saved state into it. Then both hashes process the second string. At the end, bytes.Equal confirms they produce the same result. This proves that marshaling preserves the hash state correctly.

This is actually useful when you need to hash large amounts of data in chunks, or when you want to checkpoint a hash computation and resume it later.

Chapter 4 Summary

Chapter 4 covered a lot of ground across both parts:

• Binary search trees for sorted data with fast lookup
• AVL trees for self-balancing binary search trees
• B-trees and B+ trees for disk-friendly, multiway search trees
• T-trees for in-memory database indexing
• Tables as basic data modeling with structs
• Containers and circular linked lists using Go’s standard library
• Hash functions with SHA-256 and binary marshaling

The chapter also touched on symbol tables and the gosym package, which is more of a Go internals topic.

Operations like insertion, deletion, and search were covered for each structure, along with their time and space complexity. The key takeaway: different data structures exist because different problems need different trade-offs between speed, memory, and disk access patterns.

End-of-Chapter Questions

The book asks these questions at the end. Good for self-testing:

1. Where would you use a binary search tree?
2. How do you search for an element in a binary search tree?
3. What techniques adjust the balance in an AVL tree?
4. What is a symbol table?
5. How do you generate a binary marshaled hash?
6. Which Go container models a circular linked list?
7. How do you create indented JSON from a tree structure?
8. How do you compare hash sums?
9. What is the balance factor in an AVL tree?
10. How do you identify rows and columns in a table?

Next up, we’re moving into Chapter 5 where things get more mathematical with arrays, matrices, and multi-dimensional data structures.

This post is part of a series retelling the book “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt, 2019, ISBN: 978-1-78961-850-1). Find the full series index here.