散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名{\displaystyle x}x到首字母{\displaystyle F(x)}F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则{\displaystyle F()}F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
基本概念
-
若关键字为{\displaystyle k}k，则其值存放在{\displaystyle f(k)}f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系{\displaystyle f}f为散列函数，按这个思想建立的表为散列表。
-
对不同的关键字可能得到同一散列地址，即{\displaystyle k{1}\neq k{2}}k{1}\neq k{2}，而{\displaystyle f(k{1})=f(k{2})}f(k{1})=f(k{2})，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数{\displaystyle f(k)}f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
-
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
构造散列函数
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。
1.直接定址法：取关键字或关键字的某个线性函数值为散列地址。即{\displaystyle hash(k)=k}hash(k)=k或{\displaystyle hash(k)=a\cdot k+b}hash(k)=a\cdot k+b，其中{\displaystyle a\,b}a\,b为常数（这种散列函数叫做自身函数）
2.数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
3.平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
4.折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
5.随机数法
6.除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即{\displaystyle hash(k)=k\,{\bmod {\,}}p}hash(k)=k\,{\bmod \,}p, {\displaystyle p\leq m}p\leq m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。
Examples
在C语言中，实现以上过程的简要程序
开放定址法
// HashTable
InitializeTable(int TableSize) {
HashTable H;
int i;
// 為散列表分配空間
// 有些编譯器不支持為struct HashTable 分配空間，聲稱這是一個不完全的結構，
// 可使用一个指向HashTable的指針為之分配空間。
// 如：sizeof(Probe)，Probe作为HashTable在typedef定義的指針。
H = malloc(sizeof(struct HashTable));
// 散列表大小为一个質数
H->TableSize = Prime;
// 分配表所有地址的空間
H->Cells = malloc(sizeof(Cell) * H->TableSize);
// 地址初始為空
for (i = 0; i < H->TableSize; i++)
H->Cells[i].info = Empty;
return H;
}查找空单元并插入
// Position
Find(ElementType Key, HashTable H) {
Position Current;
int CollisionNum;
// 冲突次数初始为0
// 通過表的大小對關鍵字進行處理
CollisionNum = 0;
Current = Hash( Key, H->TableSize );
// 不為空時進行查詢
while (H->Cells[Current].info != Empty &&
H->Cells[Current].Element != Key) {
Current = ++CollosionNum * ++CollisionNum;
// 向下查找超過表範圍時回到表的開頭
if (Current >= H->TableSize)
Current -= H->TableSize;
}
return Current;
}分离连接法
查找效率
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
- 散列函数是否均匀；
- 处理冲突的方法；
- 散列表的载荷因子（英语：load factor）。
