PID控制详解


一、PID控制简介


   PID( Proportional Integral Derivative)控制是最早发展起来的控制策略之一，由于其算法简单、鲁棒性好和可靠性高，被广泛应用于工业过程控制，尤其适用于可建立精确数学模型的确定性控制系统。


   在工程实际中，应用最为广泛的调节器控制规律为比例、积分、微分控制，简称PID控制，又称PID调节，它实际上是一种算法。PID控制器问世至今已有近70年历史，它以其结构简单、稳定性好、工作可靠、调整方便而成为工业控制的主要技术之一。当被控对象的结构和参数不能完全掌握，或得不到精确的数学模型时，控制理论的其它技术难以采用时，系统控制器的结构和参数必须依靠经验和现场调试来确定，这时应用PID控制技术最为方便。即当我们不完全了解一个系统和被控对象，或不能通过有效的测量手段来获得系统参数时，最适合用PID控制技术。PID控制，实际中也有PI和PD控制。PID控制器就是根据系统的误差，利用比例、积分、微分计算出控制量进行控制的。


   从信号变换的角度而言，超前校正、滞后校正、滞后－超前校正可以总结为比例、积分、微分三种运算及其组合。


   PID调节器的适用范围：PID调节控制是一个传统控制方法，它适用于温度、压力、流量、液位等几乎所有现场，不同的现场，仅仅是PID参数应设置不同，只要参数设置得当均可以达到很好的效果。均可以达到0.1%，甚至更高的控制要求。


PID控制的不足


　　1. 在实际工业生产过程往往具有非线性、时变不确定，难以建立精确的数学模型，常规的PID控制器不能达到理想的控制效果；


　　2. 在实际生产现场中，由于受到参数整定方法烦杂的困扰，常规PID控制器参数往往整定不良、效果欠佳，对运行工况的适应能力很差。


二、PID控制器各校正环节


   任何闭环控制系统的首要任务是要稳（稳定）、快（快速）、准（准确）的响应命令。PID调整的主要工作就是如何实现这一任务。


　　增大比例系数P将加快系统的响应，它的作用于输出值较快，但不能很好稳定在一个理想的数值，不良的结果是虽较能有效的克服扰动的影响，但有余差出现，过大的比例系数会使系统有比较大的超调，并产生振荡，使稳定性变坏。积分能在比例的基础上消除余差，它能对稳定后有累积误差的系统进行误差修整，减小稳态误差。微分具有超前作用，对于具有容量滞后的控制通道，引入微分参与控制，在微分项设置得当的情况下，对于提高系统的动态性能指标，有着显著效果，它可以使系统超调量减小，稳定性增加，动态误差减小。


   综上所述，P—比例控制系统的响应快速性，快速作用于输出，好比"现在"（现在就起作用，快），I—积分控制系统的准确性，消除过去的累积误差，好比"过去"（清除过去积怨，回到准确轨道），D—微分控制系统的稳定性，具有超前控制作用，好比"未来"（放眼未来，未雨绸缪，稳定才能发展）。当然这个结论也不可一概而论，只是想让初学者更加快速的理解PID的作用。


　　在调整的时候，你所要做的任务就是在系统结构允许的情况下，在这三个参数之间权衡调整，达到最佳控制效果，实现稳快准的控制特点。


   比例控制可快速、及时、按比例调节偏差，提高控制灵敏度，但有静差，控制精度低。积分控制能消除偏差，提高控制精度、改善稳态性能，但易引起震荡，造成超调。微分控制是一种超前控制，能调节系统速度、减小超调量、提高稳定性，但其时间常数过大会引入干扰、系统冲击大，过小则调节周期长、效果不显著。比例、积分、微分控制相互配合，合理选择PID调节器的参数，即比例系数KP、积分时间常数τi和微分时间常数τD，可迅速、准确、平稳的消除偏差，达到良好的控制效果。


　　1. 比例环节


   成比例地反映控制系统的偏差信号e(t)，偏差一旦产生，控制器立即产生控制作用，以减小偏差。当仅有比例控制时系统输出存在稳态误差（Steady-state error）。


   P参数越小比例作用越强，动态响应越快，消除误差的能力越强。但实际系统是有惯性的，控制输出变化后，实际y(t)值变化还需等待一段时间才会缓慢变化。由于实际系统是有惯性的，比例作用不宜太强，比例作用太强会引起系统振荡不稳定。P参数的大小应在以上定量计算的基础上根据系统响应情况，现场调试决定，通常将P参数由大向小调，以能达到最快响应又无超调(或无大的超调)为最佳参数。


　　优点:调整系统的开环比例系数，提高系统的稳态精度，减低系统的惰性，加快响应速度。


　　缺点:仅用P控制器,过大的开环比例系数不仅会使系统的超调量增大，而且会使系统稳定裕度变小，甚至不稳定。

　　

　　2. 积分环节


   控制器的输出与输入误差信号的积分成正比关系。主要用于消除静差，提高系统的无差度。积分作用的强弱取决于积分时间常数T,T越大，积分作用越弱，反之则越强。


　　为什么要引进积分作用？


   比例作用的输出与误差的大小成正比，误差越大，输出越大，误差越小，输出越小，误差为零，输出为零。由于没有误差时输出为零，因此比例调节不可能完全消除误差，不可能使被控的PV值达到给定值。必须存在一个稳定的误差，以维持一个稳定的输出，才能使系统的PV值保持稳定。这就是通常所说的比例作用是有差调节，是有静差的，加强比例作用只能减少静差，不能消除静差(静差：即静态误差，也称稳态误差)。


   为了消除静差必须引入积分作用，积分作用可以消除静差，以使被控的y(t)值最后与给定值一致。引进积分作用的目的也就是为了消除静差，使y(t)值达到给定值，并保持一致。


   积分作用消除静差的原理是，只要有误差存在，就对误差进行积分，使输出继续增大或减小，一直到误差为零，积分停止，输出不再变化，系统的PV值保持稳定，y(t)值等于u(t)值，达到无差调节的效果。


   但由于实际系统是有惯性的，输出变化后，y(t)值不会马上变化，须等待一段时间才缓慢变化，因此积分的快慢必须与实际系统的惯性相匹配，惯性大、积分作用就应该弱，积分时间I就应该大些，反之而然。如果积分作用太强，积分输出变化过快，就会引起积分过头的现象，产生积分超调和振荡。通常I参数也是由大往小调，即积分作用由小往大调，观察系统响应以能达到快速消除误差，达到给定值，又不引起振荡为准。


   对一个自动控制系统，如果在进入稳态后存在稳态误差，则称这个控制系统是有稳态误差的或简称有差系统（System with Steady-state Error）。为了消除稳态误差，在控制器中必须引入“积分项”。积分项对误差取决于时间的积分，随着时间的增加，积分项会增大。这样，即便误差很小，积分项也会随着时间的增加而加大，它推动控制器的输出增大使稳态误差进一步减小，直到等于零。因此，比例+积分(PI)控制器，可以使系统在进入稳态后无稳态误差。PI控制器不但保持了积分控制器消除稳态误差的“记忆功能”，而且克服了单独使用积分控制消除误差时反应不灵敏的缺点。


　　优点：消除稳态误差。

　　

　　缺点：积分控制器的加入会影响系统的稳定性，使系统的稳定裕度减小。


　　3. 微分环节


   反映偏差信号的变化趋势，并能在偏差信号变得太大之前，在系统中引入一个有效的早期修正信号，从而加快系统的动作速度，减少调节时间。在微分控制中，控制器的输出与输入误差信号的微分（即误差的变化率）成正比关系。


