ハッシュマップでキーに関連付けられた値を格納する
一般的なコレクションの最後の 1 つがハッシュマップです。型 HashMap<K, V> は、ハッシュ関数 を使って、型 K のキーから型 V の値への対応付けを格納します。この関数は、これらのキーと値をメモリ内のどこに配置するかを決定します。多くのプログラミング言語はこの種のデータ構造をサポートしていますが、hash、map、object、hash table、dictionary、associative array など、さまざまな名前で呼ばれることがよくあります。
ハッシュマップは、ベクタのようにインデックスを使ってではなく、任意の型になりうるキーを使ってデータを検索したいときに便利です。たとえばゲームでは、各チームのスコアをハッシュマップで管理できます。この場合、各キーはチーム名で、各値はそのチームのスコアです。チーム名が与えられれば、そのスコアを取り出せます。
このセクションではハッシュマップの基本的な API を見ていきますが、標準ライブラリが HashMap<K, V> に対して定義している便利な機能はほかにもたくさんあります。いつものように、より詳しい情報については標準ライブラリのドキュメントを確認してください。
新しいハッシュマップを作成する
空のハッシュマップを作成する 1 つの方法は、new を使い、insert で要素を追加することです。リスト 8-20 では、名前が Blue と Yellow の 2 チームのスコアを追跡しています。Blue チームは 10 点から始まり、Yellow チームは 50 点から始まります。
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
}まず、標準ライブラリの collections 部分から HashMap を use する必要があることに注意してください。3 つの一般的なコレクションのうち、これは最も使用頻度が低いため、prelude によって自動的にスコープに導入される機能には含まれていません。また、ハッシュマップは標準ライブラリからのサポートもやや少なく、たとえばそれらを構築するための組み込みマクロはありません。
ベクタと同様に、ハッシュマップはデータをヒープに格納します。この HashMap は、キーの型が String、値の型が i32 です。ベクタと同様に、ハッシュマップも同種です。つまり、すべてのキーは同じ型でなければならず、すべての値も同じ型でなければなりません。
ハッシュマップ内の値にアクセスする
ハッシュマップから値を取り出すには、リスト 8-21 に示すように、そのキーを get メソッドに渡します。
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
let team_name = String::from("Blue");
let score = scores.get(&team_name).copied().unwrap_or(0);
}ここで、score には Blue チームに関連付けられた値が入り、結果は 10 になります。get メソッドは Option<&V> を返します。ハッシュマップ内にそのキーに対応する値がない場合、get は None を返します。このプログラムでは、copied を呼び出して Option<&i32> ではなく Option<i32> を取得し、その後 unwrap_or を使って、scores にそのキーのエントリがない場合は score を 0 に設定することで、この Option を処理しています。
ハッシュマップ内の各キーと値のペアは、ベクタと同様に for ループを使って走査できます。
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
for (key, value) in &scores {
println!("{key}: {value}");
}
}このコードは、各ペアを任意の順序で出力します。
Yellow: 50
Blue: 10
ハッシュマップで所有権を管理する
i32 のように Copy トレイトを実装している型では、値はハッシュマップにコピーされます。String のような所有権を持つ値では、値はムーブされ、ハッシュマップがそれらの値の所有者になります。これはリスト 8-22 で示しています。
fn main() {
use std::collections::HashMap;
let field_name = String::from("Favorite color");
let field_value = String::from("Blue");
let mut map = HashMap::new();
map.insert(field_name, field_value);
// field_name and field_value are invalid at this point, try using them and
// see what compiler error you get!
}field_name と field_value は insert の呼び出しによってハッシュマップにムーブされているため、その後はこれらの変数を使うことはできません。
値への参照をハッシュマップに挿入する場合、値自体はハッシュマップにムーブされません。参照が指す値は、少なくともハッシュマップが有効であるのと同じだけ長く有効でなければなりません。これらの問題については、第 10 章の 「ライフタイムで参照を検証する」 で詳しく説明します。
ハッシュマップを更新する
キーと値のペアの数は増やせますが、各一意なキーに同時に関連付けられる値は 1 つだけです（ただし逆は成り立ちません。たとえば Blue チームと Yellow チームの両方が、scores ハッシュマップで値 10 を持つことはできます）。
ハッシュマップ内のデータを変更したいときは、あるキーにすでに値が割り当てられている場合をどう扱うか決める必要があります。古い値を完全に無視して新しい値で置き換えることもできます。古い値を保持して新しい値を無視し、そのキーにまだ値が ない 場合にだけ新しい値を追加することもできます。あるいは、古い値と新しい値を組み合わせることもできます。それぞれの方法を見ていきましょう。
値を上書きする
キーと値をハッシュマップに挿入し、その後同じキーに対して別の値を挿入すると、そのキーに関連付けられた値は置き換えられます。リスト 8-23 のコードでは insert を 2 回呼び出していますが、Blue チームのキーに対する値を両方とも挿入しているため、ハッシュマップに含まれるキーと値のペアは 1 つだけになります。
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);
println!("{scores:?}");
}このコードは {"Blue": 25} を出力します。元の値 10 は上書きされています。
キーが存在しない場合にのみキーと値を追加する
特定のキーがすでに値とともにハッシュマップに存在するかどうかを確認し、その後に次のような動作を行うのは一般的です。キーがハッシュマップ内に存在する場合は、既存の値はそのままにしておきます。キーが存在しない場合は、そのキーとそれに対応する値を挿入します。
ハッシュマップには、このための特別な API として entry があり、確認したいキーを引数として取ります。entry メソッドの戻り値は Entry という enum で、存在するかもしれないし存在しないかもしれない値を表します。たとえば、Yellow チームのキーに値が関連付けられているかどうかを確認したいとします。もし関連付けられていなければ、値 50 を挿入したいとし、Blue チームについても同様です。entry API を使うと、コードはリスト 8-24 のようになります。
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Blue")).or_insert(50);
println!("{scores:?}");
}リスト 8-24 のコードを実行すると、{"Yellow": 50, "Blue": 10} が出力されます。最初の entry 呼び出しでは、Yellow チームにはまだ値がないため、値 50 とともに Yellow チームのキーが挿入されます。2 回目の entry 呼び出しでは、Blue チームにはすでに値 10 があるため、ハッシュマップは変更されません。
古い値に基づいて値を更新する
ハッシュマップのもう 1 つの一般的な使用例は、キーの値を調べてから、その古い値に基づいて更新することです。たとえば、リスト 8-25 は、あるテキスト内で各単語が何回現れるかを数えるコードを示しています。単語をキーとするハッシュマップを使い、その単語を見かけた回数を追跡するために値を増やしています。ある単語を初めて見たときは、まず値 0 を挿入します。
fn main() {
use std::collections::HashMap;
let text = "hello world wonderful world";
let mut map = HashMap::new();
for word in text.split_whitespace() {
let count = map.entry(word).or_insert(0);
*count += 1;
}
println!("{map:?}");
}このコードは {"world": 2, "hello": 1, "wonderful": 1} を出力します。同じキーと値のペアが別の順序で出力されることもあります。「ハッシュマップ内の値にアクセスする」 で述べたように、ハッシュマップの反復は任意の順序で行われることを思い出してください。
split_whitespace メソッドは、text の値に含まれる、空白で区切られた部分スライスに対するイテレータを返します。or_insert メソッドは、指定されたキーに対応する値への可変参照 (&mut V) を返します。ここでは、その可変参照を count 変数に格納しているので、その値に代入するには、まずアスタリスク (*) を使って count をデリファレンスしなければなりません。可変参照は for ループの終わりでスコープを抜けるため、これらの変更はすべて安全であり、借用規則によって許可されます。
ハッシュ関数
デフォルトでは、HashMap は SipHash と呼ばれるハッシュ関数を使用しており、ハッシュテーブルを利用したサービス拒否 (DoS) 攻撃への耐性を提供できます1。これは利用可能な中で最速のハッシュアルゴリズムではありませんが、性能低下に伴う、より高いセキュリティとのトレードオフには十分な価値があります。コードをプロファイルして、デフォルトのハッシュ関数が用途に対して遅すぎるとわかった場合は、別の hasher を指定することで別の関数に切り替えることができます。hasher とは、BuildHasher トレイトを実装する型です。トレイトとその実装方法については、第 10 章 で説明します。必ずしも自分で hasher をゼロから実装する必要はありません。crates.io には、一般的なハッシュアルゴリズムを実装した hasher を提供する、ほかの Rust ユーザーによって共有されたライブラリがあります。
まとめ
ベクタ、文字列、ハッシュマップは、データを保存、アクセス、変更する必要があるときに、プログラムで必要となる多くの機能を提供してくれます。これで、次のような練習問題を解けるようになっているはずです。
- 整数のリストが与えられたとき、ベクタを使って中央値（ソートしたときの中央の位置にある値）と最頻値（最も多く現れる値。ここではハッシュマップが役に立ちます）を返してください。
- 文字列を Pig Latin に変換してください。各単語の最初の子音を単語の末尾に移動し、ay を追加します。たとえば first は irst-fay になります。母音で始まる単語には、代わりに末尾に hay を追加します（apple は apple-hay になります）。UTF-8 エンコーディングに関する詳細も忘れないでください。
- ハッシュマップとベクタを使って、ユーザーが会社内の部署に従業員名を追加できるテキストインターフェースを作成してください。たとえば、「Add Sally to Engineering」や「Add Amir to Sales」のようにします。続いて、ユーザーが部署ごとの全従業員の一覧、または会社全体の全従業員を部署別にアルファベット順で取得できるようにしてください。
標準ライブラリの API ドキュメントには、これらの練習問題に役立つ、ベクタ、文字列、ハッシュマップが持つメソッドが説明されています。
処理が失敗する可能性のある、より複雑なプログラムに入っていくので、エラーハンドリングについて議論するには絶好のタイミングです。次はそれを見ていきましょう！