哈希表(Hash table),也称为散列表,是一种根据关键码值(Key value)直接进行访问的数据结构。它通过散列函数(Hash function)将关键码值映射到表中的一个位置,以此来访问记录,从而加快查找的速度。以下是关于哈希表的详细解释:
基本概念
散列函数:将关键码值映射到表中位置的函数,记作f(key)。给定关键字k,其值存放在f(k)的存储位置上。
冲突:对于不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)==f(k2),这种现象称为冲突。
同义词:具有相同函数值的关键字对该散列函数来说称做同义词。
实现方法
哈希表的实现主要有两种方法:
开放寻址法:所有的元素都存储在哈希表的数组中,冲突发生时会探测下一个可用的位置,直到找到一个空闲的位置。这种方法保持了元素的顺序,但可能导致聚集(clustering)。
链地址法:使用一个数组来存储指向链表头部的指针,每个链表存储具有相同哈希值的元素。如果发生冲突,新的元素将被添加到该链表的末尾。这种方法可以避免聚集,但不保持元素的顺序。
特点
高效性:哈希表可以在O(1)的平均时间复杂度下完成查找、插入和删除操作,这是因为它通过散列函数直接定位到元素在数组中的位置。
无序性:哈希表不保证元素的顺序,元素在表中的位置取决于其关键码值和散列函数。
空间利用率