区块链 - 区块链基础知识：深入了解交易哈希链
 
本文的主题是执行有关交易哈希链、 交易池的角色以及 一个最长的区块链如何永远占据主导。
 
讨论的细节包括以下内容：
 
事务哈希链的实现细节 
交易池的角色 
为什么需要共识算法 
PoW vs PoS
为什么最长的区块链永远占据主导
 
包含的技术：
 
区块链（Blockchain） 
交易哈希链（Transaction Hash Chain） 
椭圆曲线加密（Elliptic Curve 
 Cryptography） 
 工作量证明算法（PoW） 
 权益证明算法（PoS）
 
回顾“交易哈希链”
 
前面讨论过交易哈希链数据结构，用于跟踪数字资产的所有权。本文深入讨论哈希链的工作原理。 
 出于对区块链的敬意，本文从中本聪2008年发表的比特币的白皮书（bitcoin.org/bitcoin.pdf）开始。虽然比特币的实现细节已经变化了很多，但是白皮书还是一本很有用的参考。特别是原始的关于交易哈希链的设计概念的图表。 
 
图表的目表是告知交易哈希链是如何构建的，以及数字签名如何验证所有权的转移。但是这个图表高度抽象，而且有点容易迷惑，为了澄清当前的交易哈希链如何运作，重制了这个图表。
 
 
 图注：中本聪的原始交易哈希链 
 
这个图表中有3个交易。Alice 的 Transaction0，Bob 的 Transaction1，Charlie 的 Transaction2。第一个交易把 Alice 作为数字资产的原始拥有者，第二个交易把所有权转移给 Bob，第三个交易把所有权转移给 Charlie。每一个交易由这些实线外框的字段组成：
 
交易哈希 
数字资产ID 
可选数据 
公钥 
签名
 
虚线框的其他字段被使用了但是没有保存在交易中：
 
私钥 
新的交易哈希
 
上图中是一个简化的交易哈希链，因为在所有权转移的过程中，它只跟踪了一个数字资产（DigitalAssetID0），而加密货币的交易哈希链通常有多个数字资产的输入和输出。另外，不要把交易哈希链和区块链搞混了，区块链把验证过的交易聚合进区块中。最后，交易哈希链通常不保存在一个单链表数据结构中。相反，交易哈希链可以从保存在区块链中的交易数据中快速地创建（根据索引）。
 
正如前一篇文章说的：交易序列是被保存起来的，因为每一个新的拥有者的交易都包含一个哈希值，这个哈希值向后链接到前一个拥有者的交易上。如上图。前一个交易的交易哈希值保存在当前的交易中时，后向的链接就建立了。 
 
比如：Bob的交易包含了一个交易哈希字段，这个字段含有 Alice 的 TransactionHash0值，类似地，Charlie 的交易包含一个交易哈希字段，这个字段包含 Bob 的 TransactionHash1值。 
 
后向链接只是交易哈希链的数据完整性的几个组件之一。交易哈希链还强制验证所有权的转移过程。比如，Alice 是世界上最好的红酒供应商，她想维护一个跟踪她每瓶酒的状况的账本。某天，Alice去酒窖，决定把自己注册为她的区块链，即所有红酒的原始拥有者，有效地把她珍藏的每瓶红酒放进交易哈希链。 
 
她拿一瓶1947年的白诗南红酒，用一个包含唯一ID的二维码作标记。然后她扫描二维码标签，存进她的区块链客户端软件中，这个客户端软件作为一个结点运行于网络中。软件把扫描的代码转换成一个数字资产ID（DigitalAssetID0），然后添加一些可选的数据（OptionalData0），与Alice的公钥（PublicKey0）放在一起。就像在上图中看到的，这些字段在它们各在的矩形线框中，表示一个未签名的交易。每个交易都包含一个后向的交易哈希链，以及一个签名，但由于这是哈希链中的第一个交易，这些字段都是空的（阴影字段Transaction0）。 
 
顶上的每个交易都是一个唯一的交易哈希值，这个哈希值是通过软件用SHA-256哈希算法把所有交易字段（交易哈希值，数字资产ID，可选数据，公钥及签名）结合在一起计算出来的。而这个计算出的哈希值，就是用于下一个交易的DigitalAssetID0的后向链接。 
 
当Alice的经理，Bob，想要收购Alice的红酒时，Bob用他的客户端软件生成一个新的公钥-私钥对，用于交易。Bob也可以跳过这个步骤，而是把他的所有数字资产聚合在单个之前用过的公钥下，但是这将让他暴露于危险之中。所以，他需要生成一个新的公钥-私钥对，交给Alice一个他从来没用过的公钥。这样的话，如果他以前丢过配对的私钥，那么他只会丢失单个数字资产。 
 
在响应Bob的请求的回复中，Alice启动她的客户端软件并浏览她的数字资产。她选择了关联到那瓶Bob想要的红酒的交易ID，然后用Bob的公钥初始化这个交易请求，这个公钥同时也是交易的目标地址。此客户端结点随即创建一个新的交易（Transaction1），其中包含
 
前一个交易哈希（TransactionHash0）的后向链接值
用于那瓶红酒的数字资产ID的值（DigitalAssetID0），这个值与用于数字资产ID的ransaction0相同。
交易相关的任意自定义字段的值（OptionalData1） 
Bob的公钥的值（PublicKey1）
 
目前为止，这个客户端结点为Bob创建一个未签名的新交易Transaction1，下一步是用Alice的私钥签名这个交易。这一步很重要，Alice现在拥有数字资产，所有只有她可以转移这个数字资产给Bob。
 
椭圆曲线加密算法（Elliptic Curve Cryptography）
 
在上图中，标签 1 和 标签 2 表示交易在哪里签名和验证。相应地，在这个版本中，比特币区块链利用公钥加密算法（PKC）的一种实现，调用椭圆曲线加密算法（ECC）。ECC 提供了更强的加密结果，并且比流行的RSA/Diffie-Hellman更短的密钥值。区块链结点使用 ECC 生成非对称的密钥对，生成的过程引用了一个在二维图表中随机选择点位的公式。这个模式允许一个丢失的公钥可以从私钥重新生成（但是当然，不允许从一个公钥重新生成一个丢失的私钥）。 
 
