是否有C＃的開源不可變的字典，快速的「有/無」方法？

Question

我正在尋找一個適當的C＃不可變的字典，使用快速更新方法（創建字典的部分副本，並稍作更改）。我自己實現了一個，使用拉鍊來更新紅黑樹，但它並不是特別快。

「不變的字典」我不只是指只讀或常量。我希望有一些合理快速的'With'和'Without'或等價的方法，可以在不修改原始內容的情況下稍作修改。

一個例子，從另一種語言是map in Scala

Answer 1

有一些implementation of the immutable dictionary基於只讀二進制AVL樹。

/** 
* To modify, use the InsertIntoNew and RemoveFromNew methods 
* which return a new instance with minimal changes (about Log C), 
* so this is an efficient way to make changes without having 
* to copy the entire data structure. 
*/ 

請大家看看InsertIntoNew()方法：

/** Return a new tree with the key-value pair inserted 
* If the key is already present, it replaces the value 
* This operation is O(Log N) where N is the number of keys 
*/ 
public ImmutableDictionary<K,V> InsertIntoNew(K key, V val) 
{ ... } 

的RemoveFromNew()方法：

/** Try to remove the key, and return the resulting Dict 
* if the key is not found, old_node is Empty, else old_node is the Dict 
* with matching Key 
*/ 
public ImmutableDictionary<K,V> RemoveFromNew(K key, out ImmutableDictionary<K,V> old_node) 
{ ... } 

此外，還有另一種實現方式：Immutable AVL Tree in C#。它具有相同的O（log N）查找和插入時間。