哈希(HASH)表相关基础知识

2013年4月15日 由 Creater 留言 »

1.与hash表冲突相关的因素

  • 装填因子。a = n/m,n表示hash表中已经存有的元素个数。m表示hash表的大小
  • 与hash函数有关
  • 与解决冲突函数有关

2.hash函数构造方法

  • 除留余数 (就是取模),一般采用素数作为模数,因为素数被整除概率小。取奇数不取偶数因为,偶数模会让偶数放在偶数区间,奇数放在奇数区间。
  • 直接定址
  • 数字分析
  • 其他如求和,位运算等等

3.hash冲突解决办法

  • 开放定址,如线性探测法,平方探测法,伪随机数法
  • 链表法
广告位

发表评论

你必须 登陆 方可发表评论.