首页 1 2 3 4 5 6 7

算法导论第11章散列表（哈希表）

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。具体的介绍网上有很详细的描述，如闲聊哈希表，这里就不再累述了；

哈希表在像Java、C#等语言中是与生俱来的。可是在C的世界中，似乎只有自己动手，丰衣足食；在网上google了一把，大致有几个版本，我会一一来分析对比；

首先先来交代一下哈希表实现中需要注意的一些概念：

（主要参考：这里）

散列函数

多数散列函数都假定关键字域为自然数集。如果所给关键字不是自然数，则必须有一种方法将它们解释为自然数。这里，介绍三种主要的散列函数：

l          除法散列法：通过取k除以m的余数，来将关键字k映射到m个槽的某一个中去，即散列函数为

h(k) = k mod m

当应用除法散列法时，要注意m的选择，这也是除法散列法的主要缺点。m不应是2的幂，因为如果m=2^p，则h(k)就是k的p个最低有效位。相反，散列函数应该考虑关键字的所有位。可以选作m的值通常是与2的整数幂不太接近的质数。

l          乘法散列法：首先，用关键字k乘上常数A(0<A<1)，并抽取kA的小数部分；然后，用m乘以这个值，再取结果的底(即整数部分)。散列函数可表达为：

h(k) = ⌊m(kA mod 1)⌋

乘法方法的一个优点是对m的选择没有特别的要求，一般选择它为2的某个幂次(m=2^p)。该方法对任何的A值都适用，但对某些值效果更好。A=(sqrt(5)-1)/2=0.6180339…是一个比较理想的值。

l          全域散列(universal hashing)：在执行开始时，从一族仔细设计的函数中，随机地选择一个作为散列函数。这里的随机选择针对的是一次对散列表的应用，而不是一次简单的插入或查找操作。散列函数的确定性，是查找操作正确执行的保证。全域散列法确保，当k!=l时，两者发生碰撞的概率不大于1/m。设计一个全域散列函数类的方法如下，该方法中，散列表大小m的大小是任意的。

选择一个足够大的质数p，使得每一个可能的关键字都落在0到p-1的范围内。设Z_p表示集合{0, 1, …, p-1}，Z_p^*表示集合{1, 2, …, p-1}。对于任何a∈Z_p^*和任何b∈Z_p，定义散列函数h_a,b

h_a,b= ((ak+b) mod p) mod m

所有这样的散列函数构成的函数族为：

H_p,m = {h_a,b : a∈Z_p^*和b∈Z_p}

由于对a来说有p-1种选择，对于b来说有p种选择，因而，H_p,m中共有p(p-1)个散列函数。

哈希冲突（Hash collision）

也就是两个不同输入产生了相同输出值的情况。首先，哈希冲突是无法避免的，因此，哈希算法的选择直接决定了哈希冲突发送的概率；同时必须要对哈希冲突进行处理，方法主要有以下几种：

1 链地址法

链地址法：把散列到同一槽中的所有元素都存放在一个链表中。每个槽中有一个指针，指向由所有散列到该槽的元素构成的链表的头。如果不存在这样的元素，则指针为空。如果链接法使用的是双向链表，那么删除操作的最坏情况运行时间与插入操作相同，都为O(1)，而平均情况下一次成功的查找需要Θ(1+α)时间。

举例说明：设有 8 个元素 { a,b,c,d,e,f,g,h } ，采用某种哈希函数得到的地址分别为： {0 ， 2 ， 4 ， 1 ， 0 ， 8 ， 7 ， 2} ，当哈希表长度为 10 时，采用链地址法解决冲突的哈希表如下图所示。

2 开放寻址法(open addressing)：所有的元素都存放在散列表中。因此，适用于动态集合大小n不大于散列表大小的情况，即装载因子不超过1。否则，可能发生散列表溢出。在开放寻址中，当要插入一个元素时，可以连续地探查散列表的各项，直到找到一个空槽来放置待插入的关键字。探查的顺序不一定是0, 1, …, m-1，而是要依赖于待插入的关键字k。于是，将探查号作为散列函数的第二个输入参数。为了使所有的槽位都能够被探查到，探查序列<h(k,0), h(k,1), …, h(k,m-1)>必须是<0, 1, …, m-1>的一个排列。有三种技术常用来计算开放寻址法中的探查序列：线性探查、二次探查，以及双重探查。

²         线性探查(linear probing)：使用的散列函数如下

h(k,i) = (h’(k) + i) mod m, i=0, 1, …, m-1

h’为一个普通的散列函数，见前面的介绍。线性探查存在一个称为一次群集的问题，即随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。但是，线性探查的优点在于，对m的取值没有特殊的要求。

²         二次探查(quadratic probing)：使用的散列函数如下

h(k,i) = (h’(k) +c₁ i + c₂ i²) mod m, i=0, 1, …, m-1

为了能够充分利用散列表，c₁、c₂和m的值要受到限制。一种好的选择是，m为2的某个幂次(m=2^p)，c₁=c₂=1/2。二次探查，不会顺序地探查每一个槽位，解决了一次群集问题。但是，如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的，这一性质导致一种程度较轻的群集现象，称为二次群集。

²         双重散列(double hashing)：使用的散列函数如下

h(k,i) = (h₁(k) + i h₂(k)) mod m, i=0, 1, …, m-1

