杂凑表，我需要那个酷东西

在线性资料结构中，若要找一个资料，花费的时间复杂度为O(n)，或是可以选择节省时间，但是耗费记忆体容量。若是两者都不想选，那就需要Hash Table这种资料结构，下面会来探讨，到底什麽是杂凑表？

Hash Table

Hash这个词在电脑科学中很常见，他是一种加密技术。例如密码，当你创建密码时，他会被加密过後才会存入後端资料库，以免密码被泄漏。不过今天我们先不谈加密，而是谈谈Hash在做些什麽。简单的说，Hash是将一组值转换成另一组，那为什麽要怎麽做呢？最主要的是要保护资料，不过此处会着重在解释如何转换值。

图片中可以看到，圈圈的部分是原本的值，透过Hash Function後存入到Hash Table中，假设每个圈圈都有一组属於他们的ID，ID在Hash过後有可能两组资料（两个圈圈）被放入到Hash Table同一个位置中，此时产生的情况称为Collision。

Hash Function

上面提到产生的冲突，不论使用何种的Hash Function都有可能会遇到，下列两种是常见的使用方式：

1. Division Method
2. Multiplication Method

这两种方法各有优缺点，可以根据需求来选择。

Division Method

• 优点：速度非常快
• 缺点：要注意不能使用2的次方进行运算，非常容易出现冲突
• 公式：Index = Key mod m
  • Index为要放入Hash表的哪个位置
  • m为长度
  • key为元素

Multiplication Method

• 公式：Index = [m(keyA % 1)]
  • A是一个无理数
  • mod1时将整数去掉，就会得到0<P<1
  • P*m
  • math.floor()

#Python
x = hash("a")
print(x) #963309178111316638
y = hash(8823748)
print(y) #8823748
z = hash(str([1,2,3]))
print(z) #6529461775645613167

JavaScript的程序码引用自上过课程老师分享的程序码：

资料来源：Udemy-资料结构与演算法 (JavaScript)

class HashTable {
    // m = hashtable size
    constructor(size){
        this.size = size;
        this.table = [];
        for(let i = 0; i < this.size; i++){
            this.table.push([]);
        }
    }


    //division method
    //把一个值换成另一个值
    hash1(key){
        return key % this.size;
    }

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

    set(key, value){
        let index = this.hash2(key);
        //this.table是一个array，才能做push
        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 == key){
                return this.table[index][i];
            }
        }
        // 找不到就回传null
        return null;
    }

    printAll(){
        console.log(this.table);
    }
}

// m = 6
let myHashTable = new HashTable(6);
myHashTable.set(11424,"Mike");
myHashTable.set(62545,"James");
myHashTable.set(4171,"Drake");
myHashTable.set(554,"Keven");

// myHashTable.printAll();

// 寻找
console.log(myHashTable.get(4171));

Hash是一种不使用明文传输，减少资料被窃取的技术，延伸阅读可参考密码学，推荐Udemy的课程

https://www.udemy.com/course/cryptography-python/