哈希表和数组的定义,区别,优缺点?

如题所述

第1个回答  2012-05-14
哈希表是通过 元素关键码 的值 直接查找 元素存储位置的 数据结构
数组是通过 下标 可以直接访问到 下标对应位置上元素的 数据结构

哈希表: 元素的关键码 通过 散射函数 映射 得到的函数值 就是 哈希表数组的下标(一般的哈希表组织元素的方法还是数组)

数组只能通过下标迅速访问,但是这个下标与数组里存的元素值没什么关系;
哈希表 通过散射函数 建立了 数组元素关键码的值 与 下标的关系 ; 是数组的加强版;

所以;哈希表可以 直接访问到 元素关键码 对应的 元素 上去;(相当于由 关键码 通过 散射函数的映射 直接找到了 这个元素 在 哈希表 中的 下标)。但是由于散射函数的作用,元素不能占满整个哈希表,哈希表不是每一个位置都有元素的;

综上述:哈希表:优点:直接访问到关键码值对应的元素(数据);缺点占用空间很大;
数组:优点:结构紧凑;缺点:不能直接访问到关键码值所对应的元素(数据);