可爱的散列

有一种容器叫做“字典”。Ruby中称为“散列”(hash)，即为散列映射(hashmap)的简写。

散列和数组是编程中最常见的两种数据结构。

Ruby中数组(array)和散列表(hashes)都是对象的集合。都会按需调整大小来保存新的数据。

数组只能通过索引(即数值)来获取数组中的元素。

散列可以通过任何东西来找到元素，即散列可以将一样东西和另一样东西关联起来。

stuff = {'name' => 'etan', 'age' => 18, 'height' => 170, 1 => 'Wow', 2 => 'Neato' }  //定义散列
stuff.delete(1)  //删除1对应的值

“对应”和“关联”是散列中的重要概念。

散列的工作原理：(查询“honorificabilitudinitatibus”这个词的意思)

到图书馆找本字典，假设你找到了OED。
你知道“honorificabilitudinitatibus”以h开头，在书的标记中找到h这个字母
继续查找，找到hon开头的部分
继续查找，直到找到“honorificabilitudinitatibus”
找到条目，阅读定义，弄清楚它的意思

这个过程和散列的工作方式完全相同。Ruby的散列和真实世界里的OED这样的字典是类似的。

创建自己散列模块

dict.rb

Dict不过是“一个由容器构成的数组，每个容器是包含多个槽位的数组，每个槽位里有一个键/值对”。

“一个由容器构成的数组”：
每个容器是包含多个槽位的数组：
每个槽位里有一个键/值对：

dict icon

上面Dict的算法通常是：

使用散列函数hash_key把键转换成一个整数
使用求余操作符(%)将这个散列值转换成一个容器编号
从容器的aDict数组中获取这一容器，然后遍历它。找到我们需要的键的槽位

我们在set函数中通过这种方法来替换重复的键，或者追加新键。

数组的三个等级

上面我们是让set用新值覆盖(替换)的方式赋值，set的速度会比较慢，但对别的操作的速度是有利的。

如果想要创建一个每个键可以对应多个值得Dict，我们需要做的是让容器的每一个槽位都是一个值得数组。也就是，追加容器的第三层，然后是槽位，然后是值。这样也符合Dict的定义的，因为我们说过“每个键可以有多个值”。换一种说法就是“每个键可以有一个值得数组”。由于键放到了槽位上，槽位上又有了值的数组。(这块可以自己尝试一下)

如何选择散列或数组

数组可以存储和组织一些数据。散列也是一样，不过在以下几种情况下可以使用散列：

需要某种标识符(名称、地址以及任何可以作为键的东西)来检索东西
不需要东西按顺序排列。散列通常不支持排序，所以若要排序就不得不使用数组
你需要实现元素及其键的添加和删除操作

散列也可称为“查找表”。

还有一块哈希(hash)的知识。抽空可以研究一下。

散列(哈希Hash) 文档

由[索引，值，…]数组转哈希表

2.2.1 :005 > ary = [1, 'a', 2, 'b', 3, 'c']
 => [1, "a", 2, "b", 3, "c"]
2.2.1 :006 > Hash[*ary]
 => {1=>"a", 2=>"b", 3=>"c"}

由索引和值配对出现的数组转哈希表(*星号是指数组作为参数时使用)

2.2.1 :007 > alist = [[1, 'a'], [2, 'b'], [3, 'c']]
 => [[1, "a"], [2, "b"], [3, "c"]]
2.2.1 :008 > Hash[*alist.flatten]
 => {1=>"a", 2=>"b", 3=>"c"}

由索引数组和值数组配对生成哈希表

2.2.1 :016 > keys = [1, 2, 3]
 => [1, 2, 3]
2.2.1 :017 > vals = ["a", "b", "c"]
 => ["a", "b", "c"]
2.2.1 :018 > alist = keys.zip(vals)
 => [[1, "a"], [2, "b"], [3, "c"]]
2.2.1 :021 > Hash[*alist.flatten]
 => {1=>"a", 2=>"b", 3=>"c"}

索引和值都是数组(一个特殊情况,无法用上面的情况时)

2.2.1 :022 > h = Hash.new
 => {}
2.2.1 :024 > alist = [[1, ['a']], [2, ['b']], [3, ['c']]]
 => [[1, ["a"]], [2, ["b"]], [3, ["c"]]]
2.2.1 :025 > alist.each {|k, v| h[k] = v }
 => [[1, ["a"]], [2, ["b"]], [3, ["c"]]]
2.2.1 :026 > h
 => {1=>["a"], 2=>["b"], 3=>["c"]}