　　为什么要引进微分作用？


   前面已经分析过，不论比例调节作用，还是积分调节作用都是建立在产生误差后才进行调节以消除误差，都是事后调节，因此这种调节对稳态来说是无差的，对动态来说肯定是有差的，因为对于负载变化或给定值变化所产生的扰动，必须等待产生误差以后，然后再来慢慢调节予以消除。


   但一般的控制系统，不仅对稳定控制有要求，而且对动态指标也有要求，通常都要求负载变化或给定调整等引起扰动后，恢复到稳态的速度要快，因此光有比例和积分调节作用还不能完全满足要求，必须引入微分作用。比例作用和积分作用是事后调节(即发生误差后才进行调节)，而微分作用则是事前预防控制，即一发现y(t)有变大或变小的趋势，马上就输出一个阻止其变化的控制信号，以防止出现过冲或超调等。

D越大，微分作用越强，D越小，微分作用越弱。系统调试时通常把D从小往大调，具体参数由试验决定。


   如：由于给定值调整或负载扰动引起y(t)变化，比例作用和微分作用一定等到y(t)值变化后才进行调节，并且误差小时，产生的比例和积分调节作用也小，纠正误差的能力也小，误差大时，产生的比例和积分作用才增大。因为是事后调节动态指标不会很理想。而微分作用可以在产生误差之前一发现有产生误差的趋势就开始调节，是提前控制，所以及时性更好，可以最大限度地减少动态误差，使整体效果更好。但微分作用只能作为比例和积分控制的一种补充，不能起主导作用，微分作用不能太强，太强也会引起系统不稳定，产生振荡，微分作用只能在P和I调好后再由小往大调，一点一点试着加上去。


   自动控制系统在克服误差的调节过程中可能会出现振荡甚至失稳。其原因是由于存在有较大惯性组件（环节）或有滞后(delay)组件，具有抑制误差的作用，其变化总是落后于误差的变化。解决的办法是使抑制误差的作用的变化“超前”，即在误差接近零时，抑制误差的作用就应该是零。这就是说，在控制器中仅引入“比例”项往往是不够的，比例项的作用仅是放大误差的幅值，而目前需要增加的是“微分项”，它能预测误差变化的趋势。这样，具有比例+微分的控制器，就能够提前使抑制误差的控制作用等于零，甚至为负值，从而避免了被控量的严重超调。所以对有较大惯性或滞后的被控对象，比例+微分(PD)控制器能改善系统在调节过程中的动态特性。PD控制只在动态过程中才起作用，对恒定稳态情况起阻断作用。因此，微分控制在任何情况下都不能单独使用。


　　优点：使系统的响应速度变快，超调减小，振荡减轻，对动态过程有“预测”作用。


   在低频段，主要是PI控制规律起作用，提高系统型别，消除或减少稳态误差；在中高频段主要是PD规律起作用，增大截止频率和相角裕度，提高响应速度。因此，控制器可以全面地提高系统的控制性能。


三、PID控制器的参数整定


   PID控制器的参数整定是控制系统设计的核心内容。它是根据被控过程的特性确定PID控制器的比例系数、积分时间和微分时间的大小。PID控制器参数整定的方法很多，概括起来有两大类：


　　1. 理论计算整定法


   它主要是依据系统的数学模型，经过理论计算确定控制器参数。这种方法所得到的计算数据未必可以直接用，还必须通过工程实际进行调整和修改。


　　2. 工程整定方法


   它主要依赖工程经验，直接在控制系统的试验中进行，且方法简单、易于掌握，在工程实际中被广泛采用。PID控制器参数的工程整定方法，主要有临界比例法、反应曲线法和衰减法。三种方法各有其特点，其共同点都是通过试验，然后按照工程经验公式对控制器参数进行整定。但无论采用哪一种方法所得到的控制器参数，都需要在实际运行中进行最后调整与完善。现在一般采用的是临界比例法。利用该方法进行 PID控制器参数的整定步骤如下：


　　(1)首先预选择一个足够短的采样周期让系统工作；


　　(2)仅加入比例控制环节，直到系统对输入的阶跃响应出现临界振荡，记下这时的比例放大系数和临界振荡周期；


　　(3)在一定的控制度下通过公式计算得到PID控制器的参数。


　　PID调试一般原则


　　a.在输出不振荡时，增大比例增益P。

　　b.在输出不振荡时，减小积分时间常数Ti。

　　c.在输出不振荡时，增大微分时间常数Td。


　　PID调试一般步骤


　　a. 确定比例增益P


　　确定比例增益P 时，首先去掉PID的积分项和微分项，一般是令Ti=0、Td=0（具体见PID的参数设定说明），使PID为纯比例调节。输入设定为系统允许的最大值的60%~70%，由0逐渐加大比例增益P，直至系统出现振荡；再反过来，从此时的比例增益P逐渐减小，直至系统振荡消失，记录此时的比例增益P，设定PID的比例增益P为当前值的60%~70%。比例增益P调试完成。


　　b. 确定积分时间常数Ti


　　比例增益P确定后，设定一个较大的积分时间常数Ti的初值，然后逐渐减小Ti，直至系统出现振荡，之后在反过来，逐渐加大Ti，直至系统振荡消失。记录此时的Ti，设定PID的积分时间常数Ti为当前值的150%~180%。积分时间常数Ti调试完成。


　　c. 确定微分时间常数Td


　　微分时间常数Td一般不用设定，为0即可。若要设定，与确定 P和Ti的方法相同，取不振荡时的30%。


　　d. 系统空载、带载联调，再对PID参数进行微调，直至满足要求。


   变速积分的基本思想是，设法改变积分项的累加速度，使其与偏差大小相对应：偏差越大，积分越慢；反之则越快，有利于提高系统品质。

转载的地址http://blog.sciencenet.cn/blog-699887-948853.html

大家再看看维基百科上面的PID的动图。







 



https://zh.wikipedia.org/wiki/PID%E6%8E%A7%E5%88%B6%E5%99%A8

维基百科上面讲的也比较清楚，结合起来看挺好。

多谢小伙伴更正了里面的小错误，步骤C为微分时间@lubingabby

为什么会有TCP/IP协议
在世界上各地，各种各样的电脑运行着各自不同的操作系统为大家服务，这些电脑在表达同一种信息的时候所使用的方法是千差万别。就好像圣经中上帝打乱了各地人的口音，让他们无法合作一样。计算机使用者意识到，计算机只是单兵作战并不会发挥太大的作用。只有把它们联合起来，电脑才会发挥出它最大的潜力。于是人们就想方设法的用电线把电脑连接到了一起。
但是简单的连到一起是远远不够的，就好像语言不同的两个人互相见了面，完全不能交流信息。因而他们需要定义一些共通的东西来进行交流，TCP/IP就是为此而生。TCP/IP不是一个协议，而是一个协议族的统称。里面包括了IP协议，IMCP协议，TCP协议，以及我们更加熟悉的http、ftp、pop3协议等等。电脑有了这些，就好像学会了外语一样，就可以和其他的计算机终端做自由的交流了。
TCP/IP模型


应用层:

向用户提供一组常用的应用程序，比如电子邮件、文件传输访问、远程登录等。远程登录TELNET使用TELNET协议提供在网络其它主机上注册的接口。TELNET会话提供了基于字符的虚拟终端。文件传输访问FTP使用FTP协议来提供网络内机器间的文件拷贝功能。
传输层:

