复杂度分析:
顺序查找: O(n)
二分查找: O(\log_2n)
散列方法: O(C)
散列表与散列方法
将一个元素的关键码和存储位置之间建立对应的函数关系 Hash( ), 使得每个关键码与结构中的唯一的存储位置相对应...闭散列又叫开地址法. 所有的桶都直接放在散列表数组中,并且把该数组组织成环形结构. 每个桶只有一个元素. 当发生冲突时, 把这个元素存放进表中”下一个”空桶中.寻找空桶的方法有很多....线性探查法
若hash(key)=d并且这个桶已经被占用, 那么检查数组中连续的桶:d+1,d+2...m-1,0,...d-1.寻找下一个桶的公式:
每次发生冲突就探查下一个桶, 当循环 m...它是对于散列表中每个地址而言的, 其实就是从每个桶到下一个空桶需要探查的次数的平均值.
散列表存储的是元素集合, 不允许关键码相同的元素存在....注意:闭散列情况下不能真正地将已有的元素删去, 因为中间的元素被删掉后会影响到之后元素的探查. 所以用一个状态数组来标识哈希表中每个元素的状态.