Goで黄金比ハッシュマップ

Linuxカーネルのソースに、不思議な定数があります

hash.h

#define GOLDEN_RATIO_32 0x61C88647

どうやらこの数字は、2 ^ 32を黄金比で割り、符号付きで表した数とのこと

\phi = \frac{(1 + \sqrt{5})} {2} \\

\frac{2^{32}} {\phi} = 2654435769.4972...

2654435769を32ビット符号付き10進数にすると-1640531527
符号をプラスにして16進数で表記すると61C88647

ハッシュマップのようなデータ構造を作る際に、程よくばらけたインデックスが必要になるのですが、黄金比から導いたこの定数を用いることで、適度にばらけた良い感じの値が得られるそうです

クヌース先生のTAOCP３巻 6-4にも触れられていました

神秘的な数字である黄金比、なんともロマンがあるじゃありませんか！

本当にばらけるの？

実際のところ、黄金比定数を使うことでどのくらいハッシュ値がばらけるのでしょうか？

以下のようなコードで実験してみます

const (
	bitSize     = 10         // 出力ビットサイズ（2 ^ N）
	goldenRatio = 0x61C88647 // 黄金比定数 2 ^ 32 / phi
	prime       = 397        // 任意の素数（文字列をハッシュ化する際に使用）
)

// calcGoldenRatioHash 黄金比ハッシュの計算
func calcGoldenRatioHash(str string) uint32 {
	hash := uint32(len(str))
	for _, c := range str {
		hash *= prime
		hash ^= uint32(c)
	}
	hash *= goldenRatio
	return hash >> (32 - bitSize)
}

bitSizeは出力される値の桁数で、10としておりますので、0〜1023の範囲の値が出力されます

primeは任意の素数で、文字列からハッシュ化する際に定数として使っています

文字列	ハッシュ値
Hello World	109
Hello World!	291
テスト太郎	909
テスト次郎	473
こんにちは	621
いい天気だ	522

よく似た文字列でも、いい感じにばらけているように見えます！
これは良さそうですね！

暗号論的に安全なハッシュ関数というわけでは無いようです
セキュリティに関わる分野では使用は避けるべきでしょう

ハッシュマップを作ってみる

名前はGoldenRatioMap（黄金比マップ）としましょう！

キーは文字列とし、バリューは任意の型をジェネリクスで指定できるようにします

文字列をハッシュ化しインデックスを計算する際に、先ほどの関数を使います

ハッシュが重複した場合は、チェーン法でノードを追加するようにします

golden_ratio_map.go

package hashmap

const (
	bitSize     = 10         // Mapのサイズ（2 ^ N）
	goldenRatio = 0x61C88647 // 黄金比定数 2 ^ 32 / phi
	prime       = 397        // 任意の素数（文字列をハッシュ化する際に使用）
)

// calcGoldenRatioHash 黄金比ハッシュの計算
func calcGoldenRatioHash(str string) uint32 {
	hash := uint32(len(str))
	for _, c := range str {
		hash *= prime
		hash ^= uint32(c)
	}
	hash *= goldenRatio
	return hash >> (32 - bitSize)
}

type node[T any] struct {
	key   string
	value T
	next  *node[T]
}

// GoldenRatioMap 黄金比マップ
type GoldenRatioMap[T any] struct {
	buckets []*node[T]
}

// NewGoldenRatioMap 黄金比マップの作成
func NewGoldenRatioMap[T any]() *GoldenRatioMap[T] {
	size := 1 << bitSize
	return &GoldenRatioMap[T]{
		buckets: make([]*node[T], size),
	}
}

// Set 値のセット
func (g *GoldenRatioMap[T]) Set(key string, value T) {
	index := calcGoldenRatioHash(key)
	newNode := &node[T]{
		key:   key,
		value: value,
		next:  nil,
	}

	// バケットが空ならノード挿入
	if g.buckets[index] == nil {
		g.buckets[index] = newNode
		return
	}

	// キーが一致したら値の更新
	if g.buckets[index].key == key {
		g.buckets[index].value = value
		return
	}

	current := g.buckets[index]
	// チェーンを辿る
	for current.next != nil {
		// 同じキーが見つかったら更新
		if current.key == key {
			current.value = value
			return
		}
		current = current.next
	}

	// チェーンの最後が同じキーだった
	if current.key == key {
		current.value = value
		return
	}

	// チェーンに新規ノード追加
	current.next = newNode
}

// Get 値の取得
func (g *GoldenRatioMap[T]) Get(key string) (T, bool) {
	index := calcGoldenRatioHash(key)
	current := g.buckets[index]

	for current != nil {
		if current.key == key {
			return current.value, true
		}
		current = current.next
	}

	// ノードが無かった場合はゼロ値を返す
	var zero T
	return zero, false
}

// Remove キーの削除
func (g *GoldenRatioMap[T]) Remove(key string) {
	index := calcGoldenRatioHash(key)
	current := g.buckets[index]
	var prev *node[T]

	// currentがnilの場合はリターン
	if current == nil {
		return
	}

	// currentのキーが一致した場合、nextを付け替える
	if current.key == key {
		g.buckets[index] = current.next
		return
	}

	prev = current
	current = current.next
	// チェーンをたどって探索
	for current != nil {
		// キーが一致したら、nextを付け替える
		if current.key == key {
			prev.next = current.next
			return
		}
		prev = current
		current = current.next
	}
}

main.go

func main() {
    // ハッシュマップの作成
	gMap := hashmap.NewGoldenRatioMap[int]()

    // 値の挿入
	gMap.Set("テスト太郎", 1)
	gMap.Set("テスト次郎", 2)
	gMap.Set("テスト三郎", 3)

    // 値の取得
	fmt.Println(gMap.Get("テスト太郎"))
	fmt.Println(gMap.Get("テスト次郎"))
	fmt.Println(gMap.Get("テスト三郎"))
}

ちゃんと動きました！

今回のハッシュ法は乗算とビット演算しか使っていないので、かなり高速に動作しそうですね！

時間ある時に、どのくらいの速度が出るか、ベンチマークを取ってみたいです