Overview

Referencing Algorithm Encyclopedia, we learn about algorithms and data structures.

The implementation is also available on github - bmf-san/road-to-algorithm-master.

HashMap

An array indexed by hash values
Hash collision handling
- Open Addressing
  - A method to find another address using a different function when a collision occurs.
- Chaining
  - A method where, instead of finding a new address when a collision occurs, a linked list is stored at the collided address, connecting the collided keys with pointers.

Computational Time

Data Access

O(1)
- Random access is possible using indices.

Data Addition

O(1)
- In the case of arrays, a linear search is needed to find the addition location, making it O(n), but hash tables determine the addition location using a hash, so it is O(1).
- This does not apply if a hash collision occurs.

Implementation

Below is a rudimentary HashMap that does not consider hash collisions.

package main

import "fmt"

// A HashMap is hash map.
type HashMap struct {
	data map[int]string
}

// hash is create a hash key.
func hash(key int) int {
	return key % 5
}

// put is add key to hash map.
func (h HashMap) put(key int, value string) {
	hash := hash(key)
	if h.data == nil {
		h.data = make(map[int]string)
	}
	h.data[hash] = value
}

// get is get a value from hash map.
func (h HashMap) get(key int) string {
	var hash int = hash(key)

	return h.data[hash]
}

func main() {
	h := &HashMap{
		data: make(map[int]string),
	}

	h.put(1, "foo")
	h.put(2, "bar")

	fmt.Printf("%#v\n", h.get(1))
	fmt.Printf("%#v\n", h.get(2))
}