ハッシュ法

• Keyの比較によってRecordの位置を探索していくという考え方の最たる例が二分探索で，比較のみによる探索では$O(\log n)$を達成できるがそれ以上は望めない
• そこで発想を逆転して，KeyそのものによってRecordの位置が一意に決まってしまえば（比較とかもはや必要なくて），探索する時には，探索対象のKeyの値のRecordが入っているであろう（それ以外の場所には入っていない）場所を確認しに行けばいいので$O(1)$で探索が実現できるのではないか...
• これがハッシュ法
• でもRecordの入ることのできる場所は有限個しかないので，異なるKeyのRecordが同じ場所に入るべきだという状況が発生してしまう
• これが衝突
• ハッシュ法は衝突をいかに回避するかでいくつかに分類することができる
• チェイン法：同じ位置に入るべきだったRecordをリスト状にぶら下げていく方法
• オープンアドレス：衝突したら本来入るべきだった位置の近辺で妥協する方法
  • 線形走査法：「本来入るべきであった場所の隣」で妥協していく方法
  • 二重ハッシュ法：ハッシュ関数を二つ使って衝突を回避していく方法

チェイン法

package main

import (
	"hash/fnv"
	"log"
	"math/rand"
	"strconv"
	"time"
)

const LENGTH = 100

type Cell struct {
	Key  int
	Next *Cell
}

type HashTable []*Cell

func (h *HashTable) Insert(key int) {
	idx := hash(key)
	log.Printf("Insert: <key: %d, idx: %d>\n", key, idx)
	if (*h)[idx] == nil {
		(*h)[idx] = &Cell{Key: key, Next: nil}
		return
	}
	p := (*h)[idx]
	for p.Next != nil {
		p = p.Next
	}
	p.Next = &Cell{Key: key, Next: nil}
}

func (h *HashTable) Search(key int) (*Cell, bool) {
	idx := hash(key)
	if (*h)[idx] == nil {
		return nil, false
	}
	p := (*h)[idx]
	for p.Next != nil {
		if p.Key == key {
			return p, true
		}
		p = p.Next
	}
	return nil, false
}

func (h *HashTable) Delete(key int) {
	idx := hash(key)
	if (*h)[idx] == nil {
		log.Printf("Info: tried to delete non existing cell <key: %d>\n", key)
		return
	}
	var prev *Cell
	p := (*h)[idx]
	for p.Next != nil {
		if p.Key == key {
			break
		}
		prev = p
		p = p.Next
	}
	if prev == nil {
		(*h)[idx] = p.Next
		p.Next = nil
		return
	}
	prev.Next = p.Next
	p.Next = nil
}

func hash(key int) int {
	s := strconv.Itoa(key)
	h := fnv.New32a()
	h.Write([]byte(s))
	ret := h.Sum32() % (LENGTH * 2)
	return abs(ret)
}

