如何访问字典或散列中的第n项？

Question

我有一个键和值的字典,例如:

{
    fred: 1,
    dave: 2,
    lily: 3
}

如何获得字典中的第二个元素 - {dave:2}在这种情况下？

---

背景:我已经在SO上以这样或那样的形式多次询问过这个问题了,所以我想我会写一个Q&A页面作为一个社区维基,人们可以被引用,这可能有希望成为这个的规范答案题.

此问答适用于字典,因为它们以多种不同语言实现.不同的语言使用不同的名称来指代基本相同的数据结构 - 例如,它们在Perl中称为哈希,在Python中称为词典.在Objective-C中,它们是NSDictionary或NSMutableDictionary类的实例 .

Answer 1

简而言之,您不能 - 因为词典是 键/值对的无序集合.填充字典的顺序不会保留在内存中.这是Python中的一个简单示例:

>>> dict = { 'a': 1, 'b': 2, 'c': 3 }
>>> dict # show the value of dict in memory
{'a': 1, 'c': 3, 'b': 2}

正如您所看到的,尽管字典是按照a,b,c的顺序初始化的,但是打印字典的值会显示它们的顺序a,c,b.即使这种排序也不会保留在内存中; 当您向字典添加更多键/值对时,上述表达式中的顺序将继续更改.

为什么是这样？

字典经过优化,可根据唯一密钥快速存储和检索值.实现方式因语言而异,但通常它的工作原理如下:

• 字典由N个元素的标准数组支持
• 在存储键/值对时,键被放置一个函数,该函数将其转换为整数("散列函数" - 因此Perl中此数据结构的名称为"hash").ASCII字符串键的简单散列函数可能是添加每个字符的ASCII值.(注意:这不是一个好的哈希算法 - 只是一个简单的例子!)
• 然后将整数除以数组的大小,并将该除法的余数用作数组的索引
• 如果已经填充了该索引处的数组元素,则使用各种技术中的一种来解决冲突(例如,数组元素的内容本身就是一个数组,其中附加了新值及其未散列的键)
• 检索与存储的工作方式相同:获取密钥,使用它来派生数组索引,然后检索与该密钥关联的值
• 随着字典的增长,可以调整后备数组的大小:在调整数组大小时,字典中的每个元素的散列值除以新的数组大小,从而产生新的余数,即后备数组中的新位置.