数据结构_10

发表于
字数统计 1.2k | 阅读时长 4

学习过程主要依照中国MOOC课程，感谢MOOC，感谢浙大授课大佬。

散列表（哈希表）

查找对象时，静态查找可以用二分查找，动态查找可以建树，但是比对的过程是数的话可以，如果是字符串的话就比较费时，那么能否把字符串映射为数字呢？这就是散列表。

查找的本质：已知对象找位置。

  • 有序安排对象：全序、半序；
  • 直接”算出”对象位置：散列；

散列查找的两项基本工作：

  • 计算位置：构造散列函数确定关键词存储位置；
  • 解决冲突：应用某种策略解决多个关键字位置相同的问题；

“散列（Hashing）”的基本思想：
1）以关键字key为自变量，通过一个确定的函数h计算出对应的函数值h(key)，作为数据对象的存储地址。
2）可能不同的关键字会映射到同一个散列地址上，称为”冲突”，需要冲突解决策略。

散列函数构造方法

考虑因素：

  1. 计算简单，以便提高转换效率
  2. 关键字对应的地址空间分布均匀，以尽量减少冲突

数字关键字

  1. 直接定制法
  2. 除留余数法
  3. 数字分析法
  4. 折叠法
  5. 平方取中法

字符关键字

  1. 简单方法-ASCII码加和法
  2. 简单改进法-前三个字符移位法
  3. 好的方法-全部字符移位法

冲突处理方法

常见思路：

  • 换个位置：开放地址法
  • 同一位置的冲突对象组织在一起：链地址法

开放地址法

  1. 线性探测法
  2. 平方探测法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */
typedef int ElementType;    /* 关键词类型用整型 */
typedef int Index;          /* 散列地址类型 */
typedef Index Position;     /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;
 
typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
    ElementType Data; /* 存放元素 */
    EntryType Info;   /* 单元状态 */
};
 
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode {   /* 散列表结点定义 */
    int TableSize; /* 表的最大长度 */
    Cell *Cells;   /* 存放散列单元数据的数组 */
};
 
int NextPrime( int N )
{ /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
    int i, p = (N%2)? N+2 : N+1; /*从大于N的下一个奇数开始 */
 
    while( p <= MAXTABLESIZE ) {
        for( i=(int)sqrt(p); i>2; i-- )
            if ( !(p%i) ) break; /* p不是素数 */
        if ( i==2 ) break; /* for正常结束，说明p是素数 */
        else  p += 2; /* 否则试探下一个奇数 */
    }
    return p;
}
 
HashTable CreateTable( int TableSize )
{
    HashTable H;
    int i;
 
    H = (HashTable)malloc(sizeof(struct TblNode));
    /* 保证散列表最大长度是素数 */
    H->TableSize = NextPrime(TableSize);
    /* 声明单元数组 */
    H->Cells = (Cell *)malloc(H->TableSize*sizeof(Cell));
    /* 初始化单元状态为“空单元” */
    for( i=0; i<H->TableSize; i++ )
        H->Cells[i].Info = Empty;
 
    return H;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Position Find( HashTable H, ElementType Key )
{
    Position CurrentPos, NewPos;
    int CNum = 0; /* 记录冲突次数 */
 
    NewPos = CurrentPos = Hash( Key, H->TableSize ); /* 初始散列位置 */
    /* 当该位置的单元非空，并且不是要找的元素时，发生冲突 */
    while( H->Cells[NewPos].Info!=Empty && H->Cells[NewPos].Data!=Key ) {
                                           /* 字符串类型的关键词需要 strcmp 函数!! */
        /* 统计1次冲突，并判断奇偶次 */
        if( ++CNum%2 ){ /* 奇数次冲突 */
            NewPos = CurrentPos + (CNum+1)*(CNum+1)/4; /* 增量为+[(CNum+1)/2]^2 */
            if ( NewPos >= H->TableSize )
                NewPos = NewPos % H->TableSize; /* 调整为合法地址 */
        }
        else { /* 偶数次冲突 */
            NewPos = CurrentPos - CNum*CNum/4; /* 增量为-(CNum/2)^2 */
            while( NewPos < 0 )
                NewPos += H->TableSize; /* 调整为合法地址 */
        }
    }
    return NewPos; /* 此时NewPos或者是Key的位置，或者是一个空单元的位置（表示找不到）*/
}
 
bool Insert( HashTable H, ElementType Key )
{
    Position Pos = Find( H, Key ); /* 先检查Key是否已经存在 */
 
    if( H->Cells[Pos].Info != Legitimate ) { /* 如果这个单元没有被占，说明Key可以插入在此 */
        H->Cells[Pos].Info = Legitimate;
        H->Cells[Pos].Data = Key;
        /*字符串类型的关键词需要 strcpy 函数!! */
        return true;
    }
    else {
        printf("键值已存在");
        return false;
    }
}
  1. 双散列探测法
  2. 再散列

分离链接法

将相同位置上冲突的所有关键词存储在同一个单链表中。

散列表性能分析

指标：平均查找长度（ASL）用来衡量散列表的查找效率：成功、不成功
关键词的比较次数，取决于产生冲突的多少，影响产生冲突多少有以下三个因素：

  1. 散列函数是否均匀
  2. 处理冲突的方法
  3. 散列表的装填因子α，应在0.5-0.85之间

以上。

注：转载文章请注明出处，谢谢~