func abs(a uint32) int {
	ret := int(a)
	if a > 0 {
		return ret
	} else {
		return -ret
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	table := make(HashTable, LENGTH*2)
	input := make([]int, LENGTH*5)
	for i := 0; i < LENGTH*5; i++ {
		input[i] = i
	}

	for _, ele := range input {
		table.Insert(ele)
	}

	for i := 0; i < LENGTH; i++ {
		target := rand.Intn(LENGTH * 10)
		cell, found := table.Search(target)
		if found {
			log.Printf("Found: <key: %d>\n", cell.Key)
		} else {
			log.Printf("Not Found: <key: %d>\n", target)
		}
	}

	for _, ele := range input {
		table.Delete(ele)
	}

	for _, ele := range input {
		cell, found := table.Search(ele)
		if found {
			log.Printf("Found: <key: %d>\n", cell.Key)
		} else {
			log.Printf("Not Found: <key: %d>\n", ele)
		}
	}
}

線形走査なオープンアドレス法

• ハッシュ値が隣接する値が入ってくるとデータがその近辺で塊（クラスタ）を形成し始めて探索性能が落ちる

package main

import (
	"hash/fnv"
	"log"
	"math/rand"
	"strconv"
	"time"
)

const LENGTH = 5

type MARK int

const (
	FREE MARK = iota
	USED
	DELETED
)

type Cell struct {
	Key  int
	Mark MARK
}

type HashTable []*Cell

func (h *HashTable) Insert(key int) {
	idx := hash(key)
	if (*h)[idx].Mark == FREE {
		(*h)[idx].Key = key
		(*h)[idx].Mark = USED
		log.Printf("Insert: <key: %d> @ [%d]\n", key, idx)
		return
	}
	for (*h)[idx].Mark == USED {
		if (*h)[idx].Key == key {
			log.Printf("Insert: <key %d> does already exist\n", key)
			return
		}
		idx = (idx + 1) % (LENGTH * 10)
	}
	(*h)[idx].Key = key
	(*h)[idx].Mark = USED
	log.Printf("Insert: <key: %d> @ [%d]\n", key, idx)
}

func (h *HashTable) Search(key int) (*Cell, bool) {
	idx := hash(key)
	for (*h)[idx].Mark != FREE {
		if (*h)[idx].Mark == DELETED {
			idx = (idx + 1) % (LENGTH * 10)
			continue
		}
		if (*h)[idx].Key == key {
			return (*h)[idx], true
		}
		idx = (idx + 1) % (LENGTH * 10)
	}
	return nil, false
}

func (h *HashTable) Delete(key int) {
	idx := hash(key)
	counter := 0
	for idx < LENGTH*10 && counter < len(*h) {
		if (*h)[idx].Key == key {
			(*h)[idx].Key = -1
			(*h)[idx].Mark = DELETED
			log.Printf("Delete: <key: %d>\n", key)
			return
		}
		idx = (idx + 1) % (LENGTH * 10)
		counter += 1
	}
	log.Printf("Info: tried to delete non existing element <key: %d>\n", key)
}

func hash(key int) int {
	s := strconv.Itoa(key)
	h := fnv.New32a()
	h.Write([]byte(s))
	ret := h.Sum32() % (LENGTH * 10)
	return abs(ret)
}

func abs(a uint32) int {
	ret := int(a)
	if a > 0 {
		return ret
	} else {
		return -ret
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	table := make(HashTable, LENGTH*10)
	for i := range table {
		table[i] = &Cell{Key: -1, Mark: FREE}
	}

	input := make([]int, LENGTH*8)
	for i := 0; i < len(input); i++ {
		input[i] = i
	}

	for _, ele := range input {
		table.Insert(ele)
	}

	for i := range table {
		switch table[i].Mark {
		case FREE:
			log.Printf("[%d] Key: %d, Mark: FREE\n", i, table[i].Key)
		case DELETED:
			log.Printf("[%d] Key: %d, Mark: DELETED", i, table[i].Key)
		case USED:
			log.Printf("[%d] Key: %d, Mark: USED\n", i, table[i].Key)
		default:
			log.Fatalln("Never reach")
		}
	}

	for i := 0; i < LENGTH; i++ {
		target := rand.Intn(LENGTH * 10)
		cell, found := table.Search(target)
		if found {
			log.Printf("Found: <key: %d>\n", cell.Key)
		} else {
			log.Printf("Not Found: <key: %d>\n", target)
		}
	}

	for i := 0; i < LENGTH; i++ {
		deleting := rand.Intn(LENGTH * 10)
		table.Delete(deleting)
	}

	for i := 0; i < LENGTH*10; i++ {
		target := rand.Intn(LENGTH * 10)
		cell, found := table.Search(target)
		if found {
			log.Printf("Found: <key: %d>\n", cell.Key)
		} else {
			log.Printf("Not Found: <key: %d>\n", target)
		}
	}
}