散列表(hash table 哈希表)，是根据关键码值(key value)而直接进行访问的数据结构.如python的dict类，C#的Dictionary类，C++的map类，java的HashTable类

通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度

这个函数叫做散列函数，存放记录的数组叫散列表

def ELFhash(self, key : str, mod):
        h = 0
        for c in key:
            h = (h << 4) + ord(c)
            g = h & 0xF0000000
            if g != 0:
                h ^= g >> 24;
            h &= ~g;  
        return h // mod  

哈希表是一个通过哈希函数来计算数据存储位置的数据结构，通过支持如下操作：

• Insert(key, value):插入键值对(key, value)
• Get(key):如果存在键为key的键值对，则返回其value，否则返回null
• delete(key):删除键为key的键值对

哈希表的优势：高效，读写操作甚至可以做到O(1)的时间复杂度

• 无法处理关键字不是数字的情况

• 当域U很大时，对于有限的内存，存储大小为|U|的一张表T很不实际

• 若关键字集合T相对于U很小，分配给T的大部分空间都要浪费掉

解决方案为使用哈希函数h，根据关键字k计算出槽的位置.函数h将关键字域U映射到哈希表T[0..m-1]的槽位上

• IPv4的格式：A.B.C.D 其中ABCD分别是一个0到255的整数，例如127.0.0.1,哈希函数H的设计要求。将其看做256进制的4位数，H(A.B.C.D)=256^3A + 256^2B + 256C + D

• 除法哈希法 h(k) = k mod m k为关键字，m为槽的大小

• 乘法哈希法 h(k) = [m (kA mod 1)] 1.用关键字k乘上常数A(0<A<1),并抽取出kA的小数部分；2.用m乘以这个值，再取结果的底。哈希函数如下：h(k)

• 哈希冲突后，位于同一个槽的元素按链表放置,目前主流语言处理都是当链表元素超过8个以后，将链表换为平衡二叉查找树(红黑树)处理,减小搜索时间

• 开放寻址法：所有元素都放在哈希表里面，或包含NIL,使用探查的方式，连续的检查哈希表，直到找到一个空槽来放置，不使用链表或者其他数据结构

• 线性探查使用的哈希函数: h(k,i)=(h`(k) + i) mod m,i=0,1,...,m-1

• 开放寻址法的缺点：从哈希表中删除操作元素比较困难。不能仅将NIL置于其中来标识它为空。有一个解决办法，就是在槽i中放置一个特定的值DELETED替代NIL来标记该槽

• 线性探查的分析：优点：容易实现，Cache友好，装载因子可以接近1；缺点：很多哈希值近似的元素会聚集在一起

• 二次探查使用的哈希函数： h(k,i)=(h`(k) + c1 * i + c2 * i^2) mod m,i=0,1,...,m-1

没有线性探查很多哈希值相似就集中在一起的情况

为了充分利用哈希表,c1,c2和m的值要受到限制

Cache不友好，多个相同哈希值相同的元素会聚集在一起

装填因子等于已插入的键值对数目除以总的容量,装填因子越高，空间利用率越高，但是冲突的可能性会增高，降低访问效率

一个好的哈希策略应该让装填因子尽可能高，同时访问效率尽可能高

理想情况设装填因子为a,假设插入的键值的哈希值随机且独立，所有插入的键值在哈希表中的位置完全随机，从任意一点开始看，从它开始的槽连续不为空的长度期望值为∑ia^i(1-a),假设N足够大，求和约等于a/(1-a)

• 线性探查中，成功的搜索的期望探查长度为: 0.5(1 + 1 / (1- a)),不成功的搜索和插入新键值的期望探查长度为:0.5(1+1/(1-a)^2)

双重哈希是用于开放寻址法的最好的方法之一，因为它所产生的排列具有随机选择排列的许多特性 h(k, i) = (h1(k) + ih2(k)) mod m

双重哈希的装填因子为a,假设插入key的哈希值随机且独立，不成功的搜索的期望探查长度为1/(1-a),成功的搜索的期望探查长度为1/aln(1/(1-a))

优点：实现简单，缺点：对Cache不友好，出现聚集的现象时效率低，特别的，开放寻址法处理删除比较困难

两个哈希函数h1和h2,一个元素k在哈希表中的位置或者为h1(k)或者h2(k)

• 查找： 分别查看h1(k)和h2(k)即可
• 删除：首先查找，若k存在，则直接将其删除即可
• 插入：相当于一个长度为2的队列,

优点：查找和删除最坏情况下只需要访问两个位置

一个元素k在哈希表中的位置或者为h(k),或者为h(k)的L个邻居之一

优点达到很高的装填因子，提高空间利用率，缺点，查找和删除最坏复杂度是O(L),局部性很好,这一点对于外村哈希表特别重要

• 每个操作执行一次或多次哈希计算
• 不支持范围查询
• 哈希表的大小固定，计算开销大，但是平摊复杂度仍为常数

key-partition-matchine-value

范围分片

• RoundRobin

H(key) = hash(key) mod k

缺乏扩展性

• 虚拟桶

单层桶变为两层映射，扩展性强

• 一致性哈希

分布式哈希表(DHT),是P2P网络和分布式存储中常见的一项技术

将哈希数据空间按照大小组成首尾相接的环状序列

路由问题：

数据映射为128位的哈希串，文件校验

SHA-224 SHA-256 SHA-384 SHA-512