Data Structures in Go: Hash Table

Overview

Data Structures in Go: Hash Table

he time has come to implement one of the most commonly used data structures in software development - the Hash Table!

A hash table is a data structure that implements an associative array, allowing us to store pairs of keys and values that can be accessed at an expected O(1) time (O(n) - worst case for a bad implementation).

Personally I love this data structure. It works a bit like magic! How could you access a random key’s value at constant time?

Here is how it works:

Create an array of a length equal to the expected number of key/value pairs in your hash table. The bigger the array, the lower the chance of collisions (explained further below). Create a hashing function which will take the value of the key you want add and transform it into a number. The better this function is, the lower the chance of collisions. Take the number generated by the hashing function and calculate the modulo with the array length. (e.g. if the hash is 1234 and the array length is 100, then calculate 1234 % 100). This is going to be the index in the array where you are going to store the value. That is pretty much how it works in a nutshell. One of the most important things in a hash map is probably the hashing function. It can make the difference between a great and a very poor hash map.

In the implementation that follows, for a hash table that allows only string keys, I chose to use the following hash function: char[0] * 31^n-1 + char[1] * 31^n-2 + ... + char[n-1]

Also, I have mentioned above collisions a couple of times. A collision happens when the array indices for two different keys happens to be the same. This could be because of a bad hashing function or a too small of an underlying array. Both of these can be fixed though. You can use a better hashing function and you can also dynamically grow the array when needed.

But collisions will happen, so then what do we do about it? Instead of storing our value as is in the array, we are going to store it in a linked list (or array) together with the un-hashed key. So, whenever we try to retrieve or modify a key value, we walk through that linked list and make sure that we are manipulating the correct key (if there are multiple at that index).

Owner
Milad Samani
Golang enthusiast
Milad Samani
Probabilistic data structures for processing continuous, unbounded streams.

Boom Filters Boom Filters are probabilistic data structures for processing continuous, unbounded streams. This includes Stable Bloom Filters, Scalable

Tyler Treat 1.4k May 19, 2022
Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

Algorithms to Go 545 May 12, 2022
Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

Algorithms to Go 9 Jan 25, 2021
This is the course materials for the Go Data Structures Crash Course!

Go Data Structures Course ?? Welcome Gophers! This is the official repository that contains all of the data structures we cover in the Go Data Structu

TutorialEdge 9 May 10, 2022
Basic Implementation of Data-structures in Go

Data structures in Go v1.15.6 This repo consists the implementation of the following: Stacks Queues Linked Lists (Singly) Binary Search Trees Heaps (M

Shehab Abdel-Salam 4 May 24, 2021
Concurrent data structures for Go

xsync Concurrent data structures for Go. An extension for the standard sync package. This library should be considered experimental, so make sure to r

Andrey Pechkurov 204 Apr 18, 2022
Algorithms and Data Structures Solved in Golang

Algorithms and Data Structures Solved in Golang Hi! I'm Bruno Melo and this repository contains a lot challenges solved on many plataforms using go as

Bruno Melo 2 Feb 22, 2022
Common data structures for solving problems in Golang

datastructs Common data structs for solving problems in Golang. List of data structures can be found in datastructs/pkg Rules for data structures Don'

Akira Masuda 1 Nov 7, 2021
Some data structures and algorithms using golang

Some data structures and algorithms using golang

null 57 Apr 12, 2022
Data structures and algorithms implementation from ZeroToMastery course

ZeroToMastery Data Structures & Algorithms course This repo includes all the data structure and algorithm exercises solutions and implementations. Ins

Fabio Bozzo 2 Dec 2, 2021
Data Structures & Algorithms in Go

Data Structures and Algorithms with Go The aim of this repository is to provide Gophers with how data structures and algorithms are implemented in the

Chris Gonzalez 0 Dec 28, 2021
Grokking-algorithms-go - Solutions to common Data Structures problems

This is a repository dedicated to study, learn and solve Data Structure algorith

Gabriel Magalhães 0 Apr 4, 2022
Practice-dsa-go - Data Structures and Algorithms for Interview Preparation in Go

Data Structures and Algorithms for Interview Preparation in Go Data Structures K

Sparsh Srivastava 1 Jan 14, 2022
Implementation of various data structures and algorithms in Go

GoDS (Go Data Structures) Implementation of various data structures and algorithms in Go. Data Structures Containers Lists ArrayList SinglyLinkedList

TopXeQ 0 Jan 25, 2022
Tutorial code for my video Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang

Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang Read text from a file and split into words. Introduction to slices / lists. Co

null 0 Jan 26, 2022
periodic table on the command line

element The periodic table on the command line Installation • Usage Installation Go get it! go get -u -v github.com/gennaro-tedesco/element Usage Usi

Gennaro Tedesco 48 May 9, 2022
GoStruct2Table - format your struct like a table.

GoStruct2Table format your struct like a table. Installing $ go get -u -v github.com/runningzyp/GoStruct2Table Simple Example import parser "github.c

YunpengZhan 8 Jan 18, 2022
ID type with marshalling to/from hash to prevent sending IDs to clients.

Hide IDs Hide is a simple package to provide an ID type that is marshalled to/from a hash string. This prevents sending technical IDs to clients and c

Emvi 46 May 12, 2022