怎么修改网站后台权限,鸿兴网站建设公司,wordpress get_comment,天元建设集团有限公司济南分公司哈希表基础
哈希表是一类数据结构#xff08;哈希表包含数组、集合和映射#xff0c;和前两篇文章叙述的字符串、链表平级#xff09;哈希表概念#xff1a;类似于Python里的字典类型#xff0c;哈希表把关键码key值通过哈希函数来和哈希表上的索引对应起来#xff0c;之…哈希表基础
哈希表是一类数据结构哈希表包含数组、集合和映射和前两篇文章叙述的字符串、链表平级哈希表概念类似于Python里的字典类型哈希表把关键码key值通过哈希函数来和哈希表上的索引对应起来之后输入key值可直接定位到对应索引位置然后进行取值哈希表的好处主要为查找方便可快速判断一个元素是否在集合中哈希函数即关键码key值和存储位置索引的对应关系一个散列函数比如把小明映射为0小李映射为1如图 哈希碰撞 定义当哈希函数的映射关系把多个关键码映射到了同一个哈希表索引上时这种现象称为哈希碰撞如图所示哈希碰撞有时候是因为关键码的数量大于哈希表的长度这时不可避免发生碰撞但是也可能是哈希函数的对应关系不合理使得即便仍有空索引还是把部分关键码分配到了同一索引上 其实发生哈希碰撞不见得是个坏事如果是因为关键码的数量大于哈希表的长度说明此时哈希表的所有索引都被完全利用没有发生内存浪费解决方案一拉链法 当发生冲突时在对应索引位置通过链表结构储存多个关键码如图所示 解决方案二线性探测法 如果是哈希函数的对应关系不合理使得即便仍有空索引还是把部分关键码分配到了同一索引上此时可以利用线性探测法从发生冲突的索引位置开始线性查找找到下一个空索引然后把多余的关键码分配过去如图所示
常见的三种哈希表结构
列表set集合 是一种数据结构常用于元素的查找和去重特点元素不重复、乱序、可遍历、可变创建方式一my_set {1, 3, 5}创建方式二my_set set()或列表转集合my_set set([1, 3, 5])元素查找使用关键字in如if TOM in my_set:元素去重集合结构会进行自动去重操作数学操作 交集set1 | set2将返回二者的交集并集set1 set2将返回二者的并集差集set1 - set2将返回1中有2中没有的元素 常用方法 添加元素set.add(data)删除元素set.remove(data)或set.discard()当删除集合中不存在的元素时前者会引起异常后者不会集合长度len(set)清空集合set.clear() map映射
