【C#集合】Hash哈希函数散列函数摘要算法
希函数定义
哈希函数（英語：Hash function）⼜称散列函数、散列函数、摘要算法、单向散列函数。散列函数把消息或数据压缩成摘要，使得数据量变⼩，将数据的格式固定下来。该将数据打乱混合，重新创建⼀个（哈希函数返回的值）称为指纹、哈希值、哈希代码、摘要或散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常⽤⼀个短的随机字母和数字组成的字符串来代表。好的散列函数在输⼊域中很少出现。
完美哈希函数就是指没有冲突的哈希函数。
如今，散列算法也被⽤来加密存在数据库中的（password）字符串，由于散列算法所计算出来的散列值（Hash Value）具有不可逆（⽆法逆向演算回原本的数值）的性质，因此可有效的保护密码。
enum函数
使⽤哈希函数为哈希表编制索引称为哈希或分散存储寻址。
单向散列函数（one-wayhash function），也就是通俗叫的哈希函数。
第⼀个特点：输⼊可以任意长度，输出是固定长度
第⼆个特点：计算hash值的速度⽐较快
第三个特点，冲突特性（Collision resistance）：出任意两个不同的输⼊值 x、y，使得 H （x）= H （y）是困难的。（这⾥称为「困难」的原因，是消息空间是⽆穷的，⽽是有限的，因此⼀定会存在碰撞，只是对寻碰撞的算⼒需要有难度上的约束以哈希函数SHAI （输出为 160-bit）为例：其输出空间为（0，2^160），假设输出范围⼀万亿个哈希值，发⽣碰撞的概率仅为 3×10-25。被碰撞的概率太低，⼏乎不可能。
第四个特点：隐藏性（Hiding）或者叫做单向性（one-way）：哈希函数的单向性意味着，给定⼀个哈希值，我们⽆法（很难）逆向计算出其原像输⼊。
第五点：谜题友好（puzzlefriendly）
HashTable
定义
哈希表时保存数据的表。通过哈希函数使得数据和存储位置之间建⽴⼀⼀对应的映射关系。在查时，通过哈希函数可以直接到该元素。
HashTable负载因⼦
负载因⼦ = 填⼊表中的元素个数 / 哈希表的长度
负载因⼦是哈希表装满的标志因⼦，由于表长是定值，负载因⼦与填⼊标志元素的个数成正⽐，所以负载因⼦越⼤，填⼊表中的元素个数越多，产⽣冲突的可能性越⼤，反之，负载因⼦越⼩，填⼊表中的元素个数越少，产⽣冲突的可能性越⼩。
对于闭散列，负载因⼦是⼀个很重要的因素，因该严格控制在07~0.8左右。超过0.8，CPU缓存命中率降低。所以，在闭散列中，⼀般负载因⼦超过0.7就会进⾏扩容处理。
为什么在散列表中不在负载因⼦等于1时扩容？
因为当哈希表快满了的时候，插⼊数据，冲突的概率很⼤，然后需要查插⼊位置。会导致效率降低。
HashTable中避免哈希函数冲突的⽅法
哈希函数的⽬标是尽量减少冲突，但实际应⽤中冲突是⽆法避免的，所以在HashTable 中哈希函数冲突发⽣时，必须有相应的解决⽅案。⽽发⽣冲突的可能性⼜跟以下两个因素有关：
（1）装填因⼦α（⽤于判断何时扩容hashtable core 是0.72 java是0.75）：所谓装填因⼦是指合希表中已存⼊的记录数n与哈希地址空间⼤⼩m的⽐值，即α=n / m ，α越⼩，冲突发⽣的可能性就越⼩；α
越⼤（最⼤可取1），冲突发⽣的可能性就越⼤。这很容易理解，因为α越⼩，哈希表中空闲单元的⽐例就越⼤，所以待插⼊记录同已插⼊的记录发⽣冲突的可能性就越⼩；反之，α越⼤，哈希表中空闲单元的⽐例就越⼩，所以待插⼊记录同已插⼊记录冲突的可能性就越⼤；另⼀⽅⾯，α越⼩，存储窨的利⽤率就越低；反之，存储窨的利⽤率就越⾼。为了既兼顾减少冲突的发⽣，⼜兼顾提⾼存储空间的利⽤率，通常把α控制在0.6～0.9的范围之内，C#的HashTable类把α的最⼤值定为0.72。
（2）与所采⽤的哈希函数有关。若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从⽽减少冲突的发⽣；否则，就可能使哈希地址集中于某些区域，从⽽加⼤冲突发⽣的可能性。
HashTable中哈希函数冲突解决⽅法
冲突解决技术可分为两⼤类：开散列法（⼜称为链地址法）和闭散列法（⼜称为开放地址法）。哈希表是⽤数组实现的⼀⽚连续的地址空间，两种冲突解决技术的区别在于发⽣冲突的元素是存储在这⽚数组的空间之外还是空间之内：
（1）开散列法也叫链地址法、拉链法（JAVA采⽤这种⽅式）发⽣冲突的元素存储于数组空间之外。可以把“开”字理解为需要另外“开辟”空间存储发⽣冲突的元素。
开散列⼜叫链地址法(开链法)，哈希表中的数组是⼀个指针数组。数据是以链表的形式保存，数组的元素指向链表的头节点。
⾸先，数据通过哈希函数计算出保存位置，计算出来相同位置的数据归于同⼀个集合中，每⼀个⼦集和称为⼀个桶，每⼀个桶中的元素通过链表连接起来，链表的头结点保存在哈希表中。
将哈希冲突的数据⼀链表的⽅式保存在⼀个位置。不会占⽤其它数据的位置。
开散列增容：
开散列增容看的也是负载因⼦。
桶的数量是⼀定的，因为数组的数量⼀定。随着元素的不断插⼊，桶中元素的数量会不断增多，极端情况下，可能会导致⼀个桶中数量链表结点⾮常多，在查元素时，会影响哈希表的效率。
因此在⼀定情况下要对哈希表进⾏增容。该条件怎么确认呢？最好的情况下，是每⼀个桶正好⼀个结点，在插⼊数据会发⽣哈希冲突，。
因当插⼊元素个数正好等于桶的个数时，即负载因⼦等于1时，可以给哈希表增容。
增容时，会按照哈希函数重新改变位置，减少冲突。
（2）闭散列法/开放定址法（ core 采⽤这种⽅式）发⽣冲突的元素存储于数组空间之内。可以把“闭”字理解为所有元素，不管是否有冲突，都“关闭”于数组之中。闭散列法⼜称开放地址法，意指数组空间对所有元素，不管是否冲突都是开放的。
线性探测
插⼊
通过哈希函数获取插⼊位置
如果该位置没有元素，直接插⼊新元素。如果有元素，发⽣哈希冲突，在冲突位置顺序往后下⼀个空位置，插⼊新元素。
删除
通过线性探测插⼊元素，我们知道哈希冲突的元素，⼀定会保存在保存位置的连续且不为空的位置，意
思就是哈希冲突的数据时，往哈希冲突位置往后到为空位置截⾄。所以删除数据时，不能随便删除数据。如下：
因此线性探测采⽤标记的伪删除来删除⼀个元素，就是哈希表中保存的是⼀个结构体，结构以⾥有⼀个变量保存数据，⼀个变量了代表当前位置的状态。
//状态
enum State{
EXIT,//存在元素
DELETE,//该位置为删除状态
EMPTY,//该位置为空，不存在元素
};
//保存的元素类型
struct Ele{
T _data;//数据
State _state = EMPTY;//状态
};
【来源：python.iitter/other/68944.html，转载请注明】
线性探测缺点：⼀旦发⽣哈希冲突，所有冲突的数据都会连在⼀起保存，容易产⽣数据堆积，此时插⼊⼀数据时，可能⼀段位置全被占⽤了，⼀直要空位置，导致效率降低。
⼆次探测
针对线性探测导致冲突数据堆积的缺点，⼆次探测空位置的⽅法是：
Hi = (H0 + i * i) % capacity，H0是⼀开始数据保存的位置，也就是冲突位置，Hi查的空位置。这样查可以使得冲突数据位置的错开的。
哈希函数算法「家族」
从哈希（Hash）函数这⼀概念诞⽣⾄今，已经提出了⼏⼗种
，每类算法对应不同的参数⼜会形成不同的算法实现。众多的哈希函数如同⼀个江湖，其中 MD 家族和 SHA 家族是「哈希江湖」中最具声望的两⼤家族。
国际： MD4、MD5、SHA-1、SHA-256、SHA-3。（MD 系列、SHA-1 已被破解）
国内：国产⾃主研发的商⽤密码哈希算法，即 SM3。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。