Ted 带你学习数据结构 之 哈希表（hashTable)
Ted 带你学习数据结构 之 哈希表
申明一下，本章节部分内容是我在不同博文中选取，最终整合梳理得出
自认为适合从"小白猿"起点的学习，内容浅，只是作为入门读物;选取博文链接置于本章尾
- 什么是散列（hashing） ？
- 什么是哈希映射？什么是散列函数（hashing function）?
- 什么是哈希表？ （hash table）
- 什么是哈希表的索引？
- 哈希存储的结构是什么？
- 哈希表的查询效率？
- 什么是哈希碰撞？
- 哈希碰撞的解决办法？
- 什么是哈希碰撞攻击？
- java中散列的实现？
！ 散列
把关键码值映射到数组中的位置来访问记录这个过程称为散列 关于散列的解释啊，说实话，就像是看很古的文言文，明明是中文，确不得其意思;但我们至少可以get到2个很重要的点，一个是散列是一种“过程”，另外，是通过“把关键码映射到数组”这种过程实现的。 那接下来，我们要做的就是去慢慢理解这个“映射”过程。 Follow Me ! 不要掉队！在理解映射时，我们需要借助到数组结构
我们都知道 ，数组是有序且占用连续内存，我们可以通过索引index快速找到对应的值value.但是在数组中插入和移除数据是要耗费很高的效率（双向链表的结构特征，正好和数组相反，查找慢，但插入和移除效率高）
散列过程，其实就是为了利用数组有索引，查找快的特点，把一个值映射到数组里（可以理解，把值存在数组里），那既然在数组里，就会实现高效的查找。
我们来看看，它的这个过程是怎么实现的
根据上图，我们可以知数，有一个集合{a,b,c,d,e,f}（这里的集合是数学定义的集合，意思是说有这么a,b,c,d,e,f一丢数，并非指的java中的容器）将它们通过某个关系 f ,使它们分布到一个数组里面。
而这个过程，就是散列过程
！散列函数 哈希表
那么关系 f，是一种函数计算，它被称为散列函数，而通过散列函数，实现了映射关系，从而完成了散列过程。
把关键码值映射到位置的函数称为散列函数；也称为哈希函数（hashing function）;一般通f()表示 而通过散列后，得到的表结构，叫做哈希表；通过哈希表，我们拥有索引，实现快速查找 关键码key其实说的就是你的值但通过上图，仔细的你，肯定发现，为什么散列过程后，数组中索引为2的位置，里面装了2个对象，分别为b和c,而索引为1的地方，确是空值？
首些，我要告诉你，这种情况是避免不了的。
因为值的存放是根据一种算法函数来自动放置的，而并非你主观上发现有空的位置，把多的值add进去的。
那你肯定想问，为什么算法函数不均匀的把值分配到数组里？ （散列后得到的这个数组，每个数组单元被称为 槽）
原则上，我们的目的是希望均匀的把对象分布在对应的槽里，可是你想，如果我只是5个数据，我分配出一个5个size以上的数组给它，它应该会合理的均匀分布（其实不是，这种分配只是你主观上认为，而真正的分配是通过散列函数实现的），那如果，有千万级以上的数据，如果给这些数据每个都分配一个槽，那会不会这些槽连起来绕地球1圈？（说笑），即便你电脑性能好，那你想想，如果想在这个数组里，中间插入一个数值，那效率会不会低到你被老板辞掉？
而散列函数的定义，你要根据实际情况，（比如数据的特性，你最多能开辟多少槽，内存和性能的博弈），来制定最合理的算法，但因为空间位置有限（槽有限）），实再最大可能的均匀分配。
不过，说到这里，你肯定还是在嘀咕为什么不均匀放值的问题
别着急，我们再深入了解散列函数后，你就会知道答案了。
散列函数的定义要求
1、计算简单。哈希函数的计算时间（指的是产生地址的时间），不应该超过其他查找技术与关键字比较的时间。
2、 地址分布均匀。尽量让哈希地址均匀分布在存储空间中，这样可以使空间有效的利用。
（1）直接定址法
我们可以去关键字的某个线性函数的值作为哈希地址，如下所示：
f（key）= a*key + b （其中a，b均为常数）
特点：简单、均匀，也不会产生冲突，但是需要事先知道关键字的分布情况，适合查找表比较小且连续的情况。在实际中并不常用。
（2）数字分析法
可以使用关键字的一部分来计算哈希存储的位置，比如手机号码的后几位（或者反转、左移右移等变换）。
特点：通常适用于处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布均匀，就可以考虑用这种方法。
（3）除留余数法
这是最为常用的构造哈希函数的方法，对于哈希表长度为m的哈希函数为：
f（key）=key mod p （p<=m）
mod是取模（求余数）的意思。事实上，如果p选得不好，就很容易出现同义冲突的情况：
如上图所示，选择p=11，就会出现key=12、144的冲突 。
就是一个索引里有多个值，但试想，如果选择p作为被除数，那们这个数组的size也就最多是p-1，其实冲突是很难避免的。
而通过f(key)函数，得到结果就是值key在数组中的索引，而因为索引冲突的情况，造成了此类中12和144存放的冲突，也造成了上图中b和c的存放的冲突，当然也有可能，在连续的数组中，中间某个槽因为没有值算到它对应的索引，而使它是空的，也就是上而图中数组索引为1的地方是空的情况。s
这种冲突也称为哈希碰撞，粗浅可以看成是一个索引对应多个值
哈希碰撞的概念我们先放置一边，等会我们再着重去深挖。
继续，散列函数一般方法
（4）字符串
将字符串作为键的时候，我们也可以将他作为一个大的整数，采用保留除余法。我们可以将组成字符串的每一个字符取值然后进行哈希，比如
public int GetHashCode(string str)
{
char[] s = str.ToCharArray();
int hash = 0;
for (int i = 0; i < s.Length; i++)
{
hash = s[i] + (31 * hash);
}
return hash;
}
上面的哈希值是Horner计算字符串哈希值的方法，公式为:
h = s[0] · 31L–1 + … + s[L – 3] · 312 + s[L – 2] · 311 + s[L – 1] · 310
举个例子，比如要获取”call”的哈希值，字符串c对应的unicode为99，a对应的unicode为97，L对应的unicode为108，所以字符串”call”的哈希值为 3045982 = 99·313 + 97·312 + 108·311 + 108·310 = 108 + 31· (108 + 31 · (97 + 31 · (99)))
如果对每个字符去哈希值可能会比较耗时，所以可以通过间隔取N个字符来获取哈西值来节省时间，比如，可以 获取每8-9个字符来获取哈希值：
public int GetHashCode(string str)
{
char[] s = str.ToCharArray();
int hash = 0;
int skip = Math.Max(1, s.Length / 8);
for (int i = 0; i < s.Length; i+=skip)
{
hash = s[i] + (31 * hash);
}
return hash;
}
但是，对于某些情况，不同的字符串会产生相同的哈希值，这就是前面说到的哈希冲突（Hash Collisions），比如下面的四个字符串：
哎，突然联想到我们java基础里的知识点:equals返回true，俩个对象的hashCode方法一定相等；俩个hashCode相同的的对象，用equals返回不一定为true;
是不是终于知道原因了，因为是算法造成的啊。
当然，散列算法根据实际应用场景，可以有不同的自定义，以上只是提供一些思路而已。
!哈希碰撞的解决办法
拉链法 (Separate chaining with linked lists)
（这种办法底层实现基础 数组+链表 ）
通过哈希函数，我们可以将键转换为数组的索引(0-M-1)，但是对于两个或者多个键具有相同索引值的情况，我们需要有一种方法来处理这种冲突。
一种比较直接的办法就是，将大小为M 的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法。下图很清楚的描述了什么是拉链法。
图中，”John Smith”和”Sandra Dee” 通过哈希函数都指向了152 这个索引，该索引又指向了一个链表， 在链表中依次存储了这两个字符串。
该方法的基本思想就是选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率。对采用拉链法的哈希实现的查找分为两步，首先是根据散列值找到对应的槽，然后沿着链表顺序找到相应的键。 我们现在使用我们之前介绍符号表中的使用无序链表实现的查找表SequentSearchSymbolTable 来实现我们这里的哈希表。当然，您也可以使用.NET里面内置的LinkList。
首先我们需要定义一个链表的总数，在内部我们定义一个SequentSearchSymbolTable的数组。然后每一个映射到索引的地方保存一个这样的数组。
public class SeperateChainingHashSet<TKey, TValue> : SymbolTables<TKey, TValue> where TKey : IComparable<TKey>, IEquatable<TKey>
{
private int M;//散列表大小
private SequentSearchSymbolTable<TKey, TValue>[] st;//
public SeperateChainingHashSet()
: this(997)
{
}
public SeperateChainingHashSet(int m)
{
this.M = m;
st = new SequentSearchSymbolTable<TKey, TValue>[m];
for (int i = 0; i < m; i++)
{
st[i] = new SequentSearchSymbolTable<TKey, TValue>();
}
}
private int hash(TKey key)
{
return (key.GetHashCode() & 0x7fffffff) % M;
}
public override TValue Get(TKey key)
{
return st[hash(key)].Get(key);
}
public override void Put(TKey key, TValue value)
{
st[hash(key)].Put(key, value);
}
}
可以看到，该实现中使用
- Get方法来获取指定key的Value值，我们首先通过hash方法来找到key对应的索引值，即找到SequentSearchSymbolTable数组中存储该元素的查找表，然后调用查找表的Get方法，根据key找到对应的Value。
- Put方法用来存储键值对，首先通过hash方法找到改key对应的哈希值，然后找到SequentSearchSymbolTable数组中存储该元素的查找表，然后调用查找表的Put方法，将键值对存储起来。
- hash方法来计算key的哈希值， 这里首先通过取与&操作，将符号位去除，然后采用除留余数法将key应到到0-M-1的范围，这也是我们的查找表数组索引的范围。
实现基于拉链表的散列表，目标是选择适当的数组大小M，使得既不会因为空链表而浪费内存空间，也不会因为链表太而在查找上浪费太多时间。拉链表的优点在于，这种数组大小M的选择不是关键性的，如果存入的键多于预期，那么查找的时间只会比选择更大的数组稍长，另外，我们也可以使用更高效的结构来代替链表存储。如果存入的键少于预期，索然有些浪费空间，但是查找速度就会很快。所以当内存不紧张时，我们可以选择足够大的M，可以使得查找时间变为常数，如果内存紧张时，选择尽量大的M仍能够将性能提高M倍。
线性探测法
线性探测法是开放寻址法解决哈希冲突的一种方法，基本原理为，使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突。如下图所示：
对照前面的拉链法，在该图中，”Ted Baker” 是有唯一的哈希值153的，但是由于153被”Sandra Dee”占用了。而原先”Snadra Dee”和”John Smith”的哈希值都是152的，但是在对”Sandra Dee”进行哈希的时候发现152已经被占用了，所以往下找发现153没有被占用，所以存放在153上，然后”Ted Baker”哈希到153上，发现已经被占用了，所以往下找，发现154没有被占用，所以值存到了154上。
开放寻址法中最简单的是线性探测法：当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1，这样的线性探测会出现三种结果：
命中，该位置的键和被查找的键相同
未命中，键为空
继续查找，该位置和键被查找的键不同。
实现线性探测法也很简单，我们只需要两个大小相同的数组分别记录key和value。
public class LinearProbingHashSet<TKey, TValue> : SymbolTables<TKey, TValue> where TKey : IComparable<TKey>, IEquatable<TKey>
{
private int N;//符号表中键值对的总数
private int M = 16;//线性探测表的大小
private TKey[] keys;
private TValue[] values;
public LinearProbingHashSet()
{
keys = new TKey[M];
values = new TValue[M];
}
private int hash(TKey key)
{
return (key.GetHashCode() & 0xFFFFFFF) % M;
}
public override TValue Get(TKey key)
{
for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
{
if (key.Equals(keys[i])) { return values[i]; }
}
return default(TValue);
}
public override void Put(TKey key, TValue value)
{
int hashCode = hash(key);
for (int i = hashCode; keys[i] != null; i = (i + 1) % M)
{
if (keys[i].Equals(key))//如果和已有的key相等，则用新值覆盖
{
values[i] = value;
return;
}
//插入
keys[i] = key;
values[i] = value;
}
}
}
线性探查（Linear Probing）方式虽然简单，但是有一些问题，它会导致同类哈希的聚集。在存入的时候存在冲突，在查找的时候冲突依然存在。
同样，哈希碰撞的解决方案有多种，上面俩种只是为长规处理办法，也有利用开放地址法（再散列法）、公共溢出区法等，这部分可查看博文 数据结构之（一）Hash（散列），里面很多方案的介绍
!哈希碰撞攻击
我们知道如果哈希函数选择不当会使得大量的键都会映射到相同的索引上，不管是采用拉链法还是开放寻址法解决冲突，在后面查找的时候都需要进行多次探测或者查找， 在很多时候会使得哈希表的查找效率退化，而不再是常数时间。下图清楚的描述了退化后的哈希表：
哈希表攻击就是通过精心构造哈希函数，使得所有的键经过哈希函数后都映射到同一个或者几个索引上，将哈希表退化为了一个单链表，这样哈希表的各种操作，比如插入，查找都从O(1)退化到了链表的查找操作，这样就会消耗大量的CPU资源，导致系统无法响应，从而达到拒绝服务供给(Denial of Service, Dos)的目的。
!hash法查找效率
我们可以看到，哈希表存储和查找数据的时候分为两步，第一步为将关键字通过哈希函数映射为数组中的索引， 这个过程可以认为是只需要常数时间的。第二步是，如果出现哈希值冲突，如何解决，对于常用的拉链法和线性探测法我们可以讨论得到：
对于拉链法，查找的效率在于链表的长度，一般的我们应该保证长度在m /8~m /2之间，如果链表的长度大于m /2，我们可以缩小链表长度。如果长度在0~M/8时，我们可以扩充链表。
对于线性探测法，需要调整数组长度，但是动态调整数组的大小需要对所有的值从新进行重新散列并插入新的表中。因此，拉链法的查找效率要比线性探测法高。
不管是拉链法还是散列法，这种动态调整链表或者数组的大小以提高查询效率的同时，还应该考虑动态改变链表或者数组大小的成本。散列表长度加倍的插入需要进行大量的探测， 这种均摊成本不能忽略。
此外，hash表的查找效率还和负载因子有关，负载因子即hash表的记录数与哈希表的长度的比值，一般为0.7左右。冲突性的概率与负载因子的大小成正比，因此负载因子越大，查找效率越低。
! java中散列的实现
HashMap 是基于 HashTable 的一种数据结构，在普通哈希表的基础上，它支持多线程操作以及空的 key 和 value。
在 HashMap 中定义了几个常量:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
依次解释以上常量:
- DEFAULT_INITIAL_CAPACITY: 初始容量，也就是默认会创建 16 个箱子，箱子的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
- MAXIMUM_CAPACITY: 哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。
- DEFAULT_LOAD_FACTOR: 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
- TREEIFY_THRESHOLD: 上文说过，如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
- UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。
- MIN_TREEIFY_CAPACITY: 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
学过概率论的读者也许知道，理想状态下哈希表的每个箱子中，元素的数量遵守泊松分布:
当负载因子为 0.75 时，上述公式中 λ 约等于 0.5，因此箱子中元素个数和概率的关系如下:
这就是为什么箱子中链表长度超过 8 以后要变成红黑树，因为在正常情况下出现这种现象的几率小到忽略不计。一旦出现，几乎可以认为是哈希函数设计有问题导致的。
Java 对哈希表的设计一定程度上避免了不恰当的哈希函数导致的性能问题，每一个箱子中的链表可以与红黑树切换。
引用博文