一. 什么是字典？
字典是一系列由键（key）和值（value）配对组成的元素的集合。字典是一个可变容器模型，可以存储任意类型对象。字典实现与哈希算法密不可分（不同的Python版本，算法会不同），不了解哈希算法的童鞋可以先去了解相关知识。
二. 字典是否是有序的？
在Python3.6之前，字典是无序的，但是Python3.7+，字典是有序的。在3.6中，字典有序是一个implementation detail，在3.7才正式成为语言特性，因此3.6中无法确保100%有序。
三. 字典的查询、添加、删除的时间复杂度？
字典的查询、添加、删除的平均时间复杂度都是O(1)（为什么是平均时间复杂度，文章后面会讲解到），相比列表与元祖，性能更优。
四. 字典的实现原理？
字典底层是维护一张哈希表（见下图），我们可以把哈希表看成一个列表，哈希表中的每一个元素又存储了哈希值（hash）、键（key）、值（value）3个元素。（Python3.6之前）
由上可以见哈希表的存储结构，我们也可以看出，元素之间有一些空元素，我们通过增加一个元素来讲解具体实现。
- 计算key的hash值【hash(key)】，再和mask做与操作【mask=字典最小长度（DictMinSize） - 1】，运算后会得到一个数字【index】，这个index就是要插入的enteies哈希表中的下标位置
- 若index下标位置已经被占用，则会判断enteies的key是否与要插入的key是否相等
- 如果key相等就表示key已存在，则更新value值
- 如果key不相等，就表示hash冲突，则会继续向下寻找空位置，一直到找到剩余空位为止。
以上介绍了老字典的实现过程，下面我们带入具体的数值来介绍。
通过上面的讲解，已经了解了字典的插入的过程，可以更具此过程分析出字典查找、插入的执行过程，这里就不过多赘述。我们可以看到，不同的key计算的出的index值是不一样的，在enteies中插入的位置不一样，所以当我们遍历字典的时候，字段的顺序与我们插入的顺序是不相同的。
我们同样可以发现，enteies表是稀疏的，随着我们插入的值不同，enteies表会越来越稀疏（enteies也是一个会动态扩展长度的，每一此扩展长度，都会重新计算所有key的hash值），所以新的字典实现就随之出现。
2. Python3.7+后的新的实现方式
老字典使用一张hash，而新字典还使用了一张Indices表来辅助。下来列出新的结构：
下面为具体的实现过程：
- 计算key的hash值【hash(key)】，再和mask做与操作【mask=字典最小长度（IndicesDictMinSize） - 1】，运算后会得到一个数字【index】，这个index就是要插入的indices的下标位置（注：具体算法与Python版本相关，并不一定一样）
- 得到index后，会找到indices的位置，但是此位置不是存的hash值，而是存的len(enteies)，表示该值在enteies中的位置
- 如果出现hash冲突，则处理方式与老字典处理方式类似
下面带入实际实现过程：
我们在来看一下查询字典的具体过程：
由上可以看出，新字典存储数据本身的enteies并不会稀疏，由indices来维护具体存储的位置，enteies中的数据是和插入的数据是一样的，所以新的字典是有序的。
上面的例子没有说明冲突的解决方案，大家可以自己思考思考。
五. 时间复杂度说明
我们在上面提到了，字典的平均时间复杂度是O(1)，因为字典是通过哈希算法来实现的，哈希算法不可避免的问题就是hash冲突，Python字典发生哈希冲突时，会向下寻找空余位置，直到找到位置。如果在计算key的hash值时，如果一直找不到空余位置，则字典的时间复杂度就变成了O(n)了，所以Python的哈希算法就显得非常重要了。Python字典的哈希算法，会尽量保证哈希值计算出的index是平均分布且每一个值之间有剩余位置，例如:
及index尽量只为 0, 3, 5, 7类似值，保证在发生哈希冲突时，能很快的找到空余位置。
六. 字典的key能使用什么值？
Python字典的key可以使用字符串（str），整型（int），元祖（tuple）等。我们已经知道，字典是通过哈希算法来计算key的值，所以key必须为可哈希的，list不能作为字典的key，因为list是可变的及不可哈希的对象，所以不能作为字典的key。
Original: https://blog.51cto.com/u_15722381/5483115
Author: ch3nnn
Title: Python字典dict实现原理
相关阅读1
Title: 基础数据类型之字典
1.字典的定义
使用{}定义字典，括号内用逗号分隔开多个key：value，其中value可以是任意类型，但是key必须是不可变类型且不能重复，是无序的！
info=[
['name','zhang'],
('age',19)
['gender','男']
]
d={} # 第一种方式定义
d=dict(x=1,y=2) #第二种，dict里面也可以穿一个info
dict（info）的工作原理等同于：
d={}
info=[
['name','zhang'],
('age',19)
['gender','男']
]
for x,y in info:
d[x]=y
2.字典的作用
存放多个无序的数据，数据以键值对的方式存储
3.字典数据类型转换
见字典的定义
4.字典的内置方法
# 1.按key存取值，可存可取
q={'k1':111,'k2':222}
q['k1']=333 # key存在，则修改值，key不存在，则添加值
# 2.长度len
print(len(q)) # 统计字典的key或者value个数
# 3. in、not in运算
print('k1' in q) # 统计的是字典中的key在不在
# 4.删除
del q['k1'] # 通用删除方式，无返回值
q.pop('k1') # 根据key删除，返回删除key对应的值
q.popitem() # 随机删除，返回一个元组，该元组是删的key和value
# 5.for循环
for k in q.keys(): # 直接获取到字典的key
print(k)
for v in q.values(): # 直接获取到字典的value
print(v)
for k,v in q.items(): #获取到对应的key和value
print(k,v)
# 其他内置方法
q.clear() # 清空字典
q.update({'k1':444,'k3':778}) # 更新q字典，如果老字典没有更新的key则添加，有则更新
q.get('k1') # key不存在不报错，返回none
q.setdefault('k1',233) # 如果key有则不添加；没有则添加。返回值是字典中key对应的值
Original: https://www.cnblogs.com/suncolor/p/16629550.html
Author: 等日落
Title: 基础数据类型之字典
相关阅读2
Title: PyCharm 2022.2 发布了，支持最新 Python 3.11 和 PyScript 框架！
来源：Jet Brains官网；翻译：Python猫
原文：https://blog.jetbrains.com/pycharm/2022/07/2022-2
通常而言，使用新潮的或者快速发展的技术，可能会挺有挑战性，你可能得经常阅读文档，才能熟悉新的语法、API 和协议。
PyCharm 2022.2 通过提供对 Python 3.11 的语言特性和新的 PyScript 框架的支持，能够帮助你完成这一过程。
让我们来看看它里面有什么吧！
Python 3.11
PyCharm 2022.2 已经为 Python 3.11 中一些主要的功能提供了代码洞察（code insight），例如异常组和 except * 运算符（PEP 654）：
以及新的用于 TypedDict 个别键的 Required[] 和 NotRequired[] 标记符号（PEP 655）。
HTTP Client
PyCharm 2022.2 支持 WebSocket 连接。有了这个 API，你可以在给服务端发送消息后，接收由事件驱动的响应，而不需轮询服务器来获取结果。
PyCharm 如今可以基于开箱即用的 HTTP 和 WebSocket 协议来发送请求。 ws:// 与 wss:// 表示的是使用 WebSocket 请求协议。
此外，PyCharm 2022.2 还提供了一种更简单的方法来选择运行环境——使用代码侧边栏上的图标。原文
若要启用此功能，请从 "Run with"下拉框中选择" Select Environment Before Run"选项。
用于设置远程解释器的新 UI
PyCharm 2022.2 引入了一个新的向导，用于在远程目标上设置解释器（如 WSL、SSH、Docker、Docker Compose 或 Vagrant）。它使得设置的过程更加结构化且易于操作。
若要找到新向导，依次打开"Settings | Preferences | Python Interpreter"，然后单击窗口右上角的"Add Interpreter"链接，或单击编辑器右下角的解释器，并选择"Add New Interpreter"。
运行当前文件
在没有使用运行配置的情况下，想要立即运行和调试单个文件，请从 " Run/Debug "_小组件中，选择 " Run Current File "_。原文
它拥有一个二级菜单，这个菜单提供了几个实用的运行器以及 _" Run with Parameters "_操作，你可以在运行文件之前，调整这个操作的运行配置参数。
对 PyScript 的初步支持
PyScript 是一个可在浏览器中创建丰富的 Python 应用的框架，使用 HTML 界面和 Pyodide、WASM 以及其它现代的 web 技术。 +
目前，代码补全和语法高亮功能已支持部分的 PyScript 标签，例如用于声明依赖项的
Jupyter Notebooks
PyCharm 2022.2 增强了 Jupyter Notebook 的用户体验。
你可以使用 Jupyter 编辑器工具栏中相应的按钮和图标，更轻松地剪切、复制和粘贴单元格。
你还可以轻松地拖动图像的下边框来调整图像的大小。从而提高这些执行结果的可读性。
数据库管理
PyCharm 2022.2 支持将多个 CSV 文件导入到新的或现有的数据库表中。
操作方法：在"项目视图"中选择多个文件，并将它们拖到数据库 schema 中。
PyCharm 2022.2 有两种解析 SQL 脚本的模式。在 Playground 模式中, 对象根据上下文而被解析。这种模式如今是查询控制台的默认解析模式。
在 Script 模式中，文件的开头部分被解析成上下文，但是，只要脚本中出现"SET CURRENT SCHEMA" 语句，它就会改变用于解析的上下文。这种模式如今是本地文件的默认解析模式。
想要切换解析模式，只需使用工具栏的下拉选项。
Docker
现在，你可以使用新的"Copy Docker Image"操作，轻松地将镜像从一个 Docker 进程复制到另一个 Docker 里，该操作会将镜像保存成一个文件，然后将其推送到所选的连接。
PyCharm 还与 Colima 和 Racher 集成，可支持更多与 Docker 进程建立连接的操作。
此外，PyCharm 2022.2 会在重启 IDE 后，自动连接到 Docker。
默认情况下，此新设置处于启用状态，可以在"Settings | Preferences | Advanced Settings | Docker"关闭。
以上内容是新版本 Pycharm 中最显著的新功能和可用性改进。更多详情，还可查阅 https://www.jetbrains.com/pycharm/whatsnew
Original: https://www.cnblogs.com/pythonista/p/16582613.html
Author: 豌豆花下猫
Title: PyCharm 2022.2 发布了，支持最新 Python 3.11 和 PyScript 框架！
相关阅读3
Title: 数据结构的几个小问题
准备好开始了吗，我觉得你没有准备好，准备好的意思是，你得做十个标准俯卧撑，然后心平气和，喝口水，我喝的是咖啡，这有助于提高注意力。要知道这部分内容有些许无聊，这样的准备是很有必要的。
概念全背
- 数据是信息的载体，是所有能够被计算机识别，存储和加工处理的符号的总称。
- 数据项是具有独立含义的标识单位，是数据不可分割的最小单位。
- 数据元素是数据的基本单位。
- 数据对象是具有相同性质的数据元素的集合。
- 数据结构是指互相之间存在着一种或多种关系的数据元素的集合。
- 逻辑结构：数据元素之间的关系称为逻辑结构
- 存储结构：最常用的是顺序存储和链式存储
- 数据的运算：运算是对数据的处理
空间复杂度是指算法运行从开始到结束所需的存储量
空间复杂度是指算法的时间耗费。
数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的计算方法和运算的学科。
算法必须具备可行性，有穷性，确定性。
非常痛苦对不对，不过别担心，第一章已经过去了，如果说会考到其他没有入选的题目，那就看运气了。
见微知著，识人心智。
说句真话，递归大家可以不用看的。
概念全背，不要有侥幸心理
递归是一个过程或函数直接或间接调用自身的一种方法。
递归的方法只需少量的代码就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。
当递归算法所涉及的数据定义形式是递归的情况下，通常可以将递归算法转化为递推算法，用递归的边界条件作为递推的边界条件。
public class HanoiY {
void Move(char chSour, char chDest) {
System.out.println("Move the top plate of" + chSour + " to " + chDest);
}
void Hanoi(int n, char a, char b, char c) {
if (n == 1) {
Move(a, c);
} else {
Hanoi(n - 1, a, c, b);
this.Move(a, c);
Hanoi(n - 1, b, a, c);
}
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
HanoiY hanoi = new HanoiY();
hanoi.Hanoi(n, 'a', 'b', 'c');
}
}
递归的优点：结构清晰，可读性强，而且容易用数学归纳法证明算法的正确性。
递归的缺点：递归算法的运行效率低，耗费时间长，占用存储空间大。
递归算法是一种直接或者间接地调用自身算法的过程。
import java.util.Scanner;
public class FinalSalary{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
System.out.print("请输入要求的哪一年工资：");
int n = input.nextInt();
//方法一：递推（迭代）
int salary = 1500;
for(int i = 1 ; i < n ; i++){
salary *= 1.1;
}
System.out.println("第"+n+"年的工资为：" + salary);
System.out.println("第"+n+"年的工资为："+ Salary(n));
}
//方法二：递归
public static int Salary(int n){
if(n == 1){
return 1500;
}else{
return (int)(Salary(n - 1) * 1.1);
}
}
}
public static DLinkList(LinkList L) {
DLinkList H;
DLinkNode rear, s;
LinkNode p;
H = new DLinkList();
rear = H.Head;
p = L.Head.next;
while (p) {
s = new LinkList(Null);
s.data = p.data;
s.next = rear.next;
s.prior = rear;
rear.next = s;
H.Head.prior = s;
rear = s;
p = p.next;
}
return H;
}
天命靡常，唯德是辅。
概念背诵
顺序存储优点：方法简单，各种高级语言中都有数组类型，容易实现，不用为表示节点间的逻辑关系而增加存储开销，逻辑相邻与物理相邻一直。顺序表具有按元素序号随机访问的特点。
链式存储的优点：在顺序表中做插入删除操作时，不需要多次移动元素，效率高。不需要预先分配足够大的存储空间，不会出现存储大量闲置或溢出。
非空的循环单链表head的尾节点满足 p.next==head
循环队列的优点：克服了假上溢现象，充分利用了向量空间(删除元素后的空间仍然可以利用，最大限度的利用空间)有效的利用了资源。
如何判断循环队列的空和满
方法之一是附设一个存储队中元素个数的变量，如num。num=0，对空，num=MAXSIZE，队满。
另一种方法是少用一个元素空间，(rear+1)%MAXSIZE==front。队满
丧家之犬，主公实不足虑也。
快把朕扶起来。
概念全部要背
- 一颗非空二叉树的第i层上最多有 2^i-1^ 个节点
- 一颗深度为k的二叉树中，最多具有2^k^-1个节点
- 对于一颗非空的二叉树，若叶子节点数为n~0~,度数为2的节点数为n~2~,则有n~0~=n~2~+1。
只有增添一些并不存在的空节点，使之成为一颗完全二叉树的形式，然后再顺序存储。
Original: https://blog.51cto.com/u_15226631/5551244
Author: Feyncode
Title: 数据结构的几个小问题