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

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

## 目次  
1. [OrderedDictionary とは？](#1-ordereddictionary-とは)
2. [OrderedDictionary と Dictionary の違い](#2-ordereddictionary-と-dictionary-の違い)  
3. [OrderedDictionary の使い所](#3-ordereddictionary-の使い所)  
4. [速度検証（OrderedDictionary vs Dictionary）](#4-速度検証ordereddictionary-vs-dictionary)  
5. [速度検証に対する考察（時間のある人向け） ](#5-速度検証に対する考察時間のある人向け)  
6. [まとめ](#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. 速度検証に対する考察（時間のある人向け）  

最初に用語解説を行い、その次に図解と考察を行なっていきます。
<details>
<summary>検証に使用したソースコード</summary>


```csharp
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; }
    }

}

```


</details>




## 用語解説（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])図解

![スクリーンショット 2025-01-15 22.05.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/07c22f5d-5cd7-a0a3-a835-bac9d8a56f8b.png)


## 検索：(OrderedDictionary[i])図解
![スクリーンショット 2025-01-15 22.05.27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/dba87bbe-9fe1-8fd9-5b83-f71c408591aa.png)

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

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

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

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

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

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

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



## 検索：(ContainsKey(Key))図解
![スクリーンショット 2025-01-15 22.05.44.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/5d0af82c-7edf-0bf9-3238-6c8128a2bd28.png)

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

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



## 追加：(Dictionary)図解
![スクリーンショット 2025-01-15 22.06.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/179f5176-ba6c-cc54-f382-e661a314425f.png)

## 追加：(OrderedDictionary)図解
![スクリーンショット 2025-01-15 22.06.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/f6e46aec-b33d-94c7-99d8-0d6ae242faa5.png)

## 追加処理についての考察  

### 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 を優先使用推奨。  

---