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

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

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

rippletek 2016-11-18 12:25:48 浏览1285
展开阅读全文

测试方法

我们使用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的散列表实现极具个性,并完全体现了散列表作为“无序数据结构”的特点。它是如何做到这一点的?

网友评论

登录后评论
0/500
评论
rippletek
+ 关注