四种编程语言中散列表的遍历顺序比较

测试方法

我们使用Ruby, JavaScript, Lua和Go这四种编程语言分别实现了以下步骤:

1. 创建一个空的散列表H
2. 以26个英文字母为key并按a-z的顺序插入H
3. 遍历H并打印遍历的顺序，重复两次
4. 从H删除"r", "p", "t", "k"这四个key
5. 遍历H并打印遍历的顺序
6. 将"r", "p", "t", "k"这四个key重新插入H
7. 遍历H并打印遍历的顺序

测试环境

• Ruby 2.3 for Ruby
• Node.js 6.9.1 for JavaScript
• Lua 5.2.2 for Lua
• Go 1.7.1 for Go

Ruby

测试代码

def keys(t)
    r = ""
    t.each { |k, v| r += k }
    r
end

s = "abcdefghijklmnopqrstuvwxyz"
t = {}
s.each_char { |c| t[c] = 1 }
puts(keys(t))
puts(keys(t))

d = "rptk"
d.each_char { |c| t.delete(c) }
puts(keys(t))

d.each_char { |c| t[c] = 100 }
puts(keys(t))

输出及其分析

反复运行多次，输出无变化，内容如下:

abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
abcdefghijlmnoqsuvwxyz
abcdefghijlmnoqsuvwxyzrptk

可见，Ruby的散列表是一个有序结构，其遍历顺序和插入顺序完全一致。

JavaScript

测试代码

var print = console.log

function keys(t) {
    r = ""
    for (k in t) {
        r += k
    }
    return r
}

s = "abcdefghijklmnopqrstuvwxyz"
t = {}
for (i in s) {
    t[s[i]] = i
}
print(keys(t))
print(keys(t))

d = "rptk"
for (i in d) {
    delete t[d[i]]
}
print(keys(t))

for (i in d) {
    t[d[i]] = 100
}
print(keys(t))

输出及其分析

反复运行多次，输出无变化，和Ruby版本的输出完全一样(在此略去)。

这说明JavaScript的散列表也是一个有序结构，其遍历顺序与插入顺序相同。

Lua

测试代码

local function keys(t)
    r = ""
    for k in pairs(t) do
        r = r .. k
    end
    return r
end

s = "abcdefghijklmnopqrstuvwxyz"
t = {}
for i = 1, #s do
    t[s:sub(i, i)] = i
end
print(keys(t))
print(keys(t))

d = "rptk"
for i = 1, #d do
    t[d:sub(i, i)] = nil
end
print(keys(t))

for i = 1, #d do
    t[d:sub(i, i)] = 100
end
print(keys(t))

输出及其分析

第一次运行输出:

yzwxuvstabijghefcdqropmnkl
yzwxuvstabijghefcdqropmnkl
yzwxuvsabijghefcdqomnl
yzwxuvstabijghefcdqropmnkl

第二次运行输出:

srqpwvutzyxcbagfedkjihonml
srqpwvutzyxcbagfedkjihonml
sqwvuzyxcbagfedjihonml
srqpwvutzyxcbagfedkjihonml

不难看出，每次运行的输出都不一样，但在单次运行中，对散列表的遍历顺序是确定的，且与插入顺序无关。

Go

测试代码

package main

import "fmt"

func keys(t map[byte]int) string {
    r := ""
    for k := range t {
        r += string(k)
    }
    return r
}

func main() {
    s := "abcdefghijklmnopqrstuvwxyz"
    t := make(map[byte]int)
    for i := range s {
        t[s[i]] = i
    }
    fmt.Println(keys(t))
    fmt.Println(keys(t))

    d := "rptk"
    for i := range d {
        delete(t, d[i])
    }
    fmt.Println(keys(t))

    for i := range d {
        t[d[i]] = 100
    }
    fmt.Println(keys(t))
}

输出及其分析

第一次运行输出:

prbgioquvxeknjlmswcdfzyaht
bgipruvxeknoqmswcdfjlzahty
gibnoquvxedfjlmswczhya
noquvxekfjlmswcdztyahirpbg

第二次运行输出:

motbcghlrvzdeijsuyakpqfnwx
deijlrvzakpqsuyfnwxbcghmot
qsuyawxfnghmobcijlvzde
tbcghmovzdeijlryapkqsufnwx

不仅每次运行的输出都不一样，甚至每一行的输出都不一样。这说明Go的散列表遍历操作是完全随机的。

总结

• Ruby和JavaScript竟然将散列表这种经典的无序数据结构选择了一种有序的实现，令人深感意外。两者的遍历顺序都和插入顺序一致。
• Lua的散列表的遍历顺序和插入顺序无关，但表的遍历顺序在表内元素无变化时是确定的。
• Go的散列表遍历顺序则是完全随机的，非常符合散列表是一种无序数据结构的特点。
• 但不论编程语言采用了哪种具体的散列表实现办法，除非情况及其特殊，我们在编写代码时都应将散列表作为一种无序数据结构来使用，即在内心机器中，总是将散列表的遍历顺序当成是完全随机的。

问题

1. Ruby是如何将散列表这种经典的无序数据结构实现为一种有序结构的？
2. 上面Lua的测试代码每次运行的输出都不一样，这是为什么？
3. Go的散列表实现极具个性，并完全体现了散列表作为“无序数据结构”的特点。它是如何做到这一点的？