您的位置:

python中可哈希(python中可哈希的数据类型)

本文目录一览:

python字典的构成形式为

python字典的构成形式为:字典是Python语言中唯一的映射类型。

映射类型对象里哈希值(键,key)和悔樱闷指向的对象(值,value)是一对多的关系,通常被认为是可变的哈希表。

字典对象是可变的,它是一个容器类型,能存储任意个数的Python对象,其中也可包括其他容器类型。

字典类型与序列类型的区别:

1、存取和访问数据的方式不同。

2、序列类型使用数字类型的键(从序列的开始按数值顺序索引)。

3、映射类型可以用其他对象类型作键(如:数字、字符串、元祖,一般用字符串作键),和序列类型的键不同,映射类型的键直接或间接的和存储数据值相关联。

4、映射类型中的数据是无序排列的。这和序列类型是不一样的,序列类型是以数值序排列的。

5、映射类型用键直接“映射”到值。

字典是Python中最强大的数据类型之一

使用字典的注意不能允许一键对应多个值;键必须是可哈希的。

len()返回字典的长度。

hash()返回对象的哈希值,可以用来判断一个对象能否用来作为字典的键。

dict()工厂函数,用来创建字典颂迹。

什么是可哈希(hashable)性?

简要的说可哈希的数据类型,即不可变的数据结构(字符串str、元组tuple、对象集objects)。

哈希有啥作用?

它是一个将大体量数据转化为很小数据的过程,甚至可以仅仅是一个数字,以便我们可以用在固定的时间复杂度下查询它,所以,哈希对高效的算法和数据结构很重要。

同理,不可哈希的数据类型,即可变的数据结构 (字典dict,列表list,集合set)

字典的值可以是任意Python对象,而键通常是不可变的标量类型(整数、浮点型、字符串)或元组(元组中的对象必须是不可变的)。这被称为“可哈希性”。可以用hash函数检测一个对象是否是可哈希的(可被用作字典的键):

要用列表当做键,一种方法是将列表转化为元组,只要内部元素可以被哈希,它也就可以被哈希:

Python如何哈希字符串

Python中字符串是可哈希的,即可以作为字典的键或者HashTable的键使用。

您可以这样子使用Python内置函数hash(散列函数):

您也可以将字符串转为一个集合:

总之,Python里面有很多内置的hash功能性数据结构和函数。

Python中冷门但非常好用的内置函数

Python中有许多内置函数,不像print、len那么广为人知,但它们的功能却异常强大,用好了可以大大提高代码效率,同时提升代码的简洁度,增强可阅读性

Counter

collections在python官方文档中的解释是High-performance container datatypes,直接的中文翻译解释高性能容量数据类型。这个模块实现了特定目标的容器,以提供Python标准内建容器 dict , list , set , 和 tuple 的替代选择。在python3.10.1中它总共包含以下几种数据类型:

容器名简介

namedtuple() 创建命名元组子类的工厂函数

deque 类似列表(list)的容器,实现了在两端快速添加(append)和弹出(pop)

ChainMap 类似字典(dict)的容器类,将多个映射集合到一个视图里面

Counter 字典的子类,提供了可哈希对象的计数功能

OrderedDict 字典的子类,保存了他们被添加的顺序

defaultdict 字典的子类,提供了一个工厂函数,为字典查询提供一个默认值

UserDict 封装了字典对象,简化了字典子类化

UserList 封装了列表对象,简化了列表子类化

UserString 封装了字符串对象,简化了字符串子类化

其中Counter中文意思是计数器,也就是我们常用于统计的一种数据类型,在使用Counter之后可以让我们的代码更加简单易读。Counter类继承dict类,所以它能使用dict类里面的方法

举例

#统计词频

fruits = ['apple', 'peach', 'apple', 'lemon', 'peach', 'peach']

result = {}

for fruit in fruits:

if not result.get(fruit):

result[fruit] = 1

else:

result[fruit] += 1

print(result)

#{'apple': 2, 'peach': 3, 'lemon': 1}下面我们看用Counter怎么实现:

from collections import Counter

