【数据结构】散列表

前端之家收集整理的这篇文章主要介绍了【数据结构】散列表前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

比较并对比散列表和STL map。

如果输入的数据量不大,可以选用哪些数据结构替代散列表?

在散列表里,值的存放是通过将键传入散列函数实现的。值并不以排序后的顺序存放。

此外,散列表以键值找出索引,进而找到存放值的地方,因此,插入或查找操作均摊后可以在O(1)时间内完成。(假定该散列表很少发生碰撞冲突)

散列表还必须处理潜在的碰撞冲突,一般通过拉链法解决(chaining),也就是,创建一个链表来存放值,这些值的键都映射到同一个索引。

STL map的做法是根据键,将键值对插入二叉查找树,不需要处理冲突。因为树是平衡的,插入和查找的时间都是O(logN)。

散列表时如何实现的?

传统上,散列表都是用元素为链表的数组实现的。想要插入键值对时,先用散列函数将键映射为数组索引,随后,将值插入那个索引位置对应的链表。
在数组的特定索引位置的链表中,各个元素的键并不相同,这些值的hashFunction(key)才是相同的。
因此,为了取回某个键对应的值,每个结点都必须存放键和值。

总之,散列表以链表数组的形式实现,链表中每个结点都会存放两块数据:值和原先的键。此外还要注意以下设计准则:
1. 我们希望使用一个优良的散列函数,确保能将键均匀地分散开来。若分散不均匀,就会发生大量碰撞冲突,那么查找元素的效率会变得非常低下。
2. 不论散列函数选得多好,还是会出现碰撞冲突,因此需要一种碰撞处理办法。通常我们会采用拉链法,但这并不是唯一的方法
3. 我们可能还希望设法根据容量动态扩大或缩小散列表的大小。例如,当元素数量和散列表大小之比超过一定阈值时,可能会希望扩大散列表的大小。
这意味着需要新建一个散列表,并将旧的散列表条目转移到新的散列表中。但这种操作开销非常大,不可频繁操作。

如果输入的数据量不大,可以选用哪些数据代替散列表?
可以使用STL map或二叉树。尽管它们的插入需要O(logN)时间,但如果数据量不大,这点时间可以忽略不计。
原文链接:https://www.f2er.com/datastructure/382620.html

猜你在找的数据结构相关文章