浅谈Hash

非科班出身的补充学习

对`window.location.hash`的常见误区

路由里的#，可以通过window.location.hash来获得，但它和Hash算法没关系，叫hash仅仅是因为英语里电话按键上的#也念做hash或者“hash tag”
路由里的#代表网页中的一个位置，右侧的字符就是位置的标识符，符号本身和他后面的字符称之为“hash”。浏览器读取url后，会自动将网页的那个位置滚动到那个指定的位置。为网页指定标识符的方法有两种：
- 锚点：比如<a name="here"></a>；
- id属性：比如<div id="here"></div>。
#用于指导浏览器的动作，对服务器端完全无用（一般的网络爬虫也会忽略该部分），Http请求中不会包括#及其右边的字符串。（但对于%23——转义的#浏览器会将它作为实义字符处理）同样，改变#后的内容，浏览器不会重载网页，不会向服务器发起请求。但是会在访问历史中增加一个记录（ie6和7例外）——可以用来根据不同的#值来表示不同的访问状态（这在SPA或者桌面应用里经常使用）。
Google提出，将带有#!的url称为pretty AJAX URL，当爬虫遇到这样的url的时候，会将带有不同的hash tag的url当做不同内容过来抓取，从而获取更全的信息。也就是说，如果希望Ajax生成的内容被浏览引擎读取，那么URL中可以使用#!，Google会自动将其后面的内容转成查询字符串_escaped_fragment_的值。比如遇到http://twitter.com/#!/username就会去抓http://twitter.com/?_escaped_fragment_=/username。
监听window.location.hash的变化：支持HTML 5的，可以简单通过window.onhashchange事件；不支持HTML 5的可以通过定时器setInterval来监听。
browserHistory需要服务端配置，因为真实URL其实是指向服务器资源，比如API接口，也是一个真实URL的资源路径，当通过真实URL访问网站的时候，第一次访问的是网站的域名，这个时候可以正常加载网站的js等文件，而用户手动刷新网页时，由于路径是指向服务器的真实路径，如果服务器端没有做路由配置，就会导致资源不存在，用户访问的资源不存在，返回给用户的是404错误。通过hashHistory来生成的URL就不会出现这样的问题，因为他不是指向真实的路由。
值得一体的是单页面应用中，常常有类似sitename.com/#/pathname这样的url。和锚点看起来有一点不同。但本质上是同一个东西。第一个/其实就是location.pathname，spa有一个主入口，其页面的“跳转”其实是更换了主页面内的dom节点，比如通过<router-view></ router-view>这样的组件来实现。所以它的pathname是不变的，#和之后的东西，就是url的hash了（TODO: 至于为什么要增加一个/ ，我的猜想是避免触发锚点机制，毕竟真的锚点，name或者id里不会有斜杠这样的符号。)
值得一提的是，单页面应用并不仅仅只能使用hash路由，还可以使用history，利用路由api来完成页面的渲染。

科班教科书上提到的Hash

先来一段概念：

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过Hash算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，Hash值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从Hash值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
对于数据的处理无外乎以下几种：读取/更新/删除数据项，或者插入新项，其中除插入外其他几种操作均要求对集合进行搜索。结构化的模型可以通过数组、链表或者树形结构等建立，不同的建模方式对于数据处理中的各种操作有不同的性能表现。一般来讲，数据结构将直接影响对其处理的算法的选择，而特别的，散列函数算法又会反过来影响散列表这种结构之于数据的存储效率。
读取/更新操作均建立在搜索的基础上，因此运行效率取决于定位待操作的数据项的时间。
1. 对于数组，如果所存储的元素集是无序的，那么搜索集合中的任一元素的期望时间E=(1+2+…+n)/n=O(n)，因此搜索某个数据项几乎总是需要遍历整个集合。如果需要大量的搜索操作，那么对于现有集合可以通过排序执行适当的预处理，并在此之后调用运行时间为O(㏒n)的二分搜索以获得较好的整体性能。
2. 对于链表结构，因为其无法提供随机访问能力，因此这决定了即使对链表进行排序也无法运用二分搜索快速查找具有某个固定值的元素，并且同未排序的普通数组一样，链表的搜索操作的期望时间也为O(n)。
3. 为什么Hash表在数据结构的“查找”上具有优势？
  - 顺序查找，有“＝”和“≠”两种情况，在折半、二叉排序树查找和B-树查找的时候，有“＞”、“＜”和“＝”三种情况。核心都是“比较”，查找的花费就是比较的次数。
  - 在关键字和结构中一个唯一的存储位置间建立一个确定的对应关系h，查找的时候，根据对应关系h找到给定值K的象h(K)，如果结构中有和关键字K相等的记录，它一定存在h(K)的位置上，这样，查找的过程完全不需要比较就能直接得到所要查的记录，对应关系h就成为Hash函数，按这个思想建立的就是Hash表。
