【C#】OrderedDictionaryとは？.NET 9の新機能とそのパフォーマンスを比較

目次

1. OrderedDictionary とは？
2. OrderedDictionary と Dictionary の違い
3. OrderedDictionary の使い所
4. 速度検証（OrderedDictionary vs Dictionary）
5. 速度検証に対する考察（時間のある人向け）
6. まとめ

---

1. OrderedDictionary とは

OrderedDictionary は、キーと値のペアを管理し、要素の追加順序を保持する特性を持つコレクションです。これにより、格納した順序でデータを取り出すことが可能です。

補足:
順序リストとは内部で使用される List<KeyValuePair<TKey, TValue>> を指します（以下、順序リストと表記）。

特徴

• 順序保持: 要素を追加した順序を保持し、格納した順序でアクセス可能。
• キーの重複禁止: Dictionary と同様に、キーの重複は許されません。
• パフォーマンス: 順序リストの管理が加わるため、追加・削除時に Dictionary よりも処理コストが高くなることがあります。

---

2. OrderedDictionary と Dictionary の違い

項目	OrderedDictionary	Dictionary
順序保持	要素の追加順序を保持	順序は保証されない
要素のアクセス方法	キーまたは順序リストのインデックスでアクセス可能	キーのみでアクセス可能
パフォーマンス	順序リスト管理が加わるため処理コスト増加	高速なキー検索が可能
主な用途	追加順序を保持しつつキー検索が必要な場合	順序不要、高速検索が必要な場合

---

3. OrderedDictionary の使い所

• データの追加順序を保持したい場合
  例: ユーザー入力データやログ情報を順序通りに保存し処理したい場合。
• 順序を意識したデータ操作が必要な場合
  例: 時系列データやイベント履歴の処理。
• キー重複禁止かつ順序が必要な場合
  例: 設定情報や構成情報を順序付きで保持したい場合。

注意点:
データ量が多い場合は順序リスト管理のコストが増えるため、パフォーマンスに注意が必要です。

---

4. 速度検証（OrderedDictionary vs Dictionary）

検証環境

• CPU: 2.60GHz
• メモリ: 9.8GB
• OS: Windows 10 64bit（仮想環境）
• ストレージ: 100GB
• コア数: 4
• .NET ランタイム: Microsoft.WindowsDesktop.App 9.0.0

---

検索処理

• Dictionary[i]

  • 説明: 指定したキー i でハッシュ値を計算し、該当するデータを取得。
  • ポイント: 高速な検索が可能。ただし、衝突時の処理が必要。
  • 例: OrderedDictionary[5] → "Key:5, Value:"a""

• OrderedDictionary[i]

  • 説明: 順序リストのインデックス i でデータを取得。
  • ポイント: ハッシュ値ではなく、追加順に基づく位置情報を使用。
  • 例: OrderedDictionary[0] → "Key:5, Value:"a""

---

ContainsKey メソッド

• Dictionary.ContainsKey(Key)

  • 説明: 指定したキー Key でハッシュ値を計算し、存在確認を行う。
  • ポイント: 高速にキーの存在を確認できるが、衝突時は探索が必要。

• OrderedDictionary.ContainsKey(Key)

  • 説明: Dictionary と同様にハッシュ値を計算し、キーの存在確認を行う。
  • ポイント: 順序リストを使用せず、速度は Dictionary とほぼ同等。

---

追加処理

• Dictionary.Add(Key, Value)

  • 説明: 指定したキー Key を元にハッシュ値を計算し、データを追加。
  • ポイント: 初期容量が不足している場合、リサイズや再ハッシュ処理が発生し、処理時間が増加。
  • 備考: 初期容量を指定することでリサイズ回数を削減し、追加処理を効率化可能。

• OrderedDictionary.Add(Key, Value)

  • 説明: Dictionary.Add と同様にデータを追加後、順序リストにも追加。
  • ポイント: 初期容量未指定時のリサイズでは順序リストとハッシュテーブル双方に影響。

---

削除処理

• Dictionary.Remove(Key)

  • 説明: 指定したキー Key を基に該当データを削除。
  • ポイント: ハッシュテーブルから直接削除されるため高速。

• OrderedDictionary.Remove(Key)

  • 説明: 指定したキー Key を基に削除後、順序リストからも削除。
  • ポイント: 順序リスト管理の影響で削除時間が増加する場合がある。