比特币之后的区块链模型在数字签名时也使用了 ECC，不像上一文中提到的简化的PKC RSA(Rivest-Shamir-Adelamn)算法，比特币现在使用椭圆曲线数字签名算法（ECDSA）做交易签名，（准确的说是带有 ECDSA 的SHA-256算法）。这个算法与其他签名技术稍有不同：在 ECDSA 中，你必须把签名者的私钥与要签名的消息一起传给函数，这个函数使用ECDSA签名生成算法创建一个签名（在上图中用1表示）。要在后面验证签名，你必须把签名者的公钥，消息体，以及签名传给函数，这个函数使用 ECDSA 验证算法生成一个 true 或 false 值，表示签名是否有效（在上图中用2表示）。 
 
下图总结了使用 ECDSA 签名和验证的过程： 
  
 图注：上面的是ECDSA生成签名，下面的是验证算法。 
 
在上一文章中，当用 PKC-RSA 算法创建了数字签名时，通过计算哈希值来验证这个签名。出于好奇心，那个签名验证策略用 ECDSA 是不行的。PKC-RSA 算法 是一个确定性的数字签名算法，因为用一个给定的私钥给一个消息做签名每次会生成同样的签名。而 ECDSA 算法，是非确定性的：也就是说，每次你传一个消息和一个私钥给 ECDSA 签名函数，你都会获得不同的签名。具体可以参考 bit.ly/2MCTuwl。 
 
继续这个例子，Alice 将要签名这笔把DigitalAsset0的所有权转移给Bob的交易，客户端结点把Alice的私钥（PrivateKey0）和消息（NewTransactionHash1）传给 ECDSA 签名生成算法函数，并获取一个签名作为输出值（Signature1）。这个客户端结点把签名值添加到新交易的签名字段中。最后，客户端结点计算交易的哈希值（TransactionHash1），这个值是所有交易字段计算出的SHA-256哈希值，包括签名。此时，客户端结点成功地生成了签名的交易，这就可以发送到交易池中了。 
 
一个签了名的交易，直到它被一个矿工结点验证之前都被认为是未验证的。当一个矿工结点尝试验证Bob的交易时，矿工使用交易哈希的后向链接到前一个交易的公钥上，即指向Alice的Transaction0。一旦客户端结点访问了前一个交易，它会把那个交易的公钥（PublicKey0）和新交易的哈希（NewTransactionHash1），以及Bob的交易的签名（Signature1）一起传给 ECDSA 验证算法，然后返回true或false，表示签名是否有效。 
 
顺便说一下，Alice 的私钥（PrivateKey0）以及新的交易哈希（NewTransactionHash1）没有保存在这个交易中。私钥值不应该保存在区块链中，而且也不需要保存新的交易哈希，因为它可以在需要时重新计算。 
 
当 Bob 接了 Charlie 的电话时，Bob正在 用他的开瓶器，准备享受这瓶红酒，Charlie 是 Alice另一个餐厅的经理。Charlie 想要一瓶特别的酒来招待新员工，Bob 遗憾地同意把这瓶红酒转交给Charlie。Bob 向 Charlie 索取了公钥，然后用同样的流程把 DigitalAsset0 的所有权从Bob 转移给了 Charlie。 
 
现在 DigitalAsset0 就有了3笔交易，分别是这3个人的，每次交易都被验证并合并进了区块链。在一定数量的额外区块被矿工挖出到包含这个交易的区块顶上之后，这个交易就被认为是确认了的（确认数视实现情况不同）。这样的话，某个数字资产的官方拥有者永远是那个有私钥的人，这个私钥用于这个数字资产的交易哈希链中最近一次确认的交易。 
 
“共识”的需要
 
你已经看到了，交易哈希链是一种致力于强制数字资产所有权的数据结构。但是要明白，这些交易保存在一个分布式的，去中心化的，异步的，易受攻击的公网上，并且暴露给其他不需要诚实的区块链协议规则的结点（也叫做“bad actors”）。这样的结果是bad-actor结点可以验证那些实际上无效的交易，或者还会破坏区块链的完整性。 
 
交易池（Transaction Pool）
 
用于防止这些交易完整性问题，所有的交易需要通过一个验证和确认的流程，每一笔交易由网络中的单个结点创建。比如，假设Alice在墨西哥而Bob在美国，当Alice她的数字资产的所有权转移给Bob时，墨西哥的结点就创建了交易Transaction1，然后广播给网络上的其他结点。同时，其他结点也广播他们自己创建的交易到网络中。这些广播到全球网络上其他结点的过程依赖于网络延迟。不考虑这笔交易最初在全球网络中的哪个结点上，区块链协议把所有新交易放进未验证交易的交易池中。 
 
PoW 与 PoS
 
在区块链中，为了获取奖励 PoW，矿工结点积极从交易池中选择交易，理所当然地，矿工结点在构建一个候选区块时会验证每个交易，因为一个区块如果包含有任何坏的交易，则会立即被其他结点拒绝，这也意味着这个结点的工作是无价值的了。 
 
回想上一文中提到的，每个结点都在竞相找到一nonce（随机数），这个nonce（随机数）结点创建的用于候选的区块，这样才能赚取财务上的奖励，然后恢复做 PoW 时消耗的能源。之前比特币区块链的奖励是12.5 btc，价值10万刀。有时财务上的奖励是一笔交易费，有时是btc外加交易费。理解 PoW 的重点是结点必须花费能源和消耗设备及基础设施成本，以达到持续挖区块的矿的目的。要想有一个可持续的（负担得起的）结点，这些成本必须能被收益抵消。 
 
这也难怪矿工找到一个 nonce（随机数）后，就立即广播这个区块给网络上的其他结点，寄期望于它被添加到区块链的末尾。比特币区块链会调整其 nonce 的难度，使得大概每10分钟发现一个新的 nonce，所以慢一秒就有可能有其他矿工找到 nonce 并广播出去成为候选区块。 
 
由于输掉矿工竞争的实现机制，考虑下不能及时找到 nonce 的矿工结点，所有花费的能源都被浪费了。没有找到 nonce 的矿工没有选择，但是也不能停止处理当前区块并重新开始获取和验证交易池中的其他交易。原因是它们必须在得知其他矿工已经找到 nonce，且这个 nonce 是候选区块，这个区块已经有一个后向链接指向区块链中的上一个区块的哈希时迅速停止挖矿。当另一个矿工挖到一个验证过的指向前一个区块的区块时，输掉的矿工必须也放弃这个它之前选择的交易，再从交易池中选择一个新的交易，因为其他结点会拒绝任何包含了已经含有前一个区块的新区块。 
 
