哈希表

简介

什么是哈希表?

哈希表是一种数据结构,借助一个或多个哈希函数将数据存储在键/值对中。 哈希表非常快-它们允许在固定时间内(至少在最佳情况下)进行数据查找(检索),插入和删除。 这使它们成为用于存储地址簿,在数据库中存储项目或以编程语言表示对象(JavaScript使用哈希表创建其对象!)之类的理想数据结构。

哈希表如何工作?

哈希表由数据数组(通常存储在存储桶中)和哈希函数组成。 哈希函数使用模块化数学将键(通常是字符串)转换为数组索引。 哈希函数是确定性的,这意味着相同的输入将始终返回相同的输出-但还应在数组中均匀分配索引,并应尽量减少冲突。

缺点?

在不断进行时间插入,删除和查找的过程中,很可能会认为哈希表是几乎任何数据需求的正确选择,但是像其他任何东西一样,它们各有千秋。 对于初学者来说,即使具有恒定的时间访问权限,哈希函数也很费力; 在某些情况下,数组或链表的线性时间性能可能优于哈希表。 对于非常小的数据集尤其如此。 此外,错误的哈希函数将严重降低任何哈希表的效率。 如果该函数不成比例地返回某些索引,而返回的索引更多,则可能导致其他冲突,从而导致访问时间变慢。 但是,某些冲突在数学上是不可避免的,并且如何处理这些冲突对哈希表的性能具有重大影响。

处理碰撞

将两个或更多键分配给同一索引时,哈希表怎么办? 一种解决方案是简单地找到下一个可用索引。 这称为开放索引。 在存储数据时,如果已分配的索引被占用,则可以应用一致的数学函数来搜索未占用的索引。 该功能就像检查紧邻的索引一样简单! 除非哈希表负载因数(当前存储的项数除以数组中的空间总数)太高,否则这是处理冲突的一种非常有效的方法。

第二次机会

另一个选择是拥有第二选择哈希函数,该函数始终会产生与第一选择函数不同的结果。 在存储或访问值时,哈希表可以检查第一个哈希函数,如果第一个哈希函数已在使用中,则可以继续检查第二个哈希函数。 这减少了发生冲突的机会,但增加了在数组中插入和访问值的负担。

桶的乐趣

处理冲突的另一种方法是使数组中的每个空间指向内存中的另一个列表。 这些列表称为存储桶。 因为从理论上讲,每个存储桶仅占整个数据集的一小部分,所以即使必须线性进行数据访问也仍然要快得多。 但是,这些存储桶不必是较小的数组,而可以是链表或二进制树或几乎任何最适合数据集需求的其他数据结构。