• OrderedDictionary.Clear()

  • 説明: ハッシュテーブルと順序リストをクリアし、全データを削除。

---

• 検索の検証結果

処理名	処理時間(ms)	メモリ使用量(KB)
Dictionary[]	13	8.69
OrderedDictionary[]	19	8.67
Dictionary.ContainsKey()	15	8.88
OrderedDictionary.ContainsKey()	14	8.69

• 追加（初期容量指定有無）の検証結果

処理名	初期容量	処理時間(ms)	メモリ使用量(KB)
Dictionary	無	271	117.48
OrderedDictionary	無	320	117.55
Dictionary	有	264	45.79
OrderedDictionary	有	286	45.81

• 追加（キーが連番orランダム）の検証結果

処理名	初期容量	処理時間(ms)	メモリ使用量(KB)
Dictionary	連番	264	45.79
OrderedDictionary	連番	286	45.81
Dictionary	ランダム	387	45.78
OrderedDictionary	ランダム	398	45.78

• 削除の検証結果

処理名	初期容量	処理時間(ms)	メモリ使用量(KB)
Dictionary	Remove(i)	95	9.82
OrderedDictionary	Remove(i)	33	9.34
OrderedDictionary	論理削除（Valueのインスタンスの削除フラグを更新）	27	9.51
OrderedDictionary	Clear	6	9.09

5. 速度検証に対する考察（時間のある人向け）

最初に用語解説を行い、その次に図解と考察を行なっていきます。

検証に使用したソースコード

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Xml.Linq;

namespace CalculatorApp.Backend.Kensyou.HairetsuSokudo
{
    public class HairetsuSokudoHikaku
    {
        // 計測結果の保存用
        private Dictionary<string, List<(long loopCnt, long TimeMs, long MemoryBytes)>> results = new Dictionary<string, List<(long, long, long)>>()
        {
            { "Dictionary Search(Contains)", new List<(long, long, long)>() },
            { "Dictionary Search(Sequential)", new List<(long, long, long)>() },
            { "OrderedDictionary Search(Contains)", new List<(long, long, long)>() },
            { "OrderedDictionary Search(Sequential)", new List<(long, long, long)>() },
            { "Dictionary Add(SerialNum)", new List<(long, long, long)>() },// キーに連番を設定
            { "Dictionary Add(SerialNum)(initialCapacity)", new List<(long, long, long)>() },// キーに連番を設定, 初期容量を指定
            { "Dictionary Add(Random)", new List<(long, long, long)>() },// キーに重複しないランダムな値を設定
            { "Dictionary Add(Random)(initialCapacity)", new List<(long, long, long)>() },// キーに重複しないランダムな値を設定, 初期容量を指定
            { "OrderedDictionary Add(SerialNum)", new List<(long, long, long)>() },// キーに連番を設定
            { "OrderedDictionary Add(SerialNum)(initialCapacity)", new List<(long, long, long)>() },// キーに連番を設定, 初期容量を指定
            { "OrderedDictionary Add(Random)", new List<(long, long, long)>() },// キーに重複しないランダムな値を設定
            { "OrderedDictionary Add(Random)(initialCapacity)", new List<(long, long, long)>() },// キーに重複しないランダムな値を設定, 初期容量を指定
            { "Dictionary Remove", new List<(long, long, long)>() },
            { "OrderedDictionary Remove(PhysicalDeletion)", new List<(long, long, long)>() },// 物理削除
            { "OrderedDictionary Remove(LogicalDeletion)", new List<(long, long, long)>() },// 論理削除
            { "OrderedDictionary Clear", new List<(long, long, long)>() },
        };

        private int loopCnt = 0;
 
        // OrderedDictionary[i]の順序リストの速度検証用
        private Dictionary<string, List<MeasurementResult>> dicOrderedDictionaryAccessList
            = new Dictionary<string, List<MeasurementResult>>()
            {
                {"OrderedDictionary" ,  new List<MeasurementResult>()}
                , {"Dictionary" ,new List<MeasurementResult>()}
            };

