标签：return 列表查找 HashTable key table 41 散列

一、什么是散列表

散列表（Hash Table，也叫 哈希表），它是根据 关键码值（key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中的一个位置来访问记录，以加快查找算法。这个映射函数叫做 散列函数，存放记录的数组叫做 散列表。

类型名称：散列表（HashTable）
数据对象集：符号表是“名字（Name）— 属性（Attribute）”对的集合。
操作集：Table ∈ HashTable, Name ∈ NameType, Attribute ∈ AttributeType

HashTable Create(int TableSize);                                              // 创建一个长度为TableSize的符号表
int IsInside(HashTable Table,NameType Name);                                  // 查找特定名字是否在符号表Table中
AttributeType Find(HashTable Table,NameType Name);                            // 获取Table中指定名字Name对应的属性
HashTable Modefy(HashType Table,NameType Name,AttributeType Attribute);       // 将Table中指定名字Name的属性修改为Attribute
HashTable Insert(HashType Table,NameType Name,AttributeType Attribute);       // 向Table中插入一个新名字Name及其属性Attribute
HashTable Delete(HashType Table,NameType Name);                               // 从Table中删除一个名字Name及其属性

装填因子（Loading Factor）：设散列表空间大小为 m，填入表中元素个数是 n，则 α = n / m 为散列表的装填因子；

二、散列函数的构造

将每个关键字映射到从 0 到 TableSize-1 这个范围中的某个数，并且放到适当的单元中。这个映射就叫散列函数（hash function），理想情况下它应该运算简单并且应该保证任何不同的两个关键字映射到不同的单元，不过这是不可能实现的。因此，我们应该要选择一个函数，决定当两个关键字散列到同一个值的时候（称为冲突（colision））应该做什么以及如何确定散列表的大小。

计算简单，以便提高转换速度；
关键词对应的 地址空间分布均匀，以尽量减少冲突；

2.1、数字关键字的散列函数的构造

直接定址法：取关键词的某个线性函数值为散列地址，即 \(h(key) = a * key + b (a,b 为常数)\)
除留余数法：散列函数为：\(h(key) = key \% TableSize\)
数字分析法：分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址；
折叠法：把关键字分割成位数相同的几个部分，然后叠加。
平方取中法

#define ElementType     int
#define MinTableSize    10

/**
 * @brief 构造哈希函数
 * 
 * @param key 待操作的元素
 * @param tableSize 待操作的哈希表
 * @return int 返回哈希值
 */
int Hash(ElementType key,HashTable table)
{
    return key % table->tableSize;
}

2.2、字符关键字散列函数的构造

ASCII 码加和法：对字符型关键字 key 定义散列函数如下：\(h(key) = (\sum{key[i]} \% TableSize)\)
前 2 个字符移位法：\(h(key) = (key[0] * 27^{2} + key[1] * 27 + key[2]) \% TableSize\)
移位法：\(h(key) = (\sum_{i=0}^{n-1}{key[n-i-1] * 32^{i}}) \% TableSize\)

三、散列冲突的处理方法

如果当一个元素被插入处另一个元素已经存在（散列值相同），那么就产生一个冲突，这个冲突需要清除。比较常用的解决冲突的方法有以下两种：分离链接法 和 开放地址法；

3.1、分离链接法

分离链接法 是将散列到同一个值的所有元素保留在一个表中。散列表中的结构包含一个链接数组（以及数组中链表的个数），它们在散列表结构初始化时动态分配空间。

typedef struct ListNode *Position;
typedef Position List;
typedef struct Table *HashTable;

struct ListNode
{
    ElementType element;
    Position next;
};

struct Table
{
    int tableSize;
    List *lists;
};

/**
 * @brief 初始化哈希表
 * 
 * @param tableSize 哈希表的大小
 * @return HashTable 返回指向哈希表的指针
 */
HashTable Initialze(int tableSize)
{
    int i = 0;

    if(tableSize < MinTableSize)
    {
        printf("散列表太小！\n");
        return NULL;
    }

    HashTable table = malloc(sizeof(struct Table));
    if(table == NULL)
    {
        printf("内存空间不足！\n");
        return NULL;
    }

    table->tableSize = tableSize;

    table->lists = malloc(sizeof(List) * table->tableSize);
    if(table->lists == NULL)
    {
        printf("内存空间不足！\n");
        return NULL;
    }

    for(i = 0; i < table->tableSize; i++)
    {
        table->lists[i] = malloc(sizeof(struct ListNode));
        if(table->lists[i] == NULL)
        {
            printf("内存空间不足！\n");
            return NULL;
        }
        else
        {
            table->lists[i]->next = NULL;
        }
    }

    return table; 
}

/**
 * @brief 查找元素
 * 
 * @param key 待查找元素的关键词
 * @param table 待查找的哈希表
 * @return Position 如果找到返回指向该元素的指针，否则返回NULL
 */