结点必须能承受支撑挖矿设备的所有成本。因为比特币区块链还在成长中，这就导致了另一种竞争：挖矿设备算力的竞争。算力越强的矿工结点，就越有可能在10分钟内解决加密算法问题，并找到一个 nonce。 
 
常见的对于 PoW 的批评是，它鼓励构建计算中心并使用增长的电力。一个有竞争力的edge会被分给 PoW 支持的区块链 网络上算力最强的计算设备的拥有者。比如，几百万美元的数据中心现在用于挖比特币的矿。根据 digiconomist.net 的数据，比特币每年的区块链能源消耗是71.12 TWh（截止2018年6月），这相当于智利每年的能源消耗量。 
 
另一个被广泛讨论的共识算法是 PoS（Proof-of-Stake）,这个算法奖励那些证明网络中的经济权益的结点。可以认证的是，PoS 的最大吸引力是更节能。而且，它不会给挖到区块的矿工给予加密货币奖励，虽然也给予交易费作为奖励。另外，PoS 也需要竞争去找到解决加密算法难题的 nonce。不像 PoW，基于加密货币单位的总价值和年龄，PoS网络随机地选择一个将自己注册为“铁匠”的结点（区别于比特比的“矿工”）。各种实现的细节都致力于强制保证选择铁匠的随机性和公平性。如果一个铁匠被选择了，那么30天内它就不能参与其他轮的打铁工作。更有效的是，包含最老的加密货币的高价值的铁匠结点，拥有其他铁匠结点的edge。 
 PoS 的支持者利用更节能的优点，鼓励更多的参与者以及更高层面的去中心化。讽刺地是，PoS 系统不鼓励使用区块链设计地用于交易的加密货币，因为花费会减少结点的总价值，并且会减少被选择成为铁匠工的机会。 
 
有一件需要考虑的事情是：区块链专家Anders Antonopoulos 指出：“PoW 也是一种 PoS，但是 PoS 不是 PoW”。他解释说：PoW 提供的一种这两种共识算法的联合，矿工参与的 PoW 网络中，选择矿工不是基于加密货币单位的年龄值，而是矿工结点通过提供所需要的能源来参与，以有效地发挥经济投资。这样的话，PoW中的 “Stake” 模式，就是结点的电力成本，会引发成功挖到一个区块。源自：https://bit.ly/2MDfkA1 
 
最长链（Longest Chain）
 
区块链网络在持续扩展，分支和并剪枝，区块链的整个视图叫做 “区块树”，每个矿工结点的挖矿会让区块树的最长链更长。你可以认为最长链就是最多区块的区块，但是实际上这个序列定义是从最初的产生最多工作量的区块来的。你可以认为这个工作量是每个区块的持之以挖矿难度（衡量发现一个作为候选区块的nonce的难度）。网络协议维护这个值，而比特币区块链调整为每2016个区块可以发现一个nonce，这样差不多每10分钟可以处理一个。这个难度值保存在每个区块中，使得工作量可以由试图识别最长链的结点来计算。 
 
有时，不可避免地会有两个结点 A 和 B，会在几秒甚至几毫秒的差距通过挖矿证明 PoW。 因为每个结点在广播区块到网络之前，会添加它的新区块到它能看见的最长链尾部，“区块树”中就会出现一个分支。取决于结处于网络中的位置以及连接的结点的宽度，树中的有些部分会先发现 区块A 作为新的区块，并添加到链的尾部。网络中的其他部分会先发现区块B 作为新的区块，并添加到链的尾部。这就导致有些结点带着 区块A，有些带着 区块B 作为末尾结点。如下图： 
 
 
当发生分支时，如上图的上面部分时，两个链都在区块树上，它们长度相等，而且都有效。此图表示的问题是：当矿工结点在挖矿前寻找最长链，因为矿工需要知道链的末尾区块的哈希值。 
 
如果矿工成功挖到 区块C，并且工作于 区块A，它会把 区块C 添加到 区块A 的后面，作为末尾区块。一旦这么做了，这就会广播 区块C 到网络中，然后其他结点会发现 区块A 是最长链，而工作在 区块B 上的结点会发现 区块A 比 区块B 更长，会停止挖矿，开始挖新的矿来延续 区块C。这样一来，网络便会释放所有 区块B 的交易，并把区块B 返回到交易池，这样他会被新一轮挖矿。 
 
你可能想知道：如果矿工已经赚取了挖到 区块B 所得到的比特币会发生什么？交易委员会和区块奖励其实不会颁发奖励。在比特币网络中，这些奖励不会在这个被挖到的区块处于100个区块之上时就颁发给矿工。 

NA公链NAC公链挖矿
 引言：在刚刚过去的2020年，“数字化”三个字在年度热词榜单里占据了绝对重要的位置。其实早在互联网出现的那一刻起，我们就已经进入数字化阶段，而互联网在近几年的突破性发展，才让“数字化”开始了新的阶段，区块链的发展就是其代表之一。
 人类社会的信息系统由单机状态转变为中心化组织状态，如今再次进入到了新的去中心化时代。高度开放式的信息结构和节点分布让数据的储存、流转变得透明，让信息的真实性变得有保证，同时也让隐私开始无处可逃。为了弥补开放系统带来的隐私泄露问题，区块链行业目前主要有零知识证明、环签名、混币、同态加密和安全多方计算五种信息加密技术。
 今天，我们将通过浅析Nirvana所采用的Zk-SNARK零知识证明以及环签名两种加密方式，来探究不同加密技术混合使用的现实可操作性。
 零知识证明：Nirvana提出一种基于zkSNARK算法的跨链交易隐私保护，打造跨链交易信息的保护伞
 【Nirvana提出采用零知识证明Zk-SNARK，根据跨链交易的特殊性，提出新的跨链交易隐私保护方法，既能够实现跨链又能保障跨链资产的安全性和隐私性的解决方案。】
 随着对数据信息安全的日益重视，隐私保护在区块链行业里越发重要，而在隐私保护的种种手段中，zk-SNARK零知识证明算法代表了一种简洁的非交互式零知识证明，是一种比较成熟和可行的隐私保护技术之一，因为具有更好的匿名性，它不需要信任中央节点或网络中其他用户的参与。用户可以通过与匿名货币进行交互来实现匿名交易， 从而有效地保护了用户的隐私，作为先进隐私保护技术被用于区块链的支付系统，故在此基础之上Nirvana提出了一种基于zkSNARK算法的跨链交易隐私保护方法。
 通俗来讲，零知识证明就是既证明了自己想证明的事情，同时透露给验证者的信息为“零”。在现在的区块链交易中，一般用地址来表示双方，以达到匿名的目的，但是在整个交易过程中，有一部分信息依然是可以被追溯，这也使得匿名性荡然无存。而零知识证明正是为了解决这一问题而出现的技术，利用零知识证明，可以将交易双方的交易细节隐藏起来。
 跨链连接链作为转发和验证跨链匿名交易的载体，需要有能够验证跨链匿名交易有效性的方式。Nirvana发现，互联链网络中的验证节点可以根据并行区块链注册的验证规则来验证交易的有效性，同时互联网网络中的验证节点需要了解在每个并行区块链网络启动阶段生成的公共参数，并使用这些公共参数来验证跨链匿名交易的有效性。这即为Nirvana提出的一种基于零知识证明Zk-SNARK算法的跨链交易隐私保护法。
 环签名：Nirvana提出为了数字资产的匿名性，采用一次性环签名技术，Nirvana网络维护着所有不完整密钥映像的数据库，而用户的真实隐藏地址P仅能使用一次
 
 