        /// <summary>
        /// 速度検証開始
        /// </summary>
        /// <param name="addCount">検証データ量（初期値は10万件）</param>
        /// <param name="numberOfRuns">検証回数（初期値は60回）</param>
        public void KensyouStart(int addCount = 100000, int numberOfRuns = 60)
        {
            try
            {
                System.Diagnostics.Debug.WriteLine("=== 辞書、OrderedDictionaryの速度検証 ===");

                // 重複しないキーの生成
                HashSet<int> uniqueKeys = new HashSet<int>();
                for (int i = 0; i < addCount; i++)
                {
                    uniqueKeys.Add(i);
                }
                int[] keysArray = uniqueKeys.ToArray();  // 配列に変換

                // ランダムキーの生成
                Random random = new Random();
                HashSet<int> uniqueRandomKeys = new HashSet<int>();
                while (uniqueRandomKeys.Count < addCount)
                {
                    uniqueRandomKeys.Add(random.Next());
                }
                int[] keysRandomArray = uniqueRandomKeys.ToArray();  // 配列に変換


                for (loopCnt = 0; loopCnt < numberOfRuns; loopCnt++)
                {
                    // 検索
                    SearchComparison(addCount, keysArray);
                    // 追加
                    AddComparison(addCount, keysArray, keysRandomArray);
                    // 削除
                    RemoveComparison(addCount, keysArray);

                }

                // OrderedDictionary[i]の内部的な線形探索の処理時間を検証（うまくいかなかった）
                //MeasureOrderedDictionaryAccessProc();

                // 結果出力
                PrintResults();
            }
            catch (Exception ex)
            {
                LogError(ex, nameof(KensyouStart));
                throw;
            }
           
        }


        /// <summary>
        /// 検索処理検証
        /// </summary>
        /// <param name="addCount"></param>
        /// <param name="keysArray"></param>
        private void SearchComparison(int addCount, int[] keysArray)
        {
            try
            {
                int searchCount = keysArray.Length;  // 10万回検索を行う

                // 検索に使用するデータ
                var orderedDictionary = new OrderedDictionary<int, int>();
                foreach (int key in keysArray)
                {
                    orderedDictionary.Add(key, key);
                }

                // 辞書(Contains)
                Dictionary<int, int> dictionary = keysArray.ToDictionary(x => x, x => x);
                MeasureTimeAndMemory("Dictionary Search(Contains)", () =>
                {
                    for (int i = 0; i < searchCount; i++)
                    {
                        bool found = dictionary.ContainsKey(i);
                    }
                });

                // 辞書(Sequential)
                MeasureTimeAndMemory("Dictionary Search(Sequential)", () =>
                {
                    for (int i = 0; i < searchCount; i++)
                    {
                        var item = dictionary[i];
                    }
                });

                // OrderedDictionary(Contains)
                MeasureTimeAndMemory("OrderedDictionary Search(Contains)", () =>
                {
                    for (int i = 0; i < searchCount; i++)
                    {
                        bool found = orderedDictionary.ContainsKey(i);
                    }
                });

                // OrderedDictionary(Sequential)
                MeasureTimeAndMemory("OrderedDictionary Search(Sequential)", () =>
                {
                    for (int i = 0; i < searchCount; i++)  // 順番通りに検索
                    {
                        var item = orderedDictionary[i];
                    }
                });
            }
            catch (Exception ex)
            {
                LogError(ex, nameof(SearchComparison));
                throw;
            }
            
        }


        /// <summary>
        /// 追加処理検証
        /// </summary>
        /// <param name="addCount"></param>
        /// <param name="keysArray"></param>
        private void AddComparison(int addCount, int[] keysArray, int[] keysRandomArray)
        {
            try
            {
                // 辞書(SerialNum)
                Dictionary<int, string> dictionary = new Dictionary<int, string>();
                MeasureTimeAndMemory("Dictionary Add(SerialNum)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        dictionary.Add(i, $"Value_{i}");
                    }
                });

