发表于

今天一早就收到一封关于 MongoDB 的邮件，MongoDB began trading as a public company on the NASDAQ under the symbol “MDB.”。是的，在经过长达 10 多年的开发应用后，MongoDB 终于登上了纳斯达克。作为一个 MongoDB 的忠实粉丝，除了为它感到骄傲之外，还想在此整理一下最近工作中在 MongoDB 上的一些想法和经验。此文也算是为 MongoDB
的推广献一份力量。

准备工作

关系型数据库已经统治数据存储长达三十几年的时间，即便在 2000 年以后诞生了 NoSQL 数据库，但他的出现并没有改变关系型数据的统治地位。随着最近几年互联网应用的快速崛起，以及互联网用户的不断增加，数据来源越来越复杂多样，传统关系型数据存储面临了很大的挑战。这种挑战体现在数据格式死板，改动困难，存储不够灵活，难于扩展等方面。因此，很多企业、公司都先后把数据从关系型迁移到 NoSQL 上来，其中 MongoDB 又是使用相对较广泛的数据库实现。本文就为大家分享一下关系型数据导入进 MongoDB
中应当遵循的步骤和注意的问题。

在考虑将关系型数据导入到 NoSQL 中时，首先需要确认的几点是：这个导入过程不会是全自动的，并不是像备份数据，迁移数据，记住几个命令那么简单；其次，这个过程不是一个纯技术问题，在制定具体方案时，项目经理，业务分析人员，开发人员，数据库管理员都应当参与到方案的讨论中。迁移的计划、技术方案、各个项目负责人的职责应当在全体人员在场的情况下制定清楚；最后，应当考虑到迁移失败以后的恢复方案，根据应用数据的复杂程度不同，迁移的工作量也不会完全一样。

上图列出了一个项目经过关系型数据向 NoSQL 中迁移的大致步骤，当然这绝对不是一个唯一的标准。只是通常情况下的做法，可能会根据不同项目的特别需求有一些调整。下面我们来详细分析每一个阶段的具体工作内容。

数据模型定义

有可能你会觉得奇怪，MongoDB 不是结构无关的 NoSQL 数据库吗？为什么我们要提到数据库表结构定义。实际上，NoSQL 中的结构是指从技术层面来讲，数据库对表结构没有强约束，任何格式的 JSON 都可以插入进 MongoDB 表中。但是，我们在做项目时不能为所欲为的在数据库中插入数据，一定要遵循我们自己定义的一套规则来进行，否则程序根本无法管理数据层面的业务逻辑。在讨论表结构之前，先来看一下 MongoDB 中的一些术语和关系型数据库的对应关系。

看起来很好理解，在 MongoDB 中我们把表称做Collection，表中每一行的数据称作Document。其他的基本沿用关系型数据库的命名。在 MongoDB 中，所有的数据格式都是以 JSON 为数据库类型，它能够比较灵活的存储各种数据库关系。这也是为什么 MongoDB 能够在一个 Collection 中存储各种不同结构的数据。比如，你可以插入这样一个 JSON 到 MongoDB 中：{"user": {"name": "Zhang San", }}，另外再插入这个
JSON{"product": {"id": "00001"}}。可以看到这两个 JSON 没有任何关系，也没有任何相同的属性，但在 MongoDB 中都是合法的数据，他们可以同时存在于一个 Collection 中。当然，我们并不鼓励大家这样做，因为这样很难维护你的数据库表格，而且对于查询索引来说也很麻烦，会产生很多不必要的索引存储。我们所说的结构灵活指的是在一个结构框架基础上，可以灵活扩充、添加新的数据而不用重新定义数据 Schema。因此，我们在进行数据库迁移之前需要讨论如何定义
Collection 的结构。

MongoDB 将 JSON 存储成一个叫BSON的数据结构中，BSON指的是Binary JSON，二进制 JSON，并在 JSON 的基础上添加了一些新的数据类型，int，float，long。JSON 格式可以灵活的存储嵌入式数据结构，以及数组，要是在关系型数据库中实现其难度是很难想象的。在定义Collection 结构时，需要根据应用程序实际需求找出数据模型的定义，最大程度的利用 MongDB 的存储灵活性。例如，下面是一个典型的两张一对多的数据库表格。

学生表：

成绩表：

其中，第一张表是学生表，第二张是学生成绩表，一个学生可以有多门课程的成绩，因此他们之间是一对多的关系，其中studnet_id在学生表中是主键，对应成绩表中的外键。在关系型数据库中这种表示方法完美并正确，但是到了 MongoDB 中也许就是另外一种存储样式了。为了充分利用 JSON 格式的内嵌式存储，我们通常会把这种关系存储到 Collection 中的一条记录（Document），如下所示：

上面是对学生 Zhang Scan 的记录存储，可以看出我们把学生成绩当作是学生表的内嵌字段，由于是一对多的关系，我们把他存储成一个数组的形式。这种基于 JSON 文档的存储结构有一下几点优势：

  • 数据一目了然，当你从数据库中取出一条学生记录后，关于学生的基本信息全部显示出来。方便大家阅读浏览。
  • 避免了多次数据库表连接操作。在关系型数据库中存在着多种表之间的链接操作，比如左右连接，内连，外连等等。为了找到关于一个学生的全部信息，我们也许需要进行若干张表的连接才能拿到想要的数据。除了需要写更复杂的 SQL 语句以外，数据库的性能也会受到影响。当数据库进行一次连接操作时，内部可能是需要从磁盘不同位置读取数据，加大了 IO 操作。反观 MongoDB，一次查询只需要读取一次磁盘，大大提高的查询效率。
  • 删除、修改操作简单方便。如果所有相关学生的信息都存储在一张 Collection 中，那么对学生信息的删除和修改只需要在一张表中操作就可以。试想一下在关系型数据库中，如果需要删除一个学生纪录，有可能需要操作学生表、成绩表、宿舍表、等等与学生关联的所有表，这样的设计是困扰关系型数据库开发人员的一大难题。搞不好数据库中就会存储大量过时、失效的数据，而这些数据可能成为永远也不会被访问的死角。
  • 所有 Document 都是自我描述的，这方便大家进行数据库的水平扩展。在 MongoDB Shard 中，我们可以将一个 Collection 切分到不同的 Shard 集群中，这种切分方法在不需要进行 JOIN 的操作前提下变得十分简单。因为，DBA 再不用担心需要进行夸节点的 JOIN 操作。（关于 MongoDB 水平扩展的内容，情参考另外一篇文章MongoDB 的水平扩展，你做对了吗？。

内嵌还是引用

上面是一个将一对多关系的两张表整合到一个 Document 中，实际上我们的数据表结构会复杂很多，一个企业级应用动辄就要设计几百甚至上千张表，表之间会有一对一，一对多，多对多种关联关系。对于如此复杂的场景目前我们还没有一个准确的可以使用任何情况的解决方案。基本上都需要针对业务数据具体分析，从而得出新的数据结构。这里，我可以给大家列出一些基本的原则以及处理不同关系的基本方法，根据这些基本原则方法我想大家总可以根据自己的业务归纳出一个行之有效的解决方案。具体到 MongoDB，有内嵌和饮用两种方式来进行关联，下面我们分布看一下它们应用的场景。

内嵌

就像上面举的例子那样，将关系型数据中表的一行内嵌到与他相关联的表中使之在新的 Collection 中成为一个 Document。这种内嵌的方法适用于两种情况：

  • 当表关系是一对一时，或者
  • 当表关系是一对多时

在上面两种关系下，如果关系表不经常单独进行查询，它只是依附在主表查询的基础上进行，那么我们可以考虑使用内嵌的方法。以产品和产品价格为例说明一下，在纪录产品价格时，价格是会随着时间的变化而取不同的值。一款新上线的产品价格相对较高，随着时间的推移其价格也会随之下降。在一些类似双十一节假日期间，价格也会临时调整。在分析产品销售状况的时候，我们还要考虑到在什么样的价格下产品销量高，所以不能简单的把产品和价格放到一张表中，必然会存在一张与产品相关联的价格表，它纪录了产品当前价格以及历史价格。那么，我们在统计产品的销量报表时，这张价格表不会单独存在，它必然会依附在产品表之下。此时，将产品价格内嵌到产品表中就是一个比较可行的方案。查询语句可以通过一个
Collection 找出所有产品相关价格从而避免了表之间的 JOIN 操作。

但是并不是所有的一对一和一对多的关系都适合使用内嵌的方式。在一下情况下应当慎重使用内嵌数据结构：

  • 如果一个 Document 的大小超过了 MongoDB 的限制（16M），此时不应考虑嵌入数据结构。当你的数据表关系很复杂，可能将所有相关的数据内嵌到一个 Document 中会超过 16M 的限制。
  • 如果一个 Document 需要经常被访问，而其中的一个内嵌 Document 很少被访问到，这时不太适合使用内嵌；因为这会使 MongoDB 在检索数据时增加内存的消耗。
  • 如果一个 Document 中的一个内嵌 Document 需要经常修改，或者大小经常发生变化，而另一个内嵌 Document 相对静态，这是也不要考虑使用内嵌结构。
  • 由于内嵌 Document 的增加和减少会导致整个 Document 大小发生变化，当变化超过了分配给 Document 的磁盘空间时会导致数据库从新为 Document 分配空间。

引用

除了内嵌之外还可以使用引用的方式来关联数据。引用的方式和关系型数据库表的主外键很想。你可以把主表和外键表分别存储成一个 Collection，然后用他们的_id进行关联，_id是 MongoDB 文档中一个比较特殊的字段，他会被 MongoDB 自动生成并且唯一存在在一个 Collection 中。但是，在使用引用的时候需要注意一下几点：

  • 在一些复杂的多对多关系表中，不要尝试引用，因为这会加大应用程序逻辑上的开发和维护。
  • 当使用内嵌结构产生过多重复数据的时候，可以考虑使用引用。
  • 虽然 MongoDB 不支持 JOIN 操作，但是可以通过 Aggregation 中的$lookup指令来完成连接多表的操作请求。

应用集成

有了数据模型的定义，我们就可以开始进行应用集成。集成的方法可以使用 MongoDB 的 Driver，它支持了几乎常用的各种计算机语言。使用简单和开发效率高是 MongoDB 的两大特点。于 SQL 语句不同的是，MongoDB 采用了 API 的方法提供接口，开发人员可以选择支持自己熟悉语言的 Driver，DBA 可以直接使用 Mongo Shell 脚本。幸运的是，MongoDB 提供了 API 和 SQL 语句的对照表供大家参考，SQL to MongoDB Mapping Chart。

另一个强大的功能不能不提的是 Aggregation Framework（聚合）。并不是所有 NoSQL 数据库都支持 Aggregation，简单理解 Aggregation 可以把它当成是 Hadoop 里面的 Map Reduce，或者 SQL 里面的 Left Join。在没有 Aggregation 的情况下，开发人员进行数据迁移不得不进行如下操作：

  • 在应用程序层开发类似 Aggregation 的功能，将数据聚合在一起并写进数据库。这样做加大了应用程序的复杂度，并且很难适应各种不同数据的组合情况。没遇到一个新的需求都需要进行一定量的开发工作。
  • 有些人会把数据到如今 Hadoop，然后在上面运行 MapReduce 生成结果，之后将结果倒进 NoSQL 中。这是一个折中的方法，但是他并不支持实时数据迁移，只能进行线下操作。

MongoDB 支持原生 Aggregation 操作，你可以把需要迁移的数据进行聚合操作，每一次操作可以想象成一个流水线上的环节，将所有的操作连接起来可以构成一条 Aggregation Pipeline。在 Pipeline 上面的每一个节点都有自己的输入输出，前一个节点的输出是下一个节点的输入。有兴趣的同学可以在这个连接上找到更多的关于 Aggregation 操作，它列出了每一个 Aggregation 命令和 SQL 语句的对应关系，SQL to Aggregation Mapping
Chart

