c# - 为什么使用 64 位哈希而不是字符串时字典的内存消耗会增加？

问题描述

我们在现有代码的不同位置使用字典，将标签映射到每个包含该标签的对象。这在以前从来不是问题，因为这些字典“只”管理数千个对象。然而，我们现在的软件更可能处理数万到数十万个对象。使用上述标签作为键会导致我们消耗大量不必要的内存，因为这些标签被存储两次并且可以达到超过 150 个字符的长度。

因此，将长标签替换为具有固定大小的散列的想法很明显。为此，我们决定使用 FNV 哈希算法，该算法从字符串中计算出一个无符号的 64 位整数。为了避免对现有代码进行过多更改，我们将字典包含在一个对象中，该对象转换传递的字符串键并在内部字典上工作。这为我们节省了使用先前实现的方法的大量更改。您可以将其称为最广泛意义上的装饰器。以下是我们提出的内容的简要概述。

[Serializable]
public class SimpleTestObject {

    public string Tag { get; set; }

    public SimpleTestObject(string tag) {
        this.Tag = tag;
    }
}


[Serializable]
public class FnvDictionary<T> : IDictionary<string, T> where T : SimpleTestObject {
    private ConcurrentDictionary<UInt64, T> _InternalDictionary = new ConcurrentDictionary<UInt64, T>();

    public T this[string key] {
        get {
            return this._InternalDictionary[this.CalculateHash(key)];
        }
        set {
            if (key != value.Tag)
                throw new ArgumentException();
            _InternalDictionary[this.CalculateHash(key)] = value;
        }
    }

    public ICollection<string> Keys {
        get { return this._InternalDictionary.Values.Select(item => item.Tag).ToList(); }
    }

    public ICollection<T> Values {
        get { return this._InternalDictionary.Values; }
    }

    public int Count {
        get { return this._InternalDictionary.Count; }
    }

    public bool IsReadOnly {
        get { return false; }
    }
    public void Add(string key, T value) {
        this._InternalDictionary[this.CalculateHash(key)] = value;
    }

    public void Add(KeyValuePair<string, T> item) {
        this.Add(item.Key, item.Value);
    }

    public void Clear() {
        this._InternalDictionary.Clear();
    }

    public bool Contains(KeyValuePair<string, T> item) {
        if (item.Key != item.Value.Tag)
            throw new ArgumentException();
        return this.ContainsKey(item.Value.Tag);
    }

    public bool ContainsKey(string key) {
        return this._InternalDictionary.ContainsKey(CalculateHash(key));
    }

    public void CopyTo(KeyValuePair<string, T>[] array, int arrayIndex) {
        KeyValuePair<string, T>[] source = this._InternalDictionary
            .Select(data => new KeyValuePair<string, T>(data.Value.Tag, data.Value))
            .ToArray();
        Array.Copy(source, 0, array, arrayIndex, source.Length);
    }

    public IEnumerator<KeyValuePair<string, T>> GetEnumerator() {
        return new FnvDictionaryEnumerator<T>(this._InternalDictionary);
    }

    public bool Remove(string key) {
        return this._InternalDictionary.TryRemove(this.CalculateHash(key), out _);
    }

    public bool Remove(KeyValuePair<string, T> item) {
        return this.Remove(item.Value.Tag);
    }

    public bool TryGetValue(string key, out T value) {
        return this._InternalDictionary.TryGetValue(this.CalculateHash(key), out value);
    }

    private UInt64 CalculateHash(string input) {
        const UInt64 MAGIC_PRIME = 1099511628211;
        UInt64 hash = 14695981039346656037;

        for (int i = 0; i < input.Length; i++)
            hash = (hash ^ (byte)input[i]) * MAGIC_PRIME;

        return hash;
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return this.GetEnumerator();
    }
}

public class FnvDictionaryEnumerator<T> : IEnumerator<KeyValuePair<string, T>> where T : SimpleTestObject {
    private ConcurrentDictionary<UInt64, T> _InternalDictionary;
    private readonly int _KeysCount;
    private int _KeyPos;

    public FnvDictionaryEnumerator(ConcurrentDictionary<UInt64, T> data) {
        _InternalDictionary = data;
        _KeysCount = data.Keys.Count;
        _KeyPos = -1;
    }

    public KeyValuePair<string, T> Current {
        get {
            T currentItem = _InternalDictionary.ElementAt(_KeyPos).Value;
            return new KeyValuePair<string, T>(currentItem.Tag, currentItem);
        }
    }

    object System.Collections.IEnumerator.Current => this.Current;