                // 辞書(SerialNum)(initialCapacity) 初期容量を指定
                Dictionary<int, string> dictionaryInitialCapacity = new Dictionary<int, string>(addCount);
                MeasureTimeAndMemory("Dictionary Add(SerialNum)(initialCapacity)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        dictionaryInitialCapacity.Add(i, $"Value_{i}");
                    }
                });

                // 辞書(Random)
                Dictionary<int, string> dictionaryRandom = new Dictionary<int, string>();
                MeasureTimeAndMemory("Dictionary Add(Random)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        dictionaryRandom.Add(keysRandomArray[i], $"Value_{i}");
                    }
                });

                // 辞書(Random)(initialCapacity) 初期容量を指定
                Dictionary<int, string> dictionaryRandomInitialCapacity = new Dictionary<int, string>(addCount);
                MeasureTimeAndMemory("Dictionary Add(Random)(initialCapacity)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        dictionaryRandomInitialCapacity.Add(keysRandomArray[i], $"Value_{i}");
                    }
                });

                // OrderedDictionary(SerialNum)
                var orderedDictionarySequential = new OrderedDictionary<int, string>();
                MeasureTimeAndMemory("OrderedDictionary Add(SerialNum)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        orderedDictionarySequential.Add(i, $"Value_{i}");
                    }
                });

                // OrderedDictionary(SerialNum)(initialCapacity) 初期容量を指定
                var orderedDictionaryInitialCapacity = new OrderedDictionary<int, string>(addCount);
                MeasureTimeAndMemory("OrderedDictionary Add(SerialNum)(initialCapacity)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        orderedDictionaryInitialCapacity.Add(keysArray[i], $"Value_{keysArray[i]}");
                    }
                });

                // OrderedDictionary(Random)
                var orderedDictionaryRandom = new OrderedDictionary<int, string>();
                MeasureTimeAndMemory("OrderedDictionary Add(Random)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        orderedDictionaryRandom.Add(keysRandomArray[i], $"Value_{i}");
                    }
                });

                // OrderedDictionary(Random)(initialCapacity) 初期容量を指定
                var orderedDictionaryRandomInitialCapacity = new OrderedDictionary<int, string>(addCount);
                MeasureTimeAndMemory("OrderedDictionary Add(Random)(initialCapacity)", () =>
                {
                    for (int i = 0; i < addCount; i++)
                    {
                        orderedDictionaryRandomInitialCapacity.Add(keysRandomArray[i], $"Value_{i}");
                    }
                });
            }
            catch (Exception ex)
            {
                LogError(ex, nameof(AddComparison));
                throw;
            }
        }

        /// <summary>
        /// 削除処理検証
        /// </summary>
        /// <param name="addCount"></param>
        /// <param name="keysArray"></param>
        private void RemoveComparison(int addCount, int[] keysArray)
        {
            try
            {
                int removeCount = keysArray.Length;
                Random random = new Random();

                // 辞書
                Dictionary<int, int> dictionary = keysArray.Take(removeCount).ToDictionary(x => x, x => x);
                MeasureTimeAndMemory("Dictionary Remove", () =>
                {
                    for (int i = 0; i < removeCount; i++)
                    {
                        int valueToSearch = random.Next(0, removeCount - i);
                        dictionary.Remove(valueToSearch);
                    }
                });

                // OrderedDictionary(PhysicalDeletion)物理削除
                var orderedDictionaryPhysicalDeletion = new OrderedDictionary<int, string>();
                foreach (int key in keysArray.Take(removeCount))
                {
                    orderedDictionaryPhysicalDeletion.Add(key, $"Value_{key}");
                }
                MeasureTimeAndMemory("OrderedDictionary Remove(PhysicalDeletion)", () =>
                {
                    for (int i = 0; i < removeCount; i++)
                    {
                        orderedDictionaryPhysicalDeletion.Remove(0);
                    }
                });

                // OrderedDictionary(LogicalDeletion)論理削除
                var orderedDictionaryLogicalDeletion = new OrderedDictionary<int, ItemStatus>();
                foreach (int key in keysArray)
                {
                    orderedDictionaryLogicalDeletion.Add(key, new ItemStatus { Value = $"Value_{key}", IsDeleted = false });
                }
                MeasureTimeAndMemory("OrderedDictionary Remove(LogicalDeletion)", () =>
                {
                    for (int i = 0; i < removeCount; i++)
                    {
                        orderedDictionaryLogicalDeletion[i].IsDeleted = true;  // フラグを直接変更
                    }
                });

                // OrderedDictionary(Clear)
                var orderedDictionaryClear = new OrderedDictionary<int, string>();
                foreach (int key in keysArray.Take(removeCount))
                {
                    orderedDictionaryClear.Add(key, $"Value_{key}");
                }
                MeasureTimeAndMemory("OrderedDictionary Clear", () =>
                {
                    orderedDictionaryClear.Clear();
                });
            }
            catch (Exception ex)
            {
                LogError(ex, nameof(RemoveComparison));
                throw;
            }
            
        }

        /// <summary>
        /// OrderedDictionary[i]の内部的な線形探索の処理時間を検証（うまくいかなかった）
        /// </summary>
        /// <param name="addCount"></param>
        private void MeasureOrderedDictionaryAccessProc(int addCount = 10000000)
        {
            try
            {
                // 事前準備: 重複しないキーを事前生成し、配列に変換
                HashSet<int> uniqueKeys = new HashSet<int>();
                for (int i = 0; i < addCount; i++)
                {
                    uniqueKeys.Add(i);
                }
                int[] keysArray = uniqueKeys.ToArray();  // 配列に変換


                // 検索に使用するデータ
                var orderedDictionary = new OrderedDictionary<int, int>();
                foreach (int key in keysArray)
                {
                    orderedDictionary.Add(key, key);
                }

                int step = 10000;  // 計測間隔
                var results = new List<MeasurementResult>();

                for (int i = 0; i < addCount; i += step)
                {
                    var stopwatch = new Stopwatch();
                    stopwatch.Start();

                    // 1回の計測で10000回繰り返しアクセス
                    for (int j = 0; j < step; j++)
                    {
                        var value = orderedDictionary[i + j];
                    }

                    stopwatch.Stop();
                    double totalElapsedTimeMs = stopwatch.Elapsed.TotalMilliseconds;  // 合計時間
                    double averageTimePerAccess = totalElapsedTimeMs / step;  // 1回あたりの平均時間

                    results.Add(new MeasurementResult() { Count = i.ToString(), AverageTimeMs = averageTimePerAccess.ToString("F10") });
                }


                dicOrderedDictionaryAccessList["OrderedDictionary"]
                    .AddRange(results);
            }
            catch (Exception ex)
            {
                LogError(ex, nameof(MeasureOrderedDictionaryAccessProc));
                throw;
            }
        }

        /// <summary>
        /// 処理の開始、および速度測定とメモリ使用量測定
        /// </summary>
        /// <param name="operationName"></param>
        /// <param name="action"></param>
        private void MeasureTimeAndMemory(string operationName, Action action)
        {
            try
            {
                var stopwatch = new Stopwatch();
                long beforeMemory = GC.GetTotalMemory(true);  // 実行前のメモリ使用量を取得

                stopwatch.Start();
                action();
                stopwatch.Stop();

                long afterMemory = GC.GetTotalMemory(false);  // 実行後のメモリ使用量を取得
                var result = ((long)loopCnt, stopwatch.ElapsedMilliseconds, afterMemory - beforeMemory);
                results[operationName].Add(result);
            }
            catch (Exception ex)
            {
                LogError(ex, nameof(MeasureTimeAndMemory));
                throw;
            }
        }

        /// <summary>
        /// 測定結果出力
        /// </summary>
        private void PrintResults()
        {
            try
            {

                System.Diagnostics.Debug.WriteLine($"各配列やコレクションの平均(初回処理は集計から除外)");
                System.Diagnostics.Debug.WriteLine($"名前\t平均時間 ms\t平均メモリ使用量 KB");
                foreach (var entry in results)
                {
                    if (entry.Value.Count > 1)
                    {
                        entry.Value.RemoveAt(0);// 初回は除外
                    }
                    string name = entry.Key;
                    var times = entry.Value.Select(x => x.TimeMs).ToArray();
                    var memories = entry.Value.Select(x => x.MemoryBytes).ToArray();

                    long avgTime = (long)times.Average();
                    double avgMemory = memories.Average(); 

                    System.Diagnostics.Debug.WriteLine($"{name}\t{avgTime} ms\t\t{avgMemory:F1} BYTE");

                }

                //  OrderedDictionary[i]の内部的な線形探索の処理時間検証結果出力
                foreach (var entry in dicOrderedDictionaryAccessList)
                {
                    string fileName = $"{entry.Key}_{DateTime.Now:yyyyMMdd_HHmmss}.csv";
                    string downloadsFolder = Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.UserProfile), "Downloads");
                    string fullPath = Path.Combine(downloadsFolder, fileName);
                    if (!Directory.Exists(downloadsFolder))
                    {
                        Directory.CreateDirectory(downloadsFolder);
                    }

                    using (var writer = new StreamWriter(fullPath))
                    {
                        writer.WriteLine("Count,AverageTime(ms)");
                        foreach (var item in entry.Value)
                        {
                            writer.WriteLine($"{item.Count},{item.AverageTimeMs:F4}");
                        }

                    }

                }
            }
            catch (Exception ex)
            {
                LogError(ex, nameof(PrintResults));
                throw;
            }
        }
        /// <summary>
        /// エラーログ出力メソッド
        /// </summary>
        /// <param name="ex"></param>
        /// <param name="methodName"></param>
        private void LogError(Exception ex, string methodName)
        {
            System.Diagnostics.Debug.WriteLine($"[Error in {methodName}] {ex.Message}");
        }

    }

    /// <summary>
    /// 論理削除フラグを持つクラス
    /// </summary>
    public class ItemStatus
    {
        public string Value { get; set; }  // 値
        public bool IsDeleted { get; set; }  // 論理削除フラグ
    }

    /// <summary>
    /// シーケンシャルアクセス検証用
    /// </summary>
    public class MeasurementResult
    {
        public string Count { get; set; }
        public string AverageTimeMs { get; set; }
    }

}