对于数据的删除操作，在有序数组中还需要将已删除数据项所占位置之后的元素逐个前移，使得在维持序关系时整个数组仍然保持紧凑，而在链表中，虽然只需改变待删除数据项的前驱的指向，但高效利用空间的前提条件将会要求维护一个空闲链表(freelist)，这些都需要额外的时间开销。至于优点，这两种结构对存储空间的利用率都很高。

Hash具有以下特点

典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。
对不同的关键字可能得到同一Hash地址，即key1≠key2，而f(key1)=f(key2)，这种现象称collision（冲突，或碰撞）。具有相同函数值的关键字对该Hash函数来说称做synonym（同义词）。通过选择合适的Hash函数可以减少这种冲突。但冲突只能减少不可能消除，所以，Hash函数不仅仅是一个映射，还需要有处理冲突的方法。
Hash可用在数据的“查找”上，也可以用在数据的“加密”上。根据算法的离散度和冲突概率来评定Hash算法的优劣。
若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个事先建立的表为散列表。Hash函数运用在字典表等需要快速查找的数据结构中，单个检查的时间为O(1)，而且不会随着数据量增加而增加。
加密方面，比较常用的有MD5和SHA，一个函数必然可逆，且由于HASH函数的值域有限，理论上会有无穷多个不同的原始值，它们的Hash值都相同。而MD5和SHA做到的，是求逆和求冲突在计算上不可能，也就是正向计算很容易，而反向计算难以做到。可以说，算一种数据的有损压缩。

关于Hash算法的应用

散列表仅仅只是Hash函数一个简单的应用，另一个具有重大意义的应用就是密码学。比如md2、md4、md5和sha-1。这要提一下王小云教授对MD5所采用的破解方式，2004年8月17日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组的研究成果——对MD5、HAVAL－128、MD4和RIPEMD四个著名密码算法的破译结果。次年二月宣布破解SHA-1密码。准确来说她所采用的方法不叫破解，而是构造了一种能够快速产生碰撞的方法，即给出一个p1，通过该方法可以很快算出一个不等于p1的p2使得 MD5(p1)=MD5(p2)，根据这一点就足以把MD5枪毙掉了。但这种方法并不意味着能根据MD5的Hash函数反算出明文来，亦即这是一种单向加密函数——不存在逆函数可以将密文重新变为明文。好的哈希算法使得构造两个相互独立且具有相同哈希的输入不能通过计算方法实现。
错误校验：使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方，对将要发送的数据应用散列函数，并将计算的结果同原始数据一同发送。在数据的接收方，同样的散列函数被再一次应用到接收到的数据上，如果两次散列函数计算出来的结果不一致，那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。比如还可以用在p2p下载的文件校验上。

Hash函数的构造方法

均匀的Hash函数（Uniform）：对于关键字集合中的任何一个关键字经过Hash函数映射到地址集合中任何一个地址的概率是相等的。这样，一组关键字的Hash地址均与分布在整个地址区间中，冲突比较少。
常见的构造Hash函数的方法有：
1. 直接定址法：
  取关键字或者其某个线性函数值为Hash地址。
  H(key)=keyorH(key)=a·key+b
2. 数字分析法：
  Hash表中可能出现的关键字都是事先知道的，而且关键字以r为基数（如以10为基的十进制数），可以取关键字的若干数位（或者其运算结果）组成Hash地址。（取法是排去那些容易造成冲突的）
