Dictionary的底层原理

📅 2026/7/27 16:19:27 👁️ 阅读次数 📝 编程学习
Dictionary的底层原理

Dictionary的底层原理图:

存储结构:数组加单链

运用了buckets,entries两个数组

为了提高查询效率:int[] buckets桶数组,存放的每一个链表的头节点的下标

详细步骤:

dict.Add("k1","v1"),通过k1获取HashCode值

然后除以buckets桶的个数获取在桶中存储的位置:k1=1304016835,k1%bucket.lenth(5)=0,将k1存储在桶为0的位置

如果该位置下entries下标为-1(代表还没存储数据),就往空的位置加入,然后使next指向-1

该数据下标为0

如果不为-1,则往末尾加,加好后,使next值指向前一个元素的下标,再将自己的下标赋值给桶在该位置的数

使用的时候就是先拿到桶的位置,然后遍历链表,而不是遍历整个数组

时间复杂度从O(n)—>O(1)

注意事项:

原链表最多存储100个数据

超出的话,则给桶扩容至下一个质数:5->7->11...