basic2.md

Python的基础故事（二）——基础数据结构

本篇文章为大家带来Python的数据结构介绍

序列

Python中序列是应用最广泛的一类数据类型。它由中括号包裹，可以存储任意数量、任意类型的数据，元素之间以逗号分隔：

a = [1, 2, 'a', 'd', True]

或者通过list()初始化：

a = list(range(10))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

元素通过下标进行访问：

print(a[0]) # 1

有趣的是，你可以通过负数下标来从后向前访问，负数下标从-1开始：

print(a[-1]) # True
print(a[-3]) # 'a'

访问越界会返回一个IndexError：

print(a[100])
# IndexError: list index out of range

遍历一个列表采用for...in...语句（这里解释过）：

for i in a:
    print(i, end='')
# 0123456789

切片

你可以通过切片的方式同时访问多个元素，切片的形式是：list[start:end:step]，可以获得从start到end步长为step（不包括end元素）的结果：

a = list(range(10))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a[1:10:2])
# [1, 3, 5, 7, 9]

step是可选的，start和end必须存在，但是两者均有默认值（一个开头一个结尾）：

# 不加step
print(a[0:3]) # [0, 1, 2]
# 不给start，默认从起始位置开始
print(a[:3]) # [0, 1, 2]
# 不给end，默认到结尾终止
print(a[8:]) # [8, 9]
# 都不给，和原序列一样
print(a[:])
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

这里看一个问题，如果你仔细看过之前的内容可以知道，列表对象是可变对象，即：

b = a
print(b)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a[0] = 10
print(b)
# [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(b is a) # True

这篇文章中提到了这个现象的原因（Python引用）。所以，当你希望拷贝一个列表时，直接令b = a会导致这个问题。切片提供了一个完美的列表拷贝解决方案：

b = a[:]
print(b)
# [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a[0] = 100
print(b)
# [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(b is a) # False

通过切片操作，b已经变成了另外一个对象，也就是实现了拷贝。（注意，切片是浅拷贝）

当然，切片操作也支持负数：

a = list(range(10))
print(a[5:-1])
# [5, 6, 7, 8]
print(a[-1:-4:-1])
# [9, 8, 7]
# step为负则倒着遍历
print(a[::-1])
# [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

可以看到，只提供一个step = -1可以反序列表。但是这不是一个好的写法，尤其当列表巨大时，你应当使用reversed()函数，因为它会生成一个迭代器，当你获取它的值时，它以反向的顺序去读取列表，而不是真的把每个元素反序并生成另一个巨大的反序的列表：

b = reversed(a)
print(b)
# <list_reverseiterator object at 0xb704dbac>
# 迭代器节省内存开销

灵活运用切片，能让你的程序更加优雅。

列表方法

这里简单介绍一些常用的列表方法，简单起见，每个示例都以a = list(range(10))开始，不在指明：

1. append列表尾部插入元素：

a.append(0)
print(a)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

2. len获取列表长度：

print(len(a)) # 10

如果你看过这篇文章，你会知道它实现了容器协议中的获取长度协议__len__。

3. count统计某个元素的个数：

print(a.count(0)) # 1

4. pop返回并移除某个元素：

print(a.pop(1)) # 1
print(a)
# [0, 2, 3, 4, 5, 6, 7, 8, 9]
# 1没了

5. reverse列表反序：

a.reverse()
print(a)
# [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

（前面说了，尽量使用reversed()）

6. index获取元素下标：

print(a.index(3)) # 3
a.append(3)
print(a)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3]
print(a.index(3)) # 3

可以看到，index只获取找到的第一个元素的下标。

元组

元组是一类以小括号包裹的重要数据结构。同列表一样，它也是由下标访问，也支持切片操作：

a = (1, 2, 3, 4)
print(a[0]) # 1
print(a[:3]) # (1, 2, 3)
a = tuple(range(10))
# (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

它是不可变对象，一旦创建就不可被修改：

a[0] = 10
# TypeError: 'tuple' object does not support item assignment

需要注意的是，如果想要创建一个只有一个元素的元组，应当这样写：

a = (1,)
print(a) # (1,)

如果不加逗号，则变成了一个运算表达式，结果是数字1：

a = (1)
print(a) # 1

由于元组不可变特性，它支持的操作相比列表少了很多。所有修改类操作均不支持，而其他操作则同列表一致：

a = tuple(range(10))
print(a.index(3)) # 3
print(a.count(1)) # 1

选列表还是选元组？

列表通常存储同质的大量的数据，而元组适合存储异构的数据（在这里提到过，有点像C语言中的struct），此外，元组相比于列表还有如下几个特点：

• 不可变性，适合存储不希望被修改的数据；
• 通常（注意用词）可哈希，因而可以作为字典的键值（这里提到过→传送门）（啥时候不可哈希？下面会说）；
• 遍历速率更快；

字典

字典是Python中另一个类重要数据结构。它由大括号包裹，以key:value形式存储数据。key必须是可哈希的数据类型，前面多次提到了，而value则可以是任何类型的数据。字典初始化可以由大括号或是dict完成：

a = {'a': 1}
b = dict(c=2, d=a)
print(b)
# {'c': 2, 'd': {'a': 1}}

想要通过key访问到value，需要通过中括号完成：

print(a['a']) # 1

尝试访问一个不存在的key会导致KeyError：

print(a['b'])
# KeyError: 'b'

为字典添加新的值也是这样操作：

