Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 12060] ファイルの概要

このコミットは、Go言語のリポジトリから test/hashmap.go というファイルを削除するものです。このファイルは、カスタムのハッシュマップ実装とそれに関連するテストコードを含んでいましたが、コミットメッセージによると、そのスタイルが「奇妙」であり、テストとしての真の目的が不明確であると判断されたため削除されました。

コミット

commit f5ff5b4fcb4098eb16e7b2390cd3553dc3a51373
Author: Rob Pike <r@golang.org>
Date:   Mon Feb 20 07:43:16 2012 +1100

    test/hashmap.go: delete
    It's in an odd style and it's unclear what true purpose it serves as
    a test other than to be another Go program.
    
    R=gri
    CC=golang-dev
    https://golang.org/cl/5674111

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/f5ff5b4fcb4098eb16e7b2390cd3553dc3a51373

元コミット内容

test/hashmap.go: delete It's in an odd style and it's unclear what true purpose it serves as a test other than to be another Go program.

変更の背景

この変更の背景には、Go言語の標準ライブラリやプロジェクトにおけるテストコードの品質と目的の明確化があります。削除された test/hashmap.go は、Go言語の初期段階で書かれた可能性のある、カスタムのハッシュマップ実装とそれに対するテストコードを含んでいました。

コミットメッセージにある「It's in an odd style」という記述は、当時のGo言語の慣習や推奨されるコーディングスタイルから逸脱していた可能性を示唆しています。また、「it's unclear what true purpose it serves as a test other than to be another Go program」という点は、このファイルが特定の機能やバグを検証するための明確なテストケースとして機能していなかったことを意味します。Go言語のテストは、通常、特定のパッケージや関数の振る舞いを検証し、回帰を防ぐことを目的とします。しかし、このファイルは単なるGoプログラムの例として存在しているだけで、テストスイートの一部として維持する価値がないと判断されたと考えられます。

Go言語の進化に伴い、テストの書き方や標準ライブラリの提供する機能も成熟していきました。おそらく、このカスタムハッシュマップの実装は、Goの組み込みマップ型（map）の登場や、より標準的なテスト手法の確立により、その存在意義が薄れたものと推測されます。

前提知識の解説

Go言語におけるテストの慣習

Go言語には、標準ライブラリに testing パッケージが用意されており、これを用いてテストを記述するのが一般的です。テストファイルは通常、テスト対象のソースファイルと同じディレクトリに配置され、ファイル名の末尾に _test.go を付けます（例: my_package_test.go）。テスト関数は Test で始まり、*testing.T 型の引数を取ります。

Goのテストは、シンプルさと高速性を重視しており、外部のフレームワークに依存することなく、標準ツール（go test コマンド）で実行できます。これにより、開発者は一貫した方法でテストを記述・実行できます。

ハッシュマップ (HashMap) の基本的な概念

ハッシュマップ（またはハッシュテーブル、連想配列、辞書）は、キーと値のペアを格納するためのデータ構造です。キーをハッシュ関数に通して得られるハッシュ値を使って、値を格納するメモリ上の位置（バケット）を決定します。これにより、キーを使って高速に値の検索、挿入、削除を行うことができます。

ハッシュマップの効率は、ハッシュ関数の品質（キーを均等に分散させる能力）と、衝突解決（異なるキーが同じハッシュ値になる場合）の戦略に大きく依存します。一般的な衝突解決の方法には、チェイニング（各バケットをリンクリストにする）やオープンアドレス法（空いている次のバケットを探す）があります。

Go言語には、組み込み型として map が提供されており、これは非常に効率的で使いやすいハッシュマップの実装です。通常、Goでハッシュマップが必要な場合は、この組み込みの map 型を使用します。

test/ ディレクトリの役割

Go言語のプロジェクトにおいて、test/ ディレクトリは、通常、特定のパッケージや機能の単体テストや統合テスト以外の、より広範なテストや、特定の環境でのみ実行されるテスト、あるいはGo言語の機能そのものを検証するためのテストコードを配置するために使用されることがあります。しかし、その役割はプロジェクトによって異なり、時には標準的なテスト慣習に沿わない実験的なコードや、一時的な検証コードが置かれることもあります。

このコミットの文脈では、test/hashmap.go が標準的な単体テストの慣習（例: _test.go ファイル）に従っていなかったため、test/ ディレクトリに配置されていたと考えられます。

技術的詳細

削除された test/hashmap.go ファイルは、Go言語で書かれたカスタムのハッシュマップ実装を含んでいました。この実装は、Goの組み込み map 型が成熟する前の、Go言語の初期段階で書かれたものと推測されます。

