今天，你hash了吗
?今天，你hash了吗
Hash，如果对一个学英语的人来说，肯定翻译成“混杂，拼凑，搞糟，把…弄乱”。
最近的各种事务真的把我hash了，以至于没有认真研究hash，只好hash了一篇博客。
?
?
Hash表作为一种数据结构，事实上就是数组与链表的“混杂”，产生的原因也很简单：对于海量的数据，我们希望能够查找快捷，同时满足数据本身的增删方便。这两个优点分别在数组和链表中展现无遗，数组的下标有利于直接对应查找，而链表的指向性又方便了数据的动态改变。
?
?
为了中和二者优点，一种称为hash表的数据结构诞生了。
事实上哈希表有多种不同的实现方法，我解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：
?
?
Hash表结合了数组与链表的优点体现在：
?
?
1、将数据根据数组长度进行分类。假设这个数组长度为16，用皮球来类比数据。就好比将所有皮球放到16个箱子里，任意一个皮球只能放在其中一个箱子，并且放在哪个箱子和皮球本身的特性有关。那么我们在寻找某个皮球时就只用在某个箱子里去找，因为这个箱子里的皮球都是这个特性，这样数据的检索量就大大缩减了，理想情况下缩减为1/16。
?
?
2、用链表解决hash冲突。事实上数据量一般会比数组长度大，这样很有可能多个数据对应同一个数组下标的空间，而数组本身不像箱子，它只能装一个数据，多出来的，就通过链表在后面动态增长。
?
?
当我们手动实现时，其实就是先写一个链表，再写把链表与数组相连。
?
一：一个简单的链表节点
?二：我把对链表的数据处理封装了起来
?
??三：hash表的实现，直接调用方法
??
四：rehash
?
黄金无足色，白璧有微瑕，任何一个数据结构都是有弱点的，不然也不会产生多种数据结构共存的繁荣景象。
?
当数据量不断增加时，可能链表长度已经非常长了，数组长度就相对比较小，直观上就像一个狭长的长方形。
（当然如果数组长度过长，数据量很少就进入另一个极端了：
这都是要避免的，毕竟最美的长方形是长宽符合黄金分割比的， 什么形状大家懂得。）
?
?
所以，数组在数据量到达一定情况时要增长，这个过程叫做rehash
就是重新开一个更长的数组空间，将所有数据根据这个空间长度重新放进去，以追求一个完美的长方形。
?
??hash的应用很广泛，我只是模仿了其中最最最基本的部分，还有更多的有待继续hash，不过今天就hash到此吧~
<!--EndFragment--><!--EndFragment-->