提供应用程序间的通信。其功能包括：一、格式化信息流；二、提供可靠传输。为实现后者，传输层协议规定接收端必须发回确认，并且假如分组丢失，必须重新发送。
网络层 ：

负责相邻计算机之间的通信。其功能包括三方面。

一、处理来自传输层的分组发送请求，收到请求后，将分组装入IP数据报，填充报头，选择去往信宿机的路径，然后将数据报发往适当的网络接口。
二、处理输入数据报：首先检查其合法性，然后进行寻径–假如该数据报已到达信宿机，则去掉报头，将剩下部分交给适当的传输协议；假如该数据报尚未到达信宿，则转发该数据报。
三、处理路径、流控、拥塞等问题。
网络接口层：

这是TCP/IP软件的最低层，负责接收IP数据报并通过网络发送之，或者从网络上接收物理帧，抽出IP数据报，交给IP层。
IP
IP 用于计算机之间的通信。
IP 是无连接的通信协议。它不会占用两个正在通信的计算机之间的通信线路。这样，IP 就降低了对网络线路的需求。每条线可以同时满足许多不同的计算机之间的通信需要。
通过 IP，消息（或者其他数据）被分割为小的独立的包，并通过因特网在计算机之间传送。
IP 负责将每个包路由至它的目的地。
IP地址
每个计算机必须有一个 IP 地址才能够连入因特网。
每个 IP 包必须有一个地址才能够发送到另一台计算机。
网络上每一个节点都必须有一个独立的Internet地址（也叫做IP地址）。现在，通常使用的IP地址是一个32bit的数字，也就是我们常说的IPv4标准，这32bit的数字分成四组，也就是常见的255.255.255.255的样式。IPv4标准上，地址被分为五类，我们常用的是B类地址。具体的分类请参考其他文档。需要注意的是IP地址是网络号+主机号的组合，这非常重要。
CP/IP 使用 32 个比特来编址。一个计算机字节是 8 比特。所以 TCP/IP 使用了 4 个字节。

一个计算机字节可以包含 256 个不同的值：

00000000、00000001、00000010、00000011、00000100、00000101、00000110、00000111、00001000 … 直到 11111111。

现在，你知道了为什么 TCP/IP 地址是介于 0 到 255 之间的 4 个数字。
TCP 使用固定的连接
TCP 用于应用程序之间的通信。
当应用程序希望通过 TCP 与另一个应用程序通信时，它会发送一个通信请求。这个请求必须被送到一个确切的地址。在双方“握手”之后，TCP 将在两个应用程序之间建立一个全双工 (full-duplex) 的通信。
这个全双工的通信将占用两个计算机之间的通信线路，直到它被一方或双方关闭为止。
UDP 和 TCP 很相似，但是更简单，同时可靠性低于 TCP。
IP 路由器
当一个 IP 包从一台计算机被发送，它会到达一个 IP 路由器。
IP 路由器负责将这个包路由至它的目的地，直接地或者通过其他的路由器。
在一个相同的通信中，一个包所经由的路径可能会和其他的包不同。而路由器负责根据通信量、网络中的错误或者其他参数来进行正确地寻址。
域名
12 个阿拉伯数字很难记忆。使用一个名称更容易。
用于 TCP/IP 地址的名字被称为域名。www.baidu.com就是一个域名。
当你键入一个像https://www.baidu.com/这样的域名，域名会被一种 DNS 程序翻译为数字。
在全世界，数量庞大的 DNS 服务器被连入因特网。DNS 服务器负责将域名翻译为 TCP/IP 地址，同时负责使用新的域名信息更新彼此的系统。
当一个新的域名连同其 TCP/IP 地址一同注册后，全世界的 DNS 服务器都会对此信息进行更新。
TCP/IP
TCP/IP 意味着 TCP 和 IP 在一起协同工作。
TCP 负责应用软件（比如你的浏览器）和网络软件之间的通信。
IP 负责计算机之间的通信。
TCP 负责将数据分割并装入 IP 包，然后在它们到达的时候重新组合它们。
IP 负责将包发送至接受者。
TCP报文格式


16位源端口号：16位的源端口中包含初始化通信的端口。源端口和源IP地址的作用是标识报文的返回地址。
16位目的端口号：16位的目的端口域定义传输的目的。这个端口指明报文接收计算机上的应用程序地址接口。
32位序号：32位的序列号由接收端计算机使用，重新分段的报文成最初形式。当SYN出现，序列码实际上是初始序列码（Initial Sequence Number，ISN），而第一个数据字节是ISN+1。这个序列号（序列码）可用来补偿传输中的不一致。
32位确认序号：32位的序列号由接收端计算机使用，重组分段的报文成最初形式。如果设置了ACK控制位，这个值表示一个准备接收的包的序列码。
4位首部长度：4位包括TCP头大小，指示何处数据开始。
保留（6位）：6位值域，这些位必须是0。为了将来定义新的用途而保留。
标志：6位标志域。表示为：紧急标志、有意义的应答标志、推、重置连接标志、同步序列号标志、完成发送数据标志。按照顺序排列是：URG、ACK、PSH、RST、SYN、FIN。
16位窗口大小：用来表示想收到的每个TCP数据段的大小。TCP的流量控制由连接的每一端通过声明的窗口大小来提供。窗口大小为字节数，起始于确认序号字段指明的值，这个值是接收端正期望接收的字节。窗口大小是一个16字节字段，因而窗口大小最大为65535字节。
16位校验和：16位TCP头。源机器基于数据内容计算一个数值，收信息机要与源机器数值 结果完全一样，从而证明数据的有效性。检验和覆盖了整个的TCP报文段：这是一个强制性的字段，一定是由发送端计算和存储，并由接收端进行验证的。
16位紧急指针：指向后面是优先数据的字节，在URG标志设置了时才有效。如果URG标志没有被设置，紧急域作为填充。加快处理标示为紧急的数据段。
选项：长度不定，但长度必须为1个字节。如果没有选项就表示这个1字节的域等于0。
数据：该TCP协议包负载的数据。
在上述字段中，6位标志域的各个选项功能如下。
URG：紧急标志。紧急标志为"1"表明该位有效。
ACK：确认标志。表明确认编号栏有效。大多数情况下该标志位是置位的。TCP报头内的确认编号栏内包含的确认编号（w+1）为下一个预期的序列编号，同时提示远端系统已经成功接收所有数据。
PSH：推标志。该标志置位时，接收端不将该数据进行队列处理，而是尽可能快地将数据转由应用处理。在处理Telnet或rlogin等交互模式的连接时，该标志总是置位的。
RST：复位标志。用于复位相应的TCP连接。
SYN：同步标志。表明同步序列编号栏有效。该标志仅在三次握手建立TCP连接时有效。它提示TCP连接的服务端检查序列编号，该序列编号为TCP连接初始端（一般是客户端）的初始序列编号。在这里，可以把TCP序列编号看作是一个范围从0到4，294，967，295的32位计数器。通过TCP连接交换的数据中每一个字节都经过序列编号。在TCP报头中的序列编号栏包括了TCP分段中第一个字节的序列编号。
FIN：结束标志。
TCP三次握手
所谓三次握手（Three-Way Handshake）即建立TCP连接，就是指建立一个TCP连接时，需要客户端和服务端总共发送3个包以确认连接的建立。在socket编程中，这一过程由客户端执行connect来触发，整个流程如下图所示：



