実装方法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/08/22 14:07 UTC 版)
連鎖法の一つの実装例を示す。まず、ルート配列と呼ばれる要素数 N の配列を一つ用意する。ルート配列の各要素は、リスト(便宜上エントリリストと呼ぶ)とする。エントリリストには、少数のエントリを格納する。 エントリを格納する場合、エントリのキーをもとにハッシュ関数を用いてハッシュ値を生成する。ハッシュ関数は 0 から N - 1 までの整数値を生成するものであって、一様な分布と高速な計算が要求される。ハッシュ値を i とするとき、ルート配列上の i 番目のエントリリストにこのエントリを格納する。衝突が発生したとき、それらのエントリは同一のエントリリストに格納される。 あるキーをもつエントリを検索する場合、そのキーからハッシュ値を生成する。ハッシュ値を j とするとき、ルート配列上の j 番目のエントリリストに入っているエントリを一つずつ検索し、キーが一致しているものを取り出す。ルート配列上のエントリリストが高速でアクセスできる必要がある。
※この「実装方法」の解説は、「ハッシュテーブル」の解説の一部です。
「実装方法」を含む「ハッシュテーブル」の記事については、「ハッシュテーブル」の概要を参照ください。
実装方法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/14 05:46 UTC 版)
「木構造 (データ構造)」の記事における「実装方法」の解説
コンピュータで利用する場合にはいくつかの実装方法がある。典型的な実装としては、動的メモリ確保でノードを表す構造体の領域を確保し、ポインタで親ノードや子ノードを参照できるようにする。 各ノードが子ノードへのポインタのリストを持つ 各ノードが親ノードへのポインタを持つ 各ノードが親ノードへのポインタと子ノードへのポインタのリストを持つ 各ノードが長男ノードへのポインタと弟ノードへのポインタを持つ 他にも、配列を使った実装(ポインタではなく、インデックスによって親子関係が決定される)などがある(例えば、二分ヒープ)。
※この「実装方法」の解説は、「木構造 (データ構造)」の解説の一部です。
「実装方法」を含む「木構造 (データ構造)」の記事については、「木構造 (データ構造)」の概要を参照ください。
- 実装方法のページへのリンク