リストと配列・ハッシュ表

リストは、要素を一定の順序で並べて扱うデータ構造であり、配列で実現する方法とポインタで実現する方法がある。ハッシュ表は、キーをハッシュ関数に通して格納位置を求め、探索を速く行うための表である。両者は追加、削除、探索に要する手間が異なる点が中心に問われ、どの操作が一定時間で済み、どの操作で要素を順にたどる必要があるかを区別することが要点となる。

配列で実現するリストの特徴

配列で実現したリストは、要素を連続した領域に格納する。そのため、添字が分かれば任意の要素を一定時間で参照できる。一方で、リストに入る要素の最大数に対応した領域をあらかじめ確保する方式を取ると、実際の要素数が少ない場合に使われない領域が生じる。この領域の無駄は、配列で実現する場合の代表的な特徴である。

配列の途中に要素を挿入するには、後続の要素を移動して空きを作る必要があり、その手間は最悪で要素数に比例する。挿入位置が分かっていても移動の手間は残る。

ポインタで実現したリストは、各要素が次の要素へのポインタ領域を持つ。このため、要素の挿入や削除で後続の要素を移動する必要はないが、特定の位置をたどるには先頭から順に進む必要がある。両者は要素の並べ方を表す手段が異なるだけで、同じ論理的な順序を表せることを押さえておく。

ハッシュ関数と衝突の条件

ハッシュ関数 h(x)＝x mod n は、キーを n で割った余りを格納位置とする。二つのキー a と b が衝突するのは、余りが等しいときであり、これは a−b が n の倍数であることと同じである。a＋b が n の倍数であるという条件は、衝突の判定には使えない。たとえば n＝5 で a＝1、b＝4 とすると和は5の倍数になるが、余りは1と4で異なり衝突しない。

同じ条件は別の出題でも扱われており、衝突の判定は余りの一致で考えるのが基本となる。