Day8: [资料结构]Hash Table - 杂凑表

在理解hash table之前，先来理解hash(杂凑)吧!

杂凑的特色有以下几点:

1. 无论原本的内容长短，经过杂凑演算法处理过的值都会是固定长度
2. 经由杂凑处理过的资料无法反推出原本的输入为何
3. 两个输入的内容即使只差一个字， 算出来的结果会会相差非常多
4. 常用的杂凑演算法有MD5和SHA ，後者的安全性更高

生活中的例子

1. 保存用户密码
   假如小明在A网站的登入密码是12345 ，存在後端资料库的密码通常会经过杂凑处理，不会大喇喇地把明码12345存进去，因此就算骇客侵入资料库， 也无法推测出原本的密码是多少，确保资料安全性，所以如果有天你在某个网站点了忘记密码，就会把原密码原封不动寄到信箱里的话 ，那就要特别小心了，那个网站可能会有资安疑虑。

2. 档案验证
   假如我们打开终端机输入md5 档名 ，就会发现生成一组杂凑值，可以用来验证两个档案是否一样
   

什麽?杂凑不等於加密吗?

• 加密需要有一把钥匙， 透过钥匙才能解密回推取得原本的内容 
• 杂凑不需要钥匙 ，无且无法回推原本的内容是甚麽

Hash Table

Hash table中文叫作杂凑表，又被称为关联式阵列，是根据key来查询资料存在哪个记忆体位置的资料结构，而这个key是透过hash function(杂凑函数)计算出来的，搜寻速度为O(1)。

buckets是储存资料的格子

图片来源:https://en.wikipedia.org/wiki/Hash_table

HashMap Collision

经过hash function 算出一个索引值，但可能会发生两组资料算出来的索引值为重复的情形，这就是HashMap Collision(碰撞)，假如真的发生碰撞的话，就把碰撞的值放到同一个阵列里或者是用linked list解决碰撞的问题，以下图为例， Danny和Ella的id经过hash funciton计算後的索引值都是4，就会发生碰撞，所以这个时候我们可以设计成每个储存格都是一个阵列，这样的话遇到碰撞的值还是可以存放在同一个索引值底下。

用js实作hash table

hash1的function为Division Method，公式为index = key mod size， 简单来说就是key(id)取size(6)的余数
hash2的function为Multiplication Method，公式为A =(√5–1)/2 , index = [m(keyA%1)]，相信这边应该已经蛮多人眼神死了，想要了解完整的公式解释可以google Multiplication Method

在无法预先得知「Key的范围」以及「在该范围内Key的分布情形」之下，使Multiplication Method会比较好，所以采取hash2来做杂凑处理

class HashTable {
    constructor(size) {
        this.size = size;
        this.table = [];
        for (let i = 0; i < this.size; i++) {
            this.table.push([]);
        }
    }
    hash1(key) {
        return key % this.size;
    }

    hash2(key) {
        let num = (Math.sqrt(5) - 1) / 2;
        return Math.floor(this.size * ((key * num) % 1));
    }

    set(key, value) {
        let index = this.hash2(key);
        this.table[index].push({ key, value });
    }

    get(key) {
        let index = this.hash2(key);
        //可能有碰撞的情形发生
        for (let i = 0; i < this.table[index].length; i++) {
            if (this.table[index][i] === key) {
                return this.table[index][i];
            }
        }
    }
    printAll() {
        console.log(this.table);
    }
}

let myHashTable = new HashTable(6);
myHashTable.set("89893", "Hank");
myHashTable.set("12343", "Sally");
myHashTable.set("72324", "Danny");
myHashTable.set("28990", "Ella");
myHashTable.set("324323", "Wason");

myHashTable.printAll();

呼叫printAll 可以发现印出来的hash table虽然有发生碰撞的情况，但还是可以看到碰撞的两个物件安然无恙的放在同一个索引值底下?

参考资料:Hashing 基础介绍