Position Find(ElementType key,HashTable table)
{
    Position position;
    List list;

    list = table->lists[Hash(key,table)];           // 计算待查找元素所属的链表
    position = list->next;
    while(position != NULL && position->element != key)
    {
        position = position->next;
    }
  
    return position;
}

/**
 * @brief 向哈希表中插入一个元素
 * 
 * @param key 待查找元素的关键词
 * @param table 待查找的哈希表
 */
void Insert(ElementType key,HashTable table)
{
    Position position;
    List newCell,list;

    position = Find(key,table);
    if(position != NULL)
    {
        printf("待插入元素已存在！\n");
        return;
    }

    newCell = malloc(sizeof(struct ListNode));
    if(newCell == NULL)
    {
        printf("内存空间不足！\n");
        return;
    }
    list = table->lists[Hash(key,table->tableSize)];
    newCell->next = list->next;
    list->element = key;
    list->next = newCell;
}

3.2、开放地址法

一旦发生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址。若发生了第 i 次冲突，试探的下一个地址将增加 \(d_{i}\)，基本公式是：\(hi(key) = (h(key) + d_{i}) \% TableSize (1 ≤ i ≤ TableSize)\)。\(d_{i}\) 决定了不同的解决冲突方案：线性探测（\(d_{i} = i\)）、平方探测（\(d_{i} = ± i^{2}\)）、双散列（\(d_{i} = i * h_{2}(key)\)）。

3.2.1、线性探测法

在线性探测法中，函数 F 是 i 的线性函数，典型情景是 \(F(i)=i\)。这相当于逐个探测每个单元（必要时可以绕回）以查找出一个空单元。但是线性探测存在聚集现象，即使表相对较空，这样占据的单元也会开始形成一些区块，其结果称为一次聚集（primary clustering）。于是，散列到区块中的任何关键字都需要多次试选单元才能解决冲突，然后该关键字被添加到相应的区块内。

3.2.2、平方探测法

平方探测就是冲突函数为二次函数的探测方法。流行的选择有 \(F(i) = i^{2}\)。平方探测是消除线性探测中一次聚集问题的冲突解决方法。但是它也存在缺点，一旦表被填充超过一半，当表的大小不是素数时甚至在表被填充一半之前，就不能保证一次找到一个空单元。这是因为最多有一半的表可以用作解决冲突的备选位置。虽然平方探测排除了一次聚集，但是散列到同一个位置上的那些元素将探测相同的备选单元。这叫作二次聚集（secondary clustering）。

typedef unsigned int Index;
typedef Index Position;
typedef struct Table *HashTable;
typedef struct HashEntry Cell;

enum KindOfEntry
{
    legitimate,empty,deleted
};

struct HashEntry
{
    ElementType element;
    enum KindOfEntry info;
};

struct Table
{
    int tableSize;
    Cell *cells;
};

/**
 * @brief 创建一个空的散列表
 * 
 * @param tableSize 待创建的散列表的大小
 * @return HahTable 返回执行散列表的指针
 */
HashTable Initialze(int tableSize)
{
    HashTable table;
    int i;

    if(tableSize < MinTableSize)
    {
        printf("散列表太小！\n");
        return NULL;
    }

    // 分配散列表
    table = (HashTable)malloc(sizeof(struct Table));
    if(table == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }

    table->tableSize = tableSize;
    table->cells = malloc(sizeof(Cell) * table->tableSize);
    if(table->cells == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }

    for(i = 0; i < table->tableSize; i++)
    {
        table->cells[i].info = empty;
    }

    return table;
}

/**
 * @brief 查找元素
 * 
 * @param key 待查找元素的关键词
 * @param table 待查找的哈希表
 * @return Position 如果找到返回指向该元素的指针，否则返回NULL
 */
Position Find(ElementType key,HashTable table)
{
    Position curremtPos;
    int collisionNum;

    collisionNum = 0;
    curremtPos = Hash(key,table);
    while(table->cells[curremtPos].info != empty &&
        table->cells[curremtPos].element != key)
    {
        curremtPos += 2 * ++collisionNum -1;
        if(curremtPos >= table->tableSize)
        {
            curremtPos -= table->tableSize;
        }
    }

    return curremtPos;
}

/**
 * @brief 向哈希表中插入一个元素
 * 
 * @param key 待查找元素的关键词
 * @param table 待查找的哈希表
 */
void Insert(ElementType key,HashTable table)
{
    Position position;

    position = Find(key,table);
    if(table->cells[position].info == legitimate)
    {
        printf("待插入元素已经存在！\n");
        return;
    }
    table->cells[position].info = legitimate;
    table->cells[position].element = key;
}

3.1.3、双散列探测法