【Nirvana环签名通过允许事务的发起者加入组，然后将事务作为一个单元加入，而不是从单个私钥签名中分配私密性。此技术允许发起者进行混合。验证者可以证明输出存在，并且组的成员之一是真正的签名者。】
 如果零知识证明解决的问题是“我有一个答案，我需要向你证明我知道这个答案，但是我不能让你知道这个答案。”那么环签名解决的问题就是“我对你说了一句话，但你只知道这个组中的某个人对你说了这句话，而你不知道是组中哪个人说了这句话。”
 环签名技术思想，最早可以追溯到十七世纪的法国，现代环签名( Ring Signature ) 方案则在2001年由Rivest、Shamir 和 Tauman 这三位密码学家提出。环签名方案去掉了群组管理员，不需要环成员之间的合作，签名者利用自己的私钥和集合中其他成员的公钥就能独立的进行签名。作为隐私保护的补充方式，环签名的优势除了能够对签名者进行无条件的匿名外，环中的其他成员也不能伪造真实签名者签名。
 Nirvana使用了一次性的环签名技术。验证者可以证明输出存在，并且组的成员之一是真正的签名者。但是，由于每个成员具有相等的概率权重，因此他们无法确定签名者是哪个组成员。随着组规模的增加，每个成员成为真实签名者的可能性降低。
 同时，为了防止双花问题的出现，Nirvana在每次资产交易中都具备了唯一的关键图像，例如可以为相同的公钥创造相同的key image这种操作方式。在资产交易中，系统中所有的节点会维护一个已见到过所有的key image集合，如果⼀笔交易的Key Image出现在该集合中，则被认为是⽆效的。Nirvana正是通过获取隐藏地址P的哈希值，并将其乘以私钥来创建密钥镜像，创造不同的事务。这种机制能确保每个P都能只能使用一次，如果用户尝试重用密钥，则网络将会拒绝交易，确保其唯一性。
 三、写在结尾
 毫不夸张地说，如今的我们完全已经进入了数字经济时代，区块链公链的发展会迎来更多的观察者，这也就决定了它必须在架构、效率、安全等多方面升级到更高的标准，才足以满足潜在客户的需求。区块链作为一个数据高透明度、高开放性的底层技术，透明与隐私两者之间似乎生来就矛盾重重，但随着环签名、零知识证明等加密技术的发展，这两种区块链特质也开始变得周全。
 隐私保护作为一种新的行业生态，其有效性和可操作性是构建完整区块链世界观必须发展开拓的技术方向，也是未来衡量一条公链成熟程度的重要指标。
 

公链，顾名思义就是公有，它是指对全世界所有人开放的，任何人都可以读取数据、发送交易且交易能够获得有效确认的共识区块链。
 
联盟链是指由多个机构共同参与管理的区块链，每个组织或机构管理一个或多个节点，其数据只允许系统内不同的机构进行读写和发送。
 
公链和联盟链，作为区块链江湖中的两大帮派，了解它们两者之间的差异以及各自适用的场景是每个关心区块链的用户必学的入门知识。
 
11月1号晚20：00，博士大爆炸第2期暨BlockMania AMA 第24期，清华大学博士、Trias首席算法科学家胡志琳做客直播间，详细介绍了公链和联盟链的异同，深入解读公链与联盟链互通以及如何保障互通安全性。
 
 
 
以下为AMA全程回顾
 
什么是公链、什么是联盟链？从技术和场景应用上有什么不同？
 
公有链是完全去中心化的一种区块链。任何人既可以进行交易也可以读取信息。任何人都可以参与链上的交易确认和共识机制。各个节点可以随时加入节点也可以随时退出节点。
 
 
公有链的特点是：
 
 
 
1）访问门槛低
 
 
只要你有计算机，只要计算机能联网，都能够访问。
 
 
2）数据公开透明且无法篡改
 
 
公有链是高度去中心化的分布式账本，每个人在任何节点的行为都是可以查看的，而且基于庞大的用户体系，想要篡改交易数据，几乎不可能实现。
 
 
3）匿名性
 
 
由于节点之间无需彼此信任，所有的操作都可以匿名进行，很好地保护使用者的隐私。
 
 
4）免受开发者影响
 
 
公有链数据的读写是不受任何人控制和篡改的，就连程序开发者也无权干涉用户。所以，极大程度上保护了用户免于程序开发者的影响。
 
 
公有链也有一定缺点，比如交易速度慢。支付宝转账可以即时到账，但公链上由于确保交易信息真实性的原因需要6个区块确认时间(比特币为例)确认该交易真实方可成效，在这一过程会影响交易速度。
 
联盟链则是指由多个机构共同参与管理的区块链，每个组织或机构管理一个或多个节点，其数据只允许系统内不同的机构进行读写和发送。
 
 
联盟链的各个节点通常有与之对应的实体机构组织，通过授权后才能加入与退出网络。各机构组织组成利益相关的联盟，共同维护区块链的健康运转。
 
