Tbpgr Blog

Ruby プログラマ tbpgr(てぃーびー) のブログ

書籍 パーフェクトJava | マップ HashMapとLinkedMapとTreeMap

パンくず

書籍 パーフェクトJava
マップ

概要

Javaのマップについて

JavaのMap

キーと値のペアを扱う場合、JavaではMapを使用します。
キーが無ければ新規作成。
キーがあれば値を上書きます。

Mapのインターフェース

項目名 処理内容
containsKey キーの存在チェック
containValue 値の存在チェック
entrySet 要素全体の取得
get キーから値を取得
keySet キーの集合を取得
put 要素を追加
remove 要素の削除
size 素数の取得
values 値の集合を取得

HashMapについて

内部で配列を確保。
キーのハッシュ値が配列のインデックスとなる。
ハッシュ値が衝突(コンフリクト)した場合はリンク構造になる。
衝突が多いと、内部でハッシュ表を拡張するが、その処理は低速です。
ハッシュ表はデフォルトで16なので、これ以上必要な場合は初期化時に拡張すること。

・LinkedMap
順序を保証したい場合
ハッシュ表とリンクリストの両方を保持する

・TreeMap
ソートに対応したい場合
木構造のため、検索時はバイナリサーチのパフォーマンス。

・NavigableMap
指定されたターゲットにもっとも近い要素を返すナビゲーションメソッドで拡張された SortedMap です

項目名 処理内容
ceilingKey(K key) 指定されたキーと等しいかそれよりも大きいキーのなかで最小のものを返します。
ceilingEntry(K key) 指定されたキーと等しいかそれよりも大きいキーのなかで最小のものに関連付けられた、キーと値のマッピングを返します。
floorKey(K key) 指定されたキーと等しいかそれよりも小さいキーのなかで最大のものを返します。
higherKey(K key) 指定されたキーよりも確実に大きいキーのなかで最小のものを返します。
lowerKey(K key) 指定されたキーよりも確実に小さいキーのなかで最大のものを返します。

サンプルコード

package perfect.map;

import java.util.NavigableMap;
import java.util.TreeMap;

public class NavigableMapSample {
  public static void main(String[] args) {
    NavigableMap<Integer, String> navi = new TreeMap<Integer, String>();
    navi.put(1, "いち");
    navi.put(5, "ご");
    navi.put(10, "じゅう");

    // ceilingは以上
    System.out.println(navi.ceilingKey(1));
    System.out.println(navi.ceilingKey(2));
    // higherはより大きい
    System.out.println(navi.higherKey(1));
    // floorは以下
    System.out.println(navi.floorKey(10));
    // lowerは未満
    System.out.println(navi.lowerKey(10));
  }
}

出力

1
5
5
10
5