> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/introduction-to-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/introduction-to-algorithms/introduction-4.md).

# 第11章 散列表

## 一、概念

### 1.综述

散表表仅支持INSERT、SEARCH、DELETE操作。

把关键字k映射到槽h(k)上的过程称为散列。

多个关键字映射到同一个数组下标位置称为碰撞。

好的散列函数应使每个关键字都等可能地散列到m个槽位中

### 2.散表函数

（1）若函数为h(k)=k，就是直接寻址表

![](http://windmissing.github.io/images_for_gitbook/Introduction_to_Algorithms/6.gif)

（2）除法散列法：h(k) = k mod m

（3）乘法散列法：h(k) = m *(k* A mod 1) (0\<A<1)

（4）全域散列：从一组仔细设计的散列函数中随机地选择一个。（即使对同一个输入，每次也都不一样，平均性态较好）

### 3.冲突解决策略

（1）链接法

（2）开放寻址法

a.线性探测：h(k, i) = (h'(k) + i) mod m

b.二次探测：h(k, i) = (h'(k) + c1*i + c2* i^2) mod m

c.双重散列：h(k, i) = (h1(k) + i \* h2(k)) mod m

（3）完全散列：设计一个较小的二次散列表

## 二、代码

代码中用到了函数指针，函数指针的用法参考函数指针总结

```
//Hash.h
#include <iostream>
using namespace std;

int m, NIL = 0;
//11.4 开放寻址法
typedef int (*Probing)(int k, int i);
int h(int k)
{
    return k % m;
}
int h2(int k)
{
    return 1 + k % (m-1);
}
//线性探测
int Linear_Probing(int k, int i)
{
    return (h(k) + i) % m;
}
//二次探测
int Quadratic_Probint(int k, int i)
{
    int c1 = 1, c2 = 3;
    return (h(k) + c1 * i + c2 * i * i) % m;
}
//双重探测
int Double_Probint(int k, int i)
{
    return (h(k) + i * h2(k)) % m;
}
int Hash_Insert(int *T, int k, Probing p)
{
    int i = 0, j;
    do{
        j = p(k, i);
        if(T[j] == NIL)
        {
            T[j] = k;
            return j;
        }
        i++;
    }
    while(i != m);
    cout<<"error:hash table overflow"<<endl;
}

int Hash_Search(int *T, int k, Probing p)
{
    int i = 0, j;
    while(1)
    {
        j = p(k, i);
        if(T[j] == NIL || i == m)
            break;
        if(T[j] == k)
            return j;
        i++;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://windmising.gitbook.io/introduction-to-algorithms/introduction-4.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.