lesson9

词典
   散列：原理
   桶(bucket)：直接存放或间接指向一个词条
   桶数组 bucket array /散列表 hash table，容量为M
   N < M <<R
   空间 = O(N+M)=O(N) M与N尽量同阶
   定址根据词条的key直接确定散列表入口
   散列函数：hash(): key -> &entry
   实例：
    hash(key) = key % M;
    N/M 装填因子
    冲突 key1 != key2
    hash( key1) = hash( key2) 大定义域向小定义域映射
    散列函数设计：
      确定：同一关键码总是被映射至同一地址
      快速：
      满射：尽可能充分覆盖整个散列空间
      均匀：关键码映射到散列表各位置的概率尽量接近可有效避免clustering（局部汇聚）现象
    散列函数
      1 除余法
       hash(key) = key % M
       若取 M = 2 ^ k, 其效果相当于截取key的最后k位，前面n-k没有影响
       M-1 = 00000000000 111111
       key % M = key & (M-1)
       推论：发生冲突 iff 最后 k 位相同  第4条  
       key = a*M + b
       
       M取为素数，数据对散列表的覆盖最充分，分布最均匀
       S为序列步长
       gcd(S,M) = 1 S任意，M则为素数
       除余法缺陷
        1 不动点：无论表长M取值如何，总有hash(0) = 0;
        2 零阶均匀：[0，R)的关键码，平均分配至M个桶；但相邻关键码的
        散列地址也必须相邻
       
       MAD法
       一阶均匀：邻近的关键码，散列地址不再邻近
       取M为素数，a>0,b>0,a%M!=0
       hash( key ) =( a*key + b )% M
       
       数字分析
       抽取key中某几位。构成地址，例如取十进制的奇数位
       平方取中
       hash(123) = [123^2 = 1 512 9]  = 512
       
       折叠法
       将 分割成等宽的若干 段 并 求和
       位异或法
       将 分割成等宽的若干 二进制段 并求 异或 
       
       伪随机数
       循环 rand(x + 1) =[ a * rand(x)] % M
       hash(key) = rand(key) = [rand(0) * a^(key)] % M
       
       ------------------------------
       key ->hashcode->bucket addr
       hash( s =x0x1x2..xn-1) = x0*a^(n-1) + x1*a^(n-2)+..xn-1
       static size_t hashCode( char s[]){
         int h = 0;
         for ( size_t n = strlen(s), i = 0; i < n; i++){
            h = (h << 5)|(h >> 27);
            h + = (int) s[i];
         }
         return (size_t) h;
       }//????????????
       
       散列：排解冲突
       一、
       多槽位
       桶单元细分成若干槽位slot，存放（与同一单元）的词条
       独立链
       每个桶存放一个指针，冲突的词条组成列表
       优点：无需为每个桶预备多个槽位，任意多次的冲突都可解决，删除简单
       缺点：指针需要额外空间，节点需要动态申请，系统缓存几乎失效
       
       开放定址
       为每个桶事先约定若干备用桶，他们构成一个查找链
       线性试探
       [hash(key) + 1] % M  .....
       懒惰删除
       先后插入、互相冲突的一组词条，将存放于同一查找链中
       仅作删除标记
       
       二、
       拉开试探间距
       平方试探
       [hash(key) + 1^2] % M  [hash(key) + 2^2] % M  .....
       优点：数据聚集现象有所缓解
       缺点：若涉及外存，I/O将激增
       M为合数：n^2 % M 可能取值少于上取整（M/2）种
       M为素数：n^2 % M 可能取值上取整（M/2）种
       若M为素数，且装填因子小于0.5，就一定能找到
       反证：假设存在0 <= a < b < 上取整(M/2),使得沿着查找链，第a项和第b项彼此冲突  
       于是：a^2 和 b^2自然属于M的某个同余类，即
       => a^2 = b^2( mod M) => b^2-a^2 = (b+a)*(b-a) = 0( mod M)
       而 0 < b-a < b+a(至少为2) < M 与 M为素数相悖
       
       双向平方试探
       建议将表长M取作4k + 3
       双平方定理
       任意素数pk可表示为一对整数的平方和,iff p % 4 =1
       (u^2 + v^2)(s^2 + t^2) = (us + vt)^2 + (ut-vs)^2
       ==> 任一自然数n可表示为一对整数的平方和，iff在其素分解中，形如 M = 4*k + 3 的每一个素因子均为偶数次方
       反证 正向a 与 反向b发生冲突，即
        -b^2 = a^2 (mod M)  且 1<=b,a<=下取整(M/2)
        (a^2 + b^2) = 0 (mod M ) 
        所以 a^2 + b^2 > M^2 与1<=b,a<=下取整(M/2)相悖
        
        桶/计数排序
        取值范围[0,M) n个数 ==》O(max(n,M))