杂凑表 (Hash table) ?? 还是你是说 : 杂货店??

在文章开始之前，要先说说小弟我本人其实非资讯相关出身，所以所有的知识都是 google 大神教的所以若是文章内有任何错误的观念也欢迎留言指教，谢谢

是这样子的 其实 hash table 的观念我大致上也是询问 google 大神来的
发现大家文章写得好像太 "程式" 了
所以我想写这篇文章想来稍微釐清一下

其实某种程度 程式语言的世界就是微观的现实世界
所以程式语言大部分在做的事都是撷取世界的一部份或是模仿世界的一部份 抽象程度的差别而已

先撇开程式 撇开杂凑表

相信大家应该都有去大卖场买过东西的经验吧
在大卖场里都会有各式各样的商品跟柜子
而这些商品跟柜子都会透过走道或楼层等等来分类

像是假设我今天我想买洗髮精 我肯定是会走到日常用品区并找到盥洗用具的走道去买
一定不会走到熟食区或生鲜食品去找

这样的分类让我很快速知道我要去哪里找到我要的东西
如果大卖场里面所有的商品都不分类 全部都是想摆哪就放哪
那找东西的时候就必须一层一柜慢慢找
哇这样要找到几年!(;ﾟдﾟ)

其实某种程度上 杂凑表 就是在做分类这件事(ゝ∀･)

接下来就是比较带有点程式方面的解释(用的语言是 js)

我今天有一大堆商品:

let 商品清单 = ["苹果", "电扇", "椅子", "洗髮精"];

那我想要去分类他的话可以透过外观, 可食用, 是否有电... 等等许多的分类方法

那我就先以人类使用的方式去分类他们吧
分完大概会是:

let 分类过后的商品 = {  食品: "苹果",  家具: "椅子",  家电: "电扇",  日用品: "洗髮精"};

所以今天如果我想要找到洗髮精 是用没分类过的清单去寻找的话

let 商品清单 = ["苹果", "电扇", "椅子", "洗髮精"];for(let i = 0; i < 商品清单.length; i++) {  if (商品清单[i] === "洗髮精") {    console.log(`找到了!!是编号第 ${i} 个商品`);    break;  }}

OK 应该可以看到很明显的问题
如果今天商品清单里面有一万多个产品 而洗髮精也在一万多号
那这迴圈是不是就要跑一万多遍 (ˊ◓Д◔ˋ)

再来今天如果是用分类后的清单去找的话
我直接这样取得

let 分类过后的商品 = {  食品: "苹果",  家具: "椅子",  家电: "电扇",  日用品: "洗髮精"};console.log(分类过后的商品.日用品); // 直接访问 分类过后的商品 里的 日用品 属性

哇!连迴圈都不用跑!这查找速度绝对是飞快阿! ( つ•̀ω•́)つ
欸可是! 程式怎么会知道要去访问 日用品 这个属性 (ˊ･_･ˋ)

OK 回想一下 去大卖场时脑中所思考的 ->『我想买洗髮精，应该是在日常用品区吧』
这个部分就是在你脑中对洗髮精的分类的过程
而得到的答案 [在日常用品区吧] 这件事就是将其分类为 日用品
跟上面我所下的方类方式的人类使用的方式所得到的答案是一样的
所以这部份就会连接上了

那如果你脑中对洗髮精分类后得到的答案是 清洁用品
这样就会跟我分类的 日用品 不一致 所以就会找不到了

透过上述就会了解
所以如果存放时跟选购时分类方法一致就永远不会出错

那其实上面提到的人类使用的方式这个分类方法，要去买之前所思考的
其实在程式中就是在经过 function 的部分
所以如果要查找时走跟当初储存资料时一样的 function 就会得到一样的答案

let 商品清单 = ["苹果", "电扇", "椅子", "洗髮精"];function 某种分类法(商品) {  // 把商品丢进来演算后输出他的分类}console.log(某种分类法("苹果")); // 输出: 食品console.log(某种分类法("电扇")); // 输出: 家具console.log(某种分类法("椅子")); // 输出: 家电console.log(某种分类法("洗髮精")); // 输出: 日用品

储存时:

let 分类过后的商品 = {};// 进行分类商品清单.forEach((el) => {  let 类别 = 某种分类法(el);  分类过后的商品[类别] = el;});// 分类过后的商品就会变成{  食品: "苹果",  家具: "椅子",  家电: "电扇",  日用品: "洗髮精"};// 当然储存杂凑表时不是去跑全部的资料去储存，而是在每单笔资料在建立时就去跑分类并储存了

读取时

// 假设我要找 "洗髮精"console.log(分类过后的商品[某种分类法("洗髮精")]);

欸!可是
如果还有沐浴乳咧??

let 商品清单 = ["苹果", "电扇", "椅子", "洗髮精", "沐浴乳"];let 分类过后的商品 = {  食品: "苹果",  家具: "椅子",  家电: "电扇",  日用品: "洗髮精",   日用品: "沐浴乳" // 两个日用品 ( ˘･з･) ??????};

这样就有两个日用品欸 不就发生 冲突(collision) 了?

对!所以如果分类的够精準或是分类的够好就可以解决冲突
像是:

let 分类过后的商品 = {  食品: "苹果",  家具: "椅子",  家电: "电扇",  洗头的: "洗髮精",   洗身体的: "沐浴乳"};

这就会取决于分类方式的优劣了

那所谓的分类方法 在杂凑表中就叫做 杂凑函式 (hash function)
那关于杂凑函式这个主题再展开的话会有太多的讨论 在这边就先姑且认定为分类方式吧

当然
冲突(collision)其实难以避免
所以冲突的解决方式也是另一个大主题

但在这边就说其中一种: Chaining
Chaining 其实就是当分类成一样的时候 把东西串起来
所以分类就会是

let 商品清单 = ["苹果", "电扇", "椅子", "洗髮精", "沐浴乳"];function 某种分类法(商品) {  // 把商品丢进来演算后输出他的分类}let 分类过后的商品: {};// 进行分类商品清单.forEach((el) => {  let 类别 = 某种分类法(el);  // 为了能够 chaining 其他分类的型别也转为阵列  分类过后的商品[类别] == undefined && (分类过后的商品[类别] = new Array());  分类过后的商品[类别].push(el);});// 分类过后的商品就会变成{  食品: ["苹果"],  家具: ["椅子"],  家电: ["电扇"],  日用品: ["洗髮精", "沐浴乳"]};

这里应该有发现到我们要查找的日用品这个属性是一个阵列
那如果经过分类后发现这个阵列超长 那这样又就会回到迴圈跑太多次的问题
所以如果杂凑函式写得很好 冲突很少
就可以尽可能地避免这样的问题了

虽然在我举的例子里把 杂凑函式 说是分类
然而事实上 杂凑函式 在做的事情并不是分类
而是针对资料进行特定的处理后而获得一个值
只是在这边举的例子像是分类而已

最后
感谢大家耐心地看完