哈希作为一种数据结构通过索引获取对应的值，Perl把哈希作为一种数据类型，这是一种很方便的做法（我们可以直接使用哈希这样的数据类型）
以下，『哈希』和『散列』二者是可以做宏替换的（在语意上完全相同）
『哈希』是英译（它的英文名叫Hash，也可以译作『散列』，以下为了文字都写作『哈希』），就是把任意长度的输入（也叫预映射，pre-image），通过哈希算法，变换成固定长度的输出，该输出就是哈希值（value）——哈希 = 预映射（键，key） + 哈希值（值，value）
通过哈希算法进行的这种转换是一种压缩映射，也就是，哈希值的空间通常小于输入的空间，不同的输入可能形成相同的输出，所以不可能从哈希的值来确定唯一的输入值（不妨想想一个在某一区间上不单调的函数，有助于理解）
是根据存储数据的关键码直接进行访问的数据结构，也就是说，它直接把关键码也映射到表中的一个位置来访问记录（这个映射函数就是哈希函数），存放记录的数组就叫『哈希表』
哈希函数实现的物理基础就是『哈希表』
前面讲的很清楚，哈希就是通过『某种方法』将哈希的『键』映射到哈希的『值』，这里某种方法指的就是『哈希函数』
哈希函数通过映射关系实现数据存储位置和存储值的一一对应（一一映射），写成表达式就是Addr = Hash(key)，这里key作为变量输入，求的的是Addr即哈希值所在的地址（必然是一一对应的）
设计一个哈希函数，一般要考虑以下几点：
1）计算哈希函数所需的时间
2）关键字的长度
3）哈希表的大小
4）关键字的分布情况
5）记录的查找频率
实现哈希函数的几种常规思路：
1）直接寻址法：取关键字或关键字的某个线性函数为哈希地址，即H(key) = key或H(key) = a * key + b （a、b为常数）；这样产生的哈希函数叫自身函数（字面意思，就是关于自身的函数）
2）数字分析法：当关键字的位数大于地址的位数。对关键字的各位分布进行分析。选出分布均匀的任意几位作为哈希地址；这种方法仅适用所有关键字都已知的情况，根据实际情况确定要选取的部分，尽量避免Collision的发生
3）平方取中法：先计算关键字的平方，再取平方值的中间几位作为哈希地址；随机分布的关键字，得到的哈希地址也是随机分布的
4）折叠法（叠加法）：将关键字的分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为哈希地址；该方法用于关键字的位数较多，并且关键字的每一位上数字分布大致均匀的情况
5）随机数法：选择一个随机数，把关键字的随机函数值作为它的哈希值；通常当关键字的长度都不相等时用该方法
6）除留余数法：取关键字被某个不大于哈希表长度m的数求余数，得到的数作为哈希地址，即H(key) = key % p（p<m）
构造哈希函数的方法有很多，具体问题要做到具体对待；比如上面当关键字是正数时考虑除留余数法，关键字是小数时选择随机数法较好
哈希函数有以下几点性质：
1）对于任意y，寻找x，使得f（x） = y，在计算上是不可行的
2）给定x1属于A，找x2属于B，使得f（x1） = f（x2），这就是弱无碰撞性
3）寻找x1，x2，使得f（x1） = f（x2），在计算上也是不可的，这就是强无碰撞性
基于以上三点，保证了Hash函数的安全性
哈希碰撞，也叫哈希冲突
对于不同的关键字如果映射到同一个地址上，即k1≠k2，而f（k1） = f（k2），这种现象称为哈希碰撞
为了解决这个问题，有如下几种做法：
0）多哈希法
看名字就知道，在一个程序中构造两个甚至多个哈希函数，这是很朴素的想法，通常这样问题就解决了（除非人品问题），不过我们要优雅，不会轻易就做一些重复的事情，对于哈希冲突我们还有以下的解决方案
1）拉链法（链接法）：
拉链法的做法是将所有关键字为同义词的结点链接在同一个单链表中
拉链法中，通常在数组中存储某个哈希地址的头指针（不存储值，或者说存储的值为NULL）
拉链法查找和删除的（最坏）时间复杂度为O（N）
现在如果要查找哈希表中的某个值，先根据输入的键找到对应的哈希地址，再在这个哈希地址对应的单链表中寻找相应的值（遍历这个链表），之后对于共享相同哈希地址的结点我们用尾插法把新结点插到单链表的尾部
拉链法比较好想到，不过难以实现
2）开放寻址法
所谓开放寻址法，就是说『对于给定的输入键值，会进行多次试探，如果符合要求的话就定下地址』，也就是说，在开放寻址法中，元素的哈希地址的备选可能有多个
公式：H0 = H(key) Hi = (H(key) + di) % m (0≤i≤m-1)
我们可以取每次试探的偏移增量di为i（线性试探），H（key）就取key值于是上述公式变为： Hi = (key + i) % m (0≤i≤m-1)
这里有一个线性试探形象的演示：开放寻址法的Flash演示
除了上面讲的，还有别的解决哈希冲突的方案（拉链法、开放寻址法较为常见）；比如，我们对于那些（因为哈希地址冲突）溢出的元素，可以为它们建立一个单独的『公共溢出区』——不过如果溢出的元素太多，那就失去哈希的作用了，还不如不要用哈希（这时候就要考虑重写Hash函数了）
Perl中的哈希，不还是Hash嘛！所以上面讲的统适用
在《Perl语言入门》这本书中，给出了两张形象的图片：
需要注意的是，在Perl的哈希中，键都是字符串类型，即使显示的写出算数表达式（如50/2），也会在运算后将所得结果（2.5）转换为字符串类型（这里就是占3个字符大小的一个字符串）
另外，虽然键是唯一的，但是值是可以重复的（再想一下那个不单调函数）
使用%符号声明一个哈希
%my_hash = ('a',1,'b',2,'c',3); #Perl会按照顺序两两配对为一个哈希，这里比如a就对应1，b对应2 %my_hash = ('a'=>1, 'b'=>2,'c'=>3); #或者使用推导符号，这样可读性较好访问哈希，就是根据哈希的键访问哈希的值
$my_value = $my_hash{'a'}; #类似于数组的访问模式，不过这里是花括号而非方括号 $my_hash{'a'} = 10; #赋值什么的还是老规矩，如果对某个已经存在的哈希赋值会覆盖原来的值