数据完整性

在关系型数据库中，有很多支持 ACID 事务操作的方法和应用，DBA 并不希望在数据迁移的过程中有任何闪失，例如损失数据完整性。MongoDB 在这方面具有不同形式的支持。在 3.0 以上版本中，MongoDB 支持了 WiredTiger Storage Engine，他支持了 Document 级别上的锁操作。也就是说，在进行数据库写操作时，MongoDB 可以保证针对一个 Document 操作的原子性，这个操作可以和其他操作完全分隔开来。除了对单个 Dcoument 的原子操作支持外，MongoDB
还支持多 Document 的事务，比如，findAndModify方法允许你在进行多个文档操作的时保持事务完整。再比如，可以通过Perform Two Phase Commits实现更新多个文档的原子操作，更多信息请访问 Perform Two Phase Commits。

数据一致性

在数据一致性方面，MongoDB 通过 Read Preference 来调节一致性的程度。默认情况下，在一个 MongoDB Replica Set 中，所有的数据库读操作都会发到 Primary 服务器上，Replica Set 中的所有 Secondary 保证数据最终一致性。同时，MongoDB 提供了修改这种一致性的行为方式。数据库管理员可以通过修改 Read Preference 参数达到对一致性不同要求的场景。数据一致性可以有下面集中方案：

  • primary： 默认模式，所有请求都会发送到 Primary 上。
  • primaryPreferred：大部分读请求都会发送到 Primary，但是当 Primary 无法访问时，改请求会被转发到 Secondary 上。
  • secondary： 所有请求都会发送到 Secondary 上。
  • secondaryPreferred： 大部分情况下，读请求被发送到 Secondary 中，但是如果 Replica 中没有 Secondary，请求会发送到 Primary 上。
  • nearest： 请求会被发送到网络最近的服务器上。该模式在多数据中心上非常有效。

数据迁移

进行完上面的设计和思考以后，数据迁移就会变得想对容易。将数据导入进 MongoDB 有几个不同的选择，可以使用 mongoimport 将 JSON 数据进行导入，也可以通过 ETL（Extract Transform Load) 工具完成。很多项目允许在当前应用程序运行的情况下并行迁移关系型数据库中的数据，并且支持增量更新，具体操作如下：

  • 当一条记录从关系型数据库读出后，应用程序会将这条记录按照先前定义的 JONS 格式插入到 MongoDB 中。
  • 一致性检查，可以通过 MD5 等方法进行数据一致性检查。
  • 新的插入操作和数据修改操作全部转到 MongoDB 中完成。

小结

按照本文提供的方法和步骤，项目团队可以在数据迁移中减少不必要的时间和错误的操作。当然，数据永远是应用系统中的核心内容，任何数据迁移都需要支持错误恢复，如果失败也要能够快速恢复到以前的版本上。在这方面，MongoDB 做到了更灵活的支持，具体内容可以参考

MongoDB Webnar。

参考文献

Data Modeling

SQL to MongoDB Mapping Chart

SQL to Aggregation Mapping Chart

WiredTiger Storage Engine

Perform Two Phase Commits

关于作者

赵翼，毕业于北京理工大学，目前就职于 SouthbankSoftware，从事 NoSQL，MongoDB 方面的开发工作。曾在 GE，ThoughtWorks，元气兔担任项目开发，技术总监等职位，接触过的项目种类繁多，有 Web，Mobile，医疗器械，社交网络，大数据存储等。

感谢蔡芳芳对本文的审校。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

论文链接：Beyond Part Models: Person Retrieval with Refined Part Pooling

本文纯属个人观点，如有错误欢迎指正，谢谢！

Motivation

当前利用 part-level feature 做re-id 的方法大致分为两类：

  1. 利用在其他数据集上训练好的 pose estimation 模型 unsupervised transfer 到 re-id 数据集上得到 local part 的定位，然后基于local parts 提取 part-level features。

2.不使用额外的类似于 pose estimation 的模型，而是用统一的分块方式，（比如给定一张行人图像，将图像均匀分割为固定的p个horizontal stripes）或者采用 attention 机制去locate 等。

使用第一种方法虽然可以显式的定位 local parts，但是也要忍受 transfer 过程由于 datasets bias 引入的误差。当然如果定位带来的提升大于引入误差导致的性能降低，整体也是可以接受的。这篇文章第一部分PCB模型属于第二类方法，使用得是均匀划分。对不同part用不同loss去训练。对于均匀分割或者其它统一的分割，不同图像在同一part可能因为没有对齐出现不同的语意信息。对此，作者提出了Refined Part Pooling 对统一分割进行提纯，增强 within-part
的一致性，这也是本文的一大亮点。

Method

  • PCB结构：

  1. 去掉Resnet50 global average pooling及以后的部分。
  2. 将最后一层feature map 分成 p个horizontal stripes。分别对p个horizontal stripes做global average pooling就得到了p个局部特征。
  3. 因为 Resnet50 最后一层feature map的通道数为2048，作者又用1x1 conv将其降到256维。
  4. 接着用p个n（训练集ID数目）分类softmax作为分类器进行训练。损失函数使用交叉熵损失。
  5. 测试时分别串联向量g和h作为行人图像的特征表示。
  • PCB细节：
  1. 为了丰富特征粒度，参考 SSD 和 R-FCN，作者去掉了 Resnet50 最后一次 down-sampling。
  2. 图像 resize 到 384x128。
  3. horizontal stripes 的个数 p 取6。
  4. 对比了使用单损失和多损失的性能。使用单损失函数时，对 p 个 h 求平均作为图像的特征表示。
  5. 对比了 p 个 softmax 前一层 FC 共享参数的性能。
  • RPP motivition: 作者将 average pooling 前后的向量做最近邻（ f_{mn} 与 g_i ），注意到真实的边界并不和统一划分的边界重合，很显然这也是统一划分最大的弊端之一。

  • RPP结构
  1. 作者在最后一层 feature map 后面训练了一个 part classifier。part classifier 使用的是线性层 + softmax，参数记为 W。
  2. 接着将 average pooling 改为向量的加权和，权值即分类器的后验概率。

  • RPP的训练：RPP 只有一项参数 W，训练分三步：
  1. 训练 PCB 至收敛。（这一步引导训练的重要性以及 step3 内在的思想见作者评论补充）
  2. 将 average pooling 替换为 part classifier。
  3. 固定其它参数训练 W 至收敛。
  4. 放开全部参数，fine tune。

Experiments

  • Datasets：Market-1501，DuckMTMC-reID，CUHK03 (new protocol)
  • setting：single-query，without re-ranking

  • 结论：
  1. 相比 IDE，PCB 的 mAP 提升8.9-15.3%
  2. RPP 对 PCB 的 rank-1 提升 1.5-3.1%，mAP 提升 3.1-4.2%
  3. 多损失比单损失提升明显，mAP 提升约 10-15%
  4. p 个分类器不共享参数相比共享参数提升 mAP 2.4-7.4%
  • 关于图像分辨率以及去掉 Resnet50 最后一次 down-sample 的实验

  • 对 horizontal stripes 数目 p 的讨论

  • PCB 引导训练的重要性讨论以及与另一篇基于 attention 机制方法的对比

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

一、前言

本篇主题为行为型模式中的第四个模式–观察者模式。上篇 Java 设计模式主题为《Java 设计模式之迭代器模式（十五）》。

二、简单介绍

# 2.1 定义

观察者模式是行为模式之一，定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。

# 2.2 参与角色

  1. 被观察者（Subject）：当需要被观察的状态发生变化时，需要通知队列中所有观察者对象。Subject 需要维持（添加，删除，通知）一个观察者对象的队列列表。
  2. 观察者（Observer）：接口或抽象类。当 Subject 的状态发生变化时，Observer 对象将通过一个 callback 函数得到通知。

# 2.3 应用场景

  1. 聊天室程序，服务器转发信息给所有客户端。
  2. 网络游戏，服务器将客户端状态进行分发。
  3. 邮件订阅等。

三、实现方式

记得笔者在上中学时，所在的学校是禁止在寝室打扑克牌的，但是还是有不少学生违背这条规定，笔者就是其中之一。我们就以这个故事为例，在这个案例中，老师是被观察者，学生则是观察者。学生观察老师是否来到寝室，从而做出不同的行为。

被观察者和子类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
复制代码public abstract class Subject {



    protected List<Observer> list = new ArrayList<Observer>();



    public void registerObserver(Observer obs) {

        list.add(obs);

    }



    public void removeObserver(Observer obs) {

        list.add(obs);

    }



    // 通知所有的观察者更新状态

    public void notifyAllObservers() {

        for (Observer obs : list) {

            obs.update(this);

        }

    }

}



public class Teacher extends Subject {



    private String action;



    public String getAction() {

        return action;

    }



    public void setAction(String action) {

        this.action = action;

        // 被观察者状态发生变化，通知观察者

        this.notifyAllObservers();

    }

    

}

Teacher 继承 Subject 类，Teacher 的实例就是被观察的对象。

观察者和实现类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
复制代码public interface Observer {



    public void update(Subject subject);

}



public class Student implements Observer {



    private String action;

    

    @Override

    public void update(Subject subject) {

        String teacherAction = ((Teacher) subject).getAction();

        

        if (teacherAction.equals("老师来了")) {

            action = "假装学习";

        } else if (teacherAction.equals("老师走了")) {

            action = "继续打牌";

        }

    }



    public String getAction() {

        return action;

    }

}

客户端：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
复制代码public class Client {



    public static void main(String[] args) {

        

        Teacher teacher = new Teacher();

        

        Student s1 = new Student();

        Student s2 = new Student();

        Student s3 = new Student();

        

        teacher.registerObserver(s1);

        teacher.registerObserver(s2);

        teacher.registerObserver(s3);

        

        teacher.setAction("老师来了");

        

        System.out.println(s1.getAction());

        System.out.println(s2.getAction());

        System.out.println(s3.getAction());

        

        System.out.println("================");

        

        teacher.setAction("老师走了");

        

        System.out.println(s1.getAction());

        System.out.println(s2.getAction());

        System.out.println(s3.getAction());

    }

}

打印结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
复制代码假装学习

假装学习

假装学习

===========

继续打牌

继续打牌

继续打牌

其实，在 JDK 中已经提供了 java.util.Observable 和 java.util.Observer 来实观察者模式。

实现方式如下：

被观察者：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
复制代码public class Teacher extends Observable{



    private String action;



    public String getAction() {

        return action;

    }



    public void setAction(String action) {

        this.action = action;

        // 被观察者状态发生变化，通知观察者

        this.setChanged();

        this.notifyObservers(this.action);

    }

}

观察者：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
复制代码public class Student implements Observer {



    private String action;

    

    @Override

    public void update(Observable o, Object arg) {

        

        String teacherAction = ((Teacher) o).getAction();

        

        if (teacherAction.equals("老师来了")) {

            action = "假装学习";

        } else if (teacherAction.equals("老师走了")) {

            action = "继续打牌";

        }



    }



    public String getAction() {

        return action;

    }

}

客户端：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
复制代码public class Client {



    public static void main(String[] args) {

        Teacher teacher = new Teacher();

        

        Student s1 = new Student();

        Student s2 = new Student();

        Student s3 = new Student();

        

        teacher.addObserver(s1);

        teacher.addObserver(s2);

        teacher.addObserver(s3);

        

        teacher.setAction("老师来了");

        

        System.out.println(s1.getAction());

        System.out.println(s2.getAction());

        System.out.println(s3.getAction());

        

        System.out.println("================");

        

        teacher.setAction("老师走了");

        

        System.out.println(s1.getAction());

        System.out.println(s2.getAction());

        System.out.println(s3.getAction());

    }

}

