不再贴完整源码,只贴关键部分源码
需要先看懂C# 字典原理
NativeHashSet的定义为:
public unsafe struct NativeHashSet<T>: INativeDisposable, IEnumerable<T> where T : unmanaged, IEquatable<T>
NativeHashMap的定义为:
public unsafe struct NativeHashMap<TKey, TValue>: INativeDisposable, IEnumerable<KVPair<TKey, TValue>> where TKey : unmanaged, IEquatable<TKey> where TValue : unmanaged
比较特殊的是T要求实现IEquatable,如果是int、float等数值类型既然就有,如果是自定义结构体,最好也在自己实现下
两者的核心都在HashMapHelper中,数据在HashMapHelper<T>* m_Data,内存分配同样调用Memory.Unmanaged.Allocate,释放调用Memory.Unmanaged.Free,有依赖释放时会自动创建NativeHashMapDisposeJob,逻辑与NativeList完全一致
与UnsafeList不同的是,这里数据类型不同,没用Block,直接调用的Memory.Unmanaged.Allocate
添加、删除元素,扩容等基本和C#字典相同,使用方式基本相同,不再赘述。
这里不同的是,将value、key、next、bucket按顺序合并在一个数组中了,实现在Init函数中
internal void Init(int capacity, int sizeOfValueT, int minGrowth, AllocatorManager.AllocatorHandle allocator){Count = 0;Log2MinGrowth = (byte)(32 - math.lzcnt(math.max(1, minGrowth) - 1));capacity = CalcCapacityCeilPow2(capacity);Capacity = capacity;//容量是2的倍数BucketCapacity = GetBucketSize(capacity);//桶数组是2倍容量Allocator = allocator;SizeOfTValue = sizeOfValueT;//value所需内存大小int keyOffset, nextOffset, bucketOffset;int totalSize = CalculateDataSize(capacity, BucketCapacity, sizeOfValueT, out keyOffset, out nextOffset, out bucketOffset);//数组中先是value的数据,其起始地址即为分配的内存的地址Ptr,其大小为valuesSize = sizeOfTValue * capacity; //随后是key的数据,其起始地址为Ptr + valuesSize,其大小为keysSize = sizeOfTKey * capacity;//再后是next的数据,其起始地址为Ptr + valuesSize + keysSize,next的数据是int类型,其大小为nextSize = sizeOfInt * capacity;//最后是bucket的数据,其起始地址为Ptr + valuesSize + keysSize + nextSize,bucket的数据是int类型,其大小为bucketSize = sizeOfInt * bucketCapacity;//四者相加得到所需内存的总大小Ptr = (byte*)Memory.Unmanaged.Allocate(totalSize, JobsUtility.CacheLineSize, allocator);Keys = (TKey*)(Ptr + keyOffset);Next = (int*)(Ptr + nextOffset);Buckets = (int*)(Ptr + bucketOffset);Clear();}
关键的查找如下
internal int Find(TKey key){if (AllocatedIndex > 0){// First find the slot based on the hashvar bucket = GetBucket(key);//根据Key做Hash计算,得到桶数组索引IDvar entryIdx = Buckets[bucket];//找到当前桶数组的位置所对应的Key数组的链头索引if ((uint)entryIdx < (uint)Capacity){var nextPtrs = Next;while (!UnsafeUtility.ReadArrayElement<TKey>(Keys, entryIdx).Equals(key))//根据Key数组索引值取值,判断是否与传入的key相等{entryIdx = nextPtrs[entryIdx];//Next数组中记录了相同桶数组索引中的key依次的Key数组索引if ((uint)entryIdx >= (uint)Capacity){return -1;}}return entryIdx;}}return -1;//表示没找到}