联盟链的特点是：
 
 
 
1）权限设计要求更复杂，可信度更高。
 
 
2）比公有链处理速度要快，因为节点的数量和身份都已经规定好了，所以可以使用相对松散的共识机制，因此数据的处理速度就会比公有链大大提高。
 
 
3）尽管联盟链速度加快，但相比公有链来说联盟链并不是完全去中心化的。因为理论上联盟之间可以联合起来修改区块链数据。由于节点少，如果权限设计不周则容易出现权力集中和安全问题。
 
 
联盟链和公链的应用场景不同。公有链适用于对可信度、安全性有很高要求，而对交易速度要求不高的场景。联盟链更适合对隐私保护、交易速度和内部监管等具有很高要求的应用，比如适合组织机构间的交易和结算，应用代表有超级账本(Hyperledger)。
 
 
 
 
有一种观点是，联盟链是公链的未完全进化版本，您觉得联盟链和公链是否能共存？是否有了公链就不再需要联盟链了？
 
人们往往都把区块链与大数据、云计算、AI放在一块，来讲述新技术对于经济的促进作用。但目前区块链爆发的能量，展现出来的能力，跟其他三个还没法比。
 
究其原因，承载区块链应用的公链和联盟链存在很大限制。公链的性能、数据安全与隐私保护、可扩展性、智能合约等都还远谈不上成熟，还无法承载互联网上主流的商业活动。现在的记账技术隐私性还没法完全保证商业机密不被泄露，导致上链隐忧仍存。
 
联盟链曾百花齐放，比起公有链，需要在安全、隐私、性能、应用型、可靠性等方面进行针对性的打磨和加强。比如说安全方面，银行作为国家的法定交易所、金融机构以及有价值数据的机构，不可能把数据、隐私、财务信息全部放在公有的环境上。
 
但目前为止，联盟链技术还是着力于核心与协议层面的技术发展，作为一种综合解决方案仍显不足，在技术定型与落地上都还存在非常多的掣肘。对作为基础设施的联盟链技术，还没有一个得到同行业公认的测评标准，且各行业对区块链技术在功能与性能上也无清晰需求。
 
不同业态的多样化业务需求对联盟链的通用性提出了极高要求，既存的“模板”都有被“作废”的可能。另外，如何从底层设计上平衡联盟链中的各方利益及话语权，践行权力分配与管理也是一大难题。
 
因此，基于目前的区块链发展状况，公有链和联盟链会在相当长的一段时间内并存，并不存在谁取代谁，谁更有优势的问题，但总的来说，谁解决了需求谁就是有价值的。
 
从技术上来看，联盟链将公有链项目的技术设计吸收进来，联盟链的技术和软件工程思想，又给公有链技术予以启发和由此诞生了如分片处理和状态通道的策略技术。二者是互相促进，并肩前行的。
 
从行业视角来看，公链和联盟链从原先的技术差别，逐渐延伸到应用阵营的区隔。公链囿于其难以攻克的技术难题和应用场景的极大局限，一直脱不开“币”的影子，目前还在充当极客的新世界期望和投机客暴富梦想的载体。而联盟链则凭借效率和技术难度的高性价比，被贴上了产业价值的标签，成为区块链落地应用底层技术的首选，商业化进程也更为明朗。
 
以太坊 V 神曾将公链的希望寄托于“未来的经济危机”，而联盟链项目却有机会被深入和落地，很大原因在于现在很多商业领域的土壤会更适合联盟链落地和生长。因为有联盟链的存在，反而更能促进区块链技术的发展，有人说公链和联盟链未来会融为一体，那么联盟链就是公链落地的另一种方法，也是区块链技术的希望所在。
 
我听说Trias在公链和联盟链的融合上做出深入的尝试。为何要实现联盟链与公链的互通？互通的必要性和意义又在哪？
 
Trias认为，公链与联盟链的融合是大方向。
 
公链和联盟链都有各自的优势，又各有各的桎梏，未来公链和联盟链会进一步融合，即在公链基础上架设联盟链，把二者的优势进行互补。
 
不论对于公有链还是联盟链来看，互通互联是实现价值互联网的关键。区块链不缺链，缺的是对产业的技术支撑和落地。区块链非常需要跨链的技术，它是把区块链从分散的孤岛中拯救出来的良药，是区块链向外拓展和连接的桥梁。
 
Trias定位于做区块链一站式服务平台，给各个公链提供跨链技术，它致力于降低跨链成本和难度。区块链是价值网络空间的核心基础设施，区块链应用不应该只局限于和止步于联盟链的应用，将价值圈在一个小范围中，人们需要链间的互通技术，对不同区块链进行连接和扩展，构建价值网络的高速公路。
 
Trias 在Leviatom -1可信层公链基础上搭建联盟链，联盟链不需要再各自建各自的链，提供信任服务。而是把经过验证、经过博弈考验的信任服务放在基础公链上，在基础公链上搭建各自联盟链。
 
各自联盟链上面可能有一些私有的数据，私有的部署。而公链上面是非私有的数据，是脱了敏的数据，而且数据主要用于存证和基础的信任服务。这样，把公链与联盟链进行融合，可以实现更加复杂的商业逻辑。
 
具体来说，Trias Leviatom-1层的意义就是把机器可信和数据（账本）可信分开，实现了机器可信，所有机器可以联通，像是互联网上的一层新的可信协议。在此基础上，再建各自独立的数据域（账本）。用-1层实现对账本可靠性的保障（每个账本不需要太多节点来对抗 51攻击，这个交给了 -1层，它有很多节点，而且能对抗90攻击），同时用-1层实现账本之间的数据交换。
 
基于我们-1层链实现的区块链云设施的生态服务，本质上是一个链接云/数据中心/边缘计算/PC/物联网设备的区块链，用于跑分布式账本/智能合约平台/企业级应用/其它SaaS，这些统称为DSaaS。
 
Trias公链链接的联盟链可以解决三个问题：
 
 
 