ファイルの内容を見ると、以下のような特徴がありました。

  • カスタムのハッシュマップ構造: HashMap という構造体が定義されており、内部に Array 型（固定サイズの配列）と、log2_capacity_、occupancy_ といったフィールドを持っていました。これは、オープンアドレス法の一種である線形プロービング（Linear Probing）を用いたハッシュマップの実装を示唆しています。
  • インターフェースの利用: KeyType と ValueType というインターフェースが定義されていました。KeyType は Hash() メソッドと Match() メソッドを持ち、キーのハッシュ値計算と等価性比較を抽象化していました。これは、Goのインターフェースの初期の利用例として興味深い点です。
  • 基本的なハッシュマップ操作: Clear(), Initialize(), Probe(), Lookup(), Resize() といったメソッドが実装されており、ハッシュマップの基本的なクリア、初期化、キーの探索、挿入、リサイズ（容量拡張）のロジックが含まれていました。
    • Probe(key KeyType) *Entry: キーに対応するエントリを見つけるためのプロービングロジック。衝突が発生した場合、次のインデックスを線形に探索します。
    • Lookup(key KeyType, insert bool) *Entry: キーを検索し、必要に応じて新しいエントリを挿入するロジック。
    • Resize(): ハッシュマップの占有率が一定の閾値（80%）を超えた場合に、容量を倍にして再ハッシュを行うロジック。
  • テストコード: main 関数内で、HashMap のインスタンスを作成し、Number 型のキーを使って Lookup を試みる、非常にシンプルなテストコードが含まれていました。しかし、コメントアウトされた部分や、ASSERT 関数が panic 0 を呼び出すだけの不完全な実装であることから、このテストコードが十分に機能していなかったことが伺えます。

コミットメッセージの「odd style」という表現は、Go言語の標準的なエラーハンドリング（panic ではなく error を返す）、インターフェースの利用方法、あるいは一般的なGoのコーディング慣習から見て、このコードが当時のベストプラクティスに沿っていなかったことを指している可能性があります。また、「unclear what true purpose it serves as a test」という点は、このハッシュマップ実装がGoの組み込み map 型の登場により不要になったこと、あるいはこのテストが特定のバグを再現したり、特定の機能の正確性を検証したりする明確な目的を持っていなかったことを示唆しています。

Go言語の進化の過程で、このような実験的なコードや、初期の設計に基づくコードが整理され、より洗練された標準的な実装やテスト手法に置き換えられていった一例と言えるでしょう。

コアとなるコードの変更箇所

このコミットでは、test/hashmap.go ファイル全体が削除されています。

--- a/test/hashmap.go
+++ /dev/null
@@ -1,181 +0,0 @@
-// run
-
-// Copyright 2009 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package main
-
-// ----------------------------------------------------------------------------
-// Helper functions
-
-func ASSERT(p bool) {
-	if !p {
-		// panic 0
-	}
-}
-
-
-// ----------------------------------------------------------------------------
-// Implementation of the HashMap
-
-type KeyType interface {
-	Hash() uint32
-	Match(other KeyType) bool
-}
-
-
-type ValueType interface {
-	// empty interface
-}
-
-
-type Entry struct {
-	key KeyType
-	value ValueType
-}
-
-
-type Array [1024]Entry
-
-type HashMap struct {
-	map_ *Array
-	log2_capacity_ uint32
-	occupancy_ uint32
-}
-
-
-func (m *HashMap) capacity() uint32 {
-	return 1 << m.log2_capacity_
-}
-
-
-func (m *HashMap) Clear() {
-	// Mark all entries as empty.
-	var i uint32 = m.capacity() - 1
-	for i > 0 {
-		m.map_[i].key = nil
-		i = i - 1
-	}
-	m.occupancy_ = 0
-}
-
-
-func (m *HashMap) Initialize (initial_log2_capacity uint32) {
-	m.log2_capacity_ = initial_log2_capacity
-	m.map_ = new(Array)
-	m.Clear()
-}
-
-
-func (m *HashMap) Probe (key KeyType) *Entry {
-	ASSERT(key != nil)
-
-	var i uint32 = key.Hash() % m.capacity()
-	ASSERT(0 <= i && i < m.capacity())
-
-	ASSERT(m.occupancy_ < m.capacity())	// guarantees loop termination
-	for m.map_[i].key != nil && !m.map_[i].key.Match(key) {
-		i++
-		if i >= m.capacity() {
-			i = 0
-		}
-	}
-
-	return &m.map_[i]
-}
-
-
-func (m *HashMap) Lookup (key KeyType, insert bool) *Entry {
-	// Find a matching entry.
-	var p *Entry = m.Probe(key)
-		if p.key != nil {
-		return p
-	}
-
-	// No entry found; insert one if necessary.
-	if insert {
-		p.key = key
-		p.value = nil
-		m.occupancy_++
-
-		// Grow the map if we reached >= 80% occupancy.
-		if m.occupancy_ + m.occupancy_/4 >= m.capacity() {
-			m.Resize()
-			p = m.Probe(key)
-		}
-
-		return p
-	}
-
-	// No entry found and none inserted.
-	return nil
-}
-
-
-func (m *HashMap) Resize() {
-	var hmap *Array = m.map_
-	var n uint32 = m.occupancy_
-
-	// Allocate a new map of twice the current size.
-	m.Initialize(m.log2_capacity_ << 1)
-
-	// Rehash all current entries.
-	var i uint32 = 0
-	for n > 0 {
-		if hmap[i].key != nil {
-			m.Lookup(hmap[i].key, true).value = hmap[i].value
-			n = n - 1
-		}
-		i++
-	}
-}
-
-
-// ----------------------------------------------------------------------------
-// Test code
-
-type Number struct {
-	x uint32
-}
-
-
-func (n *Number) Hash() uint32 {
-	return n.x * 23
-}
-
-
-func (n *Number) Match(other KeyType) bool {
-	// var y *Number = other
-	// return n.x == y.x
-	return false
-}
-
-
-func MakeNumber (x uint32) *Number {
-	var n *Number = new(Number)
-	n.x = x
-	return n
-}
-
-
-func main() {
-	// func (n int) int { return n + 1; }(1)
-
-	//print "HashMap - gri 2/8/2008\n"
-
-	var hmap *HashMap = new(HashMap)
-	hmap.Initialize(0)
-
-	var x1 *Number = MakeNumber(1001)
-	var x2 *Number = MakeNumber(2002)
-	var x3 *Number = MakeNumber(3003)
-	_, _, _ = x1, x2, x3
-
-	// this doesn't work I think...
-	//hmap.Lookup(x1, true)
-	//hmap.Lookup(x2, true)
-	//hmap.Lookup(x3, true)
-
-	//print "done\n"
-}

