如题所述
平均情况下,查找速度最快,而且又能适应插入、删除的数据结构是散列表。
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash)函数。
平均情况下,查找速度最快,而且又能适应插入、删除的数据结构便是散列表。
散列表的特点
1、访问速度很快
由于散列表有散列函数,可以将指定的Key都映射到一个地址上,所以在访问一个Key(键)对应的Value(值)时,根本不需要一个一个地进行查找,可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时,速度都很快。
2、需要额外的空间
首先,散列表实际上是存不满的,如果一个散列表刚好能够存满,那么肯定是个巧合。而且当散列表中元素的使用率越来越高时,性能会下降,所以一般会选择扩容来解决这个问题。
另外,如果有冲突的话,则也是需要额外的空间去存储的,比如链地址法,不但需要额外的空间,甚至需要使用其他数据结构。这个特点有个很常用的词可以表达,叫作“空间换时间”,在大多数时候,对于算法的实现,为了能够有更好的性能,往往会考虑牺牲些空间,让算法能够更快些。
3、无序
散列表还有一个非常明显的特点,那就是无序。为了能够更快地访问元素,散列表是根据散列函数直接找到存储地址的,这样我们的访问速度就能够更快,但是对于有序访问却没有办法应对。
4、可能会产生碰撞
没有完美的散列函数,无论如何总会产生冲突,这时就需要采用冲突解决方案,这也使散列表更加复杂。通常在不同的高级语言的实现中,对于冲突的解决方案不一定一样。