（1）第一次握手：Client将标志位SYN置为1，随机产生一个值seq=J，并将该数据包发送给Server，Client进入SYN_SENT状态，等待Server确认。
（2）第二次握手：Server收到数据包后由标志位SYN=1知道Client请求建立连接，Server将标志位SYN和ACK都置为1，ack=J+1，随机产生一个值seq=K，并将该数据包发送给Client以确认连接请求，Server进入SYN_RCVD状态。
（3）第三次握手：Client收到确认后，检查ack是否为J+1，ACK是否为1，如果正确则将标志位ACK置为1，ack=K+1，并将该数据包发送给Server，Server检查ack是否为K+1，ACK是否为1，如果正确则连接建立成功，Client和Server进入ESTABLISHED状态，完成三次握手，随后Client与Server之间可以开始传输数据了。
简单来说，就是
1、建立连接时，客户端发送SYN包（SYN=i）到服务器，并进入到SYN-SEND状态，等待服务器确认
2、服务器收到SYN包，必须确认客户的SYN（ack=i+1）,同时自己也发送一个SYN包（SYN=k）,即SYN+ACK包，此时服务器进入SYN-RECV状态
3、客户端收到服务器的SYN+ACK包，向服务器发送确认报ACK（ack=k+1）,此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手，客户端与服务器开始传送数据。
SYN攻击：
在三次握手过程中，Server发送SYN-ACK之后，收到Client的ACK之前的TCP连接称为半连接（half-open connect），此时Server处于SYN_RCVD状态，当收到ACK后，Server转入ESTABLISHED状态。SYN攻击就是Client在短时间内伪造大量不存在的IP地址，并向Server不断地发送SYN包，Server回复确认包，并等待Client的确认，由于源地址是不存在的，因此，Server需要不断重发直至超时，这些伪造的SYN包将产时间占用未连接队列，导致正常的SYN请求因为队列满而被丢弃，从而引起网络堵塞甚至系统瘫痪。SYN攻击时一种典型的DDOS攻击，检测SYN攻击的方式非常简单，即当Server上有大量半连接状态且源IP地址是随机的，则可以断定遭到SYN攻击了，使用如下命令可以让之现行：
#netstat -nap | grep SYN_RECV

TCP四次挥手
所谓四次挥手（Four-Way Wavehand）即终止TCP连接，就是指断开一个TCP连接时，需要客户端和服务端总共发送4个包以确认连接的断开。在socket编程中，这一过程由客户端或服务端任一方执行close来触发，整个流程如下图所示：



由于TCP连接时全双工的，因此，每个方向都必须要单独进行关闭，这一原则是当一方完成数据发送任务后，发送一个FIN来终止这一方向的连接，收到一个FIN只是意味着这一方向上没有数据流动了，即不会再收到数据了，但是在这个TCP连接上仍然能够发送数据，直到这一方向也发送了FIN。首先进行关闭的一方将执行主动关闭，而另一方则执行被动关闭，上图描述的即是如此。
（1）第一次挥手：Client发送一个FIN，用来关闭Client到Server的数据传送，Client进入FIN_WAIT_1状态。
（2）第二次挥手：Server收到FIN后，发送一个ACK给Client，确认序号为收到序号+1（与SYN相同，一个FIN占用一个序号），Server进入CLOSE_WAIT状态。
（3）第三次挥手：Server发送一个FIN，用来关闭Server到Client的数据传送，Server进入LAST_ACK状态。
（4）第四次挥手：Client收到FIN后，Client进入TIME_WAIT状态，接着发送一个ACK给Server，确认序号为收到序号+1，Server进入CLOSED状态，完成四次挥手。
为什么建立连接是三次握手，而关闭连接却是四次挥手呢？
这是因为服务端在LISTEN状态下，收到建立连接请求的SYN报文后，把ACK和SYN放在一个报文里发送给客户端。而关闭连接时，当收到对方的FIN报文时，仅仅表示对方不再发送数据了但是还能接收数据，己方也未必全部数据都发送给对方了，所以己方可以立即close，也可以发送一些数据给对方后，再发送FIN报文给对方来表示同意现在关闭连接，因此，己方ACK和FIN一般都会分开发送。
为什么TIME_WAIT状态需要经过2MSL(最大报文段生存时间)才能返回到CLOSE状态？

原因有二：

一、保证TCP协议的全双工连接能够可靠关闭

二、保证这次连接的重复数据段从网络中消失
先说第一点，如果Client直接CLOSED了，那么由于IP协议的不可靠性或者是其它网络原因，导致Server没有收到Client最后回复的ACK。那么Server就会在超时之后继续发送FIN，此时由于Client已经CLOSED了，就找不到与重发的FIN对应的连接，最后Server就会收到RST而不是ACK，Server就会以为是连接错误把问题报告给高层。这样的情况虽然不会造成数据丢失，但是却导致TCP协议不符合可靠连接的要求。所以，Client不是直接进入CLOSED，而是要保持TIME_WAIT，当再次收到FIN的时候，能够保证对方收到ACK，最后正确的关闭连接。
再说第二点，如果Client直接CLOSED，然后又再向Server发起一个新连接，我们不能保证这个新连接与刚关闭的连接的端口号是不同的。也就是说有可能新连接和老连接的端口号是相同的。一般来说不会发生什么问题，但是还是有特殊情况出现：假设新连接和已经关闭的老连接端口号是一样的，如果前一次连接的某些数据仍然滞留在网络中，这些延迟数据在建立新连接之后才到达Server，由于新连接和老连接的端口号是一样的，又因为TCP协议判断不同连接的依据是socket pair，于是，TCP协议就认为那个延迟的数据是属于新连接的，这样就和真正的新连接的数据包发生混淆了。所以TCP连接还要在TIME_WAIT状态等待2倍MSL，这样可以保证本次连接的所有数据都从网络中消失。
认识HTTP协议
它是互联网协议(Internet Protocol Suite)，一个网络通信模型，是互联网的一个基本的构架。
HTTP协议是Hyper Text Transfer Protocol（超文本传输协议）的缩写,是用于从万维网（WWW:World Wide Web ）服务器传输超文本到本地浏览器的传送协议。
HTTP是一个基于TCP/IP通信协议来传递数据（HTML 文件, 图片文件, 查询结果等）。
HTTP是一个属于应用层的面向对象的协议，由于其简捷、快速的方式，适用于分布式超媒体信息系统。它于1990年提出，经过几年的使用与发展，得到不断地完善和扩展。目前在WWW中使用的是HTTP/1.0的第六版，HTTP/1.1的规范化工作正在进行之中，而且HTTP-NG(Next Generation of HTTP)的建议已经提出。
HTTP协议工作于客户端-服务端架构为上。浏览器作为HTTP客户端通过URL向HTTP服务端即WEB服务器发送所有请求。Web服务器根据接收到的请求后，向客户端发送响应信息。
TCP/IP协议它们并不是一个协议，而是一个协议簇，这些协议的目的，就是使计算机之间可以进行信息交换，并且两大协议其中都包含其他的协议，虽然放在了一起，但它们的作用和工作是不一样的。
HTTP协议定义了内容的格式，这是一个应用层的协议，应用层协议的内容需要通过传输层在浏览器和服务器之间传送，TCP/IP协议是ISO网络参考模型的一种实现。在TCP/IP协议中，与网络程序员相关的主要有两层：传输层和应用层。
传输层协议负责解决数据传输问题，包括数据通行的可靠性问题。传输层依赖更底层的网络层来完成实际的数据传输，在TCP/IP网络协议中，负责可靠通信的传输层协议为TCP协议。而网络层一般用网络驱动来实现，普通的程序员不会涉及；在TCP/IP协议中，网络层的协议为IP协议。
HTTP请求处理图解
浏览器与Web服务器之间的协议是应用层协议，当前，我们主要遵循的协议为HTTP/1.1。HTTP协议是Web开发的基础，这是一个无状态的协议，客户机与服务器之间通过请求和相应完成一次会话（Session）。