用語解説（HashTable 関連）

1. ハッシュテーブル (Hash Table)

説明:
ハッシュ値をインデックスとしてデータを格納・管理するデータ構造です。
ポイント:

• 直接インデックスでアクセスできるため、高速な検索が可能です。

2. インデックス (Index)

説明:
ハッシュテーブル内のデータ位置を示す番号です。
ポイント:

• ハッシュ値 % テーブルサイズ で計算され、実際のデータ格納位置を決定します。

3. テーブルサイズ (Table Size)

説明:
ハッシュテーブルの容量を示す数値です。
ポイント:

• データ量に応じて拡張されるため、初期容量を適切に設定すると、パフォーマンスの最適化が可能です。

4. リサイズ (Resize)

説明:
ハッシュテーブルの容量が足りない場合、容量を拡張する処理です。
ポイント:

• 通常は容量を2倍に拡張します。
• この際、内部データが再配置されるため、処理負荷が一時的に増加します。

---

用語解説（ハッシュ関数 関連）

1. ハッシュ関数 (Hash Function)

説明:
入力データ（キー）を固定長の数値（ハッシュ値）に変換する関数です。
ポイント:

• 同じ入力なら同じハッシュ値を生成しますが、異なる入力でも同じハッシュ値を生成すること（衝突）が発生する場合があります。

