python之字典（哈希表应用）

哈希表定义哈希表Hash Table是一种根据键Key直接访问值Value的数据结构。它通过哈希函数将键映射到表中的一个位置从而实现 O(1) 平均时间复杂度的插入、删除和查找操作。python中对字典进行的优化在3.6之前字典只是无序的哈希表一样可以看作一个嵌套数组整体是一个数组里面又存储了hash值键值的小数组。而从3.7以后紧凑存储将哈希表拆分为两个结构紧凑布局减少内存占用保留顺序提高遍历效率1.索引2.实体这很像我们查字典先在索引里查找这个对应的页码再翻到这页找到这个字。你可能很困惑这到底那里紧凑了这又要说回老字典。enteies [ [--, --, --], [hash, key, value], [--, --, --], [--, --, --], [hash, key, value], ]你会发现这里是有空位的这是牺牲了内存来换取稳定的速度为了减少不同键映射到同一位置的概率。哈希表内部有一个固定长度的数组称为桶数组。当我们插入一个键值对时会先通过一个哈希函数计算出键的哈希值一个整数然后对这个整数取模hash % len(array)得到该键在数组中的存储位置索引。由于数组的长度是固定的比如 8、16、32…而哈希值取模后的结果只能是 0 到len-1之间的整数。因此只要键的数量超过数组长度或者不同的键经过取模后得到相同的余数就会发生哈希冲突——即多个键被映射到同一个位置。键cat的 ASCII 和 9997116 312取模 5 → 312 % 5 2键dog的 ASCII 和 100111103 314取模 5 → 314 % 5 4键tac的 ASCII 和 1169799 312取模 5 → 312 % 5 2indices [None, None, index, None, index, None, index] enteies [ [hash0, key0, value0], [hash1, key1, value1], [hash2, key2, value2] ]新代码改后减少了内存占用保持插入顺序迭代效率提升冲突解决python使用的解决方法是开放寻址法会自动寻找下一个空位或者直到发现已经满了即为On,为了保证能很快查找到下一个空位Python字典的哈希算法会尽量保证哈希值计算出的index是平均分布且每一个值之间有剩余位置开放方式j ((5*j) 1) mod 2**i动态扩容与负载因子dict会保持一个约 2/3 的负载因子即当实际元素数量达到哈希表容量的约三分之二时就会触发扩容。扩容通常会将哈希表容量翻倍并重新计算所有已有键的位置rehash。这虽然是一次性开销但能确保长期性能稳定在O(1)级别。字典的基本使用语法创建1.直接创建 hash{} 2.dict()创建 hashdict() 3.字典推导式Python 2.7 squares {x: x**2 for x in range(5)} # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}访问值1.直接访问键对应的值如果不存在会报KeyError dict[key] 2.安全访问不存在时返回defalt默认None dict.get(key,default)修改值dict[apple]12 #若存在就会新建不存在则修改遍历字典# 遍历所有键 for key in my_dict: print(key) # 遍历所有值 for value in my_dict.values(): print(value) # 遍历所有键值对 for key, value in my_dict.items(): print(f{key}: {value})字典的排序# 按键排序 sorted_by_key dict(sorted(my_dict.items())) print(sorted_by_key) # 按值排序 sorted_by_value dict(sorted(my_dict.items(), keylambda x: x[1])) print(sorted_by_value)注意点Python字典的key可以使用字符串str整型int元祖tuple等。我们已经知道字典是通过哈希算法来计算key的值所以key必须为可哈希的list不能作为字典的key因为list是可变的及不可哈希的对象所以不能作为字典的key。键唯一性重复键赋值时后值覆盖前值。一个键里可以有两个或多个避免在循环中动态修改字典。PTAL2-021微博上有个“点赞”功能你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签而你点赞的博文的类型也间接刻画了你的特性。然而有这么一种人他们会通过给自己看到的一切内容点赞来狂刷存在感这种人就被称为“点赞狂魔”。他们点赞的标签非常分散无法体现出明显的特性。本题就要求你写个程序通过统计每个人点赞的不同标签的数量找出前3名点赞狂魔。输入格式输入在第一行给出一个正整数N≤100是待统计的用户数。随后N行每行列出一位用户的点赞标签。格式为“NameK F1​⋯FK​”其中Name是不超过8个英文小写字母的非空用户名1≤K≤1000Fi​i1,⋯,K是特性标签的编号我们将所有特性标签从 1 到 107 编号。数字间以空格分隔。输出格式统计每个人点赞的不同标签的数量找出数量最大的前3名在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列则输出标签出现次数平均值最小的那个题目保证这样的用户没有并列。若不足3人则用-补齐缺失例如mike jenny -就表示只有2人。输入样例5bob 11 101 102 103 104 105 106 107 108 108 107 107peter 8 1 2 3 4 3 2 5 1chris 12 1 2 3 4 5 6 7 8 9 1 2 3john 10 8 7 6 5 4 3 2 1 7 5jack 9 6 7 8 9 10 11 12 13 14输出样例jack chris johnn int(input()) users {} for _ in range(n): parts input().split() name parts[0] k int(parts[1]) tags list(map(int, parts[2:2 k])) unique_tags set(tags) count_unique len(unique_tags) avg k / count_unique users[name] { count_unique: count_unique, avg: avg } sorted_users sorted(users.items(), keylambda x: (-x[1][count_unique], x[1][avg])) top_names [user[0] for user in sorted_users[:3]] while len(top_names) 3: top_names.append(-) print( .join(top_names[:3]))