¿Existe un diccionario inmutable de código abierto para C#, con métodos rápidos 'Con/Sin'?

Question

Estoy buscando un diccionario inmutable C# adecuado, con métodos de actualización rápida (que crean una copia parcial del diccionario con ligeros cambios). Implementé uno yo mismo, usando cremalleras para actualizar un árbol rojo-negro, pero no es particularmente rápido.

Por 'diccionario inmutable' no me refiero solo a readonly o const. Quiero algo que tenga métodos "con" y "sin" razonablemente rápidos, o equivalentes, que devuelvan algo con ligeras modificaciones sin modificar el original.

Un ejemplo de otro idioma es map in Scala

Answer 1

Existe cierta implementation of the immutable dictionary basado en sólo lectura árbol AVL binario.

/** 
* 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. 
*/ 

favor, eche un vistazo al método 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) 
{ ... } 

El método 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) 
{ ... } 

Además, existe otra aplicación: Immutable AVL Tree in C#. Tiene los mismos tiempos de búsqueda O (log N) e inserción.