客户端、web服务器、HTTP三者之间的联系
（1）客户端与web服务器工作过程

当浏览器寻找到Web服务器的地址之后，浏览器帮助我们把对服务器的请求转换为一系列参数发送给Web服务器。服务器受到浏览器发来的请求参数之后，将会分析这些数据，并进行处理。然后向浏览器回应处理的结果，也就是一些新的数据；这些数据通常是HTML网页或者图片。浏览器收到之后，解析这些数据，将它们呈现在浏览器的窗口中，这就是我们看到的网页。

（2）客户端与web服务器遵守共同标准：HTTP协议

在浏览器与Web服务器的对话中，需要使用双方都能够理解的语法规范进行通信，这种程序之间进行通信的语法规范，我们称之为协议。协议有许多种，根据国际标准化组织ISO的网络参考模型，程序与程序之间的通信可分为7层，从低到高依次为：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。
ISO模型：



（3）客户端、web服务器、数据库服务器图解


浏览器与服务器图解
HTTP协议就是TCP/IP协议中专门用于浏览器与Web服务器之间通信的应用层协议。应用层协议依赖于传输层协议完成数据传输，传输层协议依赖于网络层协议王城数据传输，他们之间的关系如下图（浏览器与服务器之间网络通信的传输过程）：


写在后面
如果觉得本文帮助了你，还请高抬贵手赠予 uh5 项目 一个 Star。

一、哈希表概述

       首先简单介绍几个概念：哈希表（散列表）、映射、冲突、链地址、哈希函数。

       哈希表（Hash table）的初衷是为了将数据映射到数组中的某个位置，这样就能够通过数组下标访问该数据，提高数据的查找速度，这样的查找的平均期望时间复杂度是O(1)的。

       例如四个整数 6、7、9、12 需要映射到数组中，我们可以开一个长度为13（C语言下标从0开始）的数组，然后将对应值放到对应的下标，但是这样做，就会浪费没有被映射到的位置的空间。



 

       采用哈希表的话，我们可以只申请一个长度为4的数组，如下图所示：



 

       将每个数的值对数组长度4取模，然后放到对应的数组槽位中，这样就把离散的数据映射到了连续的空间，所以哈希表又称为散列表。这样做，最大限度上提高空间了利用率，并且查找效率还很高。

       那么问题来了，如果这四个数据是6、7、8、11呢？继续看图：



       7 和 11 对4取模的值都是 3，所以占据了同一个槽位，这种情况我们称为冲突 （collision）。一般遇到冲突后，有很多方法解决冲突，包括但不限于 开放地址法、再散列法、链地址法 等等。 Redis采用的是链地址法，所以这里只介绍链地址法，其它的方法如果想了解请自行百度。

      链地址法就是将有冲突的数据用一个链表串联起来，如图所示：



       这样一来，就算有冲突，也可以将有冲突的数据存储在一起了。存储结构需要稍加变化，哈希表的每个元素将变成一个指针，指向数据链表的链表头，每次有新数据来时从链表头插入，可以达到插入的时间复杂度保持O(1)。

        再将问题进行变形，如果4个数据是 "are",  "you",  "OK",  "？" 这样的字符串，如何进行映射呢？没错，我们需要通过一个哈希函数将字符串变成整数，哈希函数的概念会在接下来详细讲述，这里只需要知道它可以把一个值变成另一个值即可，比如哈希函数f(x)，调用 f("are") 就可以得到一个整数，f("you") 也可以得到一个整数。

        一个简易的大小写不敏感的字符串哈希函数如下：

unsigned int hashFunction(const unsigned char *buf, int len) {
    unsigned int hash = (unsigned int)5381;                       // hash初始种子，实验值
    while (len--)
        hash = ((hash << 5) + hash) + (tolower(*buf++));          // hash * 33 + c
    return hash;
}

        我们看到，哈希函数的作用就是把非数字的对象通过一系列的算法转化成数字（下标），得到的数字可能是哈希表数组无法承载的，所以还需要通过取模才能映射到连续的数组空间中。对于这个取模，我们知道取模的效率相比位运算来说是很低的，那么有没有什么办法可以把取模用位运算来代替呢？

        答案是有！我们只要把哈希表的长度 L 设置为2的幂（L = 2^n），那么 L-1 的二进制表示就是n个1，任何值 x 对 L 取模等同于和 (L-1) 进行位与（C语言中的&）运算。



        介绍完哈希表的基础概念，我们来看看 Redis 中是如何实现字典的。

二、Redis数据结构定义

     1、哈希表

       哈希表的结构定义在 dict.h/dictht ：

typedef struct dictht {
    dictEntry **table;             // 哈希表数组
    unsigned long size;            // 哈希表数组的大小
    unsigned long sizemask;        // 用于映射位置的掩码，值永远等于(size-1)
    unsigned long used;            // 哈希表已有节点的数量
} dictht;

       table 是一个数组，数组的每个元素都是一个指向 dict.h/dictEntry 结构的指针；

       size 记录哈希表的大小，即 table 数组的大小，且一定是2的幂；

       used 记录哈希表中已有结点的数量；

       sizemask 用于对哈希过的键进行映射，索引到 table 的下标中，且值永远等于 size-1。具体映射方法很简单，就是对 哈希值 和 sizemask 进行位与操作，由于 size 一定是2的幂，所以 sizemask=size-1，自然它的二进制表示的每一个位(bit)都是1，等同于上文提到的取模；

       如图所示，为一个长度为8的空哈希表。



     2、哈希表节点

       哈希表节点用 dict.h/dictEntry 结构表示，每个 dictEntry 结构存储着一个键值对，且存有一个 next 指针来保持链表结构：

typedef struct dictEntry {
    void *key;                  // 键
    union {                     // 值
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     // 指向下一个哈希表节点，形成单向链表
} dictEntry;

       key 是键值对中的键；

       v 是键值对中的值，它是一个联合类型，方便存储各种结构；

       next 是链表指针，指向下一个哈希表节点，他将多个哈希值相同的键值对串联在一起，用于解决键冲突；如图所示，两个dictEntry 的 key 分别是 k0 和 k1，通过某种哈希算法计算出来的哈希值和 sizemask 进行位与运算后都等于 3，所以都被放在了 table 数组的 3号槽中，并且用 next 指针串联起来。



     3、字典

       Redis中字典结构由 dict.h/dict 表示：

typedef struct dict {
    dictType *type;                        // 和类型相关的处理函数
    void *privdata;                        // 上述类型函数对应的可选参数
    dictht ht[2];                          // 两张哈希表，ht[0]为原生哈希表，ht[1]为 rehash 哈希表
    long rehashidx;                        // 当等于-1时表示没有在 rehash，否则表示 rehash 的下标
    int iterators;                         // 迭代器数量(暂且不谈)
} dict;

     type 是一个指向 dict.h/dictType 结构的指针，保存了一系列用于操作特定类型键值对的函数；

     privdata 保存了需要传给上述特定函数的可选参数；

     ht 是两个哈希表，一般情况下，只使用ht[0]，只有当哈希表的键值对数量超过负载(元素过多)时，才会将键值对迁移到ht[1]，这一步迁移被称为 rehash (重哈希)，rehash 会在下文进行详细介绍；

     rehashidx 由于哈希表键值对有可能很多很多，所以 rehash 不是瞬间完成的，需要按部就班，那么 rehashidx 就记录了当前 rehash 的进度，当 rehash 完毕后，将 rehashidx 置为-1；

     4、类型处理函数

      类型处理函数全部定义在 dict.h/dictType 中：

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);                                         // 计算哈希值的函数
    void *(*keyDup)(void *privdata, const void *key);                                      // 复制键的函数
    void *(*valDup)(void *privdata, const void *obj);                                      // 复制值的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);                 // 比较键的函数
    void (*keyDestructor)(void *privdata, void *key);                                      // 销毁键的函数
    void (*valDestructor)(void *privdata, void *obj);                                      // 销毁值的函数
} dictType;

       以上的函数和特定类型相关，主要是为了实现多态，看到这个如果懵逼也没关系，下面会一一对其进行介绍。