3. 平方取中法：
  常用的一种，通常，在选定Hash函数时并不知道关键字的全部情况，可以取关键字平方后的中间几位为Hash地址——因为平方之后中间的几位和数的每一位都相关，由此随机分布的关键字得到的Hash地址也是随机的，取的位数由表长决定。
4. 折叠法：
  当关键字位数较多，且每一位上数字分布大致均匀的时候，可以将关键字分割成位数相同的几部分（最后一部分的位数可以不用），然后取这几部分的叠加和（舍掉进位）作为Hash地址。
  - 移位叠加：将分割后的每一部分的最低位对齐然后相加；
  - 间界叠加：从一端向另一端沿分割界来回折叠，然后对齐相加。
    需要预估总量大概在什么范围内，然后再给定范围，如10000以内，则即使记数的有10位数字，也可以只取其中4位来折叠（这样肯定是在0-9999范围内）。
5. 除留余数法：
  最简单也最常用的，取关键字被某个不大于Hash表表长m的数p除后所得余数为Hash地址，也就是
  H(key)=key mod p, p≤m
  重点是p的选取，一般可以选取一个质数或者不包含小于20的质因数的合数。
  这是因为，输入的关键字集合，其特征是不固定的，所以我们要保证不论是什么关键字集合被输入，其Hash值都应该有均匀的分布。举个例子，H(key)=key mod 6，如果输入的集合是[0,2,4,6,8,10]那么计算出来的Hash地址是[0,2,4,0,2,4]，但如果采用h(key)=key mod 7，则是[0,2,4,6,1,3]很显然，后者得到了一个更加均匀的Hash表。同样可以证明，如果M=km，那么对于r=N mod M这样的计算，其实r是被压缩的集合，因为当N=kn,M=km，r其实就是k的倍数，本
6. 随机数法：
  当关键字长度不等时，可以选一个随机函数，取关键字的随机函数值作为其Hash地址。也就是：
  H(key)=random(key)其中random是一个随机函数。
选取Hash函数的考虑因素：
1. 计算Hash函数所需时间
2. 关键词长度
3. Hash表大小
4. 关键字分布情况
5. 记录的查找频率

冲突的处理方法

处理冲突，就是为关键字的记录找到另一个“空”Hash地址，在处理冲突时，若得到的另一个Hash地址仍然发生冲突，就再求下一个地址，直至不发生冲突，此时的地址为记录在表中的地址。
常用的处理冲突的方法：
1. 开放定址：
  H_i=(H(key)+d_i) MOD m; i=1,2,…,k (k≤m-1)
  其中m为Hash表长；d_i为增量序列，根据它的取法可以分为：线性（1,2,…,m-1）、二次（1², -1²,2²,-2²,…,±k² k≤m/2）、伪随机数探测再散列。
  处理同义词的冲突过程中，会增加非同义词的冲突，但是可以保证做到只要表没有填满就总能找到一个不冲突的地址——显然这对”查找“是不利的。
2. 再Hash：
  当同义词产生地址冲突的时候，计算另一个Hash函数的地址，直到冲突不在发生：
  H_i=RH_i(key) i=1,2,…,k
  其中R和H_i是不同的Hash函数，显然，这样增加了计算的时间。
3. 链地址：
  也就是将所有关键字是同义词的记录，都存储在同一个线性链表中。
  假设某个Hash函数产生的Hash地址在区间[0, m-1]上，就设立一个指针型的向量Chain ChainHash[m]，其每个分量的初始状态都是空指针。所有Hash地址为i的记录就都插入到头指针为ChainHash[i]的链表里——在表内的插入位置可以是约定是表头、表尾或者中间，以保证同义词在同一线性链表中按关键字是有序的。
4. 公共溢出区：
  假设Hash函数的值域是[0,m-1]，设向量HashTable[0..m-1]为基本表，每个分量存一个记录；再设向量OverTable[0..v]为溢出表。所有关键字和基本表中的关键字为同义词的记录，不管他们由Hash函数得到的Hash地址是什么，一旦发生冲突，就填入溢出表。