打印结果与上文的一致。

使用 JDK 提供的这 2 个类大大的简化了代码量。

UML 类图表示如下：

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

什么是插入排序

插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的合适位置上，直到所有的待排序记录全部插入为止。
根据查找的方法不同，有多种不同的排序方法，接下来将介绍三种方法：直接插入排序、折半排序、希尔排序。

直接插入排序

算法思想：

将记录插入到已经排好序的有序表中，从而得到一个新的、记录数量加一的有序表。基本的实现思想是：新增的数据和有序表中的最末尾的数据进行比较，如果记录小于有序表的最后一个记录，那么将这个记录存放在监视哨中，同时不断的比较前方数据 ，并且将比这个数据大的数据进行后移。当监视哨里面的数据发现了有序表中的数据不再比他大的时候间数据进行存放在后移所留下的空余位置。

算法过程实现

enter description here

直接插入

算法代码实现

具体的代码实现如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
复制代码class InserSort {
public:
	void InsertSort (vector<int> &arry) {
	for (i = 2; i <= arry.size(); i++) {
		if (arry[i] < arry[i-1]) {
			arry[0] = arry[i];
			arry[i] = arry[i-1];
			for(j = i - 2; arry[0] < arry[j]; j--) 
				arry[j+1] = arry[j];
			arry[j+1] = arry[0];
		}
	}
}
private:
	int i;	
	int j;
};

算法分析

(1)时间复杂度：从时间来看，排序最基本的操作为：比较 两个关键字的大小和移动记录。时间复杂度为O(n2)；
(2)空闲复杂度：直接插入只需要一个记录的辅助空间，所以 空格键复杂度为O（1）；

折半插入排序

算法思想：

和直接插入类似,折半插入的方法是，按照折半查找的顺序来实现的，利用顺序摆的顺序，按照折半的方式进行查找，如果数据出现较小的话，那么就把high前移，反之则后移当出现low<=high的时候，就找到了数据最佳存在的位置，这样排序就实现了。

算法过程实现

和直接插入类似。

算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复制代码class BInsertSort {
public:	
	void BInsertSorts (vector<int> &arry)  {
		for(i = 2; i < arry.size(); i++) {
			arry[0] = arry[i];
			low = 1; high = i-1;
			while(low<=high) {
				mid = (low + high) / 2;
				if (arry[0] < arry[mid]) high = mid - 1;
				else low = mid + 1;
			}
			for (j = i -1; j >= high+1; j--) arry[j+1] = arry[j];
			arry[high+1] = arry[0]; 
		}
	}
private:
	int i,j,low,high;
	int mid;
};

算法分析

（1）时间复杂度：从时间上来讲折半插入的速度比顺序查找块。在平均情况下，折半插入排序仅减少了关键字之间的比较次数，而记录的移动次数不变。因此，折半插入排序的算法复杂度仍然是O（n2）
（2）空间复杂度：和直接插入排序的空间复杂度相同。都是O(n2)。

希尔排序

算法思想：

希尔排序又称之为“缩小增量排序”，是插入排序的一种。
希尔排序的实质就是采用分组排序的方法。现将整个待排序的记录分隔成为几组，从而减少参与直接排序的数据量，对每一组的数据进行直接插入排序，然后增加没组的数据量，重新分组。这样当经过几次分组之后，整个序列中 的记录“基本有序”时，再对全体记录进行一次直接插入排序。

算法过程实现

enter description here

希尔排序

算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
复制代码class ShellInster {
public:
	void ShellInsters (vector<int> &arry, int dk) {
	 for (i = dk + 1; i < arry.size(); i++) {
	 	if (arry[i] < arry[i - dk]) {
	 		arry[0] = arry[i];
	 		for (j = i - dk; j > 0 && arry[0] < arry[j]; j-=dk) 
	 			arry[j + dk] = arry[j];
	 		arry[j + dk] = arry[0];
		 }
	 }
	}
	
private:
	int i,j;
	
};

class ShellSort {
public:
	void ShellSorts(vector<int> &arry) {
		m = arry.size()/2;
		while(m >= 1) {
			m=m/2;
			m1.ShellInsters(arry,m);
		}
	}

private:
	int m;
	ShellInster m1; 
};

算法分析

（1） 时间复杂度
时间复杂度减少到n(log2n²)
（2） 空间复杂度
也是O（1）

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是「AI 学习之路」的第 6 篇，「Python 学习」的第 6 篇

小之的公众号 : WeaponZhi

题外话

这周工作日 5 天，我并没有更新文章，但大家并不要以为小之懒惰了。正好相反，自从上篇的 AI 入门文章后，我自己便开始进行机器学习的系统学习了，这周一到周五，只要有空闲时间，我就开始看吴恩达 Coursera 的视频，可以说是非常痴迷了。

吴教授的课程非常通俗易懂，而且他本人的教学风格也是不紧不慢，循序渐进，甚至有关微积分和线代甚至 Octave 这些知识点都花了比较多的篇幅进行展开讲解，亲身体会后，再次推荐给大家。

目前，机器学习篇我已经学到一半了，实际上本来可以更快一些，但中间的一些微积分和线代的知识点，我又回炉复习了一下。非常庆幸我在大四的时候把高数重新复习了一遍，现在虽说不能完全回想起来，但回炉和记忆的串联算是比较快的，节省了很多的时间。

同时，我现在每天保持一到两题的 LeetCoded 的刷题量，实际上我不太追求说要刷的多快，刷题的目的一来是巩固基础，二来是每天刷一两道，活动下脑子。我每天早上上班前，先打开一道题，然后把题目阅读一下，过个脑子，上班途中就想想思路，如果思路比较清晰，到公司在别人吃早饭的时间，我就把代码提交了，如果思路不太顺，我就工作空闲或者中午的时候在桌上用纸笔画一画，然后晚上下班之后开始码代码。

如果这样的流程一天时间还是想不起来思路，那我就会直接看一下 discuss 或者 Solution，不追求必须靠自己解答出来，只要学到方法，过个脑子，然后把代码码出来上传到 GitHub 留个记录，对我来说就够了。

好了，回归正题，今天我们来较为细致的讲解下 Python 中的函数。

函数的定义

我们之前已经看了很多函数的使用例子了，比如我们要定义一个函数可以这样写

1
2
3
4
5
6
7
复制代码>>> def testFun(a):
...     print(a)
...
>>> testFun
<function testFun at 0x1060f28c8>
>>> testFun('这是一个方法输出')
这是一个方法输出

我们来看看这段代码。通过 def 语句，依次写出函数名、括号、括号中的参数，还有最后的冒号，千万不要忘记了。

冒号后面，就是具体的函数体了，函数体第一行和函数定义要有一个 Tab 的缩进距离。我们知道 Python 是没有分号和大括号来区分代码的结束和开始的，所以缩进的问题一定要注意，如果你的缩进不正确，可能会报 indented 错误。

在交互式环境下定义函数的时候，冒号输入完毕回车后，会有... 的提示，每行结束回车到下一行，连续两次回车定义该函数完毕，重新回到>>>提示符下。

Python 是一门面向对象语言，一切都是对象，甚至函数本身也是对象，我们称这种特性为「函数式编程」，上面的例子中，我们直接打印testFun是可以打印出它的函数类型的。

像我们熟悉的 Kotlin、Groovy 还有 Go 语言，都有这样的特性，函数式编程可以有非常强大的拓展性，同时可以很轻易的解决很多不支持函数式编程的语言下的一些写法问题。这个我会在后面专门写一篇文章来介绍 Python 的函数式编程。

使用函数很简单， 函数名、括号，加上参数即可调用函数。因为 Python 是动态类型语言，所以我们不需要像 Java 那样，对每一个变量和方法参数都提前在编译期设置好类型，我们定义testFun(a)的时候，并没有指示 a 到底是字符串类型还是别的类型。这样的自由肯定是有一定代价的，当函数体内部对参数的使用有较严格的要求的时候，如果传参类型错误，就会报错。

1
2
3
4
5
6
7
8
9
10
复制代码>>> def func_abs(x):
...   if x >= 0:
...      return x
...   else:
...      return -x
...
>>> func_abs(-1)
1
>>> func_abs('string')
TypeError: '>=' not supported between instances of 'str' and 'int'

函数的参数

函数的定义不是很复杂，但搭配参数，就会非常灵活，Python 的参数五花八门，除了我们常用的位置参数外，还有默认参数、可变参数和关键字参数。

位置参数

我们之前定义的 testFun(a) 中的 a 就是一个位置参数，当然你可以设置很多位置参数，顾名思义，参数的意义是和位置一一对应的，比如我们现在改写下 testFun 让它具备输出两个参数的能力

1
2
3
4
5
复制代码>>> testFun(a,b):
...    print(a,b)
...
>>> testFun('测试','参数')
测试 参数

刚刚说的位置一致性的意思就是我们的输入参数的顺序是和函数定义时候的参数顺序是一致的，第一个参数是'测试'，第二个参数是'参数'，只能代表a='测试'，b='参数'，顺序不能错乱。

默认参数

Java 中，如果需要使用一个函数的多种参数形式，是通过重载的形式的，这种方式是比较麻烦的，比如，上面的例子中，我们想让testFun既可以使用一个参数，也可以使用两个参数

1
2
3
4
5
6
7
复制代码public void testFun(String a){
    System.out.println(a);
}

public void testFun(String a,String b){
    System.out.println(a + " " + b);
}

在 Python 中，我们可以使用默认参数来一次性完成这样的函数定义

1
2
3
4
5
6
7
复制代码>>> def testFun(a,b='函数'):
...     print(a,b)
...
>>> testFun('测试')
测试 函数
>>> testFun('测试',"参数")
测试 参数

使用 testFun(a) 的时候，会自动把 b 赋值为 ‘函数’，只有当你需要改变 b 的时候，才需要自己输入参数值。需要注意的是，默认参数定义要放在位置参数的后面。

不仅如此，默认参数的默认值一定要指向的是不可变对象，否则就会出现一些难以预料的问题，这里举一个例子

1
2
3
4
5
6
7
8
复制代码>>> def app_end(L=[]):
...     L.append('END')
...     return L
...
>>> app_end()
['END']
>>> app_end()
['END','END']

注意到了吗，虽然我们的默认参数 L 是一个空 list，但在调用的过程中，每次添加元素，都会被添加到 L 这个 list 中去，而不是我们预料的那样，每次都是一个新的单元素 list，所以我们的默认参数，尽量使用不可变对象，除非你的设计逻辑就是如此。

可变参数

默认参数虽然可以拓展函数的参数数量，但毕竟数量还是固定的，如果我们想让参数数量是任意的，可以使用可变参数，可变参数很简单，在参数前加 * 号即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码>>> def calcSum(*nums):
...     sum = 0
...     for n in nums:
...         sum = sum + n
...     return sum
...
>>> calcSum(1,2,3)
6
>>> nums = [1,2,3]
>>> calcSum(*nums)
6
>>> nums = (1,2,3)
>>> calcSum(*nums)
6

我们也可以把 list 和 tuple 加星号传入可变参数中

关键字参数

关键字参数和可变参数一样，可以允许你传入 0 到任意个参数，不过这些参数都是含有参数名的，在函数内部是以一个 dict 的形式组装

1
2
3
4
5
6
7
8
复制代码>>> def testKW(a,b,**kw):
...     print(a,b,kw)
...
>>> testKW('测试','关键字参数',name='小之')
测试 关键字参数 {'name':'小之'}
>>> kw = {'name':'小之','age':23}
>>> testKW('测试','关键字参数',**kw)
测试 关键字参数 {'name':'小之','age':23}