三、哈希函数

      类型处理函数中的第一个函数 hashFunction 就是计算某个键的哈希值的函数，对于不同类型的 key，哈希值的计算是不同的，所以在字典进行创建的时候，需要指定哈希函数。

      哈希函数可以简单的理解为就是小学课本上那个函数，即y = f(x)，这里的 f(x)就是哈希函数，x是键，y就是哈希值。好的哈希函数应该具备以下两个特质：

       1、可逆性；

       2、雪崩效应：输入值(x)的1位(bit)的变化，能够造成输出值(y)1/2的位(bit)的变化；

       可逆性很容易理解，来看两个图。图(a)中已知哈希值 y 时，键 x 可能有两种情况，所以显然是不可逆的；而图(b)中已知哈希值 y 时，键 x 一定是唯一确定的，所以它是可逆的。从图中看出，函数可逆的好处是：减少冲突。由于 x 和 y 一一对应，所以在没有取模之前，至少是没有冲突的，这样就从本原上减少了冲突。



       雪崩效应是为了让哈希值更加符合随机分布的原则，哈希表中的键分布的越随机，利用率越高，效率也越高。

       Redis源码中提供了一些哈希函数的实现：

      1、整数哈希

unsigned int dictIntHashFunction(unsigned int key)
{
    key += ~(key << 15);
    key ^=  (key >> 10);
    key +=  (key << 3);
    key ^=  (key >> 6);
    key += ~(key << 11);
    key ^=  (key >> 16);
    return key;
}

       2、字符串哈希

unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
    unsigned int hash = (unsigned int)dict_hash_function_seed;
    while (len--)
        hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
    return hash;
}

       这些哈希函数是前人经过一系列的实验，科学计算总结得出来的，我们只需要知道有这么些函数就行了。当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。MurmurHash 算法最初由 Austin Appleby 于 2008 年发明， 这种算法的优点在于， 即使输入的键是有规律的， 算法仍能给出一个很好的随机分布性， 并且算法的计算速度也非常快。

 

四、哈希算法

     1、索引 

       当要将一个新的键值对添加到字典里面或者通过键查找值的时候都需要执行哈希算法，主要是获得一个需要插入或者查找的dictEntry 所在下标的索引，具体算法如下：

       1、通过宏 dictHashKey 计算得到该键对应的哈希值

#define dictHashKey(d, key) (d)->type->hashFunction(key)

       2、将哈希值和哈希表的 sizemask 属性做位与，得到索引值 index，其中 ht[x] 可以是 ht[0] 或者 ht[1]

index = dictHashKey(d, key) & d->ht[x].sizemask;

      2、冲突解决

        哈希的冲突一定发生在键值对插入时，插入的  API 是 dict.c/dictAddRaw：

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
    if (dictIsRehashing(d)) _dictRehashStep(d);               // 1、执行rehash
    if ((index = _dictKeyIndex(d, key)) == -1)                // 2、索引定位
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];          // 3、根据是否 rehash ，选择哈希表
    entry = zmalloc(sizeof(*entry));                          // 4、分配内存空间，执行插入
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    dictSetKey(d, entry, key);                                // 5、设置键
    return entry;
}

       1、判断当前的字典是否在进行 rehash，如果是，则执行一步 rehash，否则忽略。判断 rehash 的依据就是 rehashidx 是否为 -1；

       2、通过 _dictKeyIndex 找到一个索引，如果返回-1表明字典中已经存在相同的 key，具体参见接下来要讲的 索引定位；

       3、根据是否在 rehash 选择对应的哈希表；

       4、分配哈希表节点 dictEntry 的内存空间，执行插入，插入操作始终在链表头插入，这样可以保证每次的插入操作的时间复杂度一定是 O(1) 的，插入完毕，used属性自增；

       5、dictSetKey 是个宏，调用字典处理函数中的 keyDup 函数进行键的复制；

 

      3、索引定位

        插入时还需要进行索引定位，以确定节点要插入到哈希表的哪个位置，实现在静态函数 dict.c/_dictKeyIndex 中：

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    if (_dictExpandIfNeeded(d) == DICT_ERR)                            // 1、rehash 判断
        return -1;
    h = dictHashKey(d, key);                                           // 2、哈希函数计算哈希值
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;                               // 3、哈希算法计算索引值
        he = d->ht[table].table[idx];
        while(he) {                          
            if (key==he->key || dictCompareKeys(d, key, he->key))      // 4、查找键是否已经存在
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;                                // 5、rehash 判断 
    }
    return idx;
}

       1、判断当前哈希表是否需要进行扩展，具体参见接下来要讲的 rehash；

       2、利用给定的哈希函数计算键的哈希值；

       3、通过位与计算索引，即插入到哈希表的哪个槽位中；

       4、查找当前槽位中的链表里是否已经存在该键，如果存在直接返回 -1；这里的 dictCompareKeys 也是一个宏，用到了keyCompare 这个比较键的函数；

       5、这个判断比较关键，如果当前没有在做 rehash，那么 ht[1] 必然是一个空表，所以不能遍历 ht[1]，需要及时跳出循环；

    五、rehash

      千呼万唤始出来，提到了这么多次的 rehash 终于要开讲了。其实没有想象中的那么复杂，随着字典操作的不断执行，哈希表保存的键值对会不断增多（或者减少），为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，需要对哈希表大小进行扩展或者收缩。

     1、负载因子

       这里提到了一个负载因子，其实就是当前已使用结点数量除上哈希表的大小，即：

load_factor = ht[0].used / ht[0].size

      2、哈希表扩展

       1、当哈希表的负载因子大于5时，为 ht[1] 分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂；

       2、将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和索引，并且重新插入到 ht[1] 中，插入一个删除一个；

       3、当 ht[0] 包含的所有键值对全部 rehash 到 ht[1] 上后，释放 ht[0] 的控件， 将 ht[1] 设置为 ht[0]，并且在 ht[1] 上新创件一个空的哈希表，为下一次 rehash 做准备；

       Redis 中 实现哈希表扩展调用的是 dict.c/_dictExpandIfNeeded 函数：

static int _dictExpandIfNeeded(dict *d)
{
    if (dictIsRehashing(d)) return DICT_OK;
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);          // 大小为0需要设置初始哈希表大小为4
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))                 // 负载因子超过5，执行 dictExpand
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}


      3、哈希表收缩

       哈希表的收缩，同样是为 ht[1] 分配空间， 大小等于 max( ht[0].used, DICT_HT_INITIAL_SIZE )，然后和扩展做同样的处理即可。

     六、渐进式rehash

       扩展或者收缩哈希表的时候，需要将 ht[0] 里面所有的键值对 rehash 到 ht[1] 里，当键值对数量非常多的时候，这个操作如果在一帧内完成，大量的计算很可能导致服务器宕机，所以不能一次性完成，需要渐进式的完成。

       渐进式 rehash 的详细步骤如下：

       1、为 ht[1] 分配指定空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表；

       2、将 rehashidx 设置为0，表示正式开始 rehash，前两步是在 dict.c/dictExpand 中实现的：