a['b'] = 2
print(a)
# {'b': 2, 'a': 1}

字典有其特有的一些方法：

1. 利用get()获取value，可以不产生KeyError：

print(a.get('a'))
# 1
print(a.get('c', None))
# None

所以当你不希望键不存在就报错时，利用get方法，并在第二个参数给出键不存在时需要返回的值是一个好的选择。

2. setdefault(key, default=None)

它和get类似，但是如果键不存在的话，会插入该键，并以第二个参数为值：

print(a.setdefault('c', None))
# None
print(a)
# {'b': 2, 'c': None, 'a': 1}

结果c被添加进了字典

3. 获取所有的key，所有的value，所有的key: value对：

for key in a.keys():
    print(key)
# 'b'
# 'c'
# 'a'
for value in a.values():
    print(value)
# 2
# None
# 1
for key, value in a.items():
    print(key, end='')
    print(': ', end='')
    print(value)
# b: 2
# c: None
# a: 1

什么是可哈希数据类型？

如果你阅读过这篇文章，你应该清楚支持哈希函数表示该类实现了哈希协议__hash__：

class A:
    def __hash__(self):
        return 1
# 哈希协议要求返回一个整数
    
a = A()
hash(a) # 1

这个自定义类型的实例可以被用作字典的key值：

b = {a: 1}
print(b)
# {<__main__.A object at 0xb7034bec>: 1}

这里需要注意的是，print函数打印出来的只是实例a转换为字符串的结果，而真正的key是**a本身**：

print(b[a]) # 1
print(str(a))
# <__main__.A object at 0xb7034bec>

实际上，自定义类默认都是可哈希的：

class A:
    pass

a = A()
print(hash(a)) # -881838924
b = {a: 1}
print(b)
# {<__main__.A object at 0xb7034b4c>: 1}

为什么字典的键要求可哈希？

字典通过哈希来加快索引速度。

它的内部存储方式简单说来是一个哈希值对应一个键值对列表，列表中每个元素是(key, value)元组，表示同一个哈希值下不同的key（这是可能存在的，见下例）。这样，当你用一个key来寻找一个value时，字典做了这样的步骤：

1. 获得key的哈希值，并获得该哈希所对应的键值对列表；
2. 遍历该列表，返回key匹配到的value；

为了验证这一点，我们改写一下A：

class A:
    def __hash__(self):
        return 1
    
    def __eq__(self, other):
        return False

其中__eq__是相等比较协议，是运算符==背后的协议。它返回self和other比较后的结果，这里强行置False：

a1 = A()
a2 = A()
print(hash(a1) == hash(a2))
# True
print(a1 == a2) # False
print(a1 == a1) # False

现在分别用a1，a2作key值：

b = {
    a1: 1,
    a2: 2,
}
print(b)
# {<__main__.A object at 0x000002DDCB505DD8>: 3, 
# <__main__.A object at 0x000002DDCB505D30>: 2}

从结果可以看到，相同哈希值的a1和a2依旧可以作为不同的key。

如果你有一些算法知识，你可以发现步骤1的时间复杂度是O(1)，而步骤2的是O(n)。所以，相同哈希值的key是否只有一个对查询性能有很大影响。

因此，自定义类型想要高效地作为key，需要保证如下一点：对任意的两个对象，如果他们的哈希值一样，那么他们就是同一个对象；反之，哈希值不一样，那么他们一定是不同的对象。

要实现这一点，我们就要再改写一下A的定义：

class A:
    def __hash__(self):
        return id(self)
    
    def __eq__(self, other):
        if (self.__hash__()
            == 
            other.__hash__()
           ):
            return True
        else:
            return False

这样便能够以最快的速度索引到value值。

为什么列表不能哈希？

列表不能作为字典的key的原因是列表不能哈希：

a = [1, 2, 3]
hash(a)
# TypeError: unhashable type: 'list'

自然，你会问，为什么列表不能哈希？

这是因为列表元素可变，哈希一个列表并作为字典的key会导致一些不可预测的问题出现：

1. 如果哈希值为id值，像A一样，那么对含相同元素的不同的两个列表，它的id是不一样的，例如：

# 假设列表可哈希
a = [1, 2, 3]
b = [1, 2, 3]
print(hash(a) == hash(b))
# False
c = {
    a: 1,
    b: 2,
}
c[[1, 2, 3]]# ???

如果你依稀记得前面一篇文章的内容，那你一定会有这样的疑问：

a = (1, 2, 3)
b = (1, 2, 3)
print(id(a) == id(b))
# False
c = {
    a: 1,
    b: 2,
}
print(c)
# {(1, 2, 3): 2}
print(c[(1, 2, 3)])
# 2
print(c[a])
# 2

具有相同元素的元组的id也不一样，为什么它能作为唯一的key？因为，元组的哈希是通过其中的元素求得的，而非id值：

a = (1, 2, 3)
print(hash(a) == id(a))
# False

当元组中存在不可哈希对象时，元组本身也变得不可哈希!

a = (1, 2, [1, 2])
print(hash(a))
# TypeError: unhashable type: 'list'

2. 如果列表像元组一样，通过元素来获得哈希值可以吗？

看下面这个伪代码：

# 假设列表可哈希
a = [1, 2, 3]
c = {
    a: 1,
}
a.append(4)

怎样获取c中的元素？？无法获取！

c[a] # key一致但哈希不一致
c[[1, 2, 3]] # 哈希一致但key不一致