実装方法

ウィキペディア小見出し辞書

実装方法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/22 14:07 UTC 版)

「ハッシュテーブル」の記事における「実装方法」の解説

連鎖法の一つの実装例を示す。まず、ルート配列と呼ばれる要素数 N の配列を一つ用意する。ルート配列の各要素は、リスト（便宜上エントリリストと呼ぶ）とする。エントリリストには、少数のエントリを格納する。 エントリを格納する場合、エントリのキーをもとにハッシュ関数を用いてハッシュ値を生成する。ハッシュ関数は 0 から N - 1 までの整数値を生成するものであって、一様な分布と高速な計算が要求される。ハッシュ値を i とするとき、ルート配列上の i 番目のエントリリストにこのエントリを格納する。衝突が発生したとき、それらのエントリは同一のエントリリストに格納される。 あるキーをもつエントリを検索する場合、そのキーからハッシュ値を生成する。ハッシュ値を j とするとき、ルート配列上の j 番目のエントリリストに入っているエントリを一つずつ検索し、キーが一致しているものを取り出す。ルート配列上のエントリリストが高速でアクセスできる必要がある。

実装方法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/14 05:46 UTC 版)

「木構造 (データ構造)」の記事における「実装方法」の解説

コンピュータで利用する場合にはいくつかの実装方法がある。典型的な実装としては、動的メモリ確保でノードを表す構造体の領域を確保し、ポインタで親ノードや子ノードを参照できるようにする。 各ノードが子ノードへのポインタのリストを持つ 各ノードが親ノードへのポインタを持つ 各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ 各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ 他にも、配列を使った実装（ポインタではなく、インデックスによって親子関係が決定される）などがある（例えば、二分ヒープ）。