什么是哈希表(Hashtable)？

在计算机科学中，哈希表是一种用于存储数据的数据结构，它由一系列值组成，称为键，与相应的值列表（称为数组）配对。例如，企业名称可能与其地址成对出现。通常，数组中的每个值都有一个称为散列的位置号。散列函数通常是一组指令或一种算法，将每个键值映射为散列-将企业名称与其地址、电话号码和业务类别连接起来，例如，哈希函数的目的是将每个键分配给数组中唯一的对应值；这通常被称为哈希。哈希函数的格式必须正确，哈希表才能正常工作。哈希表是一种数据结构，用于存储由一组称为键的值组成的数据与相应的值列表配对，一个哈希表在一组数据上的性能取决于它的哈希函数的效率。一个好的哈希函数通常提供一个统一的键查找和均匀的分布对应数组中的映射。当两个键分配给相同的对应值时，会发生哈希冲突。当发生哈希冲突时，通常会再次执行哈希函数，直到找到唯一的对应值；这通常会导致哈希时间更长。虽然哈希表中的键数通常为修正了，有时可能有重复的密钥即使如此，一个设计良好的哈希表也有有效的哈希函数，可以将每个键映射到数组中唯一的对应值，哈希表中效率低下的哈希函数也可能生成映射簇。如果哈希函数为现有键创建映射簇，则会增加查找相应值所需的时间。这会减慢对未来键的哈希处理，因为大多数哈希函数通常会查找下一个可用的在数组中的位置。如果已经分配了一个大的值簇，则通常需要更长的时间来寻找一个新的键的未分配值。加载因子是另一个与哈希函数的效率有关的概念；加载因子是与哈希表中相应数组的总大小相关的已存在哈希值的量。它通常是通过将已分配的键的数目除以相应数组的大小来定义的。随着加载因子的增加，一个好的哈希函数通常仍会保持一个恒定的数目碰撞和聚集到某一点。通常这个阈值可以用来确定哈希函数在给定的密钥数下的效率，以及何时需要一个新的哈希函数努力生成完美的哈希函数-在负载因子增加的情况下不会产生冲突或簇。理论上，产生完美哈希表的关键是生成一个完美的哈希函数研究人员认为，在一般情况下，哈希函数在达到一个常数的情况下，在没有达到一个完美的阈值的情况下，哈希函数仍然可以达到理想的性能。