Hash表的查找和分析

查找过程和造表过程类似，给定关键字，根据造表的Hash函数求Hash地址：
- 对应的地址上没有记录，那就是查找失败，没有结果
- 对应的地址上有记录，就比较关键字：
  - 关键字和给定的关键字相等，查找成功
  - 否则，根据造表的时候设定的冲突处理方法寻找“下一个地址”循环以上步骤。
由于冲突的不可避免，查找Hash表的过程，其实就是一个给定值和关键字进行比较的过程，需要以“平均查找长度”来衡量Hash表的查找效率。
- Hash函数的“好坏”首先影响了冲突的频繁程度，所以要设计“均匀的”Hash函数。
- 不同的冲突处理办法会影响表结构，比如线性探测再散列在处理冲突中容易产生记录的二次聚焦——Hash地址不相同的记录又产生新的冲突；链地址法处理冲突则不会有以上问题。
- 处理冲突方法相同的Hash表，其平均查找长度依赖于Hash表的装填因子。
  - Hash表装填因子load factor=表中填入的记录数/Hash表的长度；
  - 它标志着Hash表的装满的程度，越大说明已经填入的记录越多，那么再填入记录的时候，冲突的可能性就越大，查找时需要比较的次数也就更多。
  - 不同的冲突处理方法的表，其查找成功和不成功时的平均查找长度，可以计算出来是和“装填因子”（这就是为什么要计算“装填因子”，而且计算的方法很简单，可以当做已知数）关联并且可以被证明的（都是约等于）大致的思想其实就是：长度m的表里，已经有n个记录的时候，查找不成功的平均查找长度就等于要插入第n+1个记录时需要做的比较次数的期望；而查找不成功的平均查找长度，由于Hash表中的n个记录都是先后填入的，所以查找每一个记录的所需的比较次数的期望，就是填入此记录时找到此Hash地址时所进行的比较次数的期望。
计算之后发现，平均查找长度是“装填因子“的函数而不是已记录数的函数，所以，总可以选择一个合适的”装填因子“来控制平均查找长度。
值得一提的是，除了链表地址法，删除一个记录后，要在原有记录上填入一个特殊的符号做标记，否则会影响其他同义词的查找。
计算装填因子是很有意义的，可以通过监视装填因子，来决定是否对表扩容。比如mod 31，改成mod 37。又比如，增加一层算法。

Hash表的容量扩张Expand和分摊转移

根据load factor的定义，一旦load factor ≥ 1那么就不应该继续往里加入新元素，否则就不能保证查找的期望时间的复杂度是常数级了，这时候就应该对Hash表做扩张。
一种思路是发现load factor == 1的时候，就开辟一个原表两倍的新表，然后把原表中的数据都转移到新的表里。转移的方式可以有多样，如果一次性转移完，或者说一次性扩张完，要花费较长的时间等待，
redis中的dict.c的设计思路是，用2个Hash表来进行扩容和转移：当第一个表的load factor == 1时，第二个表开辟为2倍大小然后轮流做“插入新数据”和“转移表1的数据”这样的操作——也就是把第一个Hash表的转移分成多次转移，每次转移的期望时间都是O(1)。这样的好处是，表满了的时候，不会出现某一次往表里插入元素要等待非常长时间的情况。转移结束后，就释放第一个表的空间。

表驱动法

这是一种编程模式（scheme）：不是通过逻辑语句if和case而是从表里查找信息——事实上，凡是能通过逻辑语句选择的，都可以通过查表来选择，逻辑链越长越复杂，查表法就越有利。
其实就是拿空间换时间。
表驱动法的优势之一，就是可以把表的数据放在文件中，在程序运行的时候再读取这些数据，这样就可以在不改动程序本身的情况下调整参数。

使用总则

