揭秘Dictionary实现原理

字典(Dictionary)是我们经常使用的一种数据结构，那它的实现原理是什么样的，他是怎么构成的呢，马上揭秘。

物理结构

Dictionary的是由两个数组和一个结构体构成：

1. buckets数组：int数组，用来分散数据的；
2. entries数组：entry数组，用来存储数据的；
3. entry：存放在entries数组中，它是一个结构体，由四个属性构成：hashCode,next,key,value，其中，hashCode存放key对应的hash值，next存放下一个节点在数组中的索引；

逻辑结构

由物理结构所展现出来的结构，如下图，长度为7的buckets数组，2、9、16、12是存放到entries数组中的元素，它所展现出来的样子就像一个hashtable，而不是数组：

实现原理

再揭秘前，先看一下Dictionary是如何添加元素的，假设要插入四个元素，第一个元素的key=16,value=16；第二个元素的key=9,value=9；第三个元素的key=12,value=12；第四个元素的key=2,value=2 。插入第一个元素，首先根据hash算法，key=16的元素落到bucktest数组索引为2的位置，这样该位置就指向第一个元素。插入第二个元素，根据hash算法，该元素也落到bucktest数组索引为2的位置，此时会采用“头插法”，将第二个元素放到第一个元素的前面， bucktest数组索引为2的位置指向第二个元素，第二个元素指向第一个元素。另外两个元素以此类推进行插入。

插入第一元素：key=16,value=16

插入第二个元素：key=9,value=9

插入第三个元素：key=12,value=12

插入第三个元素：key=2,value=2

此时entries数组存放的数据是这样的，根据插入的先后顺序，依次是16、9、12、2：


揭秘答案：

1. buckets数组中的元素记录最近节点所在数组(entries数组)中的索引。
2. entries数组仅仅是存放entry实体。
3. entry最关键的点是next属性，记录下一个节点在数组(entries数组)中的索引。

综上三点，揭露了Dictionary的实现原理。