具有增删困难、查找容易的特点,可以在任意位置增删数据,所以数组的增删操作会更为多样。
ArrayList
时,数组申请的空间永远是我们在估计了数据的大小后才执行,所以在后期维护中也相当麻烦。s = ""
,书面中也可以直接用 Ø
表示。s = " "
,就是包含了 3 个空格的字符串。O(logn)
。O(logn)
。这里的时间复杂度更多是消耗在了遍历数据去找到查找位置上,真正执行插入动作的时间复杂度仍然是 O(1)。实现 “地址 = f (关键字)” 的映射关系,快速完成基于数据的数值的查找。
哈希函数为关键字到地址的线性函数。如,H (key) = a*key + b。这里,a 和 b 是设置好的常数。
假设关键字集合中的每个关键字 key 都是由 s 位数字组成(k1,k2,…,Ks),并从中提取分布均匀的若干位组成哈希地址。
如果关键字的每一位都有某些数字重复出现,并且频率很高,我们就可以先求关键字的平方值,通过平方扩大差异,然后取中间几位作为最终存储地址。
如果关键字的位数很多,可以将关键字分割为几个等长的部分,取它们的叠加和的值(舍去进位)作为哈希地址。
预先设置一个数 p,然后对关键字进行取余运算。即地址为 key mod p。
常用的探测方法是线性探测法。比如有一组关键字 {34,35,36,45},采用的哈希函数为 key mod 11。当插入 34,35,36 时可以直接插入,地址分别为 1、2、3。而当插入 45 时,哈希地址为 45 mod 11 = 1。然而,地址 1 已经被占用,因此沿着地址 1 依次往下探测,直到探测到地址 4,发现为空,则将 45 插入其中。
将哈希地址相同的记录存储在一张线性链表中。如果出现冲突,就在对应的位置上加上链表的数据结构。