# Data Structures in Go: Hash Table

### Related tags

Data Structures go golang linked-list data-structures

# 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
Golang enthusiast
###### 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

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

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

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

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

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

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

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'

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

Some data structures and algorithms using golang

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

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

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

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

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

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

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

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

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

46 May 12, 2022