1. 基本概念

查找表：由相同数据类型的数据元素构成的集合。
关键字：数据元素中某个数据项，它可以标识一个数据元素，是唯一的。
查找（Searching）就是根据给定的某个值，在查找表中找到一个关键字等于给定
值的数据元素。
静态查找表：查找表中的数据元素不会发生变化
动态查找表：查找表中的数据元素会发生变化（插入、修改和删除）
查找长度：在查找运算中，需要对比关键字的次数
平均查找长度（ASL）：所查找过程中进行关键字比较次数的平均值，用于衡量查找算法的效率，包括成功和失败两种情况。

2. 顺序表查找

2.1 顺序查找

顺序查找（线性查找）：用于在静态的线性表（顺序表或链表）中进行查找
算法的思想是从线性表的某一端开始，把表中的元素和关键字逐个比较（线性表的遍历）

// 查找表arry中关键字key是否存在，返回数组下标
int Search_Seql(int *array,int len,int key)
{for(int i =0;i<len;i++){if(array[i]==key){return i;}}return -1; // 查找失败
}

2.2 顺序查找优化-哨兵

每次循环查找都需要对下标i是否越界进行判断，可以把数组的首个元素设置为哨兵(需要数组把下标为0的位置预留给哨兵)，从数组末尾开始遍历，可以省略每次比较下标是否越界。

int Search_Seql_2(int* array,int len,int key)
{// 设置哨兵array[0]=key; int i =0;for(i = len-1;array[i]!=key;i--); // 空语句return i; // 如果找到直接返回，如果没找到则会下标为0，此时返回0表示未找到
}

3. 有序表查找

3.1 折半查找（二分查找）

折半查找（二分查找）：只适用于有序（升序或降序，通常升序）的顺序表（不能是链表）
算法思想：在有序表中，取中间作为比较对象，如果查找目标大于中间记录的关键字，那么在右半区继续查找；如果查找目标小于中间记录的关键字，则在左半区进行查找。不断重复上述过程，直到找到查找成功，或者查找完毕无法找到为止。

• 迭代方法实现：

