前回の続きです。
このシリーズ、ソースを見るのが面倒なのか、
難易度が高そうに見えるのか、いまひとつ利便性が見えないからか、非常にアクセス数が少ないです。
しかし、2次元のMapで集計処理をやろうなどという奇特な人が検索で引っ掛けてきた場合を思うと書かずにはいられません。
リハッシュ
ハッシュテーブルは内部の配列サイズに対して格納データが多くなると、同じインデックスに格納されるデータが増えます。
そうなると単方向リストを辿ることになりますから目的のデータへの到達にコストがかかるようになります。
そのため、用意した配列に対しある割合を超えるデータ数が格納された際に、内部の配列を大きくしてやり、
データを移してやる処理を行います。これをリハッシュ(rehash)といいます。なんだか蛇の脱皮のようですね。
Javaの標準APIの場合、HashMapを
デフォルトコンストラクタで
インスタンスを生成すると内部の配列サイズが16、負荷係数0.75で初期化されます。
これは、16の配列サイズに対し0.75を超えるデータが格納されたとき、つまり12個を超える場合にリハッシュされることを意味します。
リハッシュ処理は非常に重たい処理であるため、最初から格納するデータ数が分かっている場合は、
サイズを指定して初期化することが望ましいのです。
/**
* リハッシュ処理。
* 配列サイズを1.5倍に拡大
*/
private void rehash() {
int xSize = (int) (this.map.length * EXT_RATE + 1);
int ySize = (int) (this.map[0].length * EXT_RATE + 1);
TableEntry<KX, KY, V>[][] newMap = createTableEntryArray(xSize, ySize);
for (TableEntry[] entrys : this.map) {
for (TableEntry<KX, KY, V> entry : entrys) {
if (entry == null) {
continue;
}
this.putImpl(newMap, entry.getKeyX(), entry.getKeyY(), entry.getValue());
TableEntry<KX, KY, V> nextEntry = entry.getNext();
while (nextEntry != null) {
this.putImpl(newMap, nextEntry.getKeyX(),
nextEntry.getKeyY(), nextEntry.getValue());
nextEntry = nextEntry.getNext();
}
}
}
this.map = newMap;
}
このHashTableMapではリハッシュ処理で内部の配列を1.5倍に拡大します。1.5倍といっても縦横のサイズを1.5倍ずつにするので面積的には2.25ですね。
そして格納されているデータをループで回して格納位置を再設定しなおすというわけです。
いかがだったでしょうか。
「データ構造とアルゴリズム」と言われるようにデータ構造はアルゴリズムとともに車輪の両輪となるものです。
データ構造はアルゴリズムと比べると鑑みられることが少ないのが寂しいところですが、
基礎知識として興味を持ってもらいたいものです。
投稿日時 : 2007年9月27日 19:29