HashMapでリストの比較を早くする
HashMapの使い方を覚えたので、関連項目と一緒にまとめてみる。まずは、HashMapとは何ぞやということを抑えてから、具体例を通して、どういう場合に使えるかを考えてみる。
HashMapとは？
Mapインターフェイスを実装しているデータストラクチャー。他にもdictionaryやunordered mapなどと呼ばれることもあるが、Javaの標準ライブラリではHashMapというクラスが使われている。
| 強み | 弱み |
|---|---|
| 基本的には早い検索機能[1] | 場合によっては時間がかかる[2] |
keyがフレキシブル |
要素の格納順が順不同 |
| - |
valueをキーとしてkeyを検索する場合は、全要素をループする必要があり時間がかかる |
| - | linked listを実装しているため、それぞれのデータがメモリ上で隣接していない[3] |
Map
Mapは、Collectionの一つ。keyとvalueのペアとなる要素を格納しており、keyを与えると、対応するvalueを検索できる。
ここで注意すべきは、keyはindexではないことだ。indexは各要素に対して、格納された順番に自動で番号が振られる。規則性が担保されているため、例えば配列の場合、indexを軸にしsort()で要素の並び替えができるが、Mapの場合はそういう手段はない。自由とは時に不自由なものなのだ！
HashMapとTreeMap
Javaの中で一般的なimplementation of MapがHashMapとTreeMapだ。両方ともMapインターフェイスを実装している。
| HashMap | TreeMap | |
|---|---|---|
| 格納方法の違い | 順不同 |
putされた順に格納されていく |
| 得意分野 |
TreeMapより少し早い。一般的に順番にこだわらない場合に使われる |
格納順にこだわる場合はTreeMap一択 |
HashMapの出番
2つのリストの比較
次のような文字列を格納する２つのリストがある。（長さは同じでなくてもよい）
List<String> strings = List.of("aba", "baba", "aba", "xzxb");
List<String> queries = List.of("aba", "xzxb", "ab");
stringsを順に調べ、queries内の各要素といくつ合致しているか分かる配列が欲しい。
上記の例で言えば、
-
abaは、strings内に2コ -
xzxbは、strings内に1コ -
abは、strings0内に0コ
となるから、求める配列は、
[2,1,0]
になる。
よくある例：for-loopを配列分回す
public static List<Integer> matchingStrings(List<String> strings, List<String> queries) {
// (1) queries内の全要素を調べ、その要素の数だけ(2)countStr()を呼び出し、
// その結果をsolに書き出す
List<Integer> sol = new ArrayList<>();
for (String s : queries)
sol.add(countStr(s, strings));
return sol;
}
// (2) strings内の全要素を調べ、sと合致した回数を返す
public static Integer countStr(String s, List<String> strings) {
int count = 0;
for(String x: strings)
if(s.equals(x))
count++;
return count;
}
public static void main(String[] args) {
List<String> strings = List.of("aba", "baba", "aba", "xzxb");
List<String> queries = List.of("aba", "xzxb", "ab");
System.out.println(matchingStrings(strings, queries));
}
HashMapを使った例
public static List<Integer> matchingStrings2(List<String> strings, List<String> queries) {
// (1) dicの作成
// dic = {key: queries内の各要素, value: strings内にそのkeyがいくつあるか}
Map<String, Integer> dic = new HashMap<>();
for(String str: strings){ // O(n)
int temp = dic.getOrDefault(str, 0);
dic.put(str, ++temp);
System.out.println("dic "+ dic);
}
// dic = {baba=1, aba=2, xzxb=1}
// (2) queriesの各要素をkeyとして、dicのvalueを取り出し、solに書き出す
List<Integer> sol = new ArrayList<>();
for (String s : queries) {
sol.add(dic.getOrDefault(s,0)); // O(m)
}
return sol;
}
public static void main(String[] args) {
List<String> strings = List.of("aba", "baba", "aba", "xzxb");
List<String> queries = List.of("aba", "xzxb", "ab");
System.out.println(matchingStrings2(strings, queries));
}
比較
quetiesの要素数をm、stringsの要素数をnとおき、この二つのアプローチの違いを調べてみるとHashMapを使ったものの方が、早い。Big O-notationで記してみると：
- よくある例は、O(m*n)
- HashMapを使った例は、O(m+n)
よくある例：for-loopを配列分回すの基本方針は、queries内の全要素を調べ、その要素の数だけcountStr()を呼び出し、その結果をsolに書き出すというものである。この中で、countStr()は呼び出される度に、stringsの全要素を調べることになる。つまり、O(m*n)。
一方HashMapを使った例では、
-
stringsを一周して、それぞれの文字列が何回出てきたかが分かるHashMapdicを作成する。 - その次に、その
dicとqueriesを比較して結果の配列に書き出す。
という二段階に分かれている。つまり、それぞれのループは独立しているので、O(m+n)
ということで、要素数が多くなれば多くなるほど、この二つのアプローチの処理効率の差は指数関数的に大きくなっていく。
Discussion