为能查找整个散列表，值h₂(k)要与表的大小m互质。确保这一条件成立的一种方法是取m为2的幂，并设计一个总能产生奇数的h₂。另一种方法是取m为质数，并设计一个总是产生较m小的正整数的h₂。例如，可以取m为质数，h₂(k)=1+(k mod m’)，m’=m-1。

完全散列

如果某一种散列技术在进行查找时，其最坏情况内存访问次数为O(1)的话，则称其为完全散列(perfect hashing)。通常利用一种两级的散列方案，每一级上都采用全域散列。为了确保在第二级上不出现碰撞，需要让第二级散列表S_j的大小m_j为散列到槽j中的关键字数n_j的平方。如果利用从某一全域散列函数类中随机选出的散列函数h，来将n个关键字存储到一个大小为m=n的散列表中，并将每个二次散列表的大小置为m_j=n_j² (j=0, 1, …, m-1)，则在一个完全散列方案中，存储所有二次散列表所需的存储总量的期望值小于2n。

哈希实现代码：

[cpp] view plain copy

#include "stdafx.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
     char *name;
     char *desc;
     struct _node *next;
}node;

#define HASHSIZE 101
static node* hashtab[HASHSIZE];

void inithashtab(){
     int i;
     for(i=0;i<HASHSIZE;i++)
         hashtab[i]=NULL;
}

unsigned int hash(char *s){
     unsigned int h=0;
     for(;*s;s++)
         h=*s+h*31;
     return h%HASHSIZE;
}

node* lookup(char *n){
     unsigned int hi=hash(n);
     node* np=hashtab[hi];
     for(;np!=NULL;np=np->next){
         if(!strcmp(np->name,n))
             return np;
     }

     return NULL;
}

char* m_strdup(char *o){
     int l=strlen(o)+1;
     char *ns=(char*)malloc(l*sizeof(char));
     strcpy(ns,o);
     if(ns==NULL)
         return NULL;
     else
         return ns;
}

char* get(char* name){
     node* n=lookup(name);
     if(n==NULL)
         return NULL;
     else
         return n->desc;
}

int install(char* name,char* desc){
     unsigned int hi;
     node* np;
     if((np=lookup(name))==NULL){
         hi=hash(name);
         np=(node*)malloc(sizeof(node));
         if(np==NULL)
             return 0;
         np->name=m_strdup(name);
         if(np->name==NULL) return 0;
         np->next=hashtab[hi];
         hashtab[hi]=np;
     }
     else
         free(np->desc);
     np->desc=m_strdup(desc);
     if(np->desc==NULL) return 0;

     return 1;
}


void displaytable(){
     int i;
     node *t;
     for(i=0;i<HASHSIZE;i++){
         if(hashtab[i]==NULL)
             printf("()");
         else{
             t=hashtab[i];
             printf("(");
             for(;t!=NULL;t=t->next)
                 printf("(%s.%s) ",t->name,t->desc);
             printf(".)");
         }
     }
}

void cleanup(){
     int i;
     node *np,*t;
     for(i=0;i<HASHSIZE;i++){
         if(hashtab[i]!=NULL){
             np=hashtab[i];
             while(np!=NULL){
                 t=np->next;
                 free(np->name);
                 free(np->desc);
                 free(np);
                 np=t;
             }
         }
     }
}

main(){
     int i;
     char* names[]={"name","address","phone","k101","k110"};
     char* descs[]={"Sourav","Sinagor","26300788","Value1","Value2"};

     inithashtab();
     for(i=0;i<5;i++)
         install(names[i],descs[i]);

     printf("Done");
     printf("If we didnt do anything wrong..""we should see %s",get("k110"));

     install("phone","9433120451");

     printf("Again if we go right, we have %s and %s",get("k101"),get("phone"));


     cleanup();
     return 0;
}

【HTML5】拖放详解及实现案例

文章目录效果预览
动态开辟空间new和delete的使用实例

#include <iostream.h> void main() { int *p1=new int; //动态开辟一个整型空间 cout<<"(
Rabbitmq消息队列详解

文章目录
函数模版与模版的特化

如果这样写：程序运行结果是过的 #include<iostream> #include<string.h> #include<string> using namespace std; namespa
HDU 5151 Sit sit sit 区间dp

题目链接：
Robotframework框架下的BDD（ATDD），比 Behave框架更简洁方便的应用（2/2）

Robotframework框架下的BDD（ATDD），比 Behave框架更简洁方便的应用（1/2）
MapReduce过程中的序列化与反序列化

map中的collect过程（序列化）： map过程中的collect主要由MapOutputBuffer来实现数据收集；变量：BlockingBuffer bb；
php中urldecode()和urlencode()

urlencode()函数原理就是首先把中文字符转换为十六进制，然后在每个字符前面加一个标识符%。 urldecode()函数与urlencode()函数原理相反，用于
ListView中Button的点击事件

相信很多像我一样的初学者在用listview时会遇到类似：item中如果有button的时候这个item中button的点击事件与listview中item点击事件的响应不能同时满足稍微研究了
魔法袍

目的：利用OpenCv 实现对颜色的过滤，实现魔法袍的效果 UE4 + OpenCV + 魔法袍一，本文目的：实现通过摄像头捕捉画面，体验者身披特定颜色长跑，可以实现类似魔法长袍的效果。二，开发环境 UE4 4.15 (必须此版

算法导论第11章 散列表（哈希表）

算法导论第11章散列表（哈希表）