散列表与散列冲突

目录 散列表与散列冲突 解决散列冲突的方法 1.分离链接法(拉链法) 2.开放寻址法 再散列 散列表与散列冲突 HashTable,音译为哈希表,是根据关键字(key)而直接进行访问的数据结构。关键字k,值存放在f(k)的存储位置上,则f为散列函数。关键字(key)通过散列函数直映射到表中一个位置,以加快查找速度。 散列冲突,因为存储单元数目是有限的,当关键字数量增大时,两个不同的关键字k1,k2可能会出现f(k1) == f(k2),而关键字实际上是无限的,所以这种冲突不可避免。目前主流解决散列冲突的方式有两种:一种是开放寻址法,另一种是分裂链接法(拉链法)。 解决散列冲突的方法 1.分离链