（1）联盟链在公链网络上的一键复制，实现联盟链项目快速实施交付甚至是无代码交付，这时联盟链本身就是我们公链的DSaaS。例如1）一键发以太坊/fabric；2）-1层链接的是一个跨云基础设施，让这个以太/fabric跑在多云上，从而消除这个区块链底层云平台的中心化。
 
 
（2）联盟链数据冗余成本问题。若用公链来实现对联盟链安全性的增强，那么联盟链的设计实现可以更简化，用更小的成本（比如更少的共识节点数，数据冗余度）来达到同等安全强度；
 
 
同时这个问题衍生到联盟链安全能力输出的问题。公有云的诞生来自于服务器集群空余计算/存储能力的对外出租，一个大型联盟链或许也能为其它联盟链输出闲散的安全能力。这也就是为什么联盟链的底层（-1层）可以链入外界公链。
 
 
（3）让联盟链之间相互验证对方联盟链的安全，实现数据互换。
 
 
现在我们可以直接支持原生的以太坊应用，因为我们上面跑了一个以太坊，然后应用是不用变的，甚至其实更理想状况是每个应用它可以根据自己的需要修改以太坊，然后让以太坊这个账本更好为他服务。
 
在这种情况下，对于传统的如果现在任何一个开发者他都可以去跑一个以太坊，那他要解决的问题是如何向他的用户证明他的以太坊没有被别人攻击。这个是很难的，因为他如果要有一个私有以太坊的话，他按照以太坊的方式，他可能得跑2000个节点，来才能让以太坊抵御有足够强大的抵御攻击的能力。因为还是这样，每个以太网节点都有可能撒谎。 
 
现在的情况是有的项目已经开发了以太坊或者是开发了hyperledger，我们希望他们的以太坊和hyperledger在我们的链上都能直接不用做修改的跑起来，并且更快而且更安全。
 
其实另外一个优势是更省钱，因为他不用依赖太多节点的以太坊，或者是不用依赖太多的hyperledger节点，因为底下我们有一个可信的网络。而且当节点减少的时候，它共识肯定是更快的。而且这个优势就不单指节点的算力本身，更主要是对企业来说，可能更重视这些，因为他会更安全。 
 
 
将公链和联盟链互通，让它们的优势得以互补的这套技术听上去非常酷！但是要如何才能确保这种互通的安全性呢？
 
Trias将可信技术与跨链技术相结合，实现公链到联盟链之间的可信链接，以此为这种互通的安全性做保障。我们从三个层次出发，来具体构建公链到联盟链之间链接的可信性：
 
（1）网络节点的可信远程证实
 
负一层的公链在联盟链的底下，在共识之前，先对对方的节点进行可信判断。其实区块链的共识协议就是一个我们双方通过问问题来判断对方真实实力的一个过程，也其实有另外一个办法可以让我们更好地判断对方的真实实力，或者是真实的想法，就像装了一台测谎仪，如果有恶意程序，马上测谎仪就亮了，所以基于可信节点的公链就不用那么复杂的共识协议。 
 
其实白名单技术能解决节点上的认证问题是这个技术里面的核心，也是最强的地方。当所有的链第一时间内排除恶意节点，让所有的链在共识的时候，我们保证参与共识的节点基本上都是对的节点，理论上来说所有人都是对的话，大家任何一个人说的话都是真话，就不用那么复杂的事情，但我们也不会完全相信所有东西都是可靠的，至少我们可以极大程度的降低共识的难度，我们用这个方法让其他链跑得更快，并且同时更安全。 
 
可信计算（Trusted Computing）是在计算和通信系统中广泛使用基于硬件安全模块支持下的可信计算平台。
 
通过建立一种特定的完整性度量机制，使计算平台运行时具备分辨可信程序代码与不可信程序代码的能力。可信计算组织(TCG，Trusted Computing Group)将可信定义为:一个实体是可信的，如果它的行为总是以预期的方式朝着预期的目标。TCG的可信计算技术通过在硬件平台上引入可信平台模块(TPM，Trusted Platform Module)来提升计算机系统的安全性。可信计算技术依赖于内嵌在平台上的协处理器TPM。TPM至少需要具备四个主要功能：对称/非对称加密、安全存储、完整性度量和签名认证。数据的非对称加密和签名认证是通过RSA算法来实现的，而完整性度量则是通过高效的SHA-1散列算法来完成，对称加密可以使用任意算法，既可以使用专用协处理器也可以使用软件来完成。
 
可信计算的主要思路是首先基于安全芯片建立终端平台信任，然后通过远程证明建立平台间的信任，最后将信任延伸到网络。远程证明是一个综合完整性校验和身份认证的过程，向验证者提供了一份可信的平台状态报告。远程证实模块主要用于统一管理所有节点的证实关系以及白名单，协助前端展示各主机的可信状态等功能。
 
主要功能包括：
 
 
 
1.白名单管理
 
 
支持主机白名单的生成、查询、更新、删除等操作，通过分析运维策略自动生成白名单，可以配置不同的可信策略更新白名单，并可以通过主机ip，文件hash等方式查询白名单。
 
 
2.证实管理
 
 
控制主机之间互相证实，支持主机可信状态查询，启动证实，停止证实操作。
 
 
3.监控报警
 
 
在证实过程中，一旦发现有主机可信状态异常，能够在秒级内感知，并发出报警。
 
 
（2）网络间的可信跨域
 
「可信计算组织」 (Trusted Computing Group，TCG)的前身为「可信计算平台联盟」 (Trusted Computing Platform Alliance，TCPA)，重组为TCG后加强了对软件安全性的关注，可信计算研究进入了发展的新高潮。2004年5月，TCG成立了可信网络连接分组(Trusted Network Connectionsub Group，TNC-SG)，相继研究和制定了可信网络连接(Trusted Network Connection，TNC)的架构和相关规范标准。
 
基于TNC基础架构，根据高可信网络对信息交互和共享更高的要求，设计了跨域远程双向认证与接入控制协议流程，有效地实现了远程双向认证与跨域接入控制。并在此基础上设计了跨域认证和授权管理系统，实现了跨安全管理域的统一身份认证，可有效地支持跨域授权管理，全面提升高可信网络信息系统的数据安全防护和安全共享能力，实现可信网络跨域环境下信息资源的高效共享。
 
