将字典序列化到磁盘

Question

我们有一个哈希表(特别是C#Dictionary类)，它包含数千/数百万个(Key，Value)对，用于接近O(1)的搜索命中/未命中。

我们希望能够将此数据结构刷新到磁盘(对其进行序列化)，然后再次加载(反序列化)，以便保留Dictionary的内部哈希表。

我们现在所做的：

1. 从磁盘加载=>List<KVEntity>。(KVEntity是可序列化的。我们使用Avro进行序列化-如果需要，可以删除Avro)
2. 从array=>字典中读取每个KVEntity。此重新生成字典/哈希表内部状态
3. <系统运行，字典可以增长/收缩/值更改等>
4. 保存时，从字典中读取到数组中(通过myKVDict.Values.SelectMany(x => x)读取到新的List<KVEntity>)
5. 我们将数组(List<KVEntity>)串行化到磁盘以保存原始数据

请注意，在保存/恢复过程中，我们会丢失内部的tashtable/didictionary状态，每次都必须重新构建它。

我们希望直接序列化到Dictionary/从Dictionary(包括它的内部"活动"状态)，而不是仅为磁盘i/o使用中间数组。我们该怎么做

一些伪代码：

// The actual "node" that has information. Both myKey and myValue have actual data work storing
public class KVEntity
{
public string myKey {get;set;}
public DataClass myValue {get;set;}
}
// unit of disk IO/serialization
public List<KVEntity> myKVList {get;set;} 
// unit of run time processing. The string key is KVEntity.myKey
public Dictionary<string,KVEntity> myKVDict {get;set;} 

Answer 1

存储Dictionary实例的内部状态将是一种糟糕的做法-OOP的一个关键原则是封装：故意向消费者隐藏内部实现细节。

此外，Dictionary使用的映射算法可能会在不同版本的.NET Framework中发生变化，特别是考虑到CIL程序集被设计为前向兼容(即，针对.NET 2.0编写的程序通常适用于.NET 4.5)

最后，串行化字典的内部状态并没有带来真正的性能提升。使用一个定义良好的文件格式，重点关注可维护性，比使用速度要好得多。此外，如果字典包含"数千"个条目，那么据我估计，它应该在15毫秒内从磁盘加载(假设你有一个高效的磁盘格式)。最后，为RAM优化的数据结构在顺序读/写更好的磁盘上不一定能很好地工作。

你的帖子非常坚持使用字典的内部状态，但你现有的方法似乎很好(阿尔比特，它可以进行一些优化)。如果您透露了更多细节，我们可以帮助您加快进度。

优化

我在现有实现中看到的主要问题是到数组和列表的转换，这是不必要的，因为Dictionary是可直接枚举的。

我会这样做：

Dictionary<String,TFoo> dict = ... // where TFoo : new() && implements a arbitrary Serialize(BinaryWriter) and Deserialize(BinaryReader) methods
using(FileStream fs = File.OpenWrite("filename.dat"))
using(BinaryWriter wtr = new BinaryWriter(fs, Encoding.UTF8)) {
wtr.Write( dict.Count );
foreach(String key in dict.Keys) {
wtr.Write( key );
wtr.Write('');
dict[key].Serialize( wtr );
wtr.Write(''); // assuming NULL characters can work as record delimiters for safety.
}
}

假设你的TFoo的Serialize方法很快，我真的不认为你会得到比这种方法更快的速度。

实现反序列化程序对读者来说是一项练习，但应该是微不足道的。请注意我是如何将字典的大小存储到文件中的，这样在创建时可以将返回的字典设置为正确的大小，从而避免@spender在评论中描述的重新平衡问题。

Answer 2

因此，考虑到Dai的推理，我们将坚持现有的策略，并且我们需要维护C#和Java的兼容性(这意味着C#字典的额外树状态位无论如何都会被丢弃在Java端，因为它现在只加载节点数据)。

对于后来仍然对此感兴趣的读者来说，我在这里找到了一个非常好的答案，在一定程度上回答了提出的问题。一个关键的区别是，这个答案适用于B+ Trees，而不是Dictionaries，尽管在实际应用中，这两种数据结构的性能非常相似。B+树的性能比常规树(如二进制、红黑、AVL等)更接近字典。具体来说，Dictionaries提供接近O(1)的性能(但没有"从范围中选择"的能力)，而B+树具有O(logb(X))，其中B=基数通常很大，这使得它们与B=2的常规树相比具有非常高的性能。为了完整起见，我将其复制粘贴在这里，但所有的功劳都归于csharptest.net，用于B+树代码、测试、基准测试和写操作。

为了完整起见，我将在这里添加我自己的实现。

• 简介-http://csharptest.net/?page_id=563
• 基准-http://csharptest.net/?p=586
• 联机帮助-http://help.csharptest.net/
• 源代码-http://code.google.com/p/csharptest-net/
• 下载-http://code.google.com/p/csharptest-net/downloads
• NuGet包-http://nuget.org/List/Packages/CSharpTest.Net.BPlusTree