哈希表（散列表）查找定义

想象一个场景，如果想在一个学校中找出一个叫王五的学生，一般思路是去学生处把全校的学生名单列表拿出一个，一个一个的查找，这种方法就是普通的顺序查找，依赖的是姓名关键字的比较。如果你恰巧遇见了一个王五班里的同学张三，他就直接可以带你去找到王五同学，这样就不需要去遍历比较姓名，就可以直接找到王五。
也就是说，只需要通过某个函数f（张三），使得

存储位置（王五） = f（关键字）

那样我们可以查找关键字f不需要比较就可以获得需要记录的位置，这种存储技术就叫做散列技术。

散列技术是在记录存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。我们把这种对应关系f称为散列函数，又称为哈希（Hash）函数。采用散列技术将基础存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表（HashTable）。

哈希表实现步骤

整个过程其实只有两步：

1. 存储时，通过哈希函数计算记录的哈希地址，并按此地址存储该记录。
2. 查找记录时，同样通过哈希函数计算记录的散列地址，按此散列地址访问该记录。

所以说散列技术既是一种存储方法，也是一种查找方法。它与线性表、树、图等数据结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，而哈希技术之间数据元素不存在逻辑关系，它只与关键字有关系。因此，哈希主要是面向查找的存储结构。

哈希表性能分析

在没有哈希冲突的情况下，哈希表是在查找中效率最高的，因为它的时间复杂度为O(1)。然而在实际应用中，冲突是不可避免的，那么散列表的平均查找长度取决于那些因素呢？

1. 处理冲突的方法：相同的关键字，相同的散列函数，处理冲突的方法不同，会使得平均查找长度不同。
2. 哈希表的装填因子α： α=填入表中的记录个数/哈希表长度。α标志着哈希表的装满程度。当填入表中的记录越多，α越大，产生冲突的可能性就越大。也就是说哈希表的平均查找长度取决于装填因子，而不是取决于集合中的记录个数。可以通过将哈希表的空间设置的比查找集合大，通过牺牲空间，在换取查找效率。这样我们的哈希查找的时间复杂度就是真的是O(1)了。

哈希表的应用场景

哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况。