Aloha！又是我少女人妻 Uerica！以前我爸开车在停红绿灯的时候，总会趁着红灯几秒的空挡跟我玩游戏，如果时间允许，就会刻意走不同的路回家看看，有时总能挖掘到一些很好吃的美食小吃，当然恶整我也是他日常的乐趣之一 QQ。总之 ”努力把一成不变的生活过得很有趣“ 是爸爸的人生观。我想我应该也有遗传到一些吧！我以前国文课本上的伟人都有化妆绑辫子呢！

杂凑表 (Hash Table)

杂凑表有点类似阵列 Array 与连结串列 Linked List 的结合，前面有提到阵列的特性为搜寻容易，但插入与删除较无效率，连结串列却刚好相反，属於搜寻困难，但插入与删除较为有效率的资料结构。而杂凑表即可解决这两种资料结构的缺点。

杂凑表的定义与特性

杂凑表的所储存的资料元素都有成对的键 (Key) 及值 (Value) ，将 Key 经过杂凑函数 (Hash Function) 後，计算出新的值并放入对应的阵列索引中。若发生杂凑碰撞 (collsion)，则使用连结串列的方式储存。此资料结构方法被广泛运用在资料库搜索、关键字搜寻、快取等。

好！先来喝杯果汁吧～
假设今天要储存水果 (Key) 以及水果的数量 (Value)，而果汁机是杂凑函数 (Hash Function)。

我想储存苹果有三颗这个资料，先将苹果 (Key) 放进果汁机 (Hash Function) 打一打。

得到了杂凑值 (Hash Values) 111，因阵列的长度是 4 ，所以将杂凑值除以 4 值取余数，放入对应的阵列索引值位置。(此部分的杂凑值只是举例)，在此得出苹果的杂凑值是 111 ，取余数後是 3。

所以将苹果及三颗的值 (Value)，一起放在索引 3 的位置

再来要处理五颗草莓，在此得出草莓的杂凑值是 112 ，取余数後是 0。

将草莓有五颗这个资料存在对应的索引值 0 。

只有一颗的桃太郎的桃子也是同样的道理。

将桃子有一颗这个资料放入对应的索引值 2 。

樱桃来了～樱桃得出的杂凑值取余数後是 0，但索引值 0 的位置已经有草莓的资料了！这种状况就称为杂凑碰撞 collsion！

这时就可以用我们之前提过的连结串列的方式来储存资料！

这种方式在查找资料的时候很简单，若已知道要找寻的资料 key 是什麽，只要将 key 经过杂凑函数的计算并取余数後，根据求得的该索引值下去查找即可！

• 杂凑表优点

  • 搜寻资料前无需事先排序
  • 无 collsion 的情况下搜寻某资料元素的时间复杂度为 O(1)。
  • 保密与安全性高

• 杂凑碰撞 collsion :
  不同的资料元素放入杂凑函数中，虽然机率很小，还是可能会获的同样的结果。这时可以使用下列方式处理。

  • 链结法 chaining : 利用串列将资料元素依序存在阵列中已有资料元素的後面，如同上面的例子
  • 开放定址法 open addressing : 发生碰撞时，计算出下一个候补位置，若下一个位置也发生碰撞，就继续计算到有空的位置为止。

• 杂凑值 Hash Values :
  杂凑值是资料经由杂凑函数後得出的结果，但杂凑值并非加密，相同的资料值进入杂凑函数後会求得相同的结果，但也有很小的机率会发生不同的资料值会得到相同的结果。但因杂凑函数的计算与设计方式，杂凑值是几乎无法回推到杂凑前的值，所以杂凑并非加密。

• 杂凑函数 Hash Function :
  又称杂凑演算法，可以想像成为资料元素建立指纹的方法，该函式会将资料打乱并混合，建立出该资料对应的杂凑值。杂凑函数的演算法有数种，有些程序语言或工具会有内建的 Hash Function，或 Hash Code 的函数可使用。代表性的演算法有 MD5、SHA系列等。

参考资料：

【资料结构】杂凑表

[资料结构] Hash Table

Data Structures 101: implement hash tables in JavaScript

好的今天就到这边啦～希望大家也都能努力在生活中找乐趣，这样不管做多无聊得事都有满满的力量坚持下去了～～明天见啦掰掰！