0
0
0
1. 云栖社区>
2. 博客>
3. 正文

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

rippletek 2016-11-18 12:25:48 浏览1285

## 测试方法

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

## 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))

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

## 总结

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

## 问题

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

rippletek
+ 关注

corcosa 10309人浏览