当然，你可以像可变参数那种形式一样，通过提前定义好 dict，再把变量以**开头传入。

关键字参数比较随意，你可以传入不受限制的参数，如果你需要判断传了哪些参数，你还需要在函数体内部进行判断，这个时候，我们就可以用命名关键字参数来作一定的限制

1
2
3
4
5
复制代码>>> def testKW(a,b,*,name,age):
...     print(a,b,name,age)
...
>>> testKW('测试','命名关键字参数',name='小之',age=23)
测试 命名关键字参数 小之 23

命名关键字参数需要一个分隔符*，*号后面就会被看作是命名关键字参数。如果定义中有一个可变参数，那么后面的命名关键字参数就不需要*了，就像这样

1
2
复制代码>>> def testKW(a,b,*args,name,age):
...     print(a,b,args,name,age)

命名关键字参数是可以有默认值的，有默认值的情况下，可以不传入该参数，这点和默认参数有点类似

1
2
3
4
5
复制代码>>> def testKW(a,b,*,name='小之',age):
...     print(a,b,name,age)
...
>>> testKW('测试','命名关键字参数',23)
测试 命名关键字参数 小之 23

参数的组合

Python 中，上述参数可以组合使用，但需要注意一定的顺序：必选位置参数、默认参数、可变参数、命名关键字参数、关键字参数，这部分我将用廖大的例子来简单介绍下，我们先定义两个有若干参数的函数：

1
2
3
4
5
复制代码def f1(a, b, c=0, *args, **kw):
    print('a =', a, 'b =', b, 'c =', c, 'args =', args, 'kw =', kw)

def f2(a, b, c=0, *, d, **kw):
    print('a =', a, 'b =', b, 'c =', c, 'd =', d, 'kw =', kw)

调用的时候，Python 解释器会自动按照参数位置和参数名把对应参数穿进去

1
2
3
4
5
6
7
8
9
10
复制代码>>> f1(1, 2)
a = 1 b = 2 c = 0 args = () kw = {}
>>> f1(1, 2, c=3)
a = 1 b = 2 c = 3 args = () kw = {}
>>> f1(1, 2, 3, 'a', 'b')
a = 1 b = 2 c = 3 args = ('a', 'b') kw = {}
>>> f1(1, 2, 3, 'a', 'b', x=99)
a = 1 b = 2 c = 3 args = ('a', 'b') kw = {'x': 99}
>>> f2(1, 2, d=99, ext=None)
a = 1 b = 2 c = 0 d = 99 kw = {'ext': None}

最神奇的是可以通过一个 tuple 和 dict 完成上述函数的调用

1
2
3
4
5
6
7
8
复制代码>>> args = (1, 2, 3, 4)
>>> kw = {'d': 99, 'x': '#'}
>>> f1(*args, **kw)
a = 1 b = 2 c = 3 args = (4,) kw = {'d': 99, 'x': '#'}
>>> args = (1, 2, 3)
>>> kw = {'d': 88, 'x': '#'}
>>> f2(*args, **kw)
a = 1 b = 2 c = 3 d = 88 kw = {'x': '#'}

所以我们可以通过类似func(*args, **kw) 的形式来调用任意函数，无论它的参数是如何定义的。你去翻看源码，可以看到很多内置的函数都是用这种形式定义函数的。

欢迎关注我的公众号

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

直播好久没有曝光量了，自荐一波《PHP进阶之路》（PHPer们，好久没有投资自己了呢？）
本文原文地址：mengkang.net/641.html
原创一篇博客不容易，请勿随意转载

云时代，为了提升静态资源的加载速度，大伙都是拼了。这促使近些年国内 CDN 的使用逐步普及。而作为一家以图片分享社区为核心业务的公司，图片 CDN 的使用比较多，下面梳理下自己的一些经验。闭门造车，如有勘误，大家多多包涵。

主要包括了以下内容：

  1. CDN使用背景，图片的分布式存储
  2. CDN 网络原理概述
  3. 批量添加、切换 CDN 的步骤和注意事项
  4. 多 CDN 切换的步骤和注意事项
  5. CDN 访问故障分析

CDN使用背景，图片的分布式存储

因为下文中的CDN的使用都是基于我们当前的图片存储，为了下文介绍不是那么突兀描述下当前图片存储的结构图：

CDN 网络原理概述

简单画了一张图予以说明：

实际我们在第五步，回源的时候，我们会要求 CDN 服务商，不能所有节点直接回源到我们源站，协商要求他们使用统一代理回源我们源站，也就是说同一个资源只许他们回源一次。之后，其他边缘节点没有缓存，请求他们自身的代理。

也就是说他们的 CDN 是有多级缓存的。

批量添加 CDN 的步骤和注意事项

业务需求：现在需要将某个域名（a.mengkang.net）下的图片访问的流量切换到 CDN 上。

操作步骤：

先对原域名下访问日志做统计，统计出访问频次较高的图片地址（比如20万个地址），把这些地址交给cdn服务商。

  1. 让他们先去预热抓取这20万个地址的资源。
  2. 预热完毕后，我们再把（a.mengkang.net）的一部分域名换为(b.mengkang.net)。然后把b.mengkang.net做cname解析到cdn服务器给定的域名地址上去（比如b.mengkang.ccgslb.com.cn）。
  3. 通过wget测试是访问域名b.mengkang.net下的图片是否能够被cdn缓存住。
  4. cache测试没有问题之后，我再把a.mengkang.net下的部分流量切到b.mengkang.net上去，同事运维的同事监控流量回源的情况，根据回源情况再对分配流量的大小做调整。

多 CDN 切换的步骤和注意事项

需求

把网宿 maa 的 cdn 切 400M 到蓝讯 mplus 上。

切换原理

最初，我们配置了n （比如 n=100）个二级域名，然后把这 n 个域名中的一半解析到网宿，另一半解析到蓝讯。比如：

  1. a001.zhoumengkang.com 解析到了蓝讯，回源的地址为y.a001.zhoumengkang.com；
  2. a001.mengkang.net 解析到了蓝讯，回源的地址为y.a001.mengkang.net；
  3. 图片资源是分布式存储存储在各个主机上，要确保上面两个回源域名指向的服务以及服务器路径是一样的。这样，这两个域名就可以相互切换了，但是切换的时候需要观察回源的压力。

这里说的“切”是从我们自身的业务代码动刀，而不是切换和 cdn 的域名解析合作。图片资源在数据库有全局唯一的uuid，然后根据该uuid生成url，只需要在这里控制url的域名输出即可。

执行步骤

  1. 查看网宿 maa 下各个域名的流量请求带宽。
  2. 查看网宿 maa 和蓝讯 mplus 回源地址相同的对应域名。
  3. 统计该域名下的热点资源地址，然后到即将切换的 cdn 服务商做预加载，否则客户端加载时，即使回源带宽不至于打满，但是会出现请求时间过长，图片无法显示的情况。
  4. 修改业务代码，减掉网宿 maa 的图片地址的输出，替换为蓝讯 mplus 的域名。逐步替换，单域名下流量过大，还需要慢慢降权重转移，而不是一次性，以防回源压力过大，导致源站无法承受。
  5. 监控两边 cdn 带宽，新 cdn 的缓存命中率，源站带宽和服务器负载、I/O以及前端图片服务器负载均衡服务器总带宽（因为和钱直接相关，必须关注）。

注意事项

  1. 关注源站的负载和 I/O
1
2
3
4
5
6
复制代码# top
top - 16:25:34 up 273 days,  8:54,  1 user,  load average: 5.54, 5.34, 5.19
Tasks: 209 total,   1 running, 208 sleeping,   0 stopped,   0 zombie
Cpu(s):  0.2%us,  0.4%sy,  0.0%ni, 47.9%id, 51.0%wa,  0.0%hi,  0.5%si,  0.0%st
Mem:  32945488k total, 32851176k used,    94312k free,  7033172k buffers
Swap: 12485164k total,      204k used, 12484960k free, 22568232k cached
  1. cdn 切换之后，除了观察新 cdn 的流量，还需要监控新 cdn 的缓存命中率，可以通过后期的回源比例来监控，也可以通过循环脚本执行wget来监测。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
复制代码$ wget -S -O /dev/null f1.topitme.com/1/40/33/1110152459d0433401m.jpg
--2015-12-29 11:11:01--  http://f1.topitme.com/1/40/33/1110152459d0433401m.jpg
Resolving f1.topitme.com... 220.181.64.145
Connecting to f1.topitme.com|220.181.64.145|:80... connected.
HTTP request sent, awaiting response... 
  HTTP/1.1 200 OK
  Content-Type: image/jpeg
  Content-Length: 33061
  Accept-Ranges: bytes
  Server: nginx
  Date: Mon, 30 Nov 2015 07:47:09 GMT
  Last-Modified: Mon, 08 Sep 2014 05:00:59 GMT
  Expires: Thu, 27 Nov 2025 07:47:09 GMT
  Cache-Control: max-age=315360000
  Powered-By-ChinaCache: HIT from 010519g3H8.6
  Age: 2489032
  Powered-By-ChinaCache: HIT from 01001023P2.2
  Switch:FSCS
Length: 33061 (32K) [image/jpeg]
Saving to: '/dev/null'
 
/dev/null           100%[=====================>]  32.29K  --.-KB/s   in 0.09s  
 
2015-12-29 11:11:02 (372 KB/s) - '/dev/null' saved [33061/33061]

这里出现了Powered-By-ChinaCache为HIT说明命中了，如果是MISS则没有命中，该规则需要咨询 cdn 运营商。

后记

根据每个产品的属性，每日流量肯定都有高峰和低谷期，我之前设置的自然回源，虽然在流量高峰期，设置的比例很小，但是基数很大，所以切过去的量比较大，应该选择在流量比较少的时间，执行预加载，这样保证了带宽的使用率。

CND资源访问故障的定位

案例一：图片大面积无法加载

现象：同一图片地址，时而能打开，时而无法访问。无法访问时，单独访问图片地址发现还跳转到了一个游戏网站主页。

联系 CDN 客服，得到的反馈是运营商 DNS 劫持，他们的服务没问题。（非常的消极怠工）

拿下面这张图片作为例子 f4.topit.me/4/2d/d1/11.…

首先我们确定我们源站资源是可访问的，在 CDN 回源上不存在问题。

我们通过wget命令绑定域名host，假如源站ip为111.1.23.214，这样则会绕过 CDN，直接访问我们源站了。

1
复制代码wget -S -0 /dev/null --header="Host: f4:topit.me" http://111.1.23.214/4/2d/d1/1133196716aead12d4s.jpg

确认图片是能正常访问的。

然后通过wget -S打印详细的 http 头信息

1
复制代码wget -S  http://f4.topit.me/4/2d/d1/1133196716aead12d4s.jpg

请求结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
复制代码# wget -S  http://f4.topit.me/4/2d/d1/1133196716aead12d4s.jpg
--2014-11-08 21:47:34--  http://f4.topit.me/4/2d/d1/1133196716aead12d4s.jpg
Resolving f4.topit.me... 123.150.50.14, 123.150.50.13
Connecting to f4.topit.me|123.150.50.14|:80... connected.
HTTP request sent, awaiting response... 
  HTTP/1.1 302 Moved Temporarily
  Server: nginx/1.7.3
  Date: Sat, 08 Nov 2014 13:45:31 GMT
  Content-Type: text/html; charset=iso-8859-1
  Content-Length: 218
  Location: http://www.aiaigame.com/index.html
  Cache-Control: max-age=300
  Expires: Sat, 08 Nov 2014 13:50:31 GMT
  Powered-By-ChinaCache: MISS from CHN-SX-3-3gC.2
  Age: 125
  Powered-By-ChinaCache: HIT from CHN-TJ-7-3V2.6
  Connection: close