コアとなるコードの解説

削除された test/hashmap.go ファイルは、Go言語で書かれたカスタムのハッシュマップ実装と、その非常にシンプルなテストコードを含んでいました。このコードは、Goの組み込み map 型が提供される以前、あるいはその初期段階で、ハッシュマップの概念をGoでどのように実装できるかを示すための実験的な試みであったと考えられます。

主要な要素は以下の通りです。

  1. HashMap 構造体:

    • map_ *Array: 実際のキーと値のペアを格納する固定サイズの配列へのポインタ。Array は [1024]Entry と定義されており、最大1024エントリを格納できることを示唆しています。
    • log2_capacity_ uint32: ハッシュマップの容量の2を底とする対数。例えば、容量が1024であれば log2_capacity_ は10になります。
    • occupancy_ uint32: 現在ハッシュマップに格納されているエントリの数。

  2. KeyType インターフェース:

    • Hash() uint32: キーのハッシュ値を計算するメソッド。
    • Match(other KeyType) bool: 2つのキーが等しいかどうかを比較するメソッド。
    • このインターフェースにより、任意の型をハッシュマップのキーとして使用できる柔軟性を提供しようとしていました。

  3. Probe メソッド:

    • func (m *HashMap) Probe (key KeyType) *Entry: 与えられたキーに対応するエントリ（または挿入可能な空のスロット）を見つけるためのメソッドです。
    • キーのハッシュ値から初期インデックスを計算し、衝突が発生した場合は線形に次のインデックスを探索します（線形プロービング）。
    • ASSERT 関数が使われていますが、これはGoの標準的なエラーハンドリングではなく、C言語のようなアサーションを模倣したものです。

  4. Lookup メソッド:

    • func (m *HashMap) Lookup (key KeyType, insert bool) *Entry: キーを検索し、見つからなかった場合に insert フラグが true であれば新しいエントリを挿入するメソッドです。
    • 挿入時には occupancy_ をインクリメントし、ハッシュマップの占有率が80%（m.occupancy_ + m.occupancy_/4 >= m.capacity()）を超えた場合に Resize() を呼び出して容量を拡張します。

  5. Resize メソッド:

    • func (m *HashMap) Resize(): ハッシュマップの容量を倍にし、既存のすべてのエントリを新しいハッシュマップに再ハッシュして移動するメソッドです。
    • m.Initialize(m.log2_capacity_ << 1) で新しい（より大きな）ハッシュマップを初期化し、古いマップのエントリを一つずつ新しいマップに Lookup してコピーしています。

  6. テストコード:

    • main 関数内で HashMap を初期化し、Number 型のキー（x uint32 を持つ構造体）を作成して Lookup を試みていました。
    • しかし、hmap.Lookup の呼び出しがコメントアウトされており、Match メソッドの実装が常に false を返すなど、テストとしては不完全な状態でした。

このコードは、Go言語の初期におけるデータ構造の実装方法や、インターフェースの活用方法の一例として興味深いものですが、Goの組み込み map 型の登場と成熟により、その役割を終えたと考えられます。また、テストとしての目的が不明確であったため、プロジェクトのコードベースから削除されることになりました。

関連リンク

参考にした情報源リンク

  • https://golang.org/cl/5674111 (Go Gerrit Code Review)
  • Go言語の公式ドキュメント (Go言語のテスト、マップ型に関する情報)
  • ハッシュマップに関する一般的なデータ構造の知識