哈希表：链地址法和开放定址法

在哈希表中不免会发生元素之间的冲突为了避免冲突因此就需要一些措施来加入元素于是链地址法和开放定址法就产生了图1.1链地址法顾名思义就是使用链表来存储冲突的元素。如果插入的元素列表是{1,11,13,73,93,125}使用链地址法的哈希表是这样的参考图1.1删除的时间复杂度O(1)最坏情况O(n)当所有元素都冲突时插入的时间复杂度O(1)最坏情况O(n)当所有元素都冲突时图2.1开放地址法当产生元素冲突时开放地址法会把当前冲突的元素往后移动直到找到空位为止。插入的元素列表同链地址法参考图2.1删除的时间复杂度O(1)最坏情况O(n)当所有元素都冲突时需要注意的是由于元素和所处的位置并不对应所以对于删除只能打删除标记插入的时间复杂度O(1)最坏情况O(n)当所有元素都冲突时