Day.13 Hash map

任何语言都会提供这一种资料结构，像Golang的map
ex. var hash map[string]int

array是以int作为index key，但hash map可以用string或其他的型态去当index使用，时间速度也很快，新增删除修改的时间复杂度都为O(1)，所以写程序的时候很常会用到。
简单说一下它的原理！

以电脑的储存方式要嘛就是连续跟非连续(array or pointer)，map是array的一种延伸用法，大家看一下这张图。

一个hash map底下会有一个array，简称bucket(桶子)，它是用来放val的，array的key都是int，那我们的key要用string那怎麽办？
这时候会设计一个hash function把string hash成int的index，找到对应的bucket，只要确保算法在同样的input有同样的output，就可以用key val的方便存取值了。

如图，现在有4个bucket，hash function就是把string的第一个值转成ASCII code再去mod(%)4，像dog的d ASCII code是100，100%4数值刚好是0，而且每次hash出来的结果都不会变，这样我们就可以把dog存在bucket 1。

现在要存apple的key，97%4 index是1，放在bucket 2。但！如果这时候要存dig这个key怎麽办？因为dig跟dog开头一样，最後hash的值一样是0，但bucket 1之前已经被占用了。这种情况叫Hash map collision，不一样的key hash出一样的结果。解法有好几种，以下为大家介绍的是链结法。

简单来说就是用链结来处理，bucket存放一条链结，当发生collision的时候，就把值串在链结就行了！
图:

你可能会想到，如果key很多都是d开头的，链结不就一直串下去吗？
对没错～读取的速度就会从O(1)变为O(n)，因为找到bucket了，还在从链结的头一直往下找，所以bucket的数量跟hash function够不够平均是很重要的！当bucket够多，hash够平均，速度就会一直保持在O(1)，我上面提到的例子只是简化给大家理解，真实上的string hash function更为复杂，而且bucket的数量还会动态去扩充！

明天会把今天讲的写成code!