以下笔记为jjyaoao本人制作，欢迎借鉴学习和提出相关建议，转载需要标明出处www.jjyaoao.space

词典

散列

引例

原理

实例

冲突

散列函数

冲突难免

何谓优劣

几种散列函数

除余法

#include "Bitmap/Bitmap.h" //引入Bitmap结构
0002 
0003 /******************************************************************************************
0004  * 筛法求素数：找出小于n的所有素数
0005  * 内循环每趟迭代O(n/i)步，外循环由素数定理至多n/ln(n)趟，累计耗时不过
0006  *       n/2 + n/3 + n/5 + n/7 + n/11 + ...
0007  *    <  n/2 + n/3 + n/4 + n/6 + n/7 + ... + n/(n/ln(n))
0008  *    =  O(n(ln(n/ln(n)) - 1))
0009  *    =  O(nln(n) - nln(ln(n)) - 1)
0010  *    =  O(nlog(n))
0011  * 如下实现中，内循环的起点、外循环的终点都了优化
0012  ******************************************************************************************/
0013 
0014 void Eratosthenes ( int n, char* file ) {
0015    Bitmap B( n ); B.set( 0 ); B.set( 1 ); //0和1都不是素数
0016    for ( int i = 2; i*i < n; i++ ) //逐个地
0017       if ( !B.test ( i ) ) //确认下一个素数i
0018          for ( int j = i * i; j < n; j += i ) //并将一系列能被i整除的
0019             B.set ( j ); //j标记为合数（小于i*i的合数，必在此之前已被标记）
0020    B.dump ( file ); //将筛选标记统一存入指定文件，以便日后直接导入
0021 }

平方取中

折叠/异或

(伪)随机数法

多项式法

排解冲突

多槽位

类似于一山不容二虎，将每个虎用铁丝网封锁在不同的山

每个桶不同的槽位就用来存储多出来的重复的散列表

只要槽位控制在常数，整体的速度不会太降低，不过缺陷是显而易见的。

每个桶需要分多少个槽位是无法预估的，如果分的过细，浪费空间，分的太少，可能装不下，反过来，无论分的多细，仍有可能面对大规模的冲突，那么我们如何破解呢？

独立链

虽然这种方式良好的解决了空间上的问题，但是引入了时间上巨大迟钝

系统的缓存几乎失效

那么为了有效的激活缓存功能，我们又应该如何改进呢？

公共溢出区

为了保证空间上彼此毗邻，我们可能应该放弃这种策略，并且反其道而行之，采用开放定址

查找链约定

线性试探

紧邻的试探，使得越后面进来的，需要的时间(冲突)越来越多

前后对比，可以发现，后一种插入所发生的的多次冲突(紫色圈起来的)的确是可以避免的。[如果对应桶的位置有人占了，则以此向后遍历，直到找到一个空桶]

【对7而言，对应的桶就应该是0】

懒惰删除

实战代码

/******************************************************************************************
0002  * 沿关键码k的试探链，找到与之匹配的桶；实践中有多种试探策略可选，这里仅以线性试探为例		搜索！
0003  ******************************************************************************************/
0004 template <typename K, typename V> int Hashtable<K, V>::probe4Hit ( const K& k ) {
0005    int r = hashCode( k ) % M; //按除余法确定试探链起点
0006    while ( ( ht[r] && ( k != ht[r]->key ) ) || removed->test(r) )
0007       r = ( r + 1 ) % M; //线性试探（跳过带懒惰删除标记的桶）
0008    return r; //调用者根据ht[r]是否为空及其内容，即可判断查找是否成功
0009 }

/******************************************************************************************
0002  * 沿关键码k的试探链，找到首个可用空桶；实践中有多种试探策略可选，这里仅以线性试探为例    插入！
0003  ******************************************************************************************/
0004 template <typename K, typename V> int Hashtable<K, V>::probe4Free ( const K& k ) {
0005    int r = hashCode ( k ) % M; //按除余法确定试探链起点
0006    while ( ht[r] ) r = ( r + 1 ) % M; //线性试探，直到首个空桶（无论是否带有懒惰删除标记）
0007    return r; //只要有空桶，线性试探迟早能找到
0008 }