fruits = ['apple', 'peach', 'apple', 'lemon', 'peach', 'peach']

c = Counter(fruits)

print(dict(c))

#{'apple': 2, 'peach': 3, 'lemon': 1}显然代码更加简单了,也更容易阅读和维护了。

elements()

返回一个迭代器,其中每个元素将重复出现计数值所指定次。元素会按首次出现的顺序返回。如果一个元素的计数值小于1,elements()将会忽略它。

c = Counter(a=4, b=2, c=0, d=-2)

sorted(c.elements())

['a', 'a', 'a', 'a', 'b', 'b']most_common([n])

返回一个列表,其中包含n个最常见的元素及出现次数,按常见程度由高到低排序。如果n被省略或为None,most_common()将返回计数器中的所有元素。计数值相等的元素按首次出现的顺序排序:

Counter('abracadabra').most_common(3)

[('a', 5), ('b', 2), ('r', 2)]这两个方法是Counter中最常用的方法,其他方法可以参考 python3.10.1官方文档

实战

Leetcode 1002.查找共用字符

给你一个字符串数组words,请你找出所有在words的每个字符串中都出现的共用字符(包括重复字符),并以数组形式返回。你可以按任意顺序返回答案。

输入:words = ["bella", "label", "roller"]

输出:["e", "l", "l"]

输入:words = ["cool", "lock", "cook"]

输出:["c", "o"]看到统计字符,典型的可以用Counter完美解决。这道题是找出字符串列表里面每个元素都包含的字符,首先可以用Counter计算出每个元素每个字符出现的次数,依次取交集最后得出所有元素共同存在的字符,然后利用elements输出共用字符出现的次数

class Solution:

def commonChars(self, words: List[str]) - List[str]:

from collections import Counter

ans = Counter(words[0])

for i in words[1:]:

ans = Counter(i)

return list(ans.elements())提交一下,发现83个测试用例耗时48ms,速度还是不错的

sorted

在处理数据过程中,我们经常会用到排序操作,比如将列表、字典、元组里面的元素正/倒排序。这时候就需要用到sorted(),它可以对任何可迭代对象进行排序,并返回列表

对列表升序操作:

a = sorted([2, 4, 3, 7, 1, 9])

print(a)

# 输出:[1, 2, 3, 4, 7, 9]对元组倒序操作:

sorted((4,1,9,6),reverse=True)

print(a)

# 输出:[9, 6, 4, 1]使用参数:key,根据自定义规则,按字符串长度来排序:

fruits = ['apple', 'watermelon', 'pear', 'banana']

a = sorted(fruits, key = lambda x : len(x))

print(a)

# 输出:['pear', 'apple', 'banana', 'watermelon']all

all() 函数用于判断给定的可迭代参数iterable中的所有元素是否都为 TRUE,如果是返回 True,否则返回 False。元素除了是 0、空、None、False外都算True。注意:空元组、空列表返回值为True。

all(['a', 'b', 'c', 'd']) # 列表list,元素都不为空或0

True

all(['a', 'b', '', 'd']) # 列表list,存在一个为空的元素

False

all([0, 1,2, 3]) # 列表list,存在一个为0的元素

False

all(('a', 'b', 'c', 'd')) # 元组tuple,元素都不为空或0

True

all(('a', 'b', '', 'd')) # 元组tuple,存在一个为空的元素

False

all((0, 1, 2, 3)) # 元组tuple,存在一个为0的元素

False

all([]) # 空列表

True

all(()) # 空元组

Trueany函数正好和all函数相反:判断一个tuple或者list是否全为空,0,False。如果全为空,0,False,则返回False;如果不全为空,则返回True。

F-strings

在python3.6.2版本中,PEP 498提出一种新型字符串格式化机制,被称为 “字符串插值” 或者更常见的一种称呼是F-strings,F-strings提供了一种明确且方便的方式将python表达式嵌入到字符串中来进行格式化:

s1='Hello'

s2='World'

print(f'{s1} {s2}!')

# Hello World!在F-strings中我们也可以执行函数:

def power(x):

return x*x

x=4

print(f'{x} * {x} = {power(x)}')

