赞
踩
#哈希表 = 散列表,本质上是数组, #其通过把键映射到存储桶中来实现快速查找。 #具体来说,哈希表使用哈希函数将键值映射到哈希表中的一个桶中,然后在该桶中查找对应的键值对 #key:value 键值对,一个键对应一个值,但值可以是list来存取多个元素 #哈系表的优势是搜索, 插入和删除, 搜索是O(1)时间复杂度 #哈希碰撞:2个不同的key通过同一个哈希函数得到了相同的内存地址 #如果发生哈希碰撞了,就把这个键值对用链表的方式存储,具体方法就是将先在存放这个内存地址上的键值对的next指针指向冲突的那个键值对。 #访问:因为哈希表没有索引这个概念,所以访问是不存在的 #搜索:指对key进行搜索,因为直接把key给哈希函数就知道内存地址了,时间复杂度0(1)。碰撞:O(K),K为碰撞元素的个数 #插入:O(1),比如插入个 5:A的键值对,把5这个key通过哈希函数找到内存地址然后把A这个值插进去。 #删除:O(1),比如 5:A的键值对,把5这个key通过哈希函数找到内存地址然后把A这个值删掉。 #哈希表常用操作 #创建哈希表 #1.用数组创建哈希表,把索引当中哈希表的key hashTable = ['']*4 print(hashTable)#['', '', '', ''] #2.用字典创建哈希表 mapping = {} #添加元素,O(1)时间复杂度,因为嗖的一下就能得到对应的内存地址,然后就修改 hashTable[1] = "gaoxiang" hashTable[2] = "yidiao" hashTable[3] = "liusha" mapping[1] = "gaoxiang" mapping[2] = "yidiao" mapping[3] = "liusha" #修改元素 hashTable[1] = 'bishi' mapping[1] = 'bishi' #删除元素,这里都是指删除key,O(1)时间复杂度 hashTable[1] = ''#把改成空字符串,下次碰到值是空字符串就代表这个key已经删掉了 mapping.pop(1) #删掉后哈希表是没有1这个key了 #del mapping[1] #删掉后哈希表是没有1这个key了 #获取key的值 hashTable[3] mapping[3] #检查key是否存在,数组创建的哈希表没法实现这个功能 3 in mapping #True #搜索元素 #a是键值key,如果存在dict存在a这个key,则函数返回dict[a]这个value;否则返回b,如果没有定义b参数,则返回None。 dict.get(a,b) dict.get(a) #哈希表长度 len(mapping) #哈希表是否还有元素 len(mapping) == 0 #遍历key for i in mapping.keys() : print(i,end=",")#2,3, #遍历value for i in mapping.values() : print(i,end=",")#yidiao,liusha, #取出全部keys和value值 for i in mapping.items() : print(i,end=",")#(2, 'yidiao'),(3, 'liusha')用下标0和1进行取值 #for key, value in mapping.items() #删除指定的键值对 dic1 = {“a”: “C”, “b”: “Python”, “c”: “RPA”, “d”:“艺赛旗”} dic1.pop(“c”) print(“dic1:”, dic1) #使用list作第一个参数,创建列表字典,即value是list #当字典中没有的键第一次出现时,default_factory自动为其返回一个空列表,list.append()会将值添加进新列表;再次遇到相同的键时,list.append()将其它值再添加进该列表 from collections import defaultdict s=[('yellow',1),('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)] d=defaultdict(list) for k, v in s: d[k].append(v) # 根据key的ASCII升序排列,把key value都打印出来 a=sorted(d.items()) print(a) #[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
Refer: 来吧!一文彻底搞定哈希表!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。