必须明确怎样从表中查询条目：可以用一些数据来直接访问表，也可以通过索引访问，还可以通过阶梯访问。
明确应该在表里存什么：有的时候是数据，有的时候需要的，是动作action。在后一种情况下，可以保存一个描述动作的代码，或者实现该动作的子程序的引用，这些都会让表变得复杂。
从另外一种说法来讲，表驱动法其实就是两个过程：提取共性，做到为每个元素做一样的事，把共性放到表里，用查表代替switch；提供支持函数，因为提取共性后会有要为这些共性服务的函数。后者才是关键。
表驱动法其实是简化上层的实现逻辑，提高代码的弹性，降低增减内容的成本，甚至做到动态支持。

直接访问表

比如每个月的天数：用一个长度12的数组来保存，然后很简单的就可以查询每个月的天数。
又比如和年龄相关的，不必每个年龄做一次判断，直接使用“以年龄为下标”的数组即可。
具有复杂参数的，完全可以把所有参数作为查表的形参。
可以用表来描述有太多的变化，多到无法用代码表示的逻辑。一个例子，有若干对象，其格式不固定，不同的做法会有不同的结果：
- 基于逻辑的做法Logic-Based Approach
  - 不得不读取每一条对象，检查某个字段，然后调用一个处理一种对象的子程序，还不包括用于支持子程序的底层程序。
  - 每一次有任何一种对象的结构变了，就要重新修改负责这种对象的子程序。
  - 子程序还包括一个循环，用于读入对象，解析特征。
- 面向对象的方法Object-Oriented Approach
  - 问题的逻辑将被隐藏在对象继承结构里，但是基本结构还是复杂。
  - 并不比基于逻辑的方法简单，每一种对象都有自己的子程序，增加一种就要修改代码。
- 表驱动法Table-Driven Approach
  - 读取子程序由一个循环组成，此循环负责读取每一个对象的特征，对其解码，然后每次都调用同一个子程序来处理
  - 可以用一张表描述每一种消息的格式，无须修改代码就能维护。
  - 比如，可以先列出所有的可能的字段，只创建少数几个子程序，分别负责一种字段。可以吧每种对象的内容放在一张表里，包括每个字段的名称，再根据表中的描述来分别解释每一个对象。
  - 表可以硬编码在程序里（每个元素都赋给一个变量）也可以在程序启动的时候或者之后从文件中读取。一旦读入程序，就能把所有的对象嵌入在数据里而不是程序的逻辑里了。
  - 数据要比逻辑更加灵活。修改数据是很容易的。
构造查询键值Fudging Lookup Keys能直接得到访问表的键值自然是最好的，但并不能总如此——所以有构造查询表键值的问题：
- 复制信息从而能够直接使用键值：复制生成的冗余信息会浪费空间，并且产生错误的可能性也变大了
- 转换键值以使其能直接使用：要求能够从打算用作键值的数据中识别出某种模式来。
- 把键值转换提取成独立的子程序：可以避免在不同位置执行了不同的转换，也使得转换操作修改起来更加容易。有的开发环境中提供了现成可用的键值转换功能，比如Java中提供的关联型容器HashMap，可以用作根据键值key查出实值value

索引访问表Indexed Access Tables

有的时候，无法通过简单的计算把数据转换为表键值。
可以先用一个基本类型的数据，从一张索引表中查出一个键值，然后再用这个键值查出对应的主数据。
这个创建索引表的过程，其实就相当于创建了一个Hash表，用较小的空间来存储
即使使用了索引之后，没有节省内存空间，操作位于索引中的记录有时也比操作位于主表中的记录更加方便和廉价。针对一个表，其实可以准备多个索引表来访问。
最后一个优点就是表查询技术在可维护性上的优势。还可以将这个灵活性最大化：把借助索引访问数据的代码提取成单独的子程序，然后在希望通过某个key获得表键值的时候调用，当需要修改表的时候，可以考虑更换这种索引访问技术，或者换用另一种表查询的技术，如果不把索引访问代码随便地写到应用程序中的各个地方，那么这种访问技术更改起来是非常容易的。

阶梯访问表Stair-Step Access Tables