2. ハッシュ計算 (Hash Calculation)

説明:
ハッシュ関数を使用してキーからハッシュ値を算出する処理です。
ポイント:

• ハッシュ計算自体は非常に高速です。
• ただし、衝突が多発すると後処理のオーバーヘッドが発生します。

3. ハッシュ値 (Hash Value)

説明:
ハッシュ関数によって計算された値です。
ポイント:

• この値を使ってハッシュテーブル内の格納位置を決定します。

---

用語解説（順序リスト 関連）

1. 順序リスト (Ordered List)

説明:
追加された順序を保持するリストです。
ポイント:

• OrderedDictionary はこのリストを用いてデータの順序を管理しています。
• データの順序を保持する場合に有効です。

2. 初期容量 (Initial Capacity)

説明:
ハッシュテーブルや順序リストの初期サイズを示す設定値です。
ポイント:

• 初期容量を大きめに設定すると、データ追加時のリサイズ回数が減り、処理速度が向上します。
• 初期容量が小さい場合はデータ追加ごとにリサイズが発生し、パフォーマンス低下の要因となります。

3. エントリ追加時の処理

• 順序リストに追加順に要素が記録され、参照のための順序が保存されます。
• 同時に、キーを元にハッシュ値を生成し、ハッシュテーブルにもデータが格納されます。

4. データ取得時の処理

• 順序リストから対象の位置を探索し、対応するハッシュテーブルのインデックスを参照して該当データを取得します。

用語解説（その他）

1. 衝突 (Collision)

説明:
異なるキーが同じハッシュ値を持つ現象です。
詳細:

• 衝突は要素の追加時に発生します。
• 衝突が発生すると、同じバケット内に複数の要素が格納され、リンクリストや配列が構築されます（チェイニング法）。
  ポイント:
• 同じインデックスに複数のデータが存在する状態です。
• 衝突が発生すると衝突解決法が必要になります。

2. 衝突解決法 (Collision Resolution)

説明:
衝突を回避・解決するための方法です。
ポイント:

• 「オープンアドレス法」: 別の場所に再配置する方法。
• 「チェイン法」: リストや配列で格納する方法。

---

検索：(Dictionary[i])図解

検索：(OrderedDictionary[i])図解

OrderedDictionary[i] vs Dictionary[i] で OrderedDictionary が遅い理由の考察

