コード

mail.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

// 1次ハッシュ
func primaryHash(key int, n int) int {
	return key % n
}

// 2次ハッシュ
func secondaryHash(key int, n int) int {
	// 再計算したハッシュ値が同じにならないように
	// 1以上かつハッシュテーブルの長さ未満の値を返す
	return 1 + (key % (n - 1))
}

func calcHash(key int, i int, n int) int {
	return (primaryHash(key, n) + i*secondaryHash(key, n)) % n
}

func Insert(hashTable []int, key int) int {
	n := len(hashTable)
	i := 0

	for i < n {
		hash := calcHash(key, i, n)
		if hashTable[hash] == 0 {
			// 格納しそのハッシュ値を返す
			hashTable[hash] = key
			return hash
		} else if hashTable[hash] == key {
			// すでに同じ値が格納されていればそのハッシュ値を返す
			return hash
		} else {
			// 衝突した場合はハッシュ値を再計算する
			i++
		}
	}

	return -1
}

func Search(hashTable []int, key int) int {
	n := len(hashTable)
	i := 0
	for i < n {
		hash := calcHash(key, i, n)
		if hashTable[hash] == key {
			// 見つかったらハッシュ値を返す
			return hash
		} else if hashTable[hash] == 0 {
			// 空だった場合は格納されていないと判定し-1を返す
			return -1
		} else {
			// 違う値が格納されていた場合はハッシュ値を再計算する
			i++
		}
	}

	return -1
}

func convertToKey(str string) int {
	sum := 0
	digit := 1
	for _, v := range str {
		sum += digit * int(v-'A'+1)
		digit *= 5
	}
	return sum
}

const HASH_TABLE_LENGTH = 1000003

func main() {
	scanner := NewScanner()
	writer := bufio.NewWriter(os.Stdout)
	N := scanner.nextInt()

	hashTable := [HASH_TABLE_LENGTH]int{}

	for i := 0; i < N; i++ {
		cmd := scanner.nextStr()
		str := scanner.nextStr()
		key := convertToKey(str)
		if cmd == "insert" {
			Insert(hashTable[:], key)
		} else {
			res := Search(hashTable[:], key)
			if res >= 0 {
				fmt.Fprintln(writer, "yes")
			} else {
				fmt.Fprintln(writer, "no")
			}
		}
	}
	writer.Flush()
}

解説

オープンアドレスで実装する場合、ハッシュが衝突した場合はハッシュを再計算して空いている他の格納先を探します。
そのため、格納できる要素数はハッシュテーブルの長さまでに制限されるので、すべての要素を格納するのに十分な長さを確保する必要があります。
なおかつダブルハッシュで実装する場合、2次ハッシュとハッシュテーブルの長さが互いに素でないといけません。
この2つの要件を満たすためにHASH_TABLE_LENGTHを1000003としています。

ダブルハッシュは線形走査法に比べて何が嬉しい？

線形走査法は常に+1しかハッシュ値が後ろにずれないので、衝突した要素のかたまりが生じやすくなります。
この+1の代わりに2次ハッシュの値を使うことでうまく分散させることができます。
例として、ハッシュテーブルの長さが7で、8, 15という要素を格納する場合を考えてみましょう。
1次ハッシュの値は両方とも1なので衝突します。
secondaryHash関数で2次ハッシュを計算すると、
8 → 1 + 8 mod 6 = 3
15 → 1 + 15 mod 6 = 4となります。
この値を1次ハッシュに足して再計算するので、線形探索法と違って要素がうまく分散されることがわかります。

ダブルハッシュを実装する上での注意点

何度再計算しても同じ値を差すことになるので、2次ハッシュが絶対に0を返さないようにしましょう。
secondaryHashにて1を足しているのはそのためです。

return 1 + (key % (n - 1))

加えて、ハッシュテーブルの長さと2次ハッシュが互いに素でないと、ハッシュテーブルの特定のインデックスを確認できなくなります。
例えば要素数が10、2次ハッシュの値が2の場合、1, 3, 5, 7, 9, 1, 3 ...と、偶数のインデックスを確認し続けることになります。
この条件を満たすために、ハッシュテーブルの長さを素数にし、2次ハッシュがその値未満を返すようにします。
つまり、ハッシュテーブルの長さがnの場合、2次ハッシュがn-1以下を返すようにすればよいわけです。
ここで、secondaryHashは0を返さないようにmodを取った結果に1を加えます。
そのため、n-1でmodを取ることによってn-2以下の値になるようにし、そこに1を加えることで最終的にn-1以下の値が返るようになっています。

Go言語でハッシュ探索をダブルハッシュ、オープンアドレスで実装する

コード

解説

ダブルハッシュは線形走査法に比べて何が嬉しい？

ダブルハッシュを実装する上での注意点