int dictExpand(dict *d, unsigned long size)
{
    dictht n;
    unsigned long realsize = _dictNextPower(size);                      // 找到比size大的最小的2的幂
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    if (realsize == d->ht[0].size) return DICT_ERR;

    n.size = realsize;                                                 // 给ht[1]分配 realsize 的空间
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    if (d->ht[0].table == NULL) {                                      // 处于初始化阶段
        d->ht[0] = n;
        return DICT_OK;
    }
    d->ht[1] = n;
    d->rehashidx = 0;                                                  // rehashidx 设置为0，开始渐进式 rehash
    return DICT_OK;
}

 

       3、在进行 rehash 期间，每次对字典执行 增、删、改、查操作时，程序除了执行指定的操作外，还会将 哈希表 ht[0].table中下标为 rehashidx 位置上的所有的键值对 全部迁移到 ht[1].table 上，完成后 rehashidx 自增。这一步就是 rehash 的关键一步。为了防止 ht[0] 是个稀疏表 （遍历很久遇到的都是NULL），从而导致函数阻塞时间太长，这里引入了一个 “最大空格访问数”，也即代码中的 enmty_visits，初始值为 n*10。当遇到NULL的数量超过这个初始值直接返回。

       这一步实现在 dict.c/dictRehash 中：

int dictRehash(dict *d, int n) {
    int empty_visits = n*10;
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;                                      // 设置一个空访问数量 为 n*10
        }
        de = d->ht[0].table[d->rehashidx];                                          // dictEntry的迁移
        while(de) {
            unsigned int h;
            nextde = de->next;
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;                                                            // 完成一次 rehash
    }

    if (d->ht[0].used == 0) {                                                      // 迁移完毕，rehashdix 置为 -1
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    return 1;
}

       4、最后，当 ht[0].used 变为0时，代表所有的键值对都已经从 ht[0] 迁移到 ht[1] 了，释放 ht[0].table， 并且将 ht[0] 设置为 ht[1]，rehashidx 标记为 -1 代表 rehash 结束。

 

     七、字典API

        1、创建字典

        内部分配字典空间，并作为返回值返回，并调用 _dictInit 进行字典的初始化，时间复杂度O(1)。

dict *dictCreate(dictType *type, void *privDataPtr)

        2、增加键值对

        调用 dictAddRaw 增加一个 dictEntry，然后调用 dictSetVal 设置值，时间复杂度O(1)。

int dictAdd(dict *d, void *key, void *val)

        3、查找键

        利用哈希算法找到给定键的 dictEntry，时间复杂度O(1)。

dictEntry *dictFind(dict *d, const void *key)

        4、查找值

        利用 dictFind 找到给定键的 dictEntry，然后获得值，值的类型不确定，所以返回一个万能指针，时间复杂度O(1)。

void *dictFetchValue(dict *d, const void *key)

        5、删除键

        通过哈希算法找到对应的键，从对应链表移除，时间复杂度O(1)。

int dictDelete(dict *ht, const void *key)

 

 

 

python中的多线程是一个非常重要的知识点，今天为大家对多线程进行详细的说明，代码中的注释有多线程的知识点还有测试用的实例。

码字不易，阅读或复制完了，点个赞！
import threading
from threading import Lock,Thread
import time,os


'''
                                      python多线程详解
      什么是线程？
      线程也叫轻量级进程，是操作系统能够进行运算调度的最小单位，它被包涵在进程之中，是进程中的实际运作单位。
      线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所
      拥有的全部资源。一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发执行
'''

'''
    为什么要使用多线程？
    线程在程序中是独立的、并发的执行流。与分隔的进程相比，进程中线程之间的隔离程度要小，它们共享内存、文件句柄
    和其他进程应有的状态。
    因为线程的划分尺度小于进程，使得多线程程序的并发性高。进程在执行过程之中拥有独立的内存单元，而多个线程共享
    内存，从而极大的提升了程序的运行效率。
    线程比进程具有更高的性能，这是由于同一个进程中的线程都有共性，多个线程共享一个进程的虚拟空间。线程的共享环境
    包括进程代码段、进程的共有数据等，利用这些共享的数据，线程之间很容易实现通信。
    操作系统在创建进程时，必须为改进程分配独立的内存空间，并分配大量的相关资源，但创建线程则简单得多。因此，使用多线程
    来实现并发比使用多进程的性能高得要多。
'''

'''
    总结起来，使用多线程编程具有如下几个优点：
    进程之间不能共享内存，但线程之间共享内存非常容易。
    操作系统在创建进程时，需要为该进程重新分配系统资源，但创建线程的代价则小得多。因此使用多线程来实现多任务并发执行比使用多进程的效率高
    python语言内置了多线程功能支持，而不是单纯地作为底层操作系统的调度方式，从而简化了python的多线程编程。
'''


'''
    普通创建方式
'''
# def run(n):
#     print('task',n)
#     time.sleep(1)
#     print('2s')
#     time.sleep(1)
#     print('1s')
#     time.sleep(1)
#     print('0s')
#     time.sleep(1)
#
# if __name__ == '__main__':
#     t1 = threading.Thread(target=run,args=('t1',))     # target是要执行的函数名（不是函数），args是函数对应的参数，以元组的形式存在
#     t2 = threading.Thread(target=run,args=('t2',))
#     t1.start()
#     t2.start()


'''
    自定义线程：继承threading.Thread来定义线程类，其本质是重构Thread类中的run方法
'''
# class MyThread(threading.Thread):
#     def __init__(self,n):
#         super(MyThread,self).__init__()   #重构run函数必须写
#         self.n = n
#
#     def run(self):
#         print('task',self.n)
#         time.sleep(1)
#         print('2s')
#         time.sleep(1)
#         print('1s')
#         time.sleep(1)
#         print('0s')
#         time.sleep(1)
#
# if __name__ == '__main__':
#     t1 = MyThread('t1')
#     t2 = MyThread('t2')
#     t1.start()
#     t2.start()


'''
    守护线程
    下面这个例子，这里使用setDaemon(True)把所有的子线程都变成了主线程的守护线程，
    因此当主线程结束后，子线程也会随之结束，所以当主线程结束后，整个程序就退出了。
    所谓’线程守护’，就是主线程不管该线程的执行情况，只要是其他子线程结束且主线程执行完毕，主线程都会关闭。也就是说:主线程不等待该守护线程的执行完再去关闭。
'''
# def run(n):
#     print('task',n)
#     time.sleep(1)
#     print('3s')
#     time.sleep(1)
#     print('2s')
#     time.sleep(1)
#     print('1s')
#
# if __name__ == '__main__':
#     t=threading.Thread(target=run,args=('t1',))
#     t.setDaemon(True)
#     t.start()
#     print('end')
'''
    通过执行结果可以看出，设置守护线程之后，当主线程结束时，子线程也将立即结束，不再执行
'''