Location: http://www.aiaigame.com/index.html [following]
--2014-11-08 21:47:36--  http://www.aiaigame.com/index.html
Resolving www.aiaigame.com... 119.90.14.54, 119.90.14.59, 220.181.64.153, ...
Connecting to www.aiaigame.com|119.90.14.54|:80... connected.
HTTP request sent, awaiting response... 
  HTTP/1.1 200 OK
  Date: Sat, 08 Nov 2014 13:42:50 GMT
  Server: Apache/2.2.10 (Unix) DAV/2 PHP/5.2.6 mod_ssl/2.2.10 OpenSSL/0.9.8e-fips-rhel5
  Last-Modified: Fri, 07 Nov 2014 09:14:50 GMT
  ETag: "31a8087-132ee-507413eb6f680"
  Accept-Ranges: bytes
  Content-Length: 78574
  Cache-Control: max-age=300
  Expires: Sat, 08 Nov 2014 13:47:50 GMT
  Vary: Accept-Encoding,User-Agent
  Content-Type: text/html
  Powered-By-ChinaCache: HIT from 01011623g3.3
  Age: 288
  Powered-By-ChinaCache: HIT from 01001743SJ
  Connection: keep-alive
Length: 78574 (77K) [text/html]
Saving to: “index.html.4”
  
100%[=====================================================================================================================================================>] 78,574      --.-K/s   in 0.005s  
  
2014-11-08 21:47:38 (16.3 MB/s) - “index.html.4” saved [78574/78574]

通过该请求，我们可以清楚的看到，请求是先已经连接到了123.150.50.14:80然后发生的302跳转，头信息里清楚的写到Powered-By-ChinaCache: HIT from CHN-TJ-7-3V2.6，也就是说是 CDN 自身的问题，而且下面的跳转的网页也是使用ChinaCache的客户。

这样问题得到了定位，CDN 那边也无法再推脱，才着手处理。

案例二：访问网页时 css 里面的图片都无法访问

访问网页时 css 里面的图片都无法访问,单独打开图片地址能访问。使用 wget –referer 定位是防盗链错误设置

故障截图（有点丑）

我把这个问题反馈给客服，给我的答复是他们没有做任何限制，是我们源站的问题。那只能讲证据了。

首先确认源站没问题，模拟浏览器访问时带上referer

1
复制代码wget -S -O /dev/null --header="Host: img.topit.me" --referer="http://static.topitme.com/s/css/main21.css" http://211.155.84.132/img/bar/next.png

结果如下，说明源站是没有设置权限的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复制代码wget -S -O /dev/null --header="Host: img.topit.me" --referer="http://static.topitme.com/s/css/main21.css" http://211.155.84.132/img/bar/next.png
--2015-05-07 13:52:50--  http://211.155.84.132/img/bar/next.png
Connecting to 211.155.84.132:80... connected.
HTTP request sent, awaiting response... 
  HTTP/1.1 200 OK
  Server: nginx
  Date: Thu, 07 May 2015 05:52:50 GMT
  Content-Type: image/png
  Content-Length: 3022
  Connection: keep-alive
  Last-Modified: Wed, 04 Jan 2012 14:44:07 GMT
  Expires: Sun, 04 May 2025 05:52:50 GMT
  Cache-Control: max-age=315360000
  Accept-Ranges: bytes
Length: 3022 (3.0K) [image/png]

同时，绑定host的也采用另一种方式wget -e http_proxy

1
复制代码wget -SO /dev/null --referer="http://static.topitme.com/s/css/main21.css" http://img.topit.me/img/style/icon_heart.png -e http_proxy=211.155.84.137

然后直接请求，不绑定host再请求

1
2
3
4
5
6
7
8
9
10
11
12
复制代码wget -S  -O /dev/null  --referer="http://static.topitme.com/s/css/main21.css"  http://img.topit.me/img/bar/next.png
--2015-05-07 11:29:21--  http://img.topit.me/img/bar/next.png
Resolving img.topit.me... 111.202.7.252, 125.39.78.164
Connecting to img.topit.me|111.202.7.252|:80... connected.
HTTP request sent, awaiting response... 
  HTTP/1.1 403 Forbidden
  Server: nginx
  Date: Thu, 07 May 2015 03:29:21 GMT
  Content-Type: text/html
  Content-Length: 162
  Connection: keep-alive
2015-05-07 11:29:21 ERROR 403: Forbidden.

可以清晰的看到域名的解析过程，CDN DNS 通过预定义策略，返回到最优的 ip 111.202.7.252予以访问。然后返回了403。只有我截图对比了两种情况，CDN 客服才主动着手处理这个问题。

永远不要指望着客服来帮你解决问题，只有自己找到问题。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

引言

HashMap<K,V>和TreeMap<K,V>都是从键映射到值的一组对象，不同的是，HashMap<K,V>是无序的，而TreeMap<K,V>是有序的，相应的他们在数据结构上区别也很大。

HashMap<K,V>在键的数据结构上采用了数组，而值在数据结构上采用了链表或红黑树这两种数据结构。

HashSet<K,V>同HashMap<K,V>的关系与TreeSet同TreeMap<K,V>的关系类似，在内部实现上也是使用了HashMap<K,V>的键集，这点我们同样通过HashSet<K,V>的构造函数可以发现。所以在文章中只会详细解说HashMap<K,V>，对HashSet<K,V>就不做分析。

1
2
3
4
5
6
7
复制代码public HashSet() {
    map = new HashMap<>();
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

框架结构

HashMap<K,V>在继承结构上和TreeMap<K,V>类似，都继承自AbstractMap<K,V>，同时也都实现了Map<K,V>接口，所以在功能上区别不大，不同的是实现功能的底层数据结构。同时由于HashMap<K,V>是无序的，没有继承自SortedMap<K,V>，相应的少了一些根据顺序查找的功能。

哈希

在分析HashMap<K,V>的具体实现之前，先来看下什么是哈希？
哈希又叫“散列”，是将任意对象或者数据根据指定的哈希算法运算之后，输出一段固定长度的数据，通过这段固定长度的数据来作为这个对象或者数据的特征，这就是哈希。这句话可能比较绕口，举个例子。

在一篇文章中有10000个单词，需要查找这10000个单词中是否存在“hello”这个单词，最直观的办法当然是遍历这个数组，每个单词跟“hello”进行比较，最坏的情况下可能要比较10000次才能找到需要的结果，如果这个数组无限大，那要比较的次数就会无限上升。那有没有更快速的查找途径呢？
答案就是哈希表。首先将这10000个单词根据一种指定的哈希算法计算出每个单词的哈希值，然后将这些哈希值映射到一个长度为100的数组内，如果映射足够均匀的话大概数组的每个值对应100个单词，这样我们在查找的时候只需要计算出“hello”的哈希值对应在数组中的索引，然后遍历这个位置中对应的100个单词即可。当映射的数组足够大，比如10000，哈希算法足够好，映射一对一，每个哈希值都不相同，这样理论上最优可以在一次查找就得道想到的结果，最坏的查找次数就是数组的每个位置所对应的单词数。这样相比较直接遍历数组要快速的多。

哈希可以大大提高查找指定元素的效率，但受限于哈希算法的好坏。一个好的哈希算法可以将元素均匀分布在固定长度的数组中，相应的如果算法不够好，对性能就会产生很大影响。

那有没有一个算法可以让任意一个给定的元素，都输出一个唯一的哈希值呢？答案是暂时没有发现这样的算法。如果不能每个元素都对应到一个唯一的哈希值，就会产生多个元素对应到一个哈希值的情况，这种情况就叫“哈希冲突”。

哈希冲突

下图中通过一个简单的哈希算法，每个单词取首字母哈希时，air和airport哈希值一样就产生了哈希冲突。

还是用之前的例子，当10000个单词存放于一个长度为100的数组中时，如果哈希算法足够好，单词分布的足够均匀，每个哈希值就会对应100个左右的元素，也就是每个位置会发生100次左右的哈希冲突。尽管我们可以通过提高数组长度来减小冲突的概率，比如将100变为10000，这样有可能会一个元素对应一个哈希值。但如果需要存储的单词量足够大的情况下，无论数组多大都可能不够用，同时很多时候内存或者硬盘也不可能无限扩大。哈希算法也不能保证2个不同元素的哈希值一定不相同，这时哈希冲突就不可避免，就需要想办法来解决哈希冲突。
一般解决哈希冲突有两种通用的办法：拉链法和开放定址法。
拉链法顾名思义就是将同一位置出现冲突的所有元素组成一个链表，每出现一次冲突，就将新的元素放置在链表末尾。当通过元素的哈希值查找到指定位置时会返回一个链表，再通过循环链表来查找完全相等的元素。
开放定址法就是当冲突出现时，直接去寻找下一个空的散列地址，将值存入其中即可。当散列数组足够大，总会有空的地址，空地址不够用时，可以扩大数组容量。
在HashMap<K,V>中使用的是第一种的拉链法。

构造函数

在HashMap<K,V>中有几个重要字段。
Node<K,V>[] table，这个数组用来存储哈希值以及哈希值对应的元素，又叫哈希桶数组。
loadFactor是默认的填充因子，当哈希桶数组中存储的元素达到填充因子乘以哈希桶数组总大小时就需要扩大哈希桶数组的容量。比如桶数组长度为16当存储的数量达到16*0.75=12时则要扩大哈希桶数组的容量。一般取默认的填充因子DEFAULT_LOAD_FACTOR = 0.75，不需要更改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
复制代码public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable  {
    //默认填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //哈希桶数组
    transient Node<K,V>[] table;

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        this.loadFactor = loadFactor;
        //临界值（第一次临界值为转换后的容量大小）
        this.threshold = tableSizeFor(initialCapacity);
    }

    //默认填充因子 threshold（第一次临界值为转换后的容量大小）
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    //默认填充因子 threshold临界值为0
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
}

在构造函数中有个tableSizeFor方法，这个方法是用来将输入的容量转换为2的整数次幂，这样无论输入的数值是多少，我们都会得到一个2的整数次幂长度的哈希桶数组。比如输入13，返回16，输入120返回128。