双散列探测法：\(d_{i}\) 为 \(i * h_{2}(key)\)，\(h_{2}(key)\) 是另一个散列函数他测序列成：\(h_{2}(key),2h_{2}(key),3h_{2}(key),...\)。对任意的 key，\(h_{2}(key) ≠ 0\)。探测散列还应该保证所有的散列存储单元都应该能够被探测到。选择以下形式有良好的效果：\(h_{2}(key) = p - (key \% p)\)。其中，p < TableSize，p、TableSize 都是素数。

当散列元素太多（即填装因子 α 太大）时，查找效率会下降。使用最大装填因子一般取 \(0.5 ≤ α ≤ 0.85\)；

当装填因子过大时，解决的方法是加倍扩大散列表，这个过程叫做“再散列（Rehashing）”；

四、再散列

对于使用平方探测的开放地址散列法，如果表的元素填充着太满，那么操作的运行时间将开始消耗过长。且 Insert 操作可能失败。这可能发生在有太多的移动和插入混合的场合。此时，一种解决方法是建立另外一个大约两倍大的表（而且使用一个相关的新散列函数）。扫描整个原始散列表，计算每个（未删除的）元素的新散列值并将其插入到新表中。这整个过程就叫做 再散列（rehashing），其运行时间为 O(N)，因为有 N 个元素要再散列而表的大小约为 2N。再最后的再散列之前必然已经存在 N/2 次 Insert，当然添加到每个插入上的花费基本是一个常数开销。

再散列可以用平方探测以多种方式实现。一种做法是只要表填充到一半就再散列。另一种极端的方法是只有当插入失败是才再散列。第三种方法是途中（middle-of-the-road）策略：当表到达某一个填装因子时进行再散列。

/**
 * @brief 再散列函数
 * 
 * @param table 新的哈希表
 * @return HashTable 返回指向新的哈希表的指针
 */
HashTable ReHash(HashTable table)
{
    int i,oldSiZe;
    Cell *oldCells;

    oldCells = table->cells;
    oldSiZe = table->tableSize;

    table = Initialze(2 * oldSiZe);

    for(i = 0; i < oldSiZe; i++)
    {
        if(oldCells[i].info == legitimate)
        {
            Insert(oldCells[i].element,table);
        }
    }

    free(oldCells);
    return table;
}

四、散列表的性能分析

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

散列函数是否均匀；
处理冲突的方法；
散列表的填装因子 α；

线性探测法的期望探测次数满足以下公式：\(p = \begin{cases} \frac{1}{2}[1 + \frac{1}{(1-α)^{2}}] &（对插入和不成功查找而言）\\ \frac{1}{2}(1 + \frac{1}{1-α}) &（对成功查找而言） \end{cases}\)，当 α=0.5 时，插入操作和不成功查找的期望 \(ASLu = 0.5 * (1 + 1 / (1-0.5)^2) = 2.5\) 次，插入成功的期望 \(ASLs = 0.5 * (1 + 1 / (1-0.5)) = 1.5\) 次；

平方探测法和双散列探测法探测次数满足以下公式：\(p = \begin{cases} \frac{1}{1-α} &（对插入和不成功查找而言） \\ - \frac{1}{α}ln(1-α) &（对成功查找而言） \end{cases}\)，当 α=0.5 时，插入操作和不成功查找的期望 \(ASLu = 1 / (1-0.5) = 2\) 次，成功查找的期望 \(ASLs = -1/0.5*ln(1-0.5) ≈ 1.39\) 次；

所有地址链表的平均长度定义成装填因子 α，α 有可能超过 1，其期望探测次数 p 为：\(p = \begin{cases} α + e^{-α} &（对插入和不成功查找而言）\\ 1 + \frac{α}{2} &（对成功查找而言） \end{cases}\)。当 α =1 时，插入操作和不成功查找的期望 \(ASLu = 1 + e^{-1} = 1.37\) 次，成功查找的期望 \(ASLs = 1 + 1/2 = 1.5\) 次；

选择合适的 \(h(key)\)，散列法的查找效率期望是常熟 \(O(1)\)，它几乎与关键词的空间的大小 n 无关，也适合于关键词直接比较计算量大的问题。它是以较小的 α 为前提。因此，散列方法是一个以空间换时间的策略。散列方法的存储对关键词是随机的，不便于顺序查找关键词，也不适合于范围查找，或最大值最小值查找。

开放地址法的散列表是一个数组，存储效率高，随机查找，但是它有聚集的现象；分离链接法的散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低，关键词删除不需要“懒惰删除”法，从而没有存储“垃圾”。分离链接法的 α 太小可能会导致空间的浪费，α 太大的话又会付出更多的时间代价，不均匀的链表长度导致时间效率的严重下降；

标签：return,列表,查找,HashTable,key,table,41,散列
From： https://www.cnblogs.com/kurome/p/17529869.html

41. 散列表