# 4 * 4 = 16而且F-strings的运行速度很快,比传统的%-string和str.format()这两种格式化方法都快得多,书写起来也更加简单。

本文主要讲解了python几种冷门但好用的函数,更多内容以后会陆陆续续更新~

Python字典的底层实现

字典是一种可变、无序容器数据结构。元素以键值对存在,键值唯一。它的特点搜索速度很快:数据量增加10000倍,搜索时间增加不到2倍;当数据量很大的时候,字典的搜索速度要比列表快成百上千倍。

在Python中,字典是通过散列表(哈希表)实现的。字典也叫哈希数组或关联数组,所以其本质是数组(如下图),每个 bucket 有两部分:一个是键对象的引用,一个是值对象的引用。所有 bucket 结构和大小一致,我们可以通过偏移量来读取指定 bucket。

定义一个字典 dic = {},假设其哈希数组长度为8。

Python会根据哈希数组的拥挤程度对其扩容。“扩容”指的是:创造更大的数组,这时候会对已经存在的键值对重新进行哈希取余运算保存到其它位置;一般接近 2/3 时,数组就会扩容。扩容后,偏移量的数字个数增加,如数组长度扩容到16时,可以用最右边4位数字作为偏移量。

计算键对象 name 的哈希值,然后比较哈希数组对应索引内的bucket是否为空,为空返回 None ,否则计算这个bucket的键对象的哈希值,然后与 name 哈希值比较,相等则返回 值对象 ,否则继续左移计算哈希值。

注意:

1.键必须为可哈希的,如数字、元组、字符串;自定义对象需要满足支持hash、支持通过 __eq__() 方法检测相等性、若 a == b 为真,则 hash(a) == hash(b) 也为真。

2.字典的内存开销很大,以空间换时间。

3.键查询速度很快,列表查询是按顺序一个个遍历,字典则是一步到位。

4.往字典里面添加新键可能导致扩容,导致哈希数组中键的次序变化。因此,不要在遍历字典的同时进行字典的修改。

一文搞懂python数据类型和结构

每次python从入门到精通都是从头开始看,做这个学习笔记主要是为了让自己可以省去学习数据类型和结构那几章的时间,所以“偷懒”可以促进生产力发展......

分别是: 整数型、浮点型、复数、常量、布尔型、字符串 。其中复数基本不会使用到,可以不用太关注

分别是 列表、字典、集合和元组 ,其中最常见并且工作中经常使用到的就是列表和字段,其他两个不常见。

02、字典

列表之外,字典可能是python中用的也比较多的数据结构了,由于字典的底层应用哈希映射,所以要求字典的所有key必须是不可变元素(可哈希对象),增删改查操作一般都能实现O(1)复杂度,是低复杂度的必备数据结构。

03、集合

集合(set)是一个无序的不重复元素序列。

可以使用大括号 { } 或者 set() 函数创建集合,注意:创建一个空集合必须用 set() 而不是 { },因为 { } 是用来创建一个空字典。

集合操作可能最常见于用于对列表去重,它的最大特性是各元素仅保留1次,底层也是应用了哈希函数,所以在集合中查找元素一般也可实现O(1)复杂度,同时集合的嵌套元素也要求是不可变类型(可哈希对象)

add:在集合中增加一个元素,如果元素已存在,则无实际操作

pop:不接受任何参数,堪称是最神秘的操作,不同于列表的从尾端删除、字典的指定键删除,集合的pop操作看似是"随机"删除。但实际上是按照加入集合的先后顺序,删除"最早"加入的元素

除了与列表和字典中类似的增删改操作外,集合还支持数学概念下的集合操作,如交集、并集、差集等。

04、元组

如果说列表、字典和集合都有其各自擅长应用场景的话,那么元组可能是最没有存在感的数据结构:它接口有限、功能单一,而且是不可变类型。一般而言,用元组解决的问题都可以用列表实现。但使用用元组时,更多在于暗示该序列为不可变类型。当然,当元组内嵌套子列表时实际上是可以对嵌套的子列表进行更改操作的。

有问题可以私信我,欢迎交流!