计算机知识处理冲突方法思维导图
简单介绍处理冲突方法的内容
树图思维导图提供 计算机知识处理冲突方法思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机知识处理冲突方法思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：65671a8f222f42e7216ad9a6e23f97c6
思维导图大纲
处理冲突方法思维导图模板大纲
开放定址法
定义
指可存放新表项的空闲地址，既向它的同义词表项开放，有向它的非同义词表项开放
递推公式
Hi = （H(key)+di）%m
i = 0,1,2,…k ( k <= m-1 )
m为散列表表长、di为增量序列
根据增量序列不同分为
平方探测法
当di = 0，1，-1^2，2^2，-2^2，3^2，-3^2....k^2, -k^2 (k <= m/2)
散列表长度m必须可以表示成 4k+3的素数，又称二次探测法
避免“堆积”问题，但不能探测到散列表的所有单元，但至少能探测到一半
再散列法
当di = Hash2(key)时，称为再散列法/双散列法
需要两个散列函数，当第一个散列函数发生冲突时，利用第二个散列函数Hash2（key）计算该关键字的地址增量
Hi = （H(key)+i*Hash2(key)）%m
初始探测位置H0=H(key)%m，i是冲突次数，初始为0
最多经过m-1次探测会遍历表中所有位置，会到H0
伪随机序列法
di为伪随机序列
线性探测法
当di = 0，1，2，3....m-1时，称为线性探测法
缺点
会造成大量相邻元素在散列地址的“聚集”/“堆积”现象，降低查找效率
当发生冲突时，循环查找散列表下一个空闲的单元（到m-1下一个要找的就是0）可能会查遍全表
注：
开放定址法不能随便删除物理表中已有的元素，删除了则会截断其他具有相同散列地址的元素的查找地址
要删除时可以进行逻辑删除，需要定期维护散列表
拉链法（链接法）
定义
把所有同义词存储在一个线性表中，这个线性表由其散列地址唯一标识
查找、插入、删除在同义词链中进行、适合频繁进行插入删除的情况
沪公网安备 31011502019485号
上海工商