跨域认证采用双向身份认证，既要保证网络的安全，也要保证终端能接入到一个可信的网络中。在实施过程中采用了CAP—TTLS协议实现双向身份认证，在TLS隧道建立阶段通过验证服务器提供的证书，证明了网络的可信性，确保终端接入到一个可信的网络中。在随后的TLS隧道内认证终端的身份并度量平台完整性，确保了终端的合法性。TLS隧道的会话密钥是在TLS建立阶段由会话双方协商出来的，只有会话双方可以获得，使用该密钥加密的消息不可能被第三方获得，从而保证隧道内进行的身份验证和平台完整性度量过程的安全性。基于隧道的保护，内层的身份认证方法和平台度量在安全方面的考虑就较少了，以传递认证过程中的数据交换为主，尽可能减少协议复杂性和传输开销。
 
（3）跨链
 
链接我们现在有设计，但还没有实现。这部分和传统区块链的跨链技术密切相关。现在仍然在不断完善的Cosmos和波卡跨链技术，都是我们的参考，例如以下跨链技术：
 
公证人机制（Notary schemes）: 公证人也称见证人机制，公证人机制本质上是一种中介的方式。具体而言，假设区块链A和B本身是不能直接进行互操作的，那么他们可以引入一个共同信任的第三方作为中介，由这个共同信任的中介进行跨链消息的验证和转发。公证人机制的优点在于能够灵活地支持各种不同结构的区块链（前提是公证人能够访问相关方的链上信息），缺点在于存在中心化风险。
 
哈希锁定（Hash-locking）: 哈希锁定技术主要是支持跨链中的原子资产交换，最早起源自比特币的闪电网络。其典型实现是哈希时间锁定合约HTLC(Hashed TimeLock Contract)。哈希锁定的原理是通过时间差和隐藏哈希值来达到资产的原子交换。哈希锁定只能做到交换而不能做到资产或者信息的转移，因此其使用场景有限。
 
侧链/中继链（Sidechains / Relays）: 侧链是指完全拥有某链的功能的另一条区块链，侧链读取和验证主链上的信息。主链不知道侧链的存在，由侧链主动感知主链信息并进行相应的动作。而中继链则是侧链和公证人机制的结合体，中继链具有访问需要和验证进行互操作的链的关键信息并对两条链的跨链消息进行转移。从这个角度看中继链也是一种去中心的公证人机制。
 
同时我们也会精心设计-1层的，通过提供网络节点可信以及网络间的可信跨域，来努力简化和支持在公链生态下广大开发者所贡献的更好的跨链技术，这个也是所有区块链研发者共同需要攻克的难题。这里讲一下其中的一个设计思路供大家参考：各条联盟链之间的资产转移可以通过链上SPV智能合约进行。同时各条联盟链还互相引用彼此的默尔克树，这大大降低了攻击成功的可能性。通过Merkle roots 共享信息实现跨链共识，连接多条联盟链分担计算负载。
 
在链接公链和联盟链的技术研发中，每一个细节都是需要深入研究的技术点，因为涉及到密码学、安全分析证明等难题，故在这个技术方向上充满了需要时间去打磨的挑战性前言技术课题。我们会首先明确方向，循序渐进的深入研究，号召更多优秀的开发者参与到我们的公链中来，一起解决这些有难度的前沿问题。
 
在下一步的工作中，我们将针对完整性度量机制基于静态完整性、缺乏动态度量的现状，提出较为完整的系统度量模型，深入研究动态度量技术。我们还会继续跟踪目前业界尚不成熟的跨链技术，持续深入研究如何实现用可信技术来优化传统的跨链技术，研究如何在链接公链和联盟上解决各种工程问题。
 
 
 
 
 
BlockMania还将上线更多AMA交流与问答活动，邀请加密行业内各专家一同对话，欢迎把您的问题、建议及意见通过公众号留言给我们，感谢您的关注！
 
 
 
 
 
 
国际区块链咨询和智库
 
 
长按二维码关注
 
以服务区块链发展为己任
 
专业视野洞悉行业先机
 
独特视角深度融合
 
输出业内高品质推广服务

参考链接：数据结构（严蔚敏）
 文章发布很久了，具体细节已经不清晰了，不再回复各种问题
 文章整理自严蔚敏公开课视频
 可以参考
 https://www.bilibili.com/video/av22258871/
 如果链接失效 可以自行搜索 数据结构严蔚敏视频
 @2021/07/12
 
一、什么是Hash表
 
要想知道什么是哈希表，那得先了解哈希函数
 哈希函数
 
对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树，它们的查找都是先从根节点进行查找，从节点取出数据或索引与查找值进行比较。那么，有没有一种函数H，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就**“预先知道”**key所在的位置，直接找到数据，提升效率。
 即
 地址index=H（key）
 说白了，hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表
 
二、哈希函数的构造方法
 
根据前人经验，统计出如下几种常用hash函数的构造方法：
 直接定制法
 哈希函数为关键字的线性函数如 H（key）=a*key+b
 这种构造方法比较简便，均匀，但是有很大限制，仅限于地址大小=关键字集合的情况
 使用举例：
 假设需要统计中国人口的年龄分布，以10为最小单元。今年是2018年，那么10岁以内的分布在2008-2018，20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据，那么关键字应该是2018，2008，1998……
 那么可以构造哈希函数H（key）=（2018-key）/10=201-key/10
 那么hash表建立如下
 
index
key
年龄
人数（假设数据）
0
2018
 0-10
200W
1
2008
 10-20
250W
2
1998
 20-30
253W
3
1988
 30-40
300W
……
 
数字分析法
 假设关键字集合中的每个关键字key都是由s位数字组成（$k_1,k_2,\dots \dots ,k_n$）,分析key中的全体数据，并从中提取分布均匀的若干位或他们的组合构成全体
 
使用举例
 我们知道身份证号是有规律的，现在我们要存储一个班级学生的身份证号码，假设这个班级的学生都出生在同一个地区，同一年，那么他们的身份证的前面数位都是相同的，那么我们可以截取后面不同的几位存储，假设有5位不同，那么就用这五位代表地址。
 H（key）=key%100000
 此种方法通常用于数字位数较长的情况，必须数字存在一定规律，其必须知道数字的分布情况，比如上面的例子，我们事先知道这个班级的学生出生在同一年，同一个地区。
 平方取中法
 如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。
 使用举例
 比如key=1234 1234^2=1522756 取227作hash地址
 比如key=4321 4321^2=18671041 取671作hash地址
 这种方法适合事先不知道数据并且数据长度较小的情况
 折叠法
 如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址
 使用举例
 比如key=123 456 789
 我们可以存储在61524，取末三位，存在524的位置
 该方法适用于数字位数较多且事先不知道数据分布的情况
 除留余数法用的较多
 H（key）=key MOD p （p<=m m为表长）
 很明显，如何选取p是个关键问题。
 
