- 2019-05-17思考题 1：
第一种方法更快，原因感觉上是和之前一样，就是不需要去调用相关的函数，而且像老师说的那样 {} 应该是关键字，内部会去直接调用底层C写好的代码
思考题 2:
用列表作为 Key 在这里是不被允许的，因为列表是一个动态变化的数据结构，字典当中的 key 要求是不可变的，原因也很好理解，key 首先是不重复的，如果 Key 是可以变化的话，那么随着 Key 的变化，这里就有可能就会有重复的 Key，那么这就和字典的定义相违背；如果把这里的列表换成之前我们讲过的元组是可以的，因为元组不可变展开作者回复: 正解
4 190 
2019-05-171.直接｛｝的方式，更高效。可以使用dis分析其字节码
2.字典的键值，需要不可变，而列表是动态的，可变的。可以改为元组作者回复: 使用dis分析其字节码很赞
1 39
2019-05-17Python 3.7 以后插入有序变为字典的特性。构造新字典的方式：
1. double star
>>> d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}
>>> d2 = {'hobby': 'swim', **d1}
2. update 函数：
>>> d3 = {'hobby': 'swim'}
>>> d3.update(d1)
我们可以看到这两种方式得到的字典是满足插入有序的：
>>> d3
{'hobby': 'swim', 'name': 'jason', 'age': 20, 'gender': 'male'}
在我的电脑上 第一种方式的性能要好一些。
double star:
229 ns ± 22.8 ns per loop
update:
337 ns ± 49.7 ns per loop展开 1 23
2019-05-18老师，你好！有几个让我困惑的地方想跟您确认一下，问题有点多，希望不吝赐教！
1. 为了提高哈希表的空间利用率，于是使用了Indices、Entries结构分开存储（index）和（hashcode、key、value），这里的index是否就是Entries列表的下标？
2、如果问题1成立，通过hash(key) & (PyDicMinSize - 1)计算出来的是否为Indices列表的下标？
3、如果问题2成立，PyDicMinSize是什么？为什么要使用hashcode与(PyDicMinSize - 1)做与运算，相比起直接用hashcode作为Indices列表的下标会有什么好处？
4、如果问题2成立，在往字典插入新元素的时候，通过hash(key) & mask计算出Indices的下标，如果Indices对应的元素位置值为None，则是否会将其值(index)修改为len(Entries)，然后在Entries列表追加一行新的记录（hashcode，key，value）？
5、如果问题2成立，在往字典插入新元素的时候，通过hash(key) & mask计算出Indices的下标，如果Indices对应的元素位置已经有值，则会跟Entries表中对应位置的key进行hash比较及相等比较来决定是进行value的更新处理还是hash冲突处理？展开 7 21
2019-05-17文中提到的新的哈希表结构有点不太明白 None 1 None None 0 None 2 是什么意思？ index是索引的话 为什么中间会出现两个None作者回复: 这只是一种表示。None表示indices这个array上对应的位置没有元素，index表示有元素，并且对应entries这个array index位置上的元素。你看那个具体的例子就能看懂了
19
2019-05-17>>> dis.dis(lambda : dict())
1 0 LOAD_GLOBAL 0 (dict)
3 CALL_FUNCTION 0 (0 positional, 0 keyword pair)
6 RETURN_VALUE
>>> dis.dis(lambda : {})
1 0 BUILD_MAP 0
3 RETURN_VALUE
>>> %timeit dict()
133 ns ± 2.95 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> %timeit {}
74.6 ns ± 3.07 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
{}, [], () 都比 dict(), list(), tuple() 初始化列表的性能要好，因为后者需要函数调用消耗了更多的时间。展开 1 12
2019-05-171. 直接使用大括号更高效，避免了使用类生成实例其他不必要的操作；
2. 列表不可以作为key，因为列表是可变类型，可变类型不可hash。
问题：为什么在旧哈希表中元素会越来越稀？作者回复: 你比较一下旧哈希表和新哈希表的存储结构就会发现，旧哈希表的空间利用率很低，一个位置要同时分配哈希值，键和值的空间，但是新哈希表把indices和entries分开后，空间利用率大大提高。
看文中的例子，这是旧哈希表存储示意图
entries = [
['--', '--', '--']
[-230273521, 'dob', '1999-01-01'],
['--', '--', '--'],
['--', '--', '--'],
[1231236123, 'name', 'mike'],
['--', '--', '--'],
[9371539127, 'gender', 'male']
]
VS
新哈希表存储示意图：
indices = [None, 1, None, None, 0, None, 2]
entries = [
[1231236123, 'name', 'mike'],
[-230273521, 'dob', '1999-01-01'],
[9371539127, 'gender', 'male']
]
你数一下两个版本中空着的元素的个数，就很清晰了。 1 6- 2019-05-29--+-------------------------------+
| 哈希值 (hash) 键 (key) 值 (value)
--+-------------------------------+
0 | hash0 key0 value0
--+-------------------------------+
1 | hash1 key1 value1
--+-------------------------------+
2 | hash2 key2 value2
--+-------------------------------+
. | ...
__+_______________________________+
第一种数据结构，如何可以o(1)的查找一个key？
没有索引啊
这篇文章感觉写的不好，例子没有讲透
稀疏一定浪费吗，里面没有值的话能占用多少空间
我理解耗费空间的应该是k v的存储吧展开作者回复: 根据key计算hash值后直接就可以找到对应的value啊，所以是O(1)，他并不是列表需要遍历，他是哈希表
稀疏肯定浪费空间啊，里面没有值也是会有一定的存储损耗的
你自己去看看市面上Python教材里讲字典集合的，有几个能讲到像我这样深入。 5 
2019-06-201, 第一种更快, 反编译后, 第二种需要调用函数
>>> import dis
>>> def f1(): return {'1':1}
...
>>> def f2(): return dict({'1':1})
...
>>> dis.dis(f1)
1 0 LOAD_CONST 1 ('1')
2 LOAD_CONST 2 (1)
4 BUILD_MAP 1
6 RETURN_VALUE
>>> dis.dis(f2)
1 0 LOAD_GLOBAL 0 (dict)
2 LOAD_CONST 1 ('1')
4 LOAD_CONST 2 (1)
6 BUILD_MAP 1
8 CALL_FUNCTION 1
10 RETURN_VALUE
2. 不可以, 列表是可变的, 但是对hash表来说, 如果键值是可变的, 那么插入以及删除的位置都变成不确定的. 另外哈希冲突的概率也大大增加展开 4- 2019-05-17老师我明白了，(hash, key, val) 都是存在 entries 里面的，通过 indices[index] 找到 entry 再做比较就好了。 4
2019-05-17插入操作,
mask = PyDicMinSize -1
index = hash(key) & mask
能否有个例子,想详细了解一下细节 2 4- 2019-05-17老师好，在王争老师的数据结构课程中提到哈希表常与链表一起使用，譬如用来解决哈希冲突。请问python底层对字典和集合的实现是否也是这样的呢？
作者回复: 这个就是文中所说的线性寻找了，但是Python底层解决哈希冲突还有更好的方法，线性寻找是最简单的，但是不是最高效的
4 
2019-05-17s2 = Set([1, 2, 3])
# Set 大写会报错：
NameError: name 'Set' is not defined
改成小写问题解决 3
2019-05-17list indices就是哈希表，None表示该位置目前尚未被占用，索引的值即是在list entries中存储dict键值和哈希值的下标。
作业中初始化dict，key不能使用可变类型吧，value可以使任意对象。作者回复: 回答的很好
3
2019-05-17Indices:none | one | none | index | none | index 是什么意思？能补充讲解下吗作者回复: 这只是一种表示。None表示indices这个array上对应的位置没有元素，index表示有元素，并且对应entries这个array index位置上的元素。你看那个具体的例子就能看懂了
3
2019-05-24老师请问，key、hash值、indice三者的联系是啥？ 一直以为hash(key)就是内存地址 2
2019-05-18老师，对于集合插值有个疑问：
s={1, 2.0}
s.add(1.0)
s
# 输出
{1, 2.0}
上面这个示例，是不是因为1和1.0的哈希值相同，所以判定已存在元素，不插入。
关于商品有多少种不同价格的时间复杂度也有疑问：
第一个例子的时间复杂度是O(n^2)，但我的理解是，最差的情况是每种商品价格不同。A层循环遍历时间复杂度是O(n)，B层的时间复杂度由添加和遍历组成，添加的总时间复杂度是O(n)，遍历时间复杂度是递增的：O(0+1+……+n-1),B层总的时间复杂度是O((n^2+n)/2)，那list的时间复杂度不就是A+B：O((n^2+3n)/2)吗？怎么想都和两层for循环嵌套的时间复杂度不一样。
第二个例子的时间复杂度是O(n)，而我的理解是A层循环遍历时间复杂度是O(n)，B层的添加查找的总时间复杂度是O(n)，那set的时间复杂度不应该是A+B：O(2n)吗？
不知道哪里理解出了问题，望老师指点。展开 2
2019-05-18最后的例子很有代表性，举例很好 2- 2019-08-08讲解得挺好，有深入讲，赞 1
2019-06-02list做key的问题有点疑惑，即使list是可变的，它在内存中的地址是不变的，对地址是可以hash的吧？不然所有引用类型都没法做key了。当然，用引用类型做key不一定是好的做法，可能会带来混淆。 1