1
2
3
4
5
6
7
8
9
10
11
复制代码static final int tableSizeFor(int cap) {
    //避免出现输入8变成16这种情况
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //低位全变为1之后，进行n + 1可以将低位全变为0，得到2的幂次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

通过对输入的参数001x xxxx xxxx xxxx位移1位后0001 xxxx xxxx xxxx与原值进行或运算，得到0011 xxxx xxxx xxxx，最高位的1与低一位都变为1。
位移2位后0000 11xx xxxx xxxx与原值0011 xxxx xxxx xxxx进行或运算，得到0011 11xx xxxx xxxx，最高2位的1与低2位都变为1。
位移4位后0000 0011 11xx xxxx与原值0011 11xx xxxx xxxx进行或运算，得到0011 1111 11xx xxxx，最高4位的1与低4位都变为1。
位移8位后0000 0000 0011 1111与原值0011 1111 11xx xxxx进行或运算，得到0011 1111 1111 1111，最高8位的1与低8位都变为1。
位移16位类似。结果就是从最高位开始所有后面的位都变为了1。然后n + 1，得到0100 0000 0000 0000。
可以看下面的例子：
当输入13时：

当输入118时：

这里要注意n = cap - 1，为什么要对输入参数减一，是为了避免输入2的幂次方时容量会翻倍，比如输入8时如果不进行减一的操作，最终会输出16，读者可以自行测试。

哈希值

那为什么一定要用2的整数次幂来初始化哈希桶数组的长度呢？这就要说到哈希值的计算问题。
在HashMap<K,V>中计算元素的哈希值代码如下：

1
2
3
4
复制代码static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在这段代码就是用来获取哈希值的，其中首先获取了key的hashCode，这个hashCode如果元素有重新实现hashCode函数则会使用自己实现的hashCode，在没有自己实现时，hashCode函数大部分情况下会返回元素在内存中的地址，但也不是绝对的，需要根据各个JVM的内在实现来判断，但大部分实现就算没直接使用内存地址，也和内存地址存在一定的关联。

在获取到key的hashCode之后将hashCode的值的低16位和hashCode的高16位进行异或运算，这就是这个函数非常巧妙的地方，异或运算会同时采用高16位和低16位所有的特征，这样就大大增加了低位的随机性，在取索引的时候tab[(n - 1) & hash]，将包含所有特征的哈希值和哈希桶长度减1进行与运行，可以得到哈希桶长度的低位值。


使用2的整数次幂可以很方便的通过tab[(n - 1) & hash]获取到哈希桶所需要的低位值，由于低位和高位进行了异或运算，保留了高低位的特征，也就减少了哈希值冲突的可能性。这就是为什么这里会使用2的整数次幂来初始化哈希桶数组长度的原因。
添加元素

通过HashMap<K,V>在添加元素的过程，可以发现HashMap<K,V>使用了数组+链表+红黑树的方式来存储数据。

当添加元素过程中出现哈希冲突时会在冲突的位置采用拉链法生成一个链表来存储冲突的数据，如果同一位置冲突的数据量大于8则会将哈希桶数组扩容或将链表转换成红黑树来存储数据。同时，在每次添加完数据后，都会检查哈希桶数据的容量，超出临界值时会扩容。

对红黑树不太理解的可以查看前两篇文章。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
复制代码public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //哈希桶数组为空时，通过resize初始化哈希桶数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //哈希值所对应的位置为空，代表不会产生冲突，直接赋值即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //产生哈希冲突
        Node<K,V> e; K k;
        //如果哈希值相等，并且key也相等，则直接覆盖值
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //p为红黑树 使用红黑树逻辑进行添加（可以查看TreeMap）
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //p为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                //查找到链表末尾未发现相等元素则直接添加到末尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //链表长度大于8时，扩容哈希桶数组或将链表转换成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //遍历链表过程中存在相等元素则直接覆盖value
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //覆盖value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //哈希桶中的数据大于临界值时扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //哈希桶数组小于64则扩容哈希桶数组
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        //将所有Node<K,V>节点类型的链表转换成TreeNode<K,V>节点类型的链表
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //将TreeNode<K,V>链表转换成红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

扩容

添加元素的过程中，以下2种情况会出现扩容：单个哈希桶存储超过8个元素会检查哈希桶数组，如果整个哈希桶数组容量小于64则会进行扩容；在每次添加完元素后也会检查整个哈希桶数组容量，超过临界值也会进行扩容。扩容源码分析如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
复制代码final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //哈希桶数组已经初始化 则直接向左位移1位 相当于扩容一倍
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //向左位移1位 扩容一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //哈希桶数组未初始化 并且已经初始化容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //哈希桶数组未初始化 并且未初始化容量 则使用默认容量DEFAULT_INITIAL_CAPACITY
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //初始化哈希桶数组容量以及临界值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //初始化哈希桶数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //将所有元素拷贝到新哈希桶数组中
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //不存在哈希冲突，重新计算哈希值并拷贝
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //冲突结构为红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //冲突结构为链表
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //扩容后最高位为0，则不需要移动到新的位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //扩容后最高位为1，则需要移动
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //对哈希值改变的节点移动到新的位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

在扩容的过程中，有一个非常巧妙的地方，因为扩容后每个元素的哈希值需要重新计算并放入新的哈希桶数组中，在哈希值计算的过程中，由于是乘以2来扩容的，也就是整数次幂。

这样在每次扩容后会多使用一位特征，这样当多使用的这一位特征为0时（(e.hash & oldCap) == 0），哈希值其实是没有变化的，就不需要移动，这一位特征为1时，只需要将位置移动旧的容量大小的即可（newTab[j + oldCap] = hiHead），这样就可以减少移动元素的次数。红黑树和链表结构都是如此。

查找元素

明白HashMap<K,V>的插入以及扩容原理，再来看查找就非常容易理解了，只是简单的通过在链表或者红黑树中查找到相等的值即可。

在查找中一个值是否是我们需要的值，首先是通过hash来判断，如果hash相等再通过==或者equals来来判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
复制代码public V get(Object key) {
    Node<K,V> e;
    //计算哈希值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //哈希值相等，并且key也相等，则返回查找到的值
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //哈希值存在冲突，第一个不是要找的key
        if ((e = first.next) != null) {
            //冲突结构为红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //冲突结构为链表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

删除元素

删除元素时首先查找到需要的元素，其次根据查找到元素的数据结构来分别进行删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
复制代码public V remove(Object key) {
    Node<K,V> e;
    //计算哈希值
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                            boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //哈希值相等，并且key也相等，则node查找到的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        //哈希值存在冲突，第一个不是要找的key
        else if ((e = p.next) != null) {
            //冲突结构为红黑树
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            //冲突结构为链表
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                                (value != null && value.equals(v)))) {
            //节点为红黑树节点，按红黑树逻辑删除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //节点为桶中第一个节点
            else if (node == p)
                tab[index] = node.next;
            //节点为后续节点
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

HashMap的Key

讲解完整个HashMap的实现，我们可以发现大部分情况下影响HashMap性能最核心的地方还是在哈希算法上面。尽管理论上HashMap在添加、删除和查找上的时间复杂度都可以达到O（1），但在实际应用过程中还受到很多因素影响，有时候时间复杂度为O（1）的HashMap可能比，时间复杂度为O（log n）的TreeMap性能更差，原因就在哈希算法上面。

如果使用一个对象默认的哈希算法，前面我们说过，大部分JVM哈希算法的实现都和内存地址有直接关系，为了减小碰撞的概率，可能哈希算法极其复杂，复杂到影响效率的程度。所以在实际使用过程中，需要尽量使用简单类型来作为HashMap的Key，比如int，这样在进行哈希时可以大大缩短哈希的时间。如果使用自己实现的哈希算法，在使用前需要先测试哈希算法的效率，减小对HashMap性能的影响。

总结

Java集合系列到这里就结束了，整个系列从集合整体框架说到了几个常用的集合类，当然还有很多没有说到的地方，比如Queue，Stack，LinkHashMap等等。虽然这是对自己Java学习过程中的总结，但也希望这个集合系列对大家理解Java集合有一定帮助，如果文章中有错误、疑问或者需要完善地方，希望大家不吝指出。接下来打算对java.util.concurrent包下的内容做一个系列进行系统总结，有什么建议也可以留言给我。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

引言

集合在任何语言中都是比较重要的基础知识，不同的集合在实现上采用了各种不同的数据结构，导致了各个集合的性能以及使用方式上存在很大差异，深入了解集合框架的整体结构以及各个集合类的实现原理，并灵活使用各个集合对编码有很大帮助。
本系列文章从集合框架的整体设计到源码细节分析了java.util包下各个集合相关接口、抽象类以及各种常用的集合实现类，希望通过这个系列的文章对大家理解各个集合有一定帮助。
如未做特殊说明，本系列所有源码出自以下JDK环境：

java version “1.8.0_131”
Java(TM) SE Runtime Environment (build 1.8.0_131-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.131-b11, mixed mode)

接口框架

一个好的框架在设计上都会考虑将接口与实现分离，java.util也不例外。要快速理解java.util，第一步就是从他的接口设计入手，从接口的整体设计可以快速明确这个框架的作用和功能。

*图1 集合接口框架*
通过上面的接口框架图可以看出：Collection和Map<K,V>是java.util框架中的两个根接口，代表了两种不同的数据结构：集合和映射表。而List、Set则是继承自Collection下最核心的两个接口，List有序可重复并可以通过整数索引来访问，Set不包含重复元素。下面我们来分别来说下这些核心接口的基本功能。
Collection

1
复制代码public interface Collection<E> extends Iterable<E>

Collection接口是集合的根接口，他代表了一组元素。但是Collection并不关心这组元素是否重复，是否有序。他只提供操作对这组元素的基本操作方法，怎么添加，怎么删除，怎么循环。所有的实现类都必须提供这些方法，下面列出了Collection接口的部分方法：

1
2
3
4
5
6
7
8
9
10
11
复制代码int size();
boolean contains(Object o);
//Returns an iterator over the elements in this collection.
Iterator<E> iterator();
//Returns an array containing all of the elements in this collection.
Object[] toArray();
//Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
void clear();

在Collection接口的方法中有几个需要注意的地方

iterator()

1
复制代码Iterator<E> iterator();

iterator方法返回一个实现了Iterator接口的对象，作用是依次访问集合中的元素，Iterator接口包含3个方法：

1
2
3
复制代码boolean hasNext();
E next();
void remove();

通过多次调用next()方法可遍历集合中的所有元素，需要注意的是需要在调用next()之前调用hasNext()方法，并在hasNext()返回true的时候才可以调用next(),例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
复制代码private static void collectionIterator() {
    //不用关注Arrays.asList，只需要知道他能返回一个Collection<E>接口就行
    Collection<String> collection = Arrays.asList("Java", "C++", "Python");
    Iterator<String> iterator = collection.iterator();
    while (iterator.hasNext()) {
        String string = (String) iterator.next();
        System.out.println(string);
    }
}
//output:
//Java
//C++
//Python

从JDK5开始使用“for each”这种更加方便的方式来遍历集合，只要实现了Iterable接口，都可以使用“for each”来遍历，效果和使用iterator一样。Iterable接口只包含一个方法：

1
复制代码Iterator<E> iterator();
1
2
3
4
5
6
7
8
9
10
复制代码private static void foreachCollectionIterator() {
	Collection<String> collection = Arrays.asList("Java", "C++", "Python");
	for (String string : collection) {
		System.out.println(string);
	}
}
//output:
//Java
//C++
//Python

toArray( ) 以及 toArray(T[ ] a)

toArray和toArray(T[ ] a)返回的都是当前所有元素的数组。
toArray返回的是一个Object[]数组，类型不能改变。
toArray(T[ ] a)返回的是当前传入的类型T的数组，更方便用户操作,比如需要获取一个String类型的数组：toArray(new String[0])。

List

1
复制代码public interface List<E> extends Collection<E>

List接口最重要的特点在有序（ordered collection）这个关键字上面，实现这个接口的类可以通过整数索引来访问元素。他可以包含重复的元素。
除了包含Collection接口的所有方法外，还包括跟索引有关的部分方法：

1
2
3
4
5
6
7
8
复制代码E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);

其中需要引起注意的地方是ListIterator这个类：
List接口在Iterator迭代器的基础上提供了另一个迭代器ListIterator，先来看看ListIterator接口的定义：

1
2
3
4
5
6
7
8
9
10
11
复制代码public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

ListIterator接口继承自Iterator接口，所以他们的差异在ListIterator接口新增的功能上：

  • ListIterator可以向后迭代previous()
  • ListIterator可以获取前后索引nextIndex()
  • ListIterator可以添加新值add(E e)
  • ListIterator可以设置新值set(E e)

Set

1
复制代码public interface Set<E> extends Collection<E>

Set接口在方法签名上与Collection接口是一样的，只不过在方法的说明上有更严格的定义，最重要的特点是他拒绝添加重复元素，不能通过整数索引来访问。Set的equals方法定义如果两个集相等是他们包含相同的元素但顺序不必相同。
至于为什么要定义一个方法签名完全重复的接口，我的理解是为了让框架结构更加清晰，将集合从可以添加重复元素和不可以添加重复元素，可以通过整数索引访问和不可以通过整数索引这几点上区别开来，这样当程序员需要实现自己的集合时能够更准确的继承相应接口。

Map<K,V>

1
复制代码public interface Map<K,V>

API说明上关于Map<K,V>的说明非常精炼：从键映射到值的一个对象，键不能重复，每个键至多映射到一个值。
从键不能重复这个特点很容易想到通过Set来实现键，他的接口方法Set keySet()也证明了这点，下面选取了Map<K,V>接口中的一些典型方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码int size();
boolean containsKey(Object key);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void clear();
//Returns a Set view of the keys contained in this map.
Set<K> keySet();
Returns a Collection view of the values contained in this map.
Collection<V> values();
//Returns a Set view of the mappings contained in this map.
Set<Map.Entry<K, V>> entrySet();
boolean equals(Object o);
int hashCode();

java Set<K> keySet()
返回映射中包含的键集视图，是一个Set，说明了映射中键是不可重复的。
java Collection<V> values()
返回映射中包含的值得集合视图，Collection，说明了映射中值是可以重复的。
java Set<Map.Entry<K,V>> entrySet()
返回映射中包含的映射集合视图，这个视图是一个Set，这是由他的键集不能重复的特点决定的。
entrySet()返回的是一个Map.Entry<K,V>类型的集，Map.Entry<K,V>接口定义了获取键值、设置值的方法，定义如下：

1
2
3
4
5
6
7
复制代码interface Entry<K,V> {
    K getKey();
    V getValue();
    V setValue(V value);
    boolean equals(Object o);
    int hashCode();
}

类框架

从一个框架的接口知道了这个框架的结构和功能，能够用来做什么。但具体怎么使用，怎么扩展，那就需要了解框架中实现这些接口的部分。
java.util提供了一系列抽象类，来实现上面的接口，这些抽象类中提供了大量基本的方法。如果需要实现自己的集合类，扩展这些抽象类比直接继承接口方便的多。

*图2 抽象类以及实现类框架*
除了图中的抽象类和具体实现类，还有部分历史版本遗留下来的类，包括Vetor,Stack,Hashtable,Properties等，在这里就不做说明，重点关注图中的类即可。
抽象类

需要关注几个关键的抽象类包括AbstractCollection;、AbstractMap<K,V>、AbstractList和AbstractSet，从命名可以看出他们分别实现了Collection、Map<K,V>、List和Set接口。
各个集合的关键区别就在每个集合所使用的数据结构和算法上，所以在抽象类层面都没有涉及具体的数据结构和算法，只对操作这些数据结构的方法做了基本实现。

AbstractCollection

1
复制代码public abstract class AbstractCollection<E> implements Collection<E>

AbstractCollection基本实现了Collection下的所有方法，除了以下几个方法:

1
2
3
4
5
6
7
复制代码public abstract Iterator<E> iterator();

public abstract int size();

public boolean add(E e) {
    throw new UnsupportedOperationException();
}

如果需要实现的是一个不可修改的集合，只需要实现iterator()和size()方法即可，如果需要实现一个可修改的集合，必须重写add(E e)方法。
在AbstractCollection已经实现的方法中可以发现，AbstractCollection所实现的所有方法都是通过Iterator来操作的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码public boolean contains(Object o) {
    //获取迭代器
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

AbstractList

1
复制代码public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

AbstractList抽象类在AbstractCollection抽象类的基础上添加了专属于List接口的部分方法，但大部分方法都是空方法，没有具体实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
复制代码abstract public E get(int index);

public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

public E remove(int index) {
    throw new UnsupportedOperationException();
}

public Iterator<E> iterator() {
    return new Itr();
}

public ListIterator<E> listIterator() {
    return listIterator(0);
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);

    return new ListItr(index);
}

没有实现的原因在于AbstractList是一个抽象类，他并没有确定具体的数据结构，当在数据结构没有确定的情况下，是直接使用整数索引的方式还是通过迭代器循环遍历的方式来查找具体的位置更方便是不确定的，所以在具体实现上都由他的子类来决定。
值得注意的是AbstractList实现了Iterator以及ListIterator两种类型的迭代器，很大程度上方便了子类的扩展：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
复制代码private class Itr implements Iterator<E> {
//......
    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            //向后遍历集合，通过get(i)获取当前索引的元素，每次调用之后cursor = i + 1，get(i)为抽象方法
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            //通过AbstractList<E>类的remove方法来删除元素，AbstractList<E>中remove(int index)是一个空方法，需要子类来实现
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }
}
//......

private class ListItr extends Itr implements ListIterator<E> {
//......
    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            //向前遍历集合，通过get(i)获取当前索引的元素，每次调用之前cursor - 1，get(i)为抽象方法
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
//......
}

AbstractSet

1
复制代码public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>

AbstractSet抽象类在实现上非常简单，只在AbstractCollection抽象类的基础上实现了equal 和 hashCode 方法，但具体的实现还是需要通过contain()方法来判断，由于Set接口类型不考虑元素的顺序，所以只要两个AbstractSet包含相同元素就判断为相等，不需要元素顺序相同，而AbstractList则需要顺序也相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
复制代码//AbstractSet<E> 中的 equals
public boolean equals(Object o) {
    if (o == this)
        return true;

    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    if (c.size() != size())
        return false;
    try {
        //containsAll在AbstractCollection<E>中已经实现，只要包含所有元素就可以
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

//AbstractCollection<E> 中的containsAll
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

//AbstractList<E> 中的equals
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    //需要两个集合中的元素以及元素顺序都相同才返回true
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

AbstractMap<K,V>

1
复制代码public abstract class AbstractMap<K,V> implements Map<K,V>

AbstractMap<K,V>抽象类中实现了除entrySet()方法外的基本所有方法，其中返回键集的Set keySet()和返回值集的Collection values()在实现上非常有趣，从返回值上看是创建了一个新的集合，但实际实现上是返回来一个实现Set或Collection的类对象，类对象的所有操作都是在原映射表的基础上进行的，这种有趣的操作叫视图，java.util框架中存在大量应用。
这里使用视图的好处在于抽象类中你不需要确定返回的Set或Collection的具体实现类是什么，这样就可以在抽象类中没有决定使用哪种数据结构的时候最大化抽象类的功能，增加扩展的方便性。
keySet()的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
复制代码public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new AbstractSet<K>() {
            public Iterator<K> iterator() {
                return new Iterator<K>() {
                    //获取原映射表的迭代器来实现自己的迭代器
                    private Iterator<Entry<K,V>> i = entrySet().iterator();

                    public boolean hasNext() {
                        return i.hasNext();
                    }

                    public K next() {
                        return i.next().getKey();
                    }

                    public void remove() {
                        i.remove();
                    }
                };
            }

            public int size() {
                //直接操作原映射表的size()方法
                return AbstractMap.this.size();
            }

            public boolean isEmpty() {
                return AbstractMap.this.isEmpty();
            }

            public void clear() {
                AbstractMap.this.clear();
            }

            public boolean contains(Object k) {
                return AbstractMap.this.containsKey(k);
            }
        };
        keySet = ks;
    }
    return ks;
}

总结

java.util这个框架的结构还是非常清晰的，从接口的分类，每个接口的抽象类实现，都很好的保证了框架的伸缩性，为后续的实现和自定义扩展提供了极大地方便。
除了上述的接口以及抽象类以外，java.util框架还提供了一些其他结构，在使用频率上不是太高，比如Queue ，Deque 等。
在后面的章节中我们会详细讲解几个关键集合的实现，从数据结构、算法以及性能等各方面分析孰优孰劣。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

前言:由于项目需求，短信验证码的接口需要换成阿里大于的，但是尴尬的发现阿里大于的jar包没有maven版本的，于是便开始了一上午的操蛋引包之路。按照套路来说，自然应该是百度一波，但是百度了好久，找了好多方案之后发现，没一个有用的，而且文章的抄袭、拷贝十分严重，试了N种方案，都是错的，都没有将外部jar包打包到BOOK-INF文件夹下。最终，在第N次尝试之后，终于在打的jar包里将外部的jar包导入进来。特此记录下，防止再犯！！！

首先在新建libs文件夹（根目录或者resource目录下都可以），将需要引入的jar放进去

libs文件夹

然后再pom中加入如下配置，告诉maven导入本地jar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码	<dependency>
        <groupId>com.aliyun</groupId>
        <artifactId>aliyun-java-sdk-core</artifactId>
        <version>3.2.2</version>
        <scope>system</scope>
        <systemPath>${project.basedir}/libs/aliyun-java-sdk-core-3.3.1.jar</systemPath>
    </dependency>
    <dependency>
        <groupId>com.aliyun</groupId>
        <artifactId>aliyun-java-sdk-dysmsapi</artifactId>
        <version>1.0.0</version>
        <scope>system</scope>
        <systemPath>${project.basedir}/libs/aliyun-java-sdk-dysmsapi-1.0.0.jar</systemPath>
    </dependency>

其中除了systemPath配置告诉maven引入的本地jar包的位置之外，其他的配置都可以随便写

划重点！！！敲黑板！！！下面的一步配置也是最重要的一步，网上很多的教程缺了这样一步之后就会导致虽然本地可以运行，但是只要使用maven打包就不行，因为maven没有将本地的jar也打到生成的包中

在pom中给spring boot的打包插件设置一下includeSystemScope参数即可

1
2
3
4
5
6
7
8
9
10
11
复制代码<build>
    <plugins>
        <plugin>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-maven-plugin</artifactId>
            <configuration>
                <includeSystemScope>true</includeSystemScope>
            </configuration>
        </plugin>
    </plugins>
</build>

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

你必须知道的HTTP基本概念

从本文你将看到：HTTP是干嘛用的？怎样和服务器通信？HTTP的基本性质？HTTP能控制什么？基于HTTP三大组件系统？HTTP 和 TCP 之间的关系？HTTP 协议如何使用 TCP 连接？

一、什么是HTTP

HTTP是干嘛用的？

HTTP学名叫做超文本传输协议，是一个网络协议。

是专门用来帮你传输诸如 HTML 的超媒体文档等 Web 内容滴。因为 HTML 本身就是超文本标记语言，HTML 中不仅有文本还有图片、音视频等内容，所以用来传输它的协议当然就叫超文本传输协议了。

关于这个协议，就算你不了解，至少也听说过吧？比如你访问俺的博客的主页，浏览器地址栏会出现如下的网址：http://dunizb.com/，加了粗体的部分就是指 HTTP 协议。大部分网站都是通过 HTTP 协议来传输 Web 页面、以及 Web 页面上包含的各种东东（图片、CSS 样式、JS 脚本）。

它基于 TCP/IP 的应用层协议。它被设计用于Web浏览器和Web服务器之间的通信，但它也可以用于其他目的。

它是 Web 上数据交换的基础，是一种 client-server 协议，也就是说请求通常是由像浏览器这样的接受方发起的。一个完整的 web文档是由不同的子文档重新组建而成的，像是文本、布局描述、图片、视频、脚本等等。

怎样和服务器通信？

  1. HTTP遵循经典的客户端-服务端模型，客户端打开一个连接以发出请求，然后等待它收到服务器端响应。 HTTP是无状态协议，意味着服务器不会在两个请求之间保留任何数据（状态）。
  2. 客户端和服务端通过交换各自的消息（与数据流正好相反）来进行交互。通常由像浏览器这样的客户端发出的消息叫做 requests，那么被服务端回应的消息就叫做 responses。

HTTP 被设计于上20世纪90年代初期，是一种可扩展性的协议。它是应用层的协议，虽然理论上它可以通过任何可靠的传输协议来发送，但是它还是通过 TCP，或者是 TLS－加密的TCP连接来发送。因为它很好的扩展性，时至今日它不仅被用来传输超文本文档，还用来传输图片、视频或者向服务器发送如 HTML 表单这样的信息。HTTP 还可以根据网页需求，来获取部分web文档的内容来更新网页。

HTTP遵循经典的客户端-服务端模型，客户端打开一个连接以发出请求，然后等待它收到服务器端响应。 HTTP是无状态协议，意味着服务器不会在两个请求之间保留任何数据（状态）。虽然通常基于TCP / IP层，但可以在任何可靠的
传输层上使用;也就是说，一个不会静默丢失消息的协议，如UDP。

二、HTTP的基本性质

总述：HTTP是简单的、可扩展、无状态的

HTTP 是简单的

即便在HTTP/2中把HTTP消息封装到了frames中，HTTP大体上还是被设计成可读的而且简单的。HTTP的消息能够让人读懂且明白它的意思，还允许简单的测试，放低了门槛，更有利于新来者了解。

HTTP 是可扩展的

在HTTP/1中就出现了, HTTP headers 让协议扩展变得非常容易。只要服务端和客户端在新的headers上语义达成一致，新的功能就可以轻松地被加进来。

HTTP 是无状态，有会话的

HTTP是无状态的：在同一个连接中，两个成功执行的请求之间是没有关系的。这就带来了一个问题，用户没办法在一个网站进行连续的交互，比如在一个电商网站里，用户把某个商品加入了购物车中，换了一个页面后再次添加商品，两次添加商品的请求没有联系，浏览器无法知道最终用户都选择了哪些商品。而用HTTP的头部扩展，HTTP Cookies就可以解决这个问题（将在后面介绍）。把Cookies添加到头部中，创建一个会话来让每次请求都能共享相同的上下文信息，相同的状态。而HTTP的核心是无状态的，cookies的使用可以创建有状态的会话。

三、HTTP能控制什么

多年以来，HTTP良好的扩展性控制着越来越多Web的功能。缓存和认证方式很早就可以由HTTP来控制了。另一方面，对同源同域的限制到2010年才有所改变。

下面就是可以用HTTP来控制的常见特性。

缓存

文档怎么缓存能够通过HTTP来控制。服务端能告诉代理和客户端什么需要被缓存，缓存多久，而客户端能够根据请求条件首部字段（如If-Modified-Since、If-Match等）来忽略存储的文档。

开放同源限制

为了防止网络窥听和其它的隐私泄漏，浏览器强制对Web网站做了分割限制。只有来自于相同来源的网页才能够获取网站的全部信息。这样的限制有时反而成了负担，HTTP可以通过修改头部来开放这样的限制，因此web文档可以是由不同域下的信息拼接成的（在某些情况下，这样做还有安全因素考虑在里面）。

认证

一些页面能够被保护起来，仅让特定的用户进行访问。基本的认证功能可以直接通过HTTP提供，使用Authenticate相似的头部就可以，或者用HTTP cookies来设定指定的会话。

代理和隧道

通常情况下，服务器和/或客户端是处于内网的，对其它（外网）隐藏其真实 IP 地址。因此 HTTP 请求就要通过代理越过这个网络屏障。但并非所有的代理都是 HTTP 代理。例如，SOCKS协议的代理就运作在更底层。一些像 ftp 其它的协议也能够被它们处理。

Cookies
Cookies用一个服务端的状态连接起了每一个请求。这就创建了会话，虽然基本的HTTP是无状态协议。这很有用，不仅是因为能用到购物车这样的电商业务上，更是因为，它使得任何网站都能够配置页面展现的东西了。

四、基于HTTP三大组件系统

客户端：user-agent

严格意义来说，user-agent 就是任何能够为用户发起行为的工具。但实际上，这个角色通常都是由浏览器来扮演。对于发起请求来说，浏览器总是作为发起一个请求的实体，而永远不是服务器（虽然一些机制已经能够模拟服务器发起请求的消息了）。

Web服务端

在上述通信过程的另一端，就是一个Web Server来服务并提供客户端请求的文档。Server只是虚拟意义上：它可以是许多共同分担负载（负载平衡）的一组服务器组成的计算机群，也可以是一种复杂的软件，通过向其他计算机发起请求来获取部分或全部资源的软件。

Server不再只是一个单独的机器，它可以是在同一个机器上装载的许多服务之一。在HTTP/1.1和Host头部中，它们甚至可以共享同一个IP地址。

Proxies 代理

在浏览器和服务器之间，有许多计算机和其他设备转发了HTTP的消息。因为Web栈层次结构的原因，它们大多数都出现在传输层、网络层和物理层上，对于HTTP的应用层来说就是透明的（虽然它们可能会对应用层的性能有重要影响）。而还有一部分表现在应用层上的，就叫做proxies了。Proxies既可以表现得透明，又可以不透明（看请求是否通过它们），主要表现在这几个功能上：

  • 缓存（可以是公开的或是私有的，像浏览器的缓存）
  • 过滤（像反病毒扫描，家长监护）
  • 负载均衡，让多个服务器服务不同的请求
  • 对不同资源的权限控制
  • 登陆，允许存储历史信息

每一个发送到服务器的请求，都会被服务器处理并且返回一个消息，也就是response。在client与server之间，还有许许多多的被称为proxies的实体，他们的作用与表现各不相同，比如有些是网关，还有些是caches等。
Client-server-chain

实际上，在一个浏览器和处理请求的服务器之间，还有计算机、路由器、调制解调器等等许多实体。由于Web的层次设计，那些在网络层和传输层都不可见了。HTTP是在最上层应用层中的，虽然下面的层次对分析网络问题非常重要，但是对HTTP的描述来说，这些大多数都是不相关的。

五、HTTP 和 TCP 之间的关系

前面说过，HTTP是基于 TCP/IP 的，简单地说，TCP 协议是 HTTP 协议的基石——HTTP 协议需要依靠 TCP 协议来传输数据。

在网络分层模型中，TCP 被称为“传输层协议”，而 HTTP 被称为“应用层协议”。有很多常见的应用层协议是以 TCP 为基础的，比如“FTP、SMTP、POP、IMAP”等。

TCP 被称为“面向连接”的传输层协议。关于它的具体细节，俺就不展开了（否则篇幅又失控了）。你只需知道：传输层主要有两个协议，分别是 TCP 和 UDP。TCP 比 UDP 更可靠。你可以把 TCP 协议想象成某个水管，发送端这头进水，接收端那头就出水。并且 TCP 协议能够确保，先发送的数据先到达（与之相反，UDP 不保证这点）。

六、HTTP 协议如何使用 TCP 连接？

HTTP 对 TCP 连接的使用，分为两种方式：俗称“短连接”和“长连接”（“长连接”又称“持久连接”，洋文叫做“Keep-Alive”或“Persistent Connection”）

假设有一个网页，里面包含好多图片，还包含好多 外部的 CSS 文件和 JS 文件。在“短连接”的模式下，浏览器会先发起一个 TCP 连接，拿到该网页的 HTML 源代码（拿到 HTML 之后，这个 TCP 连接就关闭了）。然后，浏览器开始分析这个网页的源码，知道这个页面包含很多外部资源（图片、CSS、JS）。然后针对 每一个 外部资源，再分别发起一个个 TCP 连接，把这些文件获取到本地（同样的，每抓取一个外部资源后，相应的 TCP 就断开）
相反，如果是“长连接”的方式，浏览器也会先发起一个
TCP 连接去抓取页面。但是抓取页面之后，该 TCP 连接并不会立即关闭，而是暂时先保持着（所谓的“Keep-Alive”）。然后浏览器分析 HTML 源码之后，发现有很多外部资源，就用刚才那个 TCP 连接去抓取此页面的外部资源。

在 HTTP 1.0 版本，默认使用的是“短连接”（那时候是 Web 诞生初期，网页相对简单，“短连接”的问题不大）.

到了1995年底开始制定 HTTP 1.1 草案的时候，网页已经开始变得复杂（网页内的图片、脚本越来越多了）。这时候再用短连接的方式，效率太低下了（因为建立 TCP 连接是有“时间成本”和“CPU 成本”滴）。所以，在 HTTP 1.1 中，默认采用的是“Keep-Alive”的方式。

七、一些术语

资源（resource）

Web资源是使用URL指向的Web内容。

  • 内容可以是静态的，如：文本文件、HTML文件、JPEG文件。
  • 或者是动态的内容。如：摄像头的实时采集软件生成的动态影像，用户填写的电子网站订单。

资源类型

Web服务器会为所有HTTP资源赋予一个类型，以便于HTTP软件处理消息主体。如，用 text/html 标记 html。可以再看两个案例：

  • text/plain :ASCII文本文档
  • image/jpeg :JPEG版本的图片

非常多的资源类型和文本标记的对应关系，一起构成了一个超长的清单，并且由RFC 2045标准化。此标准被称为MIME。MIME是Multipurpose Internet Mail Extension的缩写。虽然名称很长，但是含义简单，就是用来指定消息内的实体类型的。之所以有Mail字样，是因为最初设计是为了Mail的异构系统交换文档的。

资源标示符

URL是一种资源位置标示方法。URL描述了一个资源在服务器上的位置。这就是一个合法的URL：example.com/part/index.…

  • 第一部分：方案(scheme)。指明了访问资源所使用的协议类型。这部分通常是HTTP协议(http://)。
  • 第二部分：服务器地址(比如，example.com）。
  • 其余部分指定了Web服务器上的某个资源(比如，/part/index.htm)。

当在地址栏输入此资源名并回车后，用户代理会把URL解析，把必要的信息以HTTP协议的要求，打入请求消息内。以www.example.com/index.html，… 

1
2
3
复制代码GET index.html HTTP/1.1
host:www.example.com
空行

打开到www.example.com的tcp连接，并发送此请求消息给服务器，然后等待服务器响应并解析显示给用户。

更多URL、URI、URN详细推荐阅读：《你知道URL、URI和URN三者之间的区别吗？》

HTTP事务

一个HTTP事务由一条请求消息和一个响应消息构成。

HTTP方法

HTTP支持几种不同的请求命令，这些命令被称为HTTP方法(HTTP method)。每条HTTP请求报文都包含一个方法。

状态码

每条HTTP响应消息返回时都会携带一个状态码。状态码是一个三位数字的代码，告知客户端请求是否成功，或者是需要采取其他行动。

消息

从Web客户端发往Web服务器的HTTP报文称为请求消息。从服务器发往客户端的消息称为响应消息。HTTP报文包括三部分： 

1
2
3
复制代码起始行
首部字段 
主体

如发送一个hello.htm 的资源给客户端，请求消息是： 

1
复制代码GET /hello.html HTTP/1.1

请求消息只有起始行，指明使用的HTTP方法、资源的URL，以及协议的版本。没有首部字段和主体。

响应消息为： 

1
2
3
4
5
6
7
8
复制代码HTTP/1.1 200 OK
X-Powered-By: Express
Content-Type: text/html; charset=utf-8
Content-Length: 22
ETag: W/"16-FmHX0hamHjYkHeAP/7PfzA"
Date: Thu, 03 Dec 2015 09:54:01 GMT
Connection: close
<h1>Hello, World!</h1>

这个消息第一行为起始行，指明协议版本、状态码（200表示成功）和状态说明（OK）。接下来一直到空行之间都是首部字段，用来说明服务器、资源类型、内容长度、生成文档时间等。空行后就是主体，这里就是一个html文件的内容。实际上，主体可以承载任何内容，而不限于文本。

总结

HTTP是一个简单快速、灵活、无连接、无状态的超文本传输协议。

HTTP是很简单可扩展的一种协议。结合了轻松添加头部信息能力的Client-server结构使得HTTP可以和Web的功能扩充一同发展。

即使HTTP/2为了提高性能把HTTP报文嵌到帧中这一举措增加了复杂度，但是从Web应用的角度来看，报文的基本结构是没有变化的，从HTTP/1.0发布起就是相同的。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%