使用举例
 比如我们存储3 6 9，那么p就不能取3
 因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
 p应为不大于m的质数或是不含20以下的质因子的合数，这样可以减少地址的重复（冲突）
 
比如key = 7，39，18，24，33，21时取表长m为9 p为7 那么存储如下
 
index
0
1
2
3
4
5
6
7
8
key
7
21（冲突后移）
24
*39*
18（冲突后移）
33冲突后移）
 **随机数法** H（key） =Random（key） 取关键字的随机函数值为它的散列地址 
hash函数设计的考虑因素
 
1.计算散列地址所需要的时间（即hash函数本身不要太复杂）
 2.关键字的长度
 3.表长
 4.关键字分布是否均匀，是否有规律可循
 5.设计的hash函数在满足以上条件的情况下尽量减少冲突
 
三、哈希冲突
 
即不同key值产生相同的地址，H（key1）=H（key2）
 比如我们上面说的存储3 6 9，p取3是
 3 MOD 3 == 6 MOD 3 == 9 MOD 3
 此时3 6 9都发生了hash冲突
 
哈希冲突的解决方案
 
不管hash函数设计的如何巧妙，总会有特殊的key导致hash冲突，特别是对动态查找表来说。
 hash函数解决冲突的方法有以下几个常用的方法
 1.开放定制法
 2.链地址法
 3.公共溢出区法
 建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
 4.再散列法
 准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个……
 重点了解一下开放定制法和链地址法
 
开放定制法
 
首先有一个H（key）的哈希函数
 如果H（key1）=H（keyi）
 那么keyi存储位置$H_i=(H(key)+d_i)MODm$m为表长
 $d_i$有三种取法
 1）线性探测再散列
 $d_i=c\ast i$
 2）平方探测再散列
 $d_i=1^2,-1^2,2^2,-2^2$……
 3）随机探测在散列（双探测再散列）
 $d_i$是一组伪随机数列
 注意
 增量di应该具有以下特点（完备性）：产生的Hi（地址）均不相同，且所产生的s（m-1）个Hi能覆盖hash表中的所有地址
 
平方探测时表长m必须为4j+3的质数（平方探测表长有限制）
随机探测时m和di没有公因子（随机探测di有限制）
 三种开放定址法解决冲突方案的例子
 
 
废话不多说，上例子就明白了
 有一组数据
 19 01 23 14 55 68 11 86 37要存储在表长11的数组中，其中H（key）=key MOD 11
 那么按照上面三种解决冲突的方法，存储过程如下：
 （表格解释：从前向后插入数据，如果插入位置已经占用，发生冲突，冲突的另起一行，计算地址，直到地址可用，后面冲突的继续向下另起一行。最终结果取最上面的数据（因为是最“占座”的数据））
 线性探测再散列
 我们取di=1，即冲突后存储在冲突后一个位置，如果仍然冲突继续向后
 
index
0
1
2
3
4
5
6
7
8
9
10
key
55
1
14
19
86
23冲突
23
68冲突
68冲突
68
11冲突
11冲突
11冲突
11冲突
11冲突
11
37冲突
37冲突
37
最终存储结果
55
1
23
14
68
11
37
19
86
 **平方探测再散列** 
index
0
1
2
3
4
5
6
7
8
9
10
key
55
1
14
37
19
86
23冲突
H（23）+1
H（68）-1冲突
68冲突
H（68）+1冲突
H（68）+4
11冲突
H（11）+1冲突
H（11）-1
最终存储结果
55
1
23
14
37
68
19
86
11
 **随机探测在散列（双探测再散列）** 发生冲突后 H（key）‘=(H(key)+di)MOD m 在该例子中 H（key）=key MOD 11 我们取di=key MOD 10 +1 则有如下结果： 
index
0
1
2
3
4
5
6
7
8
9
10
key
55
1
68
14
19
86
23冲突
H（23）+3+1
11冲突
H（11）+1+1冲突
H（11）+1+1+1+1
（H（37）+8）模11冲突
37冲突
（H（37）+8+8+8）模11
（H（37）+8+8）模11冲突
最终存储结果
55
1
68
14
23
11
37
19
86
 
链地址法
 
产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据
 上面的例子，用链地址法则是下面这样：
 

 四、hash表的查找
 
查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
 对于给定的key，计算hash地址index = H（key）
 如果数组arr【index】的值为空 则查找不成功
 如果数组arr【index】== key 则查找成功
 否则 使用冲突解决方法求下一个地址，直到arr【index】== key或者 arr【index】==null
 
hash表的查找效率
 
决定hash表查找的ASL因素：
 1）选用的hash函数
 2）选用的处理冲突的方法
 3）hash表的饱和度，装载因子 α=n/m(n表示实际装载数据长度 m为表长)
 一般情况，假设hash函数是均匀的，则在讨论ASL时可以不考虑它的因素
 hash表的ASL是处理冲突方法和装载因子的函数
 前人已经证明，查找成功时如下结果：
 

 可以看到无论哪个函数，装载因子越大，平均查找长度越大，那么装载因子α越小越好？也不是，就像100的表长只存一个数据，α是小了，但是空间利用率不高啊，这里就是时间空间的取舍问题了。通常情况下，认为α=0.75是时间空间综合利用效率最高的情况。
 
上面的这个表可是特别有用的。假设我现在有10个数据，想使用链地址法解决冲突，并要求平均查找长度<2
 那么有1+α/2 <2
 α<2
 即 n/m<2 (n=10)
 m>10/2
 m>5 即采用链地址法，使得平均查找长度< 2 那么m>5
 
之前我的博客讨论过各种树的平均查找长度，他们都是基于存储数据n的函数，而hash表不同，他是基于装载因子的函数，也就是说，当数据n增加时，我可以通过增加表长m，以维持装载因子不变，确保ASL不变。
 那么hash表的构造应该是这样的：
 

 五、hash表的删除
 
首先链地址法是可以直接删除元素的，但是开放定址法是不行的，拿前面的双探测再散列来说，假如我们删除了元素1，将其位置置空，那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据，比如-1