    public bool MoveNext() => ++_KeyPos < _KeysCount;

    public void Reset() => _KeyPos = -1;

    public void Dispose() {
        _InternalDictionary = null;
    }
}

现在问题来了：我们用一个小测试程序检查了上面描述的对象，并直接与目前使用的 ConcurrentDictionary 进行了比较。为此，我们构建了一个输出各个字典大小的小函数：

public static long GetObjectSize(object source) {
    BinaryFormatter formatter = new BinaryFormatter();
    using (MemoryStream stream = new MemoryStream()) {
        formatter.Serialize(stream, source);
        return stream.Length;
    }
}

在我们在测试的基础上创建了 250000 个数据集并将它们打包到字典中之后，我们的幻想破灭了。尽管我们自己的创建只使用每个 8 字节长的哈希，但内存消耗比 ConcurrentDictionary 中的要高。

const string TAG_BASE = "XXXXX|XXXXXX|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|XXXXXXXXXXX-";
const int TEST_OBJECTS_COUNT = 250000;

SimpleTestObject[] testObjects = new SimpleTestObject[TEST_OBJECTS_COUNT];
for (int index = 0; index < testObjects.Length; index++)
    testObjects[index] = new SimpleTestObject($"{TAG_BASE}{index}");
    
ConcurrentDictionary<string, SimpleTestObject> concurrentDict = new ConcurrentDictionary<string, SimpleTestObject>();
foreach (SimpleTestObject testObject in testObjects)
    concurrentDict[testObject.Tag] = testObject;
    
Console.WriteLine("Size of the ConcurrentDictionary = {0} bytes.", GetObjectSize(concurrentDict));

FnvDictionary<SimpleTestObject> customDict = new FnvDictionary<SimpleTestObject>();
foreach (SimpleTestObject testObject in testObjects)
    customDict.Add(testObject.Tag, testObject);

Console.WriteLine("Size of the FnvDictionary = {0} bytes.", GetObjectSize(customDict));


// Output:
// Size of the ConcurrentDictionary = 36140494 bytes.
// Size of the custom dictionary = 36890908 bytes.

现在出现的问题是，一个本应保存较少数据的字典怎么可能具有更大的内存消耗。很明显，ConcurrentDictionary 也仅在散列的基础上工作，但这与可以连续检索键集合的事实相矛盾。在上面描述的测试场景中，甚至在 GetObjectSize 函数中是否存在设计问题？还有更重要的：如何尽可能减少字典的内存消耗？

标签： c#dictionary

解决方案

请记住，.NET 中的字符串是引用类型：实际的字符串数据存储在堆分配的对象中，任何具有字符串字段的类型都只有对该对象的指针大小的引用。第七州

我以前没有意识到这一点。我假设字符串是值类型。为了更详细地研究这方面，我给自己安装了 Visual Studio Enterprise，因为它有内存分析工具。使用小型测试程序，行为很容易观察。在以下示例的代码中，值类型会导致字典的大小是列表的两倍。不是这种情况。

const string TAG_BASE = "XXXXX|XXXXXX|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX|XXXXXXXXXXX-";
const int TEST_OBJECTS_COUNT = 250000;

List<string> myList = new List<string>();
Dictionary<string, string> myDictionary = new Dictionary<string, string>();

for (int index = 0; index < TEST_OBJECTS_COUNT; index++)
{
    string myString = TAG_BASE + index;
    myList.Add(myString);
    myDictionary.Add(myString, myString);
}

结果已经在评论中向我预测：

还要记住，字典已经使用散列码组织自己，但它们使用 32 位散列码这样做。您已经添加了字典需要存储的额外 64 位哈希码，但它仍然在内部将其压缩为 32 位哈希码。您刚刚给了它另一个新的哈希码来担心，同时也让自己面临哈希码冲突。第七州

在分析内存转储时，很快就清楚字符串确实存储为引用。因此，我们善意的方法只会通过强制内存管理存储另一个数值而不是实际使用的引用来使问题恶化，而实际使用的引用又必须再次计算。

事实上，在上述示例中，两个集合消耗的内存量大致相同。就字典而言，还有一些管理开销。

对象类型	大小（字节）
字典<字符串，字符串>	65,448,420
列表<字符串>	60,007,980

回答我的问题：内存消耗正在增加，因为我们无意中强迫它这样做。其原因是对内部内存管理的了解不足。未来：依靠分析工具而不是自建！

感谢所有评论者的重要建议！

c# - 为什么使用 64 位哈希而不是字符串时字典的内存消耗会增加？

问题描述

解决方案

推荐阅读