iT邦幫忙

2

雜湊表 (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);
});

// 分類過後的商品就會變成
{
  食品: ["蘋果"],
  家具: ["椅子"],
  家電: ["電扇"],
  日用品: ["洗髮精", "沐浴乳"]
};

這裡應該有發現到我們要查找的日用品這個屬性是一個陣列
那如果經過分類後發現這個陣列超長 那這樣又就會回到迴圈跑太多次的問題
所以如果雜湊函式寫得很好 衝突很少
就可以盡可能地避免這樣的問題了

雖然在我舉的例子裡把 雜湊函式 說是分類
然而事實上 雜湊函式 在做的事情並不是分類
而是針對資料進行特定的處理後而獲得一個值
只是在這邊舉的例子像是分類而已

最後
感謝大家耐心地看完


2 則留言

1
心原一馬
iT邦研究生 5 級 ‧ 2019-12-19 15:34:25

嗨嗨,邦友您好,我是小馬,
我覺得你的比喻寫的相當好哦,
例子蠻生活化的,
使人淺白易懂,
有助於普及困難的程式概念。
小馬自己還蠻喜歡這類文章的,讚讚~
(小馬自己的寫作也朝生活淺白的方向在寫呢~)

/images/emoticon/emoticon42.gif

紅柿 iT邦新手 5 級 ‧ 2019-12-19 19:09:32 檢舉

就像我裡面說的:

某種程度 程式語言的世界就是微觀的現實世界
程式語言大部分在做的事都是擷取世界的一部份或是模仿世界的一部份 抽象程度的差別而已

然後也很希望把程式的東西講得很生活
現在最難的就是想到 相近的 或是 合適的 的例子 _(:3 」∠ )_

感謝你的喜歡!!

0
player
iT邦大師 1 級 ‧ 2019-12-20 17:56:45

hash table 通常用在 Associative Array
將用來索引的key用hash function方式化簡(例如把字串轉成int)
來改善查詢時的效能
例如VC++的MFC的class CMap

我要留言

立即登入留言