测试方法
我们使用Ruby, JavaScript, Lua和Go这四种编程语言分别实现了以下步骤:
创建一个空的散列表H以26个英文字母为key并按a-z的顺序插入H遍历H并打印遍历的顺序，重复两次从H删除"r", "p", "t", "k"这四个key遍历H并打印遍历的顺序将"r", "p", "t", "k"这四个key重新插入H遍历H并打印遍历的顺序
测试环境
Ruby 2.3 for RubyNode.js 6.9.1 for JavaScriptLua 5.2.2 for LuaGo 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的散列表遍历顺序则是完全随机的，非常符合散列表是一种无序数据结构的特点。但不论编程语言采用了哪种具体的散列表实现办法，除非情况及其特殊，我们在编写代码时都应将散列表作为一种无序数据结构来使用，即在内心机器中，总是将散列表的遍历顺序当成是完全随机的。
问题
Ruby是如何将散列表这种经典的无序数据结构实现为一种有序结构的？上面Lua的测试代码每次运行的输出都不一样，这是为什么？Go的散列表实现极具个性，并完全体现了散列表作为“无序数据结构”的特点。它是如何做到这一点的？