// 迭代实现
int Binary_Search1(int* array, int len, int key)
{int low = 0, high = len - 1;int mid = (low + high) / 2;while (low <= high){if (array[mid] == key) // 找到{return mid;}else if (key < array[mid]) //key小，在左半区{high = mid - 1;}else // key大，在右半区{low = mid + 1;}mid = (low + high) / 2;}return -1; // 查找失败
}

• 递归实现：

// 递归实现
int Binary_Search2(int* array, int key, int low, int high)
{if (low>high) // 查找失败{return -1;}int mid = (low + high) / 2;if(key== array[mid]) // 找到{return mid;}// key小else if (key < array[mid]){//向左递归return Binary_Search2(array, key, low, mid- 1);}//key 大else {// 向右递归return Binary_Search2(array, key, mid + 1, high);}
}

4. 分块查找（索引顺序查找）

分块查找（索引顺序查找），是顺序查找的一种改进方法。在此查找法中，除表本身外，还需要建立一个索引表。索引表中存放了每个分块的最大关键字，和分块的起始地址。
分块有序：

• 块内无序，即每一块内的记录不要求有序
• 块间有序，即第一块，第二块，第三块…之间要求有顺序。

查找过程：

• 先查找索引表，确定待查找元素所属的分块（顺序或折半查找）
• 在分块内使用顺序查找

5. Hash表（散列表）

散列（Hash）表，这种数据结构的特点是：数据元素关键字和它在表中的存储的地址直接相关。关键字与存储地址之间的对应关系的函数称为哈希函数。
哈希函数：Address = Hash(Key)

1. Hash是一种以常数平均时间执行插入、删除和查找的技术，但是不支持元素排序和查找最小（大）值的操作
2. Hash函数是一种映射关系，很灵活，任何关键字通过它的计算，返回的值都落在表长允许的范围之内即可
3. 对于不同的关键字，可能得到相同的Hash地址，这种现象称为冲突；Hash地址相同的关键字称为同义词。
4. 处理冲突的办法由四种：链地址法、开放定址法、再散列法和建立公共溢出区。
5. Hash表的装填因子（表中记录数/表长）越大，关键字冲突的可能性越大，同义词越多，查找效率可能更低。
   
   对于长度固定的散列表来说，当数据分布的越均匀，查找效率越高。

5.1 散列函数的设计

• 除留余数法：Hash(key)=key%p
  如果散列表的表长为m，p为小于等于m的最大质数，在一般情况下，对质数取余会让冲突更少，数据元素在散列表中分布的更均匀。
• 直接定址法：Hash(key)=a*key+b
  这种方法的计算最简单，不会产生冲突，适合关键字的分布比较连续的情况，如果关键字分布不连续，空位较多，会造成存储空间浪费。

散列函数的设计没有固定的方法，需要结合实际情况，考虑的因素有：

1. 清楚关键字分布情况
2. 散列表的大小合理，太大浪费空间，太小则产生太多的同义词
3. 散列表中的数据分布要均匀，不要形成堆积
4. 散列函数代码要精简

5.2 代码实现

5.2.1 初始化Hash表

Hash表由存储链表头结点的数组，数据元素单链表构成，并且每个数据元素对应有关键字’key’和数值’value’，因此需要构建三个结构体，并对他们初始化

// Hash表中数据元素结构体
struct Element
{int key; // 关键字int value; // 数据元素，可以是任意数据类型
};// 数据元素单链表
struct Node
{Element elem; // 数据元素Node* next; // next指针
};// Hash表
struct HashTable 
{Node* head;// 数据元素存储地址，动态分配数组int table_size;// 表的大小int count; // 数据元素个数
};// 初始化Hash表
HashTable* InitHashTable(int table_size)
{HashTable* ht = new(HashTable);ht->table_size = table_size; // 表长ht->count = 0; // 数据元素个数// 分配和初始化数据元素单链表的头结点ht->head = new Node[ht->table_size]; // 产生大小为table_size的数组，用于存放头结点// 初始化单链表头结点for (int i = 0; i < ht->table_size; i++){ht->head[i].next = nullptr;ht->head[i].elem.key = 0;ht->head[i].elem.value = 0;}return ht;
}

5.2.2 插入数据元素操作

Hash表根据数据元素的key生成一个Hash地址，找到Hash地址对应的头结点后，插入到头结点对应的单链表中，这里使用的是头插法。实际开发中，可以对value按照一定顺序插入

// Hash函数,产生Hash地址
unsigned int Hash(HashTable* hs, int key)
{return key % hs->table_size; // 除留余法，对表长取余
}// 查找关键字为key的数据元素，存在则返回结点地址
Node* Lookup(HashTable* hs, int key)
{int pos = Hash(hs, key); // 找到Hash地址Node* pp = hs->head[pos].next;// 从头结点下一个结点开始遍历这个单链表while (pp != nullptr && pp->elem.key != key){pp = pp->next;}return pp;
}// 向Hash表中插入数据元素
bool Insert(HashTable* hh, Element* ee)
{// 查找关键字是否存在，存在则插入失败Node* pp = Lookup(hh,ee->key);if (pp != nullptr){return false;}// 不存在，创建新的结点Node* qq = new Node; qq->elem = *ee;qq->next = nullptr;// 插入新数据元素int pos = Hash(hh, ee->key); // 获取Hash地址// 头插法Node head_node = hh->head[pos]; // 找到头结点qq->next = head_node.next;hh->head[pos].next = qq;// 表中元素个数hh->count++;return true;
}

5.2.3 删除数据元素

从Hash表中删除数据元素也是根据它的key值，生成一个Hash地址，然后找到头结点，遍历整个头结点对应的单链表，找到key值对应结点的前一个结点，删除最后key值对应的结点。

// 删除Hash表中的一个数据，根据key删除数据
bool Delete(HashTable* hs, unsigned int key)
{//  根据key产生Hash地址int pos = Hash(hs, key);Node* node_ptr = &hs->head[pos]; // 找到头结点所在位置while (node_ptr->next != nullptr && node_ptr->next->elem.key != key) // 遍历单链表，找到key前的结点{node_ptr = node_ptr->next;}if (node_ptr->next == nullptr) // 查找失败{return false;}// 删除链表结点Node* delete_node = node_ptr->next;node_ptr->next = delete_node->next;delete delete_node;hs->count--;return 0;
}

5.2.4 完整实现

#include <iostream>
using namespace std;// Hash表中数据元素结构体
struct Element
{int key; // 关键字int value; // 数据元素，可以是任意数据类型
};// 数据元素单链表
struct Node
{Element elem; // 数据元素Node* next; // next指针
};// Hash表
struct HashTable 
{Node* head;// 数据元素存储地址，动态分配数组int table_size;// 表的大小int count; // 数据元素个数
};// 初始化Hash表
HashTable* InitHashTable(int table_size)
{HashTable* ht = new(HashTable);ht->table_size = table_size; // 表长ht->count = 0; // 数据元素个数// 分配和初始化数据元素单链表的头结点ht->head = new Node[ht->table_size]; // 产生大小为table_size的数组，用于存放头结点// 初始化单链表头结点for (int i = 0; i < ht->table_size; i++){ht->head[i].next = nullptr;ht->head[i].elem.key = 0;ht->head[i].elem.value = 0;}return ht;
}// Hash函数,产生Hash地址
unsigned int Hash(HashTable* hs, int key)
{return key % hs->table_size; // 除留余法，对表长取余
}// 查找关键字为key的数据元素，存在则返回结点地址
Node* Lookup(HashTable* hs, int key)
{int pos = Hash(hs, key); // 找到Hash地址Node* pp = hs->head[pos].next;// 从头结点下一个结点开始遍历这个单链表while (pp != nullptr && pp->elem.key != key){pp = pp->next;}return pp;
}// 向Hash表中插入数据元素
bool Insert(HashTable* hh, Element* ee)
{// 查找关键字是否存在，存在则插入失败Node* pp = Lookup(hh,ee->key);if (pp != nullptr){return false;}// 不存在，创建新的结点Node* qq = new Node; qq->elem = *ee;qq->next = nullptr;// 插入新数据元素int pos = Hash(hh, ee->key); // 获取Hash地址// 头插法Node head_node = hh->head[pos]; // 找到头结点qq->next = head_node.next;hh->head[pos].next = qq;// 表中元素个数hh->count++;return true;
}// 打印Hash表
void PrintHash(HashTable* hs)
{for (int i = 0; i < hs->table_size; i++){Node* pp = hs->head[i].next;// 招待第一个结点while (pp){cout << "[" << pp->elem.key << "-" << pp->elem.value << "] ";pp = pp->next;}cout << "^\n";}
}// 删除Hash表中的一个数据，根据key删除数据
bool Delete(HashTable* hs, unsigned int key)
{//  根据key产生Hash地址int pos = Hash(hs, key);Node* node_ptr = &hs->head[pos]; // 找到头结点所在位置while (node_ptr->next != nullptr && node_ptr->next->elem.key != key) // 遍历单链表，找到key前的结点{node_ptr = node_ptr->next;}if (node_ptr->next == nullptr) // 查找失败{return false;}// 删除链表结点Node* delete_node = node_ptr->next;node_ptr->next = delete_node->next;delete delete_node;hs->count--;return 0;
}// 销毁Hash表
void DestoryHash(HashTable* hs)
{if (hs == nullptr){return;}// 遍历Hash表，释放全部单链表for (int i = 0; i < hs->table_size; i++){// 访问每个头结点的下一个结点Node* tmp_Ptr = hs->head[i].next;while (tmp_Ptr){Node* next_Ptr = tmp_Ptr->next;delete tmp_Ptr;// 访问下一个结点tmp_Ptr = next_Ptr;}}hs->count = 0;hs->table_size = 0;// 释放头结点数组delete [] hs->head;// 删除Hash表delete hs;
}
int main(void)
{HashTable* hs = InitHashTable(10);// 数据元素Element ee;// 插入数据元素ee.key = 10; ee.value = 110; Insert(hs, &ee);ee.key = 11; ee.value = 111; Insert(hs, &ee);ee.key = 12; ee.value = 112; Insert(hs, &ee);ee.key = 13; ee.value = 113; Insert(hs, &ee);ee.key = 14; ee.value = 114; Insert(hs, &ee);ee.key = 15; ee.value = 115; Insert(hs, &ee);ee.key = 16; ee.value = 116; Insert(hs, &ee);ee.key = 17; ee.value = 117; Insert(hs, &ee);ee.key = 18; ee.value = 118; Insert(hs, &ee);ee.key = 19; ee.value = 119; Insert(hs, &ee);ee.key = 20; ee.value = 120; Insert(hs, &ee);ee.key = 21; ee.value = 121; Insert(hs, &ee);PrintHash(hs);if (Lookup(hs, 21) == nullptr){cout << "查找key=21失败" << endl;}else{cout << "key=21,value=" << Lookup(hs, 21)->elem.value << endl;}Delete(hs, 21);PrintHash(hs);if (Lookup(hs, 21) == nullptr){cout << "查找key=21失败" << endl;}else{cout << "key=21,value=" << Lookup(hs, 21)->elem.value << endl;}DestoryHash(hs);return 0;
}