三亩地 三亩地SAN MU DI · CODE DIARY
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天,欢迎挑你感兴趣的翻一翻。

Dictionary的底层原理

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

← 返回列表