不像索引访问那么直接，但是更加节省空间。
基本思想：表中的记录，对于不同的数据范围有效，而不是对不同的数据点有效。
比如说，划分范围彼此有覆盖，又是浮点数，不能用索引。
为了使用阶梯法，要把每一区间的上限写入一张表，然后写一个循环，按照各区间的上限来检查入参，当入参第一次超过某个区间的上限时，就知道相应的阶梯了。
使用阶梯方法，必须很谨慎的处理范围的端点
阶梯法的优点在于它很适合处理那些无规则的数据。无规则的数据，是不可能用一个函数把他们整齐地转换成表键值的，阶梯法才是正确的处理方式。
阶梯法使用中需要注意的细节：
- 留心端点：
  1. 确认已经考虑到了每一个阶梯区间的上界。
  2. 进行阶梯查询找出位于上界之外的项目，把剩下的那些项目归于最上一级范围内
  3. 这样做有时候需要为最高一级区间的最高点假拟出一个值
  4. 不要把＜误用成≤，确认循环能够在找出最高一级的区间之后，恰当的终止
- 考虑用二分查找取代顺序查找。
  1. 作为在等级界限的列表中查找的循环，如果是很大的列表，这个顺序型的查找的成本会成为效率的一种制约。
  2. “准二分查找法”：大多数二分查找的主要目的都是要找到一个数值，而阶梯法中，是要为某一个数值找到正确的分类，所以这里的二分查找略有不同，要正确判断数据的归属并且把端点作为一种特殊的情况来对待。
- 考虑用索引访问来取代阶梯法。
  1. 阶梯法中的查找操作比较耗时，如果执行速度很重要，那么可以牺牲存储空间来换取速度
  2. 这种“替代”的做法不是任何时候都适用的。且不说内存成本，有些时候，就是没法把一些数据作为记录的键值。
- 把阶梯表查询操作提取成单独的子程序

表查询的其他示例

根据一个数据来查询表很简单，如果关联的有多个逻辑怎么办？比如有a、b、c三个因素，是否又会写成复杂的逻辑？完全可以用多维数组来做，比如arr[a][b][c]或者arr[ab][c]。

HashMap

什么是HashMap

在java语言中，最基本的结构是数组和模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造。HashMap实际上是一个数组和链表的结合体（在数据结构中，称为“链表散列”）。
往HashMap中put元素的时候，先根据key的Hash值得到这个元素在数组中的位置（也就是下标）如果这个元素的所在位置上已经有其他元素了，那么在同一个位置上的元素将以链表的形式存放，新加入的放在链头。从HashMap中get元素的时候，首先计算key的hashCode，然后通过key的equal方法在对应的位置的链表里找到需要的元素。

一般用以下函数来取hashCode，以获得较为均匀的分布

1
2
3

static int indexFor(int h, int length) {
  return h & (length-1); // 这里用到了一个“按位与”的运算。
}

HashMap中的元素个数超过“数组大小*装载因子”的时候（一般而言装载因子loadFactor的默认值取0.75），就应该进行数组扩容（resize）。

Java里的hashCode

在Java的Object类中有一个方法:public native int hashCode();
hashCode的主要作用是为了配合基于散列的集合一起正常运行，包括HashMap, HashMap, HashTable
当集合需要插入一个对象时，用equals方法去逐一比较，其效率是有问题的。先调用这个对象的hashCode方法，得到值。而在HashMap的具体实现里，会用一个table来保存已经存进去的对象的hashCode，如果没有，则插入，有则用equals方法和新元素对比，相同的话不存，不相同就散列其他地址。
有些JVM在实现的时候，hashCode返回的就是对象的存储地址，但是大多不是这样。
判断两个对象是否相等，不应当通过hashCode，而要通过equals方法。
有些时候，在设计一个类的时候需要重写equals方法，同时还要重写hashCode方法，以维护 hashCode 方法的常规协定。

对window.location.hash的常见误区

科班教科书上提到的Hash

Hash具有以下特点

关于Hash算法的应用

Hash函数的构造方法

冲突的处理方法

Hash表的查找和分析

Hash表的容量扩张Expand和分摊转移

表驱动法

使用总则

直接访问表

索引访问表Indexed Access Tables

阶梯访问表Stair-Step Access Tables

表查询的其他示例

HashMap

什么是HashMap

Java里的hashCode

对`window.location.hash`的常见误区