散列存储的特点:

散列是数组存储方式的一种发展,相比数组散列的数据访问速度要高于数组,因为可以依据存储数据的部分内容找到数 据在数组中的存储位置,进而能够实现快速的访问,理想的散列访问速度是非常迅速的,而不像在数组中的遍历过程,采用存储数组中内容的部分元素作为映射函数的输入,映射函数的输出就是存储数据的位置。这样就省去了遍历数组的过程所用的时间。

散列存储存在的问题:

散列是一种快速实现访问的存储方式。通常作为检索部分的数据项是整型或者字符串,当时字符串时,字符串的数量要远大于数组的长度,这时候就会有多个字符串映射到一个存储位置的情况,这就是所谓的冲突问题。

解决冲突的方式:

(1)采用链表的形式,将所有冲突的数据项采用链表的形式链接起来,这样搜索数据的复杂度就包含了链表的遍历问题,特别是当所有项都链接到一个链表下时,这时候实际上就是遍历链表,复杂度不一定有很大的进步,但是这种链表链接的方式有很高的填充性。

(2)充分利用没有实现的存储空间,利用探测法探测空闲的空间,进而实现数据的存储,目前有三种探测方式:线性探测法,平方探测法,以及双散列法,其中平方探测法运用比较多。