'''
    主线程等待子线程结束
    为了让守护线程执行结束之后，主线程再结束，我们可以使用join方法，让主线程等待子线程执行
'''
# def run(n):
#     print('task',n)
#     time.sleep(2)
#     print('5s')
#     time.sleep(2)
#     print('3s')
#     time.sleep(2)
#     print('1s')
# if __name__ == '__main__':
#     t=threading.Thread(target=run,args=('t1',))
#     t.setDaemon(True)    #把子线程设置为守护线程，必须在start()之前设置
#     t.start()
#     t.join()     #设置主线程等待子线程结束
#     print('end')


'''
    多线程共享全局变量
    线程时进程的执行单元，进程时系统分配资源的最小执行单位，所以在同一个进程中的多线程是共享资源的
'''
# g_num = 100
# def work1():
#     global  g_num
#     for i in range(3):
#         g_num+=1
#     print('in work1 g_num is : %d' % g_num)
#
# def work2():
#     global g_num
#     print('in work2 g_num is : %d' % g_num)
#
# if __name__ == '__main__':
#     t1 = threading.Thread(target=work1)
#     t1.start()
#     time.sleep(1)
#     t2=threading.Thread(target=work2)
#     t2.start()


'''
        由于线程之间是进行随机调度，并且每个线程可能只执行n条执行之后，当多个线程同时修改同一条数据时可能会出现脏数据，
    所以出现了线程锁，即同一时刻允许一个线程执行操作。线程锁用于锁定资源，可以定义多个锁，像下面的代码，当需要独占
    某一个资源时，任何一个锁都可以锁定这个资源，就好比你用不同的锁都可以把这个相同的门锁住一样。
        由于线程之间是进行随机调度的，如果有多个线程同时操作一个对象，如果没有很好地保护该对象，会造成程序结果的不可预期，
    我们因此也称为“线程不安全”。
        为了防止上面情况的发生，就出现了互斥锁（Lock）
'''
# def work():
#     global n
#     lock.acquire()
#     temp = n
#     time.sleep(0.1)
#     n = temp-1
#     lock.release()
#
#
# if __name__ == '__main__':
#     lock = Lock()
#     n = 100
#     l = []
#     for i in range(100):
#         p = Thread(target=work)
#         l.append(p)
#         p.start()
#     for p in l:
#         p.join()


'''
    递归锁：RLcok类的用法和Lock类一模一样，但它支持嵌套，在多个锁没有释放的时候一般会使用RLock类
'''
# def func(lock):
#     global gl_num
#     lock.acquire()
#     gl_num += 1
#     time.sleep(1)
#     print(gl_num)
#     lock.release()
#
#
# if __name__ == '__main__':
#     gl_num = 0
#     lock = threading.RLock()
#     for i in range(10):
#         t = threading.Thread(target=func,args=(lock,))
#         t.start()


'''
    信号量（BoundedSemaphore类）
    互斥锁同时只允许一个线程更改数据，而Semaphore是同时允许一定数量的线程更改数据，比如厕所有3个坑，
    那最多只允许3个人上厕所，后面的人只能等里面有人出来了才能再进去
'''
# def run(n,semaphore):
#     semaphore.acquire()   #加锁
#     time.sleep(3)
#     print('run the thread:%s\n' % n)
#     semaphore.release()    #释放
#
#
# if __name__== '__main__':
#     num=0
#     semaphore = threading.BoundedSemaphore(5)   #最多允许5个线程同时运行
#     for i in range(22):
#         t = threading.Thread(target=run,args=('t-%s' % i,semaphore))
#         t.start()
#     while threading.active_count() !=1:
#         pass
#     else:
#         print('----------all threads done-----------')

'''
    python线程的事件用于主线程控制其他线程的执行，事件是一个简单的线程同步对象，其主要提供以下的几个方法：
        clear将flag设置为 False
        set将flag设置为 True
        is_set判断是否设置了flag
        wait会一直监听flag，如果没有检测到flag就一直处于阻塞状态
    事件处理的机制：全局定义了一个Flag，当Flag的值为False，那么event.wait()就会阻塞，当flag值为True，
    那么event.wait()便不再阻塞
'''
event = threading.Event()
def lighter():
    count = 0
    event.set()         #初始者为绿灯
    while True:
        if 5 < count <=10:
            event.clear()  #红灯，清除标志位
            print("\33[41;lmred light is on...\033[0m]")
        elif count > 10:
            event.set()    #绿灯，设置标志位
            count = 0
        else:
            print('\33[42;lmgreen light is on...\033[0m')

        time.sleep(1)
        count += 1


def car(name):
    while True:
        if event.is_set():     #判断是否设置了标志位
            print('[%s] running.....'%name)
            time.sleep(1)
        else:
            print('[%s] sees red light,waiting...'%name)
            event.wait()
            print('[%s] green light is on,start going...'%name)


# startTime = time.time()
light = threading.Thread(target=lighter,)
light.start()

car = threading.Thread(target=car,args=('MINT',))
car.start()
endTime = time.time()
# print('用时：',endTime-startTime)

'''
                           GIL  全局解释器
        在非python环境中，单核情况下，同时只能有一个任务执行。多核时可以支持多个线程同时执行。但是在python中，无论有多少个核
        同时只能执行一个线程。究其原因，这就是由于GIL的存在导致的。
        GIL的全程是全局解释器，来源是python设计之初的考虑，为了数据安全所做的决定。某个线程想要执行，必须先拿到GIL，我们可以
        把GIL看做是“通行证”，并且在一个python进程之中，GIL只有一个。拿不到线程的通行证，并且在一个python进程中，GIL只有一个，
        拿不到通行证的线程，就不允许进入CPU执行。GIL只在cpython中才有，因为cpython调用的是c语言的原生线程，所以他不能直接操
        作cpu，而只能利用GIL保证同一时间只能有一个线程拿到数据。而在pypy和jpython中是没有GIL的
        python在使用多线程的时候，调用的是c语言的原生过程。
'''
'''
                            python针对不同类型的代码执行效率也是不同的
        1、CPU密集型代码（各种循环处理、计算等），在这种情况下，由于计算工作多，ticks技术很快就会达到阀值，然后出发GIL的
        释放与再竞争（多个线程来回切换当然是需要消耗资源的），所以python下的多线程对CPU密集型代码并不友好。
        2、IO密集型代码（文件处理、网络爬虫等设计文件读写操作），多线程能够有效提升效率（单线程下有IO操作会进行IO等待，
        造成不必要的时间浪费，而开启多线程能在线程A等待时，自动切换到线程B，可以不浪费CPU的资源，从而能提升程序的执行
        效率）。所以python的多线程对IO密集型代码比较友好。
'''
'''
    主要要看任务的类型，我们把任务分为I/O密集型和计算密集型，而多线程在切换中又分为I/O切换和时间切换。如果任务属于是I/O密集型，
    若不采用多线程，我们在进行I/O操作时，势必要等待前面一个I/O任务完成后面的I/O任务才能进行，在这个等待的过程中，CPU处于等待
    状态，这时如果采用多线程的话，刚好可以切换到进行另一个I/O任务。这样就刚好可以充分利用CPU避免CPU处于闲置状态，提高效率。但是
    如果多线程任务都是计算型，CPU会一直在进行工作，直到一定的时间后采取多线程时间切换的方式进行切换线程，此时CPU一直处于工作状态，
    此种情况下并不能提高性能，相反在切换多线程任务时，可能还会造成时间和资源的浪费，导致效能下降。这就是造成上面两种多线程结果不能的解释。
结论:I/O密集型任务，建议采取多线程，还可以采用多进程+协程的方式(例如:爬虫多采用多线程处理爬取的数据)；对于计算密集型任务，python此时就不适用了。
'''