OrderedDictionary の処理フロー
OrderedDictionary は内部で「順序リスト」を保持しており、要素検索時に以下の流れで処理が行われます：

1. 順序リストを線形探索
   順序リストを順番に確認し、目的の要素が格納されているインデックスを見つけます。
2. ハッシュテーブルを参照
   見つけたインデックスを使用し、対応するハッシュテーブルの要素を取得します。

ポイント

• 順序リスト内の線形探索がボトルネックとなるため、要素数が増えるほど処理時間が増加します。

Dictionary の処理フロー
Dictionary は以下の流れで処理を行います：

1. ハッシュテーブルの検索
   指定されたキーを基にハッシュ値を生成し、該当インデックスを使用してハッシュテーブル内のデータを取得します。

ポイント

• ハッシュ値を使用した検索のため、要素数に関係なく定数時間で検索が可能です。

検索：(ContainsKey(Key))図解

ContainsKey(Key) で処理時間に差異がほとんどない理由の考察

• 双方とも同じ処理フローで検索を行っているため。
• OrderedDictionary の ContainsKey(Key) は存在チェックのため、順序リストを参照せず、ハッシュテーブルのみを使用します。
• ContainsKey(Key) はキーの存在を確認する処理であり、順序リストのアクセスが不要なため、Dictionary と OrderedDictionary の処理時間に大きな差は生じません。

追加：(Dictionary)図解

追加：(OrderedDictionary)図解

追加処理についての考察

1. なぜ OrderedDictionary の方が遅いのか？

• ハッシュテーブルに追加する処理は Dictionary と同じですが、順序リストにも追加するため、リスト管理のオーバーヘッドが発生します。
• 追加ごとに順序リストのサイズが拡張される場合、再確保やデータ移動が発生し、処理が遅くなります。

補足
List<KeyValuePair<TKey, TValue>> などのリスト型コレクションは、内部容量を超えるとリスト全体を再確保し、データをコピーする処理が発生するため、追加処理が重くなります。

2. 初期容量指定なしだと遅い理由

• 初期容量が不足すると、データ追加の過程でハッシュテーブルや順序リストが自動的にリサイズされます。
• リサイズ処理では、内部データの再配置やコピーが必要なため、処理時間が増加します。

ポイント
初期容量を適切に指定することで、リサイズ回数を減らし、追加処理の効率化が図れます。

3. Key がランダムな場合の遅さの理由

• ランダムなキーでは、ハッシュ衝突が発生しやすくなり、同じバケット内に複数のデータが格納されます。
• 衝突が発生すると、バケット内のリストや配列を線形探索するため、処理時間が増加します。

補足
ランダムなキー追加時はバケット内の探索回数が増加するため、パフォーマンスに影響を与えます。連番のキーでは衝突が起こりにくいため、処理が高速化します。

削除処理についての考察

1. Clear() メソッドについて

• Dictionary と OrderedDictionary の Clear() メソッドは、全要素を一括削除するため、処理時間は高速です。
• 実際の検証結果でも、Clear() の処理時間は非常に短く、一括で全要素を初期化できていることが確認されています。

補足
Clear() メソッドは内部のハッシュテーブルや順序リストをリセットするため、ループを使った個別削除より効率的です。

2. 個別削除 (Remove(Key)) について

• Dictionary

  • ハッシュ値を基に対応するバケットを特定して削除するため、高速に削除できます。

• OrderedDictionary

  • ハッシュテーブルの管理に加え、順序リスト内の該当要素も削除する必要があるため、削除処理に追加コストが発生します。

ポイント

• 論理削除を行う場合は、該当する要素の削除フラグを更新するだけで済むため、物理削除よりも処理が高速です。
• 物理削除は、順序リストから要素を削除しデータを再配置するため時間がかかることがあります。

6. まとめ

OrderedDictionary の特徴

• 順序を保持しつつキーと値のペアを効率的に管理。
• 順序を意識したデータ操作に最適。

Dictionary との違い

• 順序保持: OrderedDictionary は順序保持、Dictionary は順序保証なし。
• パフォーマンス: OrderedDictionary は順序リスト管理があるため、追加・削除時の処理コストが増加。

検証結果のポイント

• 初期容量を設定することでパフォーマンス最適化が可能。
• ランダムなキーの追加は衝突を引き起こしやすく、処理時間が増加。
• 大量データを扱う場合は Dictionary を優先使用推奨。

---