Mapを極める - key->valueの索引の使い方

Mapは key -> valueの索引のためのデータ構造。keyの値には重複を許さない。内部的にはHashMapが使われており、要素を挿入した順番は保持されない。

Mapの作成

scala> val m = Map(1 -> "Apple", 2 -> "Banana", 3 -> "Chocolate")
m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> Apple, 2 -> Banana, 3 -> Chocolate)

1 -> "Apple"の部分では、(1, "Apple")のTupleが生成され、最終的にMap.apply(elems:(A, B)*)が呼ばれている。

Builderを使ってMapを作成

ファイルやDBなどから大量のデータを読み込んで、immutableなMapを作りたい場合はBuilderを使うと良い。

val m = {
	val b = Map.newBuilder[Int, String]
	b += 1 -> "Apple" 
	b += ...   
	...
	b.result
}

mutableなデータ(builder)は外に見せないように閉じ込めている。

Mapの使い方

keyの集合を取得

scala> m.keys
res0: Iterable[Int] = Set(1, 2, 3)

valueの集合を取得

scala> m.values
res1: Iterable[java.lang.String] = MapLike(Apple, Banana, Chocolate)

key, valueのエントリを取得

scala> for((key, value) <- m) println("key:%s, value:%s".format(key, value))
key:1, value:Apple
key:2, value:Banana
key:3, value:Chocolate

keyに対応する値の取得

scala> m(1)
res4: java.lang.String = Apple

scala> m(4)
java.util.NoSuchElementException: key not found: 4

Optionを使ってvalueを取得

例外処理のコードを書くのは面倒なので、Optionを返すこともできる。

scala> m.get(1)
res15: Option[java.lang.String] = Some(Apple)

scala> m.get(5)
res16: Option[java.lang.String] = None

Optionを使う利点は、keyに対応するentryがあってもなくてもコードの流れをさまたげないようにプログラミングできること。

scala> def printIfExists(key:Int) = for(v <- m.get(key)) println(v)
printIfExist: (key: Int)Unit

scala> printIfExists(1)
Apple

scala> printIfExists(5)
                       // 何も表示されない(println(v)が実行されない)

この動作は、None.foreach では何もしないように定義されていることによる。

エントリが見つからないときのデフォルト値を与える

getOrElseを使う。

scala> m.getOrElse(10, "N/A")
res21: java.lang.String = N/A

変更可能(mutable)なマップを使う

上記の例でmapに新しいエントリを追加すると、新しいMapが生成される。

scala> val m2 = m + (4 -> "Donut")
m2: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> Apple, 2 -> Banana, 3 -> Chocolate, 4 -> Donut)

元のマップには変更が加えられていない（persistent)

scala> m
res29: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> Apple, 2 -> Banana, 3 -> Chocolate)

Mapの内容をin placeで上書きしたい場合は、scala.collection.mutable.Mapを使う。

mutable.Mapの作成

+=で追加、-=で削除。

scala> val m = scala.collection.mutable.Map[Int, String]()
m: scala.collection.mutable.Map[Int,String] = Map()

scala> m += 1 -> "Apple"
res22: m.type = Map(1 -> Apple)

scala> m += 2 -> "Banana"
res23: m.type = Map(1 -> Apple, 2 -> Banana)

scala> m += 3 -> "Cookie"
res24: m.type = Map(3 -> Cookie, 1 -> Apple, 2 -> Banana)

scala> m += 4 -> "Donut"
res25: m.type = Map(3 -> Cookie, 4 -> Donut, 1 -> Apple, 2 -> Banana)

scala> m -= 2
res26: m.type = Map(3 -> Cookie, 4 -> Donut, 1 -> Apple)

mutable.Mapでエントリが存在しなければ更新を行う

getOrElseUpdate(key, default)を使う。

scala> m.getOrElseUpdate(10, "Penut")
res27: String = Penut

10 -> Penutが追加されている

scala> m
res28: scala.collection.mutable.Map[Int,String] = 
   Map(10 -> Penut, 3 -> Cookie, 4 -> Donut, 1 -> Apple)

応用例

getOrElseUpdateはエントリが存在しない場合の処理を一行に納めることができるので重宝する。

def getValue(key:Int) : String = {
	def createNewEntry : String = {
		// (初期化に必要な処理をする。例：DBへのクエリなど)
		database.query(key)
	}
	// Mapにエントリが存在すればそれを返し、なければ初期化して追加し、追加した値を返す
	m.getOrElseUpdate(key, createNewEntry)
}

キャッシュとしてマップを使う

Mapにエントリを格納するとMapから各エントリへの参照が保存される。しかし、Map内のエントリが不要になったとしても、Mapのインスタンスがある限りgarvage collector(GC)が参照関係を考慮してエントリを含むメモリ領域を回収してくれない。

そこでWeakHashMapを使うと、keyの値はWeakReference(GCが参照先として辿らない特別な参照)として管理されるため、エントリをGC(garvage collection)による回収の対象にしてくれる。

例えば初期化に時間がかかったり、メモリを大量に使うようなオブジェクトの一時的なキャッシュとしてWeakHashMapを使う。

class HeavyObject(id:Int) {
   ... (do some heavy initializations here)
}

object HeavyObject {
	private val w = scala.collection.mutable.WeakHashMap[Int, HeavyObject]()

	def apply(key:Int) = 
	   w.getOrElseUpdate(key, new HeavyObject(key)) // new HeavyObjectは遅延評価される
}

{
	val h = HeavyObject(1) 
     ...
	val ref = HeavyObject(1)  // ここでは高い確率でWeakHashMap内の同じインスタンスが使い回される
}

// 1 -> HeavyObject(1) のエントリはGCの回収の対象
// いつ解放されるかはGCのタイミング次第（メモリが不足したときなど）

Mapを極める key->valueの索引の使い方