8.ハードウェア・メモリ・データ構造 - YukaKoshiba/MyknowledgeDocs GitHub Wiki
Hardware @Japanese Version
Create Date：2025/3/12
Last Update Date：2025/7/7
ストレージデバイス：
ハードディスク
SSD
ストレージデバイスの保存
スラック領域(slack space)
データ構造： 配列 連結リスト 単方向連結リスト 二重連結リスト スタック キュー 木 ハッシュ 辞書型 トライ
ハードディスクやSSDなどのストレージデバイスは、データを「セクタ」や「クラスタ」と呼ばれる固定サイズの単位で管理する
ファイルシステムは、ファイルをこれらのクラスタ単位で保存する< br>
ファイルサイズがクラスタサイズより小さい場合、残りのクラスタ領域は未使用のままになり、この未使用の領域がスラック領域となる
ハードウェア(主にハードディスクやSSDなどのストレージデバイス)におけるディスク上の無駄な領域のこと
スラック領域の管理は、セキュリティの観点でも非常に重要である
フォレンジック調査官は、以下のような理由から疑わしいデータの残骸がないかどうか、データ領域を調べることが多い
- 削除データの不正利用の可能性
ファイルを削除しても、実際にはファイルシステム上のデータ自体は完全に消去されず、スラック領域に断片的に残ることがある
特に機密情報や個人情報を含むファイルの場合、悪意のある第三者がこれらの残存データを復元し、不正利用する可能性がある
フォレンジック調査では、このような残存データを解析し、情報漏洩や不正アクセスの有無を調査する - 隠蔽データの存在
攻撃者がマルウェアや不正なファイルをスラック領域に隠蔽することがある
通常のファイルシステムからは検出されにくいスラック領域を利用することで、証拠隠滅を図りやすい
フォレンジック調査では、スラック領域を詳細に分析し、隠蔽された不正なデータを検出する - 過去の操作履歴の追跡
スラック領域には、過去に削除されたファイルや変更されたファイルの断片が残ることがある
これらの断片を解析することで、過去の操作履歴やファイルの変遷を追跡し、不正行為の証拠を収集することができる
フォレンジック調査では、この機能を利用して、不正アクセスの経路や情報漏洩の経緯を解明する
フォレンジック調査官は、専用のツールを使用してスラック領域をスキャンし、残存データや隠蔽されたデータを抽出する
抽出されたデータは、ファイルの種類や内容に基づいて解析され、機密情報や不正なデータの有無が確認される
必要に応じて、データの復元やタイムライン分析を行い、事件の全容解明に役立てられる
つまり、スラック領域は、犯罪者にとって証拠を隠滅したり、不正なデータを隠したりする場所として利用される可能性があるため、セキュリティ調査において重要な調査対象である
データとは、０と１の電気信号を指し、この０と１の電気信号はメモリICの中に保存されている
IC,LSI,GPU,CPU,DRAM,フラッシュメモリ,MPU,FPGA他を含む
ICの一種であるメモリICは、データを保存するための電子部品のこと
コンピュータ上で一時的にデータを保存できる共有メモリ領域のこと テキスト、画像、フォーマット済みテキストなど、様々な種類のデータを保存し、複数の異なるプログラムからアクセスできる
データを効率的に扱うための組み合わせ方のこと(＝データを扱いやすくするための仕組み)
本質的にはメモリ内の組織化の形式のこと
メモリ内でデータを整理する方法は多数ある
コンピュータサイエンスを学ぶときは、抽象データ型(概念的に想像できるデータ型)を使ったの概念的なデータ構造の理解から始めると理解しやすい
概念を理解することで、具体的なデータ構造の実装方法が理解しやすくなる
特に、情報量が増えた際には、データ構造によってデータの探索/追加/削除に関わる処理時間が大きく異なり、
システム全体のパフォーマンスに影響が出る為、理解しておくことが非常に重要
よく似た概念として、アルゴリズムがある
ソフトウェアを効率よく動かすための概念であることは共通しているが、効率化を考える対象範囲が異なる
・アルゴリズム：作業手順
・データ構造 ：データの取り扱い方法
例えば、カレーを作る際に、
どう作るかという作業工程がアルゴリズムであり、
食材をどう取り扱うか(他の料理の食材とどう一緒に冷蔵庫に保管するか,他の料理と一緒にどう食材をカットして効率よく料理するかなど)がデータ構造にあたる
特定の処理(アルゴリズム)を実行する際に、その処理に最適なデータ構造を選ぶことで、アルゴリズムの性能を最大限に引き出すことができる
データ構造とアルゴリズムは車の両輪のような関係
データ構造の処理時間も、アルゴリズムと同様にオーダ記法で処理時間を表す
(参考)アルゴリズム-オーダ記法
同じ型のデータを連続したメモリ領域に並べて格納する方法
インデックス(添え字)を使って、特定のデータに直接アクセスできる
インデックスを用いた検索は速いが、途中の要素の追加や削除にはコストがかかる場合がある
検索
インデックスアクセス：O(1)
線形探索：O(n)
追加
要素の末尾に追加：O(1)
要素の途中に追加：O(n)
→既存の配列の途中に要素を追加することはできない為、新しい配列を先に作ってから、それぞれコピーする必要がある
削除
要素の末尾に削除：O(1)
要素の途中に削除：O(n)
→要素を削除し、データをスライドさせる必要がある
データ要素(ノード)がポインタによって連結されたデータ構造
各ノードは、データと次のノードへの参照(ポインタ)を持つ
これにより、物理的に連続していなくてもデータを連結して管理できる
また、データの追加や削除が比較的容易える
一方で、特定のデータにアクセスするためには、先頭から順にたどっていく必要があるため、配列に比べて検索に時間がかかる場合がある
検索：O(n)
→先頭から順にポインタをたどっていく必要があるため、要素の数に比例して時間がかかる
挿入/削除(先頭/末尾)：O(1)
→先頭または末尾のポインタを付け替えるだけで良い為、一定時間で操作できる
挿入/削除(途中の要素)：O(n)
→その要素まで到達するのにO(n)要する
到達後はO(1)
単方向連結リストの限界
単方向連結リストは、リスト内の要素を一方向しかたどることができない
これにより、要素の削除時に、前の要素へのアクセスが困難になるという問題がある
そのため、両方向連携リストと比較すると、単方向連結リストの処理の効率は悪くなる
各ノードが次のノードへのポインタだけでなく、前のノードへのポインタも持つ連結リスト(＝前後に動ける)
これにより、リスト内を双方向に辿ることが可能で、要素の検索や削除の際のリスト連結の修正が容易になる
操作方法
二重連結リストの操作では、ポインタの操作が非常に重要になる
そのため、動的に割り当てられたメモリは、不要になったら必ず解放する必要がある
また、ポインタの指し示す順番を間違えてしまうと、リストのデータが消失してしまうなどの事故に繋がり、ポインタの順番が非常に重要
*連結リストを使用する際、単方向にするか二重連結にするかは、トレードオフである
単方向リスト ：メモリ使用量が少ない代わりに、削除など柔軟な操作が難しい
二重連結リスト：メモリ使用量が増加する代わりに、より柔軟な操作が可能
配列は、高速に検索できる連続したメモリを提供し、バイナリ検索を実行できる
一方で、リンクリストを利用すると、メモリのさまざまな領域にある値を含めることができ、必要に応じてリストを動的に拡大したり縮小することが可能になる
配列と連結リストという基本的なデータ構造を応用して、両者の長所を組み合わせたものが以下の通り：
データを整理された方法で保持する特別なデータ構造
スタックは、後入れ先出し(LIFO:Last In, First Out)の原則に従う
＝最後に追加されたデータが最初に削除される
実装方法：配列 or 連結リストを使用する
基本操作
・push：
・pop ：
スタックの用途
・関数呼び出し ：関数の呼び出し履歴をスタックに保持することで、関数から戻る際に正しい場所に戻ることができる
・逆ポーランド記法：数式の計算にスタックを使用できる
・ブラウザの履歴 ：ブラウザの「戻る」ボタンは、閲覧履歴をスタックに保持することで実現されている
挿入/削除：O(1)
→常にデータの端(先頭または末尾)での操作の為、一定時間で完了する
抽象データ構造の1つの形式
先入れ先出し(FIFO:First In, First Out)の原則に従うデータ構造
＝最初に追加されたデータが最初に削除される
実装方法：配列 or 連結リストを使用する
基本操作(2つ)
・enqueue(エンキュー)：キューの末尾に新しい要素を追加する操作
・dequeue(デキュー )：キューの先頭から最も古い要素を削除する操作
キューの用途
・タスク管理 ：コンピュータのタスク処理やプリンタの印刷ジョブの管理など
・メッセージキュー：複数のプロセス間でメッセージをやり取りするために使用される
・幅優先探索 ：グラフの探索アルゴリズムで使用される
挿入/削除：O(1)
→常にデータの端(先頭または末尾)での操作の為、一定時間で完了する
二分探索木は、データをより効率的に保存し、検索および取得ができるデータ構造
配列の中央の値を木の頂点と捉え、この値より小さい値は左側、大きい値は右側に配置する
この操作を繰り返し、配置したデータをポインタで繋ぐことで、各ノードを接続できるようになる
挿入/検索/削除
バランス木：平均: O(logn)
→バランスが取れていれば、探索範囲が半分ずつに絞られる為、対数時間で操作可能
バランスの崩れた木：O(n)
→バランスが崩れて一方後に偏っていると、連結リストのように1つずつ探索する必要がある
配列のランダムアクセス(特定の要素に直接アクセスできる)の速さと、連結リストの柔軟性(要素数の増減が容易)を両立させたデータ構造
データの挿入、削除、検索を高速に行うことができる
挿入/検索/削除
衝突なし：O(1)
衝突あり：O(n)
利点：
・平均的な挿入、削除、検索の時間がほぼ一定時間(定数時間)に近づく
・大規模なデータセットでも高速な処理が可能
欠点：
・データの順序やソートには向かない
・ハッシュ関数によっては、性能が大きく左右される
構成要素
・Hash Function(ハッシュ関数)：
データを入力として受け取り、非負の整数(ハッシュコード)を返す関数
同じデータからは常に同じハッシュコードが生成される(決定論的)
データをハッシュテーブル内の適切な位置に割り当てるために使用される
・Array(配列)
データを格納する場所
ハッシュ関数によって生成されたハッシュコードを配列のインデックスとして使用し、データを格納する
ハッシュテーブルの動作
1.データの挿入
データをハッシュ関数に入力し、ハッシュコードを生成する
生成されたハッシュコードを配列のインデックスとして使用し、データを格納する
2.データの検索
検索したいデータをハッシュ関数に入力し、ハッシュコードを生成する
生成されたハッシュコードを配列のインデックスとして使用し、データを検索する
衝突とは、異なるキー(データ)が同じハッシュコードを生成し、配列の同じ位置に格納しようとすること
衝突はソフトウェアの効率に大きく影響を与える
ハッシュテーブルにおける衝突を完全に回避することは一般的に不可能
しかし、衝突の発生確率を最小限に抑え、発生した場合の対処法を適切に実装することで、効率的なハッシュテーブルを実現できる
衝突低減のコツ
・適切なハッシュ関数を選択する
良いハッシュ関数は、キーの分布を均等に分散させ、衝突の確率を低減している関数を指す
一般的なハッシュ関数として、乗算ハッシュ、剰余ハッシュ、FNVハッシュなどがある
キーのデータ型や分布に応じて、最適なハッシュ関数を選択すること
※インターネット上に様々なハッシュ関数が公開されている
・ハッシュテーブルのサイズ調整
ハッシュテーブルのサイズは、格納するデータ数に対して適切に設定する必要がある
一般的に、ハッシュテーブルのサイズは、格納するデータ数の1.2〜2倍程度に設定すると、効率的なパフォーマンスが得られると言われる
ロードファクタ(格納されたデータ数/ハッシュテーブルのサイズ)を監視し、一定の閾値を超えた場合にハッシュテーブルをリサイズすることで、衝突の増加を抑制できる
サイズが小さすぎると衝突回数が増えるが、大きすぎてもメモリの無駄遣いになるため、適切なサイズを設定すること
衝突が発生した場合の対処法
衝突の低減に加え、衝突が発生した際の処理を実装することは非常に重要である
最悪の場合、システムがクラッシュする可能性がある
具体的な解消方法例：
・Chaining(チェイン法,連鎖法)：
各ハッシュテーブルのエントリに、連結リストなどのデータ構造を保持する
衝突が発生した場合、同じハッシュ値を持つキーを連結リストに追加する
連鎖法は、実装が比較的容易であり、衝突が多数発生する場合でも効率的なパフォーマンスを維持できる
・オープンアドレス法
衝突が発生時、ハッシュテーブル内の別の空いているエントリを探してデータを格納する
オープンアドレス法には、線形探索、二次探索、ダブルハッシュなどのバリエーションがある
オープンアドレス法は、メモリ効率が良いという利点があるが、
衝突が頻繁に発生するとパフォーマンスが低下する可能性がある
実装方法
ハッシュテーブルの実装には、配列と同様に静的および動的に実装方法することができる
単語と定義を持つ実際の書籍形式の辞書と同様に、key(キー)とvalue(値)を持つデータ構造
キーは一意である必要があり、重複は許されない
内部的にはハッシュテーブルなどのデータ構造が使用されており、平均的な検索時間はO(1)で、瞬時にデータへアクセスできる
配列をツリー型にしたデータ構造で、データの挿入、削除、検索を高速に行うことができる
キー(検索に使用するデータ)がユニーク(重複がない)な場合に特に有効
仕組み
配列、構造体、ポインタを組み合わせてデータを格納する
データを"道順"として使用し、データ構造内を移動する
道順を辿りきることができれば、データが存在することがわかる
道順を辿りきることができなければ、データが存在しないことがわかる
利点
・キーがユニークな為、ハッシュテーブルのように衝突を考慮する必要がない
・検索時間がキーの長さに比例するため、非常に高速
・文字列の検索に特に有効
欠点
・メモリ使用量が大きい