来源： Docker入门——理解Docker的核心概念 – 南瓜慢说 – 博客园

1 前言

相信不少人听过这么一句话：

人类的本质是复读机。

在软件开发领域也一样，我们总是想寻找更好地方式复制优秀的逻辑或系统。最核心的方法是抽取通用逻辑和组件，把差异化的东西接口化或配置化，达到复用的效果。如Java的Build Once, Run Everywhere，还有Spring的强大的抽象能力。这是应用层面的复用，Docker则在系统层面作文章，让我们可以快速复制一个系统（如CentOS）或一个服务（如Kafka）。

2 Docker的便利与优势

利用Docker，我们可以很快的使用别人已经建立好的镜像来发布一个完整的系统或某个组件。它至少提供了以下便利：

• 提供一致的运行环境。从同一个镜像文件创建容器，应用运行环境相同，保持开发环境、测试环境和生产环境的一致。这能减少许多因环境差异和配置差异带来的问题。测试提了Bug，开发再也不能第一时间回：是你环境没配好吧？是你不会用吧？
• 弹性的系统。因Docker可快速启动/停止，使系统能根据请求量/数据量动态的改变运行的服务数量，以提供伸缩可变的系统服务。
• 微服务开发。容器可以非常轻量级，而且可快速动态启停，非常适用于微服务架构。一台物理机器也能运行多个容器，不一定需要物理集群。

复制一个系统，我们可以通过增加一台物理机，或者通过虚拟机技术运行多个系统，现在有了Docker，还可以通过它来启动一个系统。与其它方式相比，Docker有以下优势：

• 启动速度快，秒级的启动速度；
• 性能好，近似物理机的性能，不会有过多资源损失和性能浪费；
• 体量小，镜像可以做得更小（MB级），不像虚拟机的几GB；
• 跨平台，能在Linux/Unix/Mac/Windows系统下运行；
• 利于CI/CD，有成熟的技术实践；
• 社区活跃，有大公司背书，应用广泛，镜像资源丰富。

3 Docker核心概念

3.1 镜像Image

说起镜像，不由想起当年拿着U盘捣鼓各种系统的日子。那时会找各种系统的iso文件，下载速度还特别慢，几GB的文件呢。那些iso文件，就是镜像文件。但这些镜像文件是相对于物理机系统或虚拟机技术而言的，而不是Docker的镜像文件。

对于Docker而言，镜像会被统一管理，在本地有特定的地方存放镜像，不同的系统位置不一样。一般而言，是无须自己管理镜像文件的，Docker会有效地管理和组织。列出所有镜像命令如下：

docker images
或docker image ls

Docker由镜像启动容器，就像通过iso文件安装启动系统一样。镜像是通用的，因此也是可以共享的。一般我们可以通过复用别人做好的优秀镜像来提高开发效率。我们只需要在别人镜像的基础上做定制开发即可。例如我们可拉取一个带JDK的Linux镜像，然后把自己的Java应用添加上去，形成自己新的镜像。

为了提高复用率与速度，我们将镜像分层，如下图所示：

如镜像B是基于镜像A打包而成的，则镜像B比镜像A多一层。镜像B包含了镜像A的所有层级。这样做的好处是，不用管理一个大的镜像，而管理层级变化。假如本机已经下载了镜像E，则本机已经有（A, B, C, E），当需要拉取F的时候，不再需要拉取（A, B）了。这利用了Docker的缓存技术，另外，在构建新镜像时，同样也使用了缓存。

标签Tag是镜像的重要概念，一般用于标记版本号，对于同一个镜像源名，可以有多个标签，如redis:5.0.8、redis:latest，5.0.8和latest都是标签名，默认使用latest。

3.2 容器Container

有了镜像后，就可以创建容器了。启动一个容器，就像启动一个进程一样快速，可以通过docker run命令启动，如下：

$ docker run hello-world

Hello from Docker!
This message shows that your installation appears to be working correctly.

To generate this message, Docker took the following steps:
 1. The Docker client contacted the Docker daemon.
 2. The Docker daemon pulled the "hello-world" image from the Docker Hub.
    (amd64)
 3. The Docker daemon created a new container from that image which runs the
    executable that produces the output you are currently reading.
 4. The Docker daemon streamed that output to the Docker client, which sent it
    to your terminal.

To try something more ambitious, you can run an Ubuntu container with:
 $ docker run -it ubuntu bash

Share images, automate workflows, and more with a free Docker ID:
 https://hub.docker.com/

For more examples and ideas, visit:
 https://docs.docker.com/get-started/

容器提供了软件硬件环境，会消耗物理机资源，同时它还具有状态，相互隔离。可以从一个镜像启动多个不同的容器，如从Ubuntu镜像启动多个Ubuntu系统。可以通过命令docker ps查看当前运行的容器，已经停止的容器不会显示出来。当容器停止时，容器文件并不会消失，可以通过docker ps -a查看所有容器。

可以简单理解镜像与容器的关系：

镜像是容器的模板，是没运行没状态的文件，启动容器需要镜像。容器是运行着的、带状态的相互隔离的服务。可以由一个镜像启动多个容器，也可以从一个容器创建一个镜像，但这并不说明两者是可逆的相互转换。

3.3 仓库Repository

仓库很容易理解，就是存放镜像的地方。既然镜像是通用的，可以共享，那就需要一个共享的地方，仓库承担着这样一个责任。这跟maven、npm等是同样的道理。最大、最常用的仓库当然是官方仓库Docker Hub，但国内访问速度也相当感人，可以通过使用国内仓库解决这个问题，如使用阿里的仓库。这跟GitHub、maven也是何其相似。

我们可以从仓库拉取别人的镜像，也可以把自己构建的镜像推送到仓库上。

4 总结

本次主要讲解一下Docker的概念，实践与命令以后再一一道来。

来源： 如何使用ABP进行软件开发之基础概览 – 溪源More – 博客园

ABP框架简述

1）简介

在.NET众多的技术框架中，ABP框架（本系列中指aspnetboilerplate项目）以其独特的魅力吸引了一群优秀开发者广泛的使用。

在该框架的赋能之下，开发者可根据需求通过官方网站【https://aspnetboilerplate.com/Templates】选择下载例如Vue/AngluarJS/MVC等不同类型的模板项目，轻松加入ABP开发者的队伍中，尽享基于ABP开发带来的乐趣。

ABP开发框架也提供了丰富的文档，能够为开发者带来许多便捷。目前ABP的文档网站为：

官方文档：https://aspnetboilerplate.com/Pages/Documents

文档库不可谓不全，加上国内众多的ABP开发者参与的活跃的技术圈子，使得学习成本只是在第一个项目中比较高，后期将会越来越平滑。

2）现状

当然，目前ABP的框架开发者和社区已经把更多的精力投入到了ABP.VNEXT开发框架，这个新框架以其DDD+微服务+模块化的理念获得了大量拥趸，使ABP框架的开发优先级已经开始逐渐降低。

但这是因为ABP框架的功能已经成熟稳定，且ABP是一种增量式的架构设计，开发者在熟练掌握这种框架后，可以根据自己的需要进行方便的扩展，使其成为小项目架构选型中一种不错的备选方案。

当然，也存在一些弊端。例如由于ABP被称为.NET众多开发框架中面向领域驱动设计的最佳实践，而囿于领域驱动设计本身不低的门槛，使得学习的过程变得看起来非常陡峭；

除此之外，ABP也广泛使用了目前ASP.NET/ASP.NET Core框架的大量比较新的特性，对于不少无法由于各种原因无法享受.NET技术飞速发展红利的传统开发者来说，无形中也提高了技术门槛。

3）综述

在这个系列中，本文计划分成三篇来介绍ABP框架，第一篇介绍ABP的基础概览，介绍基础知识，第二篇介绍ABP的模式实践，第三篇，试图介绍如何从更传统的三层甚至是单层+SQL的单层架构，如何迁移到ABP框架。

（毕竟。。.NET遗留应用实在是太多了，拯救或不拯救？）

代码结构结构

基本文件夹简述

当我们通过ABP模板项目的官方网站下载一个项目后，我们所获得的代码包的结构如下图所示，其中：

• vue为使用iview框架构建的管理系统基本模板，该脚手架使用了yarn作为包管理器，并集成了vuex/axios等常用框架，并提供了用户，租户，权限三个基本功能的示例代码，开发者只需发挥聪明才智就能快速的通过该框架入手前端项目。
• （当然，该项目广泛使用了typescript+面向对象的设计，似乎前端开发者。。普遍不擅长面向对象开发？）
• aspnet-core则是一个完整的ASP.NETcore项目的快速开发脚手架。该脚手架集成了docker打包于一体，并包含基本的单元测试示例，使用了identity作为权限控制单元，使用swagger作为接口文档管理工具，集成了efcore、jwt等常用组件，对于开发者来说，基本上算是开箱即用了。

前端vue项目

打开vue文件夹之后，该项目的基本目录如下图所示。（src文件夹）

lib文件夹

定义了与abp+vue脚手架项目的基础组件和常见类库，封装了一系列基本方法。例如权限控制，数据请求，菜单操作，SignalR等基础组件的用法。

router文件夹

定义了vue项目的路由规则，其中index.ts文件是项目的入口，router.ts文件定义了vue文件的路由规则。

store文件夹

由于本项目使用了vuex框架，所以我们可以来看看对于store文件夹的介绍。

在vuex框架中：

每一个 Vuex 应用的核心就是 store（仓库）。“store”基本上就是一个容器，它包含着你的应用中大部分的状态 (state)。
Vuex 和单纯的全局对象有以下两点不同：
Vuex 的状态存储是响应式的。当 Vue 组件从 store 中读取状态的时候，若 store 中的状态发生变化，那么相应的组件也会相应地得到高效更新。
你不能直接改变 store 中的状态。改变 store 中的状态的唯一途径就是显式地提交 (commit) mutation。这样使得我们可以方便地跟踪每一个状态的变化，从而让我们能够实现一些工具帮助我们更好地了解我们的应用。

即vuex框架中，将原来的请求链路，抽象化为状态的变化，通过维护状态，使得数据的管理更加便捷，也易于扩展。

views文件夹

定义了登录、首页、用户、角色、租户的基本页面，并提供了新增、查看、编辑、删除的代码示例。

综上，该项目是一个结构清晰，逻辑缜密的前端框架，可以作为常见管理系统的脚手架。

后端项目

简介

后端项目是一个遵循了领域驱动设计的分层，同时又符合Robert Martin在《代码整洁之道》提出的【整洁架构】。

领域驱动设计简介

在领域驱动设计的分层设计中，共有四个功能分层，分别是：

表示层（Presentation Layer）：为用户提供接口，使用应用层实现用户交互。

应用层（Application Layer）：介于用户层和领域层之间，协调用户对象，完成对应的任务。

领域层（Domain Layer）：包含业务对象和规则，是应用程序的心脏。

基础设施层（Infrastructure Layer）：提供高层级的通用技术功能，主要使用第三方库完成。

在后文中，基于abp对领域驱动设计的功能分层将进行多次、详细叙述，本小节不再赘述。

整洁架构简介

整洁架构是由Bob大叔提出的一种架构模型，来源于《整洁架构》这本书，顾名思义，其目的并不是为了介绍这一种优秀的架构本身，而是介绍如何设计一种整洁的架构，使得代码结构易于维护。

（整洁架构就是这样一个洋葱，所以也有人称它为“洋葱”架构）

1. 依赖规则(Dependency Rule)

用一组同心圆来表示软件的不同领域。一般来说，越深入代表你的软件层次越高。外圆是战术是实现机制(mechanisms)，内圆的是核心原则(policy)。

Policy means the application logic.

Mechanism means the domain primitives.

使此体系架构能够工作的关键是依赖规则。这条规则规定软件模块只能向内依赖，而里面的部分对外面的模块一无所知，也就是内部不依赖外部，而外部依赖内部。同样，在外面圈中使用的数据格式不应被内圈中使用，特别是如果这些数据格式是由外面一圈的框架生成的。我们不希望任何外圆的东西会影响内圈层

2. 实体 (Entities)

实体封装的是整个企业范围内的业务核心原则(policy)，一个实体能是一个带有方法的对象，或者是一系列数据结构和函数，只要这个实体能够被不同的应用程序使用即可。

如果你没有编写企业软件，只是编写简单的应用程序，这些实体就是应用的业务对象，它们封装着最普通的高级别业务规则，你不能希望这些实体对象被一个页面的分页导航功能改变，也不能被安全机制改变，操作实现层面的任何改变不能影响实体层，只有业务需求改变了才可以改变实体

3. 用例 (Use case)

在这个层的软件包含只和应用相关的业务规则，它封装和实现系统的所有用例，这些用例会混合各种来自实体的各种数据流程，并且指导这些实体使用企业规则来完成用例的功能目标。

我们并不期望改变这层会影响实体层. 我们也不期望这层被更外部如数据库 UI或普通框架影响，而这也正是我们分离出这一层来的原因所在。

然而，应用层面的操作改变将会影响到这个用例层，如果需求中用例发生改变，这个层的代码就会随之发生改变。所以可以看到，这一层是和应用本身紧密相关的

4. 接口适配器 (Interface Adapters)

这一层的软件基本都是一些适配器，主要用于将用例和实体中的数据转换为外部系统如数据库或Web使用的数据，在这个层次，可以包含一些GUI的MVC架构，表现视图 控制器都属于这个层，模型Model是从控制器传递到用例或从用例传递到视图的数据结构。

通常在这个层数据被转换，从用例和实体使用的数据格式转换到持久层框架使用的数据，主要是为了存储到数据库中，这个圈层的代码是一点和数据库没有任何关系，如果数据库是一个SQL数据库， 这个层限制使用SQL语句以及任何和数据库打交道的事情。

5. 框架和驱动器

最外面一圈通常是由一些框架和工具组成，如数据库Database, Web框架等. 通常你不必在这个层不必写太多代码，而是写些胶水性质的代码与内层进行粘结通讯。

这个层是细节所在，Web技术是细节，数据库是细节，我们将这些实现细节放在外面以免它们对我们的业务规则造成影响伤害

ABP的分层实现

在ABP项目中，层次划分如下。

1. 应用层（Application项目）

在领域驱动设计的分层式架构中，应用层作为应用系统的北向网关，对外提供业务外观的功能。在Abp模板项目中,Application项目也是编写主要用例代码的位置，开发者们在此定义与界面有关的数据行为，实现面向接口的开发实践。

应用服务层包含应用服务，数据传输单元，工作单元等对象。

• Application Service

为面向用户界面层实现业务逻辑代码。例如需要为某些界面对象组装模型，通常会定义ApplicationService，并通过DTO对象，实现与界面表现层的数据交换。

• Data Transfer Object (DTO)

最常见的数据结构为DTO（数据传输对象），这是来源于马丁弗勒在《企业架构应用模式》中提到的名词，其主要作用为：

是一种设计模式之间传输数据的软件应用系统。 数据传输目标往往是数据访问对象从数据库中检索数据。

在ABP的设计中，有两种不同类型的DTO，分别是用于新增、修改、删除的Input DTO，和用于查询的Output DTO。

• Unit of Work：

工作单元。工作单元与事务类似，封装了一系列原子级的数据库操作。

2. 核心层（Core项目）

核心层包含领域实体、值对象、聚合根，以及领域上下文实现。

• Entity(实体）：

实体有别于传统意义上大家所理解的与数据库字段一一匹配的实体模型，在领域驱动设计中,虽然实体同样可能持久化到数据库，但实体包含属性和行为两种不同的抽象。

例如，如果有一个实体为User，其中有一个属性为Phone，数据为086-132xxxxxxxx，我们有时需要判断该手机号码的国际代号，可能会添加一个新的判定 GetNationCode()，可以通过从Phone字段中取出086来实现，这就是一种通俗意义上的行为。

• Value Object（值对象）:

值对象无需持久化到数据库，往往是从其他实体或聚合中“剥离”出来的与某些聚合具备逻辑相关性或语义相关性的对象，有时值对象甚至只有个别属性。

例如，上述实体，包含Phone字段，我们可以将整个Phone“剥离”为一个Telephone对象，该对象可包含PhoneNumber和NationCode字段。

public class User
{
     public Telephone Phone{public get;private set;}
}
public class Telephone
{
    public string  PhoneNumber {get;set;}
     public string NationCode  {get;set;}
}

• Aggregate & Aggregate Root（聚合，聚合根）：

聚合是业务的最小工作单元，有时，一个实体就是一个小聚合，而为聚合对外提供访问机制的对象，就是聚合根。

在领域驱动设计中，识别聚合也是一件非常重要的工作，有一组系统的方法论可以为我们提供参考。

当然，事实上识别领域对象，包括且不限定于识别聚合、值对象、实体识别该对象的行为或（方法）本身是一件需要经验完成的工作，有时需要UML建模方法的广泛参与。

有时，我们会习惯于通过属性赋值完成梭代码的过程，从而造成领域行为流失在业务逻辑层的问题，那么或许可以采取这样的方法：

1、对象的创建，使用构造函数赋值，或工厂方法创建。

2、将所有对于属性的访问级别都设置为

public string Phone{public get;private set;}

然后再通过一个绑定手机号码的方法，来给这个对象设置手机号码。

public string BindPhone(string phone)
{
}

将所有一切涉及到对Phone的操作，都只能通过规定的方法来赋值，这样可以实现我们开发过程中，无意识的通过属性赋值，可能导致的“领域行为”丢失的现象发生。
这种方式可以使得对对象某些属性的操作，只能通过唯一的入口完成，符合单一职责原则的合理运用，如果要扩展方法，可以使用开闭原则来解决。

但是，采用这种方式，得尽量避免出现：SetPhone(string phone) 这样的方法出现，毕竟这样的方法，其实和直接的属性赋值，没有任何区别。

• Repository（仓储）

仓储封装了一系列对象数据库操作的方法，完成对象从数据库到对象的转换过程。在领域驱动设计中，一个仓储往往会负责一个聚合对象从数据库到创建的全过程。

• Domain Service（领域服务）

领域服务就是“实干家”，那些不适合在领域对象中出现，又不属于对象数据库操作的方法，又与领域对象息息相关的方法，都可以放到领域服务中实现。

• Specification（规格定义）

规范模式是一种特殊的软件设计模式，通过使用布尔逻辑将业务规则链接在一起，可以重新组合业务规则。

实际上，它主要用于为实体或其他业务对象定义可重用的过滤器。

3. 其他基础设施（EntityFrameworkCore，Web.Core,Web.Host项目)

EntityFrameworkCore负责定义数据库上下文和对EFCore操作的一系列规则、例如种子数据的初始化等。

Web.Core：定义了应用程序的外观和接口。虽然从表面上看，Web.Core定义了作为Web访问入口的控制器方法和登录验证的逻辑，看起来像是用户表现层的东西，但是仔细想想，这些东西，何尝不是一种基础设施？

Web.Host：定义WEB应用程序的入口。

总结

本文简述了ABP框架的前后端项目的分层结构，通过了解这些结构，将有助于我们在后续的实战中更快入手，为应用开发插上翅膀。

来源： 用户画像产品化——从零开始搭建实时用户画像(六) – 独孤风 – 博客园

在开发好用户标签以后，如何将标签应用到实际其实是一个很重要的问题。只有做好产品的设计才能让标签发挥真正的价值，本文将介绍用户画像的产品化过程。

一、标签展示

首先是标签展示功能，这个主要供业务人员和研发人员使用，是为了更直观的看见整个的用户标签体系。

不同的标签体系会有不同的层级，那么这个页面的设计就需要我们展示成树状的结构，方便以后的扩展。

在最后一个层级，比如自然性别，可以设计一个统计页面，在进入页面后，可以展示相应的数据统计情况，

可以更直观看见标签中值得比例，也可以为业务提供好的建议，另外可以对标签的具体描述进行展示，起到一个说明的作用，还可以展示标签按天的波动情况，观察标签的变化情况。

这一部分的数据来源呢？之前也提到过，这些标签的元数据信息都存在mySQL中，方便我们查询。

所以树状图和标签描述信息需要去mySQL中获取，而比例等图表数据则是从Hbase，Hive中查询获取的，当然也有直接通过ES获取的。但是每天的标签历史波动情况，还是要通过每天跑完标签后存在mySQL中作为历史记录进行展示。

二 、标签查询

这一功能可以提供给研发人员和业务人员使用。

标签查询功能其实就是对用户进行全局画像的过程，对于一个用户的全量标签信息，我们是需要对其进行展示的。

输入用户id后，可以查看该用户的属性信息、行为信息、风控属性等信息。从多方位了解一个具体的用户特征。

这些已经是标签的具体信息了，由于是对单一id的查找，从hive中获取会造成查询速度的问题，所以我们更建议从Hbase或者ES中查询获取，这样查询效率和实时性都能获得极大的提升。

三、标签管理

这一功能是提供给研发人员使用的。

对于标签，不能每一次新增一个标签都进行非常大改动，这样是非常耗费人力的，所以必须要有可以对标签进行管理的功能。

这里定义了标签的基本信息，开发方式，开发人员等等，在完成标签的开发以后，直接在此页面对标签进行录入，就可以完成标签的上线工作，让业务人员可以对标签进行使用。

新增和编辑标签的页面，可以提供下拉框或者输入框提供信息录入的功能。

之前已经提到过，这些标签的元数据信息都保存在了Mysql中，只要完成对其的新增和修改就可以了。

四、用户分群

作为用户画像最核心的功能，用户分群功能。是用户画像与业务系统建立联系的桥梁，也是用户画像的价值所在。

这项功能主要供业务人员使用。

此功能允许用户自定义的圈定一部分人员，圈定的规则就是对于标签的条件约束。

在圈定好人群以后，可以对这部分人群提供与业务系统的外呼系统，客服系统，广告系统，Push系统的交互，达到真正的精细化运营的目的。

对于标签规则的判断，需要将记录好的规则存储于Mysql中，在进行人群计算时又需要将规则解析成可计算的逻辑。不管是解析成Sql或者其他的查询语言都难度巨大，这对于研发是一个非常大的挑战。

在此功能中，还可以增加人群对比的功能，对不同人群的不同标签进行圈定，对比。这对于查询性能也是一个巨大的考验。

但是，用户分群功能作为用户画像的核心是我们必须要实现的。对于技术架构，Hbase更擅长与KV形式的查询，对于多维度查询性能较差，所以可以采取ES索引，在ES查询出Hbase的Rowkey，再去查询Hbase的方式。也有很多公司选择整体迁移到ES中完成此项工作。那么ES可以胜任这项工作吗？

下一章，我们来聊一聊如何用ES来实现用户分群，未完待续~

参考文献

《用户画像：方法论与工程化解决方案》

更多实时数据分析相关博文与科技资讯，欢迎关注 “实时流式计算” 获取用户画像相关资料 请关注 “实时流式计算” 回复 “用户画像”

来源： 你真的了解字典(Dictionary)吗? – 码农阿宇 – 博客园

从一道亲身经历的面试题说起

半年前,我参加我现在所在公司的面试,面试官给了一道题,说有一个Y形的链表,知道起始节点,找出交叉节点.

为了便于描述,我把上面的那条线路称为线路1,下面的称为线路2.

思路1#

先判断线路1的第一个节点的下级节点是否是线路2的第一个节点,如果不是,再判断是不是线路2的第二个,如果也不是,判断是不是第三个节点,一直到最后一个.
如果第一轮没找到,再按以上思路处理线路一的第二个节点,第三个,第四个… 找到为止.
时间复杂度n²,相信如果我用的是这种方法,可肯定被Pass了.

思路2#

首先,我遍历线路2的所有节点,把节点的索引作为key,下级节点索引作为value存入字典中.
然后,遍历线路1中节点,判断字典中是否包含该节点的下级节点索引的key,即dic.ContainsKey((node.next) ,如果包含,那么该下级节点就是交叉节点了.
时间复杂度是n.
那么问题来了,面试官问我了,为什么时间复杂度n呢?你有没有研究过字典的ContainsKey这个方法呢?难道它不是通过遍历内部元素来判断Key是否存在的呢?如果是的话,那时间复杂度还是n²才是呀?
我当时支支吾吾,确实不明白字典的工作原理,厚着面皮说 “不是的,它是通过哈希表直接拿出来的,不用遍历”,面试官这边是敷衍过去了,但在我心里却留下了一个谜,已经入职半年多了,欠下的技术债是时候还了.

带着问题来阅读

在看这篇文章前,不知道您使用字典的时候是否有过这样的疑问.

1. 字典为什么能无限地Add呢?
2. 从字典中取Item速度非常快,为什么呢?
3. 初始化字典可以指定字典容量,这是否多余呢?
4. 字典的桶buckets 长度为素数,为什么呢?

不管您以前有没有在心里问过自己这些问题,也不管您是否已经有了自己得答案,都让我们带着这几个问题接着往下走.

从哈希函数说起

什么是哈希函数?
哈希函数又称散列函数,是一种从任何一种数据中创建小的数字“指纹”的方法。
下面,我们看看JDK中Sting.GetHashCode()方法.

public int hashCode() {
        int h = hash;
 //hash default value : 0 
        if (h == 0 && value.length > 0) {
 //value : char storage
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

可以看到,无论多长的字符串,最终都会返回一个int值,当哈希函数确定的情况下,任何一个字符串的哈希值都是唯一且确定的.
当然,这里只是找了一种最简单的字符数哈希值求法,理论上只要能把一个对象转换成唯一且确定值的函数,我们都可以把它称之为哈希函数.
这是哈希函数的示意图.

所以,一个对象的哈希值是确定且唯一的!.

字典

如何把哈希值和在集合中我们要的数据的地址关联起来呢?解开这个疑惑前我来看看一个这样不怎么恰当的例子:

有一天,我不小心干了什么坏事,警察叔叔没有逮到我本人,但是他知道是一个叫阿宇的干的,他要找我肯定先去我家,他怎么知道我家的地址呢?他不可能在全中国的家庭一个个去遍历,敲门,问阿宇是你们家的熊孩子吗?

正常应该是通过我的名字,找到我的身份证号码,然后我的身份证上登记着我的家庭地址(我们假设一个名字只能找到一张身份证).

阿宇—–> 身份证(身份证号码,家庭住址)——>我家

我们就可以把由阿宇找到身份证号码的过程,理解为哈希函数,身份证存储着我的号码的同时,也存储着我家的地址,身份证这个角色在字典中就是 bucket,它起一个桥梁作用,当有人要找阿宇家在哪时,直接问它,准备错的,字典中,bucket存储着数据的内存地址(索引),我们要知道key对应的数据的内存地址,问buckets要就对了.

key—>bucket的过程 ~= 阿宇—–>身份证 的过程.

警察叔叔通过家庭住址找到了我家之后,我家除了住我,还住着我爸,我妈,他敲门的时候,是我爸开门,于是问我爸爸,阿宇在哪,我爸不知道,我爸便问我妈,儿子在哪?我妈告诉警察叔叔,我在书房呢.很好,警察叔叔就这样把我给逮住了.

字典也是这样,因为key的哈希值范围很大的,我们不可能声明一个这么大的数组作为buckets,这样就太浪费了,我们做法时HashCode%BucketSize作为bucket的索引.

假设Bucket的长度3,那么当key1的HashCode为2时,它数据地址就问buckets2要,当key2的HashCode为5时,它的数据地址也是问buckets2要的.

这就导致同一个bucket可能有多个key对应,即下图中的Johon Smith和Sandra Dee,但是bucket只能记录一个内存地址(索引),也就是警察叔叔通过家庭地址找到我家时,正常来说,只有一个人过来开门,那么,如何找到也在这个家里的我的呢?我爸记录这我妈在厨房,我妈记录着我在书房,就这样,我就被揪出来了,我爸,我妈,我 就是字典中的一个entry.

如果有一天,我妈妈老来得子又生了一个小宝宝,怎么办呢?很简单,我妈记录小宝宝的位置,那么我的只能巴结小宝宝,让小宝宝来记录我的位置了.

既然大的原理明白了,是不是要看看源码,来研究研究代码中字典怎么实现的呢?

DictionaryMini

上次在苏州参加苏州微软技术俱乐部成立大会时,有幸参加了蒋金楠 老师讲的Asp .net core框架解密,蒋老师有句话让我印象很深刻,”学好一门技术的最好的方法,就是模仿它的样子,自己造一个出来”于是他弄了个Asp .net core mini,所以我效仿蒋老师,弄了个DictionaryMini

其源代码我放在了Github仓库,有兴趣的可以看看:https://github.com/liuzhenyulive/DictionaryMini

我觉得字典这几个方面值得了解一下:

1. 数据存储的最小单元的数据结构
2. 字典的初始化
3. 添加新元素
4. 字典的扩容
5. 移除元素

字典中还有其他功能,但我相信,只要弄明白的这几个方面的工作原理,我们也就恰中肯綮,他么问题也就迎刃而解了.

数据存储的最小单元(Entry)的数据结构#

   private struct Entry
        {
            public int HashCode;
            public int Next;
            public TKey Key;
            public TValue Value;
        }

一个Entry包括该key的HashCode,以及下个Entry的索引Next,该键值对的Key以及数据Vaule.

字典初始化#

        private void Initialize(int capacity)
        {
            int size = HashHelpersMini.GetPrime(capacity);
            _buckets = new int[size];
            for (int i = 0; i < _buckets.Length; i++)
            {
                _buckets[i] = -1;
            }

            _entries = new Entry[size];

            _freeList = -1;
        }

字典初始化时,首先要创建int数组,分别作为buckets和entries,其中buckets的index是key的哈希值%size,它的value是数据在entries中的index,我们要取的数据就存在entries中.当某一个bucket没有指向任何entry时,它的value为-1.
另外,很有意思得一点,buckets的数组长度是多少呢?这个我研究了挺久,发现取的是大于capacity的最小质数.

添加新元素#

  private void Insert(TKey key, TValue value, bool add)
        {
            if (key == null)
            {
                throw new ArgumentNullException();
            }
            //如果buckets为空,则重新初始化字典.
            if (_buckets == null) Initialize(0);
            //获取传入key的 哈希值
            var hashCode = _comparer.GetHashCode(key);
            //把hashCode%size的值作为目标Bucket的Index.
            var targetBucket = hashCode % _buckets.Length;
            //遍历判断传入的key对应的值是否已经添加字典中
            for (int i = _buckets[targetBucket]; i > 0; i = _entries[i].Next)
            {
                if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
                {
                    //当add为true时,直接抛出异常,告诉给定的值已存在在字典中.
                    if (add)
                    {
                        throw new Exception("给定的关键字已存在!");
                    }
                    //当add为false时,重新赋值并退出.
                    _entries[i].Value = value;
                    return;
                }
            }
            //表示本次存储数据的数据在Entries中的索引
            int index;
            //当有数据被Remove时,freeCount会加1
            if (_freeCount > 0)
            {
                //freeList为上一个移除数据的Entries的索引,这样能尽量地让连续的Entries都利用起来.
                index = _freeList;
                _freeList = _entries[index].Next;
                _freeCount--;
            }
            else
            {
                //当已使用的Entry的数据等于Entries的长度时,说明字典里的数据已经存满了,需要对字典进行扩容,Resize.
                if (_count == _entries.Length)
                {
                    Resize();
                    targetBucket = hashCode % _buckets.Length;
                }
                //默认取未使用的第一个
                index = _count;
                _count++;
            }
            //对Entries进行赋值
            _entries[index].HashCode = hashCode;
            _entries[index].Next = _buckets[targetBucket];
            _entries[index].Key = key;
            _entries[index].Value = value;
            //用buckets来登记数据在Entries中的索引.
            _buckets[targetBucket] = index;
        }

字典的扩容#

private void Resize()
        {
            //获取大于当前size的最小质数
            Resize(HashHelpersMini.GetPrime(_count), false);
        }
 private void Resize(int newSize, bool foreNewHashCodes)
        {
            var newBuckets = new int[newSize];
            //把所有buckets设置-1
            for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
            var newEntries = new Entry[newSize];
            //把旧的的Enties中的数据拷贝到新的Entires数组中.
            Array.Copy(_entries, 0, newEntries, 0, _count);
            if (foreNewHashCodes)
            {
                for (int i = 0; i < _count; i++)
                {
                    if (newEntries[i].HashCode != -1)
                    {
                        newEntries[i].HashCode = _comparer.GetHashCode(newEntries[i].Key);
                    }
                }
            }
            //重新对新的bucket赋值.
            for (int i = 0; i < _count; i++)
            {
                if (newEntries[i].HashCode > 0)
                {
                    int bucket = newEntries[i].HashCode % newSize;
                    newEntries[i].Next = newBuckets[bucket];
                    newBuckets[bucket] = i;
                }
            }

            _buckets = newBuckets;
            _entries = newEntries;
        }

移除元素#

        //通过key移除指定的item
        public bool Remove(TKey key)
        {
            if (key == null)
                throw new Exception();

            if (_buckets != null)
            {
                //获取该key的HashCode
                int hashCode = _comparer.GetHashCode(key);
                //获取bucket的索引
                int bucket = hashCode % _buckets.Length;
                int last = -1;
                for (int i = _buckets[bucket]; i >= 0; last = i, i = _entries[i].Next)
                {
                    if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
                    {
                        if (last < 0)
                        {
                            _buckets[bucket] = _entries[i].Next;
                        }
                        else
                        {
                            _entries[last].Next = _entries[i].Next;
                        }
                        //把要移除的元素置空.
                        _entries[i].HashCode = -1;
                        _entries[i].Next = _freeList;
                        _entries[i].Key = default(TKey);
                        _entries[i].Value = default(TValue);
                        //把该释放的索引记录在freeList中
                        _freeList = i;
                        //把空Entry的数量加1
                        _freeCount++;
                        return true;
                    }
                }
            }

            return false;
        }

我对.Net中的Dictionary的源码进行了精简,做了一个DictionaryMini,有兴趣的可以到我的github查看相关代码.
https://github.com/liuzhenyulive/DictionaryMini

答疑时间

字典为什么能无限地Add呢#

向Dictionary中添加元素时,会有一步进行判断字典是否满了,如果满了,会用Resize对字典进行自动地扩容,所以字典不会向数组那样有固定的容量.

为什么从字典中取数据这么快#

Key–>HashCode–>HashCode%Size–>Bucket Index–>Bucket–>Entry Index–>Value
整个过程都没有通过遍历来查找数据,一步到下一步的目的性时非常明确的,所以取数据的过程非常快.

初始化字典可以指定字典容量,这是否多余呢#

前面说过,当向字典中插入数据时,如果字典已满,会自动地给字典Resize扩容.
扩容的标准时会把大于当前前容量的最小质数作为当前字典的容量,比如,当我们的字典最终存储的元素为15个时,会有这样的一个过程.
new Dictionary()——————->size:3
字典添加低3个元素—->Resize—>size:7
字典添加低7个元素—->Resize—>size:11
字典添加低11个元素—>Resize—>size:23

可以看到一共进行了三次次Resize,如果我们预先知道最终字典要存储15个元素,那么我们可以用new Dictionary(15)来创建一个字典.

new Dictionary(15)———->size:23

这样就不需要进行Resize了,可以想象,每次Resize都是消耗一定的时间资源的,需要把OldEnties Copy to NewEntries 所以我们在创建字典时,如果知道字典的中要存储的字典的元素个数,在创建字典时,就传入capacity,免去了中间的Resize进行扩容.

Tips:
即使指定字典容量capacity,后期如果添加的元素超过这个数量,字典也是会自动扩容的.

为什么字典的桶buckets 长度为素数#

我们假设有这样的一系列keys,他们的分布范围时K={ 0, 1,…, 100 },又假设某一个buckets的长度m=12,因为3是12的一个因子,当key时3的倍数时,那么targetBucket也将会是3的倍数.

        Keys {0,12,24,36,...}
        TargetBucket将会是0.
        Keys {3,15,27,39,...}
        TargetBucket将会是3.
        Keys {6,18,30,42,...}
        TargetBucket将会是6.
        Keys {9,21,33,45,...}
        TargetBucket将会是9.

如果Key的值是均匀分布的(K中的每一个Key中出现的可能性相同),那么Buckets的Length就没有那么重要了,但是如果Key不是均匀分布呢?
想象一下,如果Key在3的倍数时出现的可能性特别大,其他的基本不出现,TargetBucket那些不是3的倍数的索引就基本不会存储什么数据了,这样就可能有2/3的Bucket空着,数据大量第聚集在0,3,6,9中.
这种情况其实时很常见的。 例如，又一种场景，您根据对象存储在内存中的位置来跟踪对象,如果你的计算机的字节大小是4，而且你的Buckets的长度也为4,那么所有的内存地址都会时4的倍数,也就是说key都是4的倍数,它的HashCode也将会时4的倍数,导致所有的数据都会存储在TargetBucket=0(Key%4=0)的bucket中,而剩下的3/4的Buckets都是空的. 这样数据分布就非常不均匀了.
K中的每一个key如果与Buckets的长度m有公因子,那么该数据就会存储在这个公因子的倍数为索引的bucket中.为了让数据尽可能地均匀地分布在Buckets中,我们要尽量减少m和K中的key的有公因子出现的可能性.那么,把Bucket的长度设为质数就是最佳选择了,因为质数的因子时最少的.这就是为什么每次利用Resize给字典扩容时会取大于当前size的最小质数的原因.
确实,这一块可能有点难以理解,我花了好几天才研究明白,如果小伙伴们没有看懂建议看看这里.
https://cs.stackexchange.com/questions/11029/why-is-it-best-to-use-a-prime-number-as-a-mod-in-a-hashing-function/64191#64191

最后,感谢大家耐着性子把这篇文章看完,欢迎fork DictionaryMini进行进一步的研究,谢谢大家的支持.
https://github.com/liuzhenyulive/DictionaryMini

来源： ConcurrentDictionary并发字典知多少? – 码农阿宇 – 博客园

背景

在上一篇文章你真的了解字典吗?一文中我介绍了Hash Function和字典的工作的基本原理.
有网友在文章底部评论,说我的Remove和Add方法没有考虑线程安全问题.
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?redirectedfrom=MSDN&view=netframework-4.7.2
查阅相关资料后,发现字典.net中Dictionary本身时不支持线程安全的,如果要想使用支持线程安全的字典,那么我们就要使用ConcurrentDictionary了.
在研究ConcurrentDictionary的源码后,我觉得在ConcurrentDictionary的线程安全的解决思路很有意思,其对线程安全的处理对对我们项目中的其他高并发场景也有一定的参考价值,在这里再次分享我的一些学习心得和体会,希望对大家有所帮助.

Concurrent

ConcurrentDictionary是Dictionary的线程安全版本,位于System.Collections.Concurrent的命名空间下,该命名空间下除了有ConcurrentDictionary,还有以下Class都是我们常用的那些类库的线程安全版本.

BlockingCollection:为实现 IProducerConsumerCollection 的线程安全集合提供阻塞和限制功能。

ConcurrentBag:表示对象的线程安全的无序集合.

ConcurrentQueue:表示线程安全的先进先出 (FIFO) 集合。

如果读过我上一篇文章你真的了解字典吗?的小伙伴,对这个ConcurrentDictionary的工作原理应该也不难理解,它是简简单单地在读写方法加个lock吗?

工作原理

Dictionary#

如下图所示,在字典中,数组entries用来存储数据,buckets作为桥梁,每次通过hash function获取了key的哈希值后,对这个哈希值进行取余,即hashResult%bucketsLength=bucketIndex,余数作为buckets的index,而buckets的value就是这个key对应的entry所在entries中的索引,所以最终我们就可以通过这个索引在entries中拿到我们想要的数据,整个过程不需要对所有数据进行遍历,的时间复杂度为1.

ConcurrentDictionary#

ConcurrentDictionary的数据存储类似,只是buckets有个更多的职责,它除了有dictionary中的buckets的桥梁的作用外,负责了数据存储.

key的哈希值与buckets的length取余后hashResult%bucketsLength=bucketIndex,余数作为buckets的索引就能找到我们要的数据所存储的块,当出现两个key指向同一个块时,即上图中的John Smith和Sandra Dee他同时指向152怎么办呢?存储节点Node具有Next属性执行下个Node,上图中,node 152的Next为154,即我们从152开始找Sandra Dee,发现不是我们想要的,再到154找,即可取到所需数据.

由于官方原版的源码较为复杂,理解起来有所难度,我对官方源码做了一些精简,下文将围绕这个精简版的ConcurrentDictionary展开叙述.
https://github.com/liuzhenyulive/DictionaryMini

数据结构#

Node#

ConcurrentDictionary中的每个数据存储在一个Node中,它除了存储value信息,还存储key信息,以及key对应的hashcode

private class Node
        {
            internal TKey m_key;   //数据的key
            internal TValue m_value;  //数据值
            internal volatile Node m_next;  //当前Node的下级节点
            internal int m_hashcode;  //key的hashcode

            //构造函数
            internal Node(TKey key, TValue value, int hashcode, Node next)
            {
                m_key = key;
                m_value = value;
                m_next = next;
                m_hashcode = hashcode;
            }
        }

Table#

而整个ConcurrentDictionary的数据存储在这样的一个Table中,其中m_buckets的Index负责映射key,m_locks是线程锁,下文中会有详细介绍,m_countPerLock存储每个lock锁负责的node数量.

 private class Tables
        {
            internal readonly Node[] m_buckets;   //上文中提到的buckets
            internal readonly object[] m_locks;   //线程锁
            internal volatile int[] m_countPerLock;  //索格锁所管理的数据数量
            internal readonly IEqualityComparer<TKey> m_comparer;  //当前key对应的type的比较器

            //构造函数
            internal Tables(Node[] buckets, object[] locks, int[] countPerlock, IEqualityComparer<TKey> comparer)
            {
                m_buckets = buckets;
                m_locks = locks;
                m_countPerLock = countPerlock;
                m_comparer = comparer;
            }
        }

ConcurrentDictionary会在构造函数中创建Table,这里我对原有的构造函数进行了简化,通过默认值进行创建,其中DefaultConcurrencyLevel默认并发级别为当前计算机处理器的线程数.

        //构造函数
        public ConcurrentDictionaryMini() : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY, true,
            EqualityComparer<TKey>.Default)
        {
        }

        /// <summary>
        ///
        /// </summary>
        /// <param name="concurrencyLevel">并发等级,默认为CPU的线程数</param>
        /// <param name="capacity">默认容量,31,超过31后会自动扩容</param>
        /// <param name="growLockArray">时否动态扩充锁的数量</param>
        /// <param name="comparer">key的比较器</param>
        internal ConcurrentDictionaryMini(int concurrencyLevel, int capacity, bool growLockArray, IEqualityComparer<TKey> comparer)
        {
            if (concurrencyLevel < 1)
            {
                throw new Exception("concurrencyLevel 必须为正数");
            }

            if (capacity < 0)
            {
                throw new Exception("capacity 不能为负数.");
            }

            if (capacity < concurrencyLevel)
            {
                capacity = concurrencyLevel;
            }

            object[] locks = new object[concurrencyLevel];
            for (int i = 0; i < locks.Length; i++)
            {
                locks[i] = new object();
            }

            int[] countPerLock = new int[locks.Length];
            Node[] buckets = new Node[capacity];
            m_tables = new Tables(buckets, locks, countPerLock, comparer);

            m_growLockArray = growLockArray;
            m_budget = buckets.Length / locks.Length;
        }

方法#

ConcurrentDictionary中较为基础重点的方法分别位Add,Get,Remove,Grow Table方法,其他方法基本上是建立在这四个方法的基础上进行的扩充.

Add#

向Table中添加元素有以下亮点值得我们关注.

• 开始操作前会声明一个tables变量来存储操作开始前的m_tables,在正式开始操作后(进入lock)的时候,会检查tables在准备工作阶段是否别的线程改变,如果改变了,则重新开始准备工作并从新开始.
• 通过GetBucketAndLockNo方法获取bucket索引以及lock索引,其内部就是取余操作.

 private void GetBucketAndLockNo(
            int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount)
        {
            //0x7FFFFFFF 是long int的最大值 与它按位与数据小于等于这个最大值
            bucketNo = (hashcode & 0x7fffffff) % bucketCount;
            lockNo = bucketNo % lockCount;
        }

• 对数据进行操作前会从m_locks取出第lockNo个对象最为lock,操作完成后释放该lock.多个lock一定程度上减少了阻塞的可能性.
• 在对数据进行更新时,如果该Value的Type为允许原子性写入的,则直接更新该Value,否则创建一个新的node进行覆盖.

        /// <summary>
        /// Determines whether type TValue can be written atomically
        /// </summary>
        private static bool IsValueWriteAtomic()
        {
            Type valueType = typeof(TValue);

            //
            // Section 12.6.6 of ECMA CLI explains which types can be read and written atomically without
            // the risk of tearing.
            //
            // See http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-335.pdf
            //
            if (valueType.IsClass)
            {
                return true;
            }
            switch (Type.GetTypeCode(valueType))
            {
                case TypeCode.Boolean:
                case TypeCode.Byte:
                case TypeCode.Char:
                case TypeCode.Int16:
                case TypeCode.Int32:
                case TypeCode.SByte:
                case TypeCode.Single:
                case TypeCode.UInt16:
                case TypeCode.UInt32:
                    return true;

                case TypeCode.Int64:
                case TypeCode.Double:
                case TypeCode.UInt64:
                    return IntPtr.Size == 8;

                default:
                    return false;
            }
        }

该方法依据CLI规范进行编写,简单来说,32位的计算机,对32字节以下的数据类型写入时可以一次写入的而不需要移动内存指针,64位计算机对64位以下的数据可一次性写入,不需要移动内存指针.保证了写入的安全.
详见12.6.6 http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-335.pdf

 private bool TryAddInternal(TKey key, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue)
        {
            while (true)
            {
                int bucketNo, lockNo;
                int hashcode;

                //https://www.cnblogs.com/blurhkh/p/10357576.html
                //需要了解一下值传递和引用传递
                Tables tables = m_tables;
                IEqualityComparer<TKey> comparer = tables.m_comparer;
                hashcode = comparer.GetHashCode(key);

                GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, tables.m_buckets.Length, tables.m_locks.Length);

                bool resizeDesired = false;
                bool lockTaken = false;

                try
                {
                    if (acquireLock)
                        Monitor.Enter(tables.m_locks[lockNo], ref lockTaken);

                    //如果表刚刚调整了大小，我们可能没有持有正确的锁，必须重试。
                    //当然这种情况很少见
                    if (tables != m_tables)
                        continue;

                    Node prev = null;
                    for (Node node = tables.m_buckets[bucketNo]; node != null; node = node.m_next)
                    {
                        if (comparer.Equals(node.m_key, key))
                        {
                            //key在字典里找到了。如果允许更新，则更新该key的值。
                            //我们需要为更新创建一个node，以支持不能以原子方式写入的TValue类型，因为free-lock 读取可能同时发生。
                            if (updateIfExists)
                            {
                                if (s_isValueWriteAtomic)
                                {
                                    node.m_value = value;
                                }
                                else
                                {
                                    Node newNode = new Node(node.m_key, value, hashcode, node.m_next);
                                    if (prev == null)
                                    {
                                        tables.m_buckets[bucketNo] = newNode;
                                    }
                                    else
                                    {
                                        prev.m_next = newNode;
                                    }
                                }

                                resultingValue = value;
                            }
                            else
                            {
                                resultingValue = node.m_value;
                            }

                            return false;
                        }

                        prev = node;
                    }

                    //key没有在bucket中找到,则插入该数据
                    Volatile.Write(ref tables.m_buckets[bucketNo], new Node(key, value, hashcode, tables.m_buckets[bucketNo]));
                    //当m_countPerLock超过Int Max时会抛出OverflowException
                    checked
                    {
                        tables.m_countPerLock[lockNo]++;
                    }

                    //
                    // 如果m_countPerLock[lockNo] > m_budget，则需要调整buckets的大小。
                    // GrowTable也可能会增加m_budget，但不会调整bucket table的大小。.
                    // 如果发现bucket table利用率很低，也会发生这种情况。
                    //
                    if (tables.m_countPerLock[lockNo] > m_budget)
                    {
                        resizeDesired = true;
                    }
                }
                finally
                {
                    if (lockTaken)
                        Monitor.Exit(tables.m_locks[lockNo]);
                }

                if (resizeDesired)
                {
                    GrowTable(tables, tables.m_comparer, false, m_keyRehashCount);
                }

                resultingValue = value;
                return true;
            }
        }

Get#

从Table中获取元素的的流程与前文介绍ConcurrentDictionary工作原理时一致,但有以下亮点值得关注.

• 读取bucket[i]在Volatile.Read()方法中进行,该方法会自动对读取出来的数据加锁,避免在读取的过程中,数据被其他线程remove了.
• Volatile读取指定字段时，在读取的内存中插入一个内存屏障，阻止处理器重新排序内存操作，如果在代码中此方法之后出现读取或写入，则处理器无法在此方法之前移动它。

 public bool TryGetValue(TKey key, out TValue value)
        {
            if (key == null) throw new ArgumentNullException("key");

            // We must capture the m_buckets field in a local variable. It is set to a new table on each table resize.
            Tables tables = m_tables;
            IEqualityComparer<TKey> comparer = tables.m_comparer;
            GetBucketAndLockNo(comparer.GetHashCode(key), out var bucketNo, out _, tables.m_buckets.Length, tables.m_locks.Length);

            // We can get away w/out a lock here.
            // The Volatile.Read ensures that the load of the fields of 'n' doesn't move before the load from buckets[i].
            Node n = Volatile.Read(ref tables.m_buckets[bucketNo]);

            while (n != null)
            {
                if (comparer.Equals(n.m_key, key))
                {
                    value = n.m_value;
                    return true;
                }
                n = n.m_next;
            }

            value = default(TValue);
            return false;
        }

Remove#

Remove方法实现其实也并不复杂,类似我们链表操作中移除某个Node.移除节点的同时,还要对前后节点进行链接,相信一块小伙伴们肯定很好理解.

 private bool TryRemoveInternal(TKey key, out TValue value, bool matchValue, TValue oldValue)
        {
            while (true)
            {
                Tables tables = m_tables;

                IEqualityComparer<TKey> comparer = tables.m_comparer;

                int bucketNo, lockNo;

                GetBucketAndLockNo(comparer.GetHashCode(key), out bucketNo, out lockNo, tables.m_buckets.Length, tables.m_locks.Length);

                lock (tables.m_locks[lockNo])
                {
                    if (tables != m_tables)
                        continue;

                    Node prev = null;
                    for (Node curr = tables.m_buckets[bucketNo]; curr != null; curr = curr.m_next)
                    {
                        if (comparer.Equals(curr.m_key, key))
                        {
                            if (matchValue)
                            {
                                bool valuesMatch = EqualityComparer<TValue>.Default.Equals(oldValue, curr.m_value);
                                if (!valuesMatch)
                                {
                                    value = default(TValue);
                                    return false;
                                }
                            }
                            if (prev == null)
                                Volatile.Write(ref tables.m_buckets[bucketNo], curr.m_next);
                            else
                            {
                                prev.m_next = curr.m_next;
                            }

                            value = curr.m_value;
                            tables.m_countPerLock[lockNo]--;
                            return true;
                        }

                        prev = curr;
                    }
                }

                value = default(TValue);
                return false;
            }
        }

Grow table#

当table中任何一个m_countPerLock的数量超过了设定的阈值后,会触发此操作对Table进行扩容.

private void GrowTable(Tables tables, IEqualityComparer<TKey> newComparer, bool regenerateHashKeys,
            int rehashCount)
        {
            int locksAcquired = 0;
            try
            {
                //首先锁住第一个lock进行resize操作.
                AcquireLocks(0, 1, ref locksAcquired);

                if (regenerateHashKeys && rehashCount == m_keyRehashCount)
                {
                    tables = m_tables;
                }
                else
                {
                    if (tables != m_tables)
                        return;

                    long approxCount = 0;
                    for (int i = 0; i < tables.m_countPerLock.Length; i++)
                    {
                        approxCount += tables.m_countPerLock[i];
                    }

                    //如果bucket数组太空，则将预算加倍，而不是调整表的大小
                    if (approxCount < tables.m_buckets.Length / 4)
                    {
                        m_budget = 2 * m_budget;
                        if (m_budget < 0)
                        {
                            m_budget = int.MaxValue;
                        }

                        return;
                    }
                }

                int newLength = 0;
                bool maximizeTableSize = false;
                try
                {
                    checked
                    {
                        newLength = tables.m_buckets.Length * 2 + 1;
                        while (newLength % 3 == 0 || newLength % 5 == 0 || newLength % 7 == 0)
                        {
                            newLength += 2;
                        }
                    }
                }
                catch (OverflowException)
                {
                    maximizeTableSize = true;
                }

                if (maximizeTableSize)
                {
                    newLength = int.MaxValue;

                    m_budget = int.MaxValue;
                }

                AcquireLocks(1, tables.m_locks.Length, ref locksAcquired);

                object[] newLocks = tables.m_locks;

                //Add more locks
                if (m_growLockArray && tables.m_locks.Length < MAX_LOCK_NUMBER)
                {
                    newLocks = new object[tables.m_locks.Length * 2];
                    Array.Copy(tables.m_locks, newLocks, tables.m_locks.Length);

                    for (int i = tables.m_locks.Length; i < newLocks.Length; i++)
                    {
                        newLocks[i] = new object();
                    }
                }

                Node[] newBuckets = new Node[newLength];
                int[] newCountPerLock = new int[newLocks.Length];

                for (int i = 0; i < tables.m_buckets.Length; i++)
                {
                    Node current = tables.m_buckets[i];
                    while (current != null)
                    {
                        Node next = current.m_next;
                        int newBucketNo, newLockNo;
                        int nodeHashCode = current.m_hashcode;

                        if (regenerateHashKeys)
                        {
                            //Recompute the hash from the key
                            nodeHashCode = newComparer.GetHashCode(current.m_key);
                        }

                        GetBucketAndLockNo(nodeHashCode, out newBucketNo, out newLockNo, newBuckets.Length,
                            newLocks.Length);

                        newBuckets[newBucketNo] = new Node(current.m_key, current.m_value, nodeHashCode,
                            newBuckets[newBucketNo]);
                        checked
                        {
                            newCountPerLock[newLockNo]++;
                        }

                        current = next;
                    }
                }

                if (regenerateHashKeys)
                {
                    unchecked
                    {
                        m_keyRehashCount++;
                    }
                }

                m_budget = Math.Max(1, newBuckets.Length / newLocks.Length);

                m_tables = new Tables(newBuckets, newLocks, newCountPerLock, newComparer);
            }
            finally
            {
                ReleaseLocks(0, locksAcquired);
            }
        }

学习感悟

• lock[]:在以往的线程安全上,我们对数据的保护往往是对数据的修改写入等地方加上lock,这个lock经常上整个上下文中唯一的,这样的设计下就可能会出现多个线程,写入的根本不是一块数据,却要等待前一个线程写入完成下一个线程才能继续操作.在ConcurrentDictionary中,通过哈希算法,从数组lock[]中找出key的准确lock,如果不同的key,使用的不是同一个lock,那么这多个线程的写入时互不影响的.
• 写入要考虑线程安全,读取呢?不可否认,在大部分场景下,读取不必去考虑线程安全,但是在我们这样的链式读取中,需要自上而下地查找,是不是有种可能在查找个过程中,链路被修改了呢?所以ConcurrentDictionary中使用Volatile.Read来读取出数据,该方法从指定字段读取对象引用,在需要它的系统上，插入一个内存屏障，阻止处理器重新排序内存操作，如果在代码中此方法之后出现读取或写入，则处理器无法在此方法之前移动它。
• 在ConcurrentDictionary的更新方法中,对数据进行更新时,会判断该数据是否可以原子写入,如果时可以原子写入的,那么就直接更新数据,如果不是,那么会创建一个新的node覆盖原有node,起初看到这里时候,我百思不得其解,不知道这么操作的目的,后面在jeo duffy的博客中Thread-safety, torn reads, and the like中找到了答案,这样操作时为了防止torn reads(撕裂读取),什么叫撕裂读取呢?通俗地说,就是有的数据类型写入时,要分多次写入,写一次,移动一次指针,那么就有可能写了一半,这个结果被另外一个线程读取走了.比如说我把 刘振宇三个字改成周杰伦的过程中,我先把刘改成周了,正在我准备去把振改成杰的时候,另外一个线程过来读取结果了,读到的数据是周振宇,这显然是不对的.所以对这种,更安全的做法是先把周杰伦三个字写好在一张纸条上,然后直接替换掉刘振宇.更多信息在CLI规范12.6.6有详细介绍.
• checked和unckecked关键字.非常量的运算(non-constant)运算在编译阶段和运行时下不会做溢出检查,如下这样的代码时不会抛出异常的,算错了也不会报错。

int ten = 10;
int i2 = 2147483647 + ten;

但是我们知道,int的最大值是2147483647,如果我们将上面这样的代码嵌套在checked就会做溢出检查了.

checked
{
int ten = 10;
int i2 = 2147483647 + ten;
}

相反,对于常量,编译时是会做溢出检查的,下面这样的代码在编译时就会报错的,如果我们使用unckeck标签进行标记,则在编译阶段不会做移除检查.

int a = int.MaxValue * 2;

那么问题来了,我们当然知道checked很有用,那么uncheck呢?如果我们只是需要那么一个数而已，至于溢出不溢出的关系不大，比如说生成一个对象的HashCode，比如说根据一个算法计算出一个相对随机数，这都是不需要准确结果的,ConcurrentDictionary中对于m_keyRehashCount++这个运算就使用了unchecked,就是因为m_keyRehashCount是用来生成哈希值的,我们并不关心它有没有溢出.

• volatile关键字,表示一个字段可能是由在同一时间执行多个线程进行修改。出于性能原因，编译器\运行时系统甚至硬件可以重新排列对存储器位置的读取和写入。声明的字段volatile不受这些优化的约束。添加volatile修饰符可确保所有线程都能按照执行顺序由任何其他线程执行的易失性写入,易失性写入是一件疯狂的事情的事情:普通玩家慎用.

本博客所涉及的代码都保存在github中,Take it easy to enjoy it!
https://github.com/liuzhenyulive/DictionaryMini/blob/master/DictionaryMini/DictionaryMini/ConcurrentDictionaryMini.cs

来源： VS2017git 提交提示错误 Git failed with a fatal error. – 不见不散com – 博客园

具体错误信息：Git failed with a fatal error.
error: open(“ConsoleApp1/.vs/ConsoleApp1/v15/Server/SQLite3/db.lock”): Permission denied

fatal: Unable to process path ConsoleApp1/.vs/ConsoleApp1/v15/Server/SQLite3/db.lock

因为git上传要忽略vs文件， Git因致命错误而失败。权限被拒绝 无法处理的路径。

解决方法下：

1. 打开团队资源管理器，点击设置

2. 点击 储存库设置

3. 添加忽略文件

完成.

来源： Newbe.Claptrap – 一套以 “事件溯源” 和 “Actor 模式” 作为基本理论的服务端开发框架 | newbe

来源： C# 中的sealed修饰符学习 – 新西兰程序员 – 博客园

转载原地址 http://developer.51cto.com/art/200908/147327.htm

C#语言还是比较常见的东西，这里我们主要介绍C# sealed修饰符，包括介绍两个修饰符在含义上互相排斥用于方法和属性等方面。

C# sealed修饰符是干什么的？

C# sealed修饰符表示密封用于类时，表示该类不能再被继承，不能和 abstract 同时使用，因为这两个修饰符在含义上互相排斥用于方法和属性时，表示该方法或属性不能再被重写，必须和 override 关键字一起使用，因为使用 C# sealed修饰符的方法或属性肯定是基类中相应的虚成员通常用于实现第三方类库时不想被客户端继承，或用于没有必要再继承的类以防止滥用继承造成层次结构体系混乱恰当的利用 C# sealed修饰符也可以提高一定的运行效率，因为不用考虑继承类会重写该成员。

示例：

using System;  
2.using System.Collections.Generic;  
3.using System.Text;  
4.   
5.namespace Example06  
6.{  
7.class Program  
8.{  
9.class A  
10.{  
11.public virtual void F()  
12.{  
13.Console.WriteLine("A.F");  
14.}  
15.public virtual void G()  
16.{  
17.Console.WriteLine("A.G");  
18.}  
19.}  
20.class B : A  
21.{  
22.public sealed override void F()  
23.{  
24.Console.WriteLine("B.F");  
25.}  
26.public override void G()  
27.{  
28.Console.WriteLine("B.G");  
29.}  
30.}  
31.class C : B  
32.{  
33.public override void G()  
34.{  
35.Console.WriteLine("C.G");  
36.}  
37.}  
38.static void Main(string[] args)  
39.{  
40.new A().F();  
41.new A().G();  
42.new B().F();  
43.new B().G();  
44.new C().F();  
45.new C().G();  
46.   
47.Console.ReadLine();  
48.}  
49.}  
50.}

转载原地址 http://www.cnblogs.com/iamdaiyuan/archive/2007/02/06/642442.html
sealed的中文意思是密封，故名思义，就是由它修饰的类或方法将不能被继承或是重写。

        sealed关键字的作用：

在类声明中使用sealed可防止其它类继承此类；在方法声明中使用sealed修饰符可防止扩充类重写此方法。

sealed修饰符主要用于防止非有意的派生，但是它还能促使某些运行时优化。具体说来，由于密封类永远不会有任何派生类，所以对密封类的实例的虚拟函数成员的调用可以转换为非虚拟调用来处理。

         密封类：

密封类在声明中使用sealed 修饰符，这样就可以防止该类被其它类继承。如果试图将一个密封类作为其它类的基类，C#将提示出错。理所当然，密封类不能同时又是抽象类，因为抽象总是希望被继承的。
在哪些场合下使用密封类呢？实际上，密封类中不可能有派生类。如果密封类实例中存在虚成员函数，该成员函数可以转化为非虚的，函数修饰符virtual 不再生效。
让我们看下面的例子：

1 abstract class AbstractClass
2 {
3       public abstract void Method( ) ;
4 }

5 sealed class SealedClass: AbstractClass
6 {
7        public override void Method( )
8         { //... }
9 }

如果我们尝试写下面的代码

class OtherClass: SealedClass
{ 
}

C#会指出这个错误，告诉你SealedClass 是一个密封类，不能试图从SealedClass  中派生任何类。

            密封方法：

C#还提出了密封方法（sealed method） 的概念，以防止在方法所在类的派生类中对该方法的重载。对方法可以使用sealed 修饰符，这时我们称该方法是一个密封方法。
不是类的每个成员方法都可以作为密封方法密封方法，要作为密封方法必须对基类的虚方法进行重载，提供具体的实现方法。所以，在方法的声明中，sealed 修饰符总是和override 修饰符同时使用。请看下面的例子代码：

 1 using System ;

 2 class A
 3 {
 4     public virtual void F( )
 5     { 
            Console.WriteLine("A.F") ; 
        }
 6     
        public virtual void G( )
 7     {     
            Console.WriteLine("A.G") ; 
        }
 8 }

 9 class B: A
10 {
11     sealed override public void F( )
12     { 
            Console.WriteLine("B.F") ; 
         }
13 
        override public void G( )
14     {
             Console.WriteLine("B.G") ; }
15     }
16 
    class C: B
17 {
18     override public void G( )
19     { 
            Console.WriteLine("C.G") ; 
        }
20 }

类B 对基类A 中的两个虚方法均进行了重载,其中F 方法使用了sealed 修饰符，成为一个密封方法。G 方法不是密封方法，所以在B 的派生类C 中，可以重载方法G，但不能重载方法F。

来源： C# 表达式树（Expression） – muzizongheng – 博客园

  Expression.Loop(
    // Adding a conditional block into the loop.
           Expression.IfThenElse(
    // Condition: value > 1
               Expression.GreaterThan(value, Expression.Constant(1)),
    // If true: result *= value --
               Expression.MultiplyAssign(result,
                   Expression.PostDecrementAssign(value)),
    // If false, exit the loop and go to the label.
               Expression.Break(label, result)
           ),
    // Label to jump to.
       label
    )

来源： [C#] C# 知识回顾 – 表达式树 Expression Trees – 反骨仔 – 博客园

目录

• 简介
• Lambda 表达式创建表达式树
• API 创建表达式树
• 解析表达式树
• 表达式树的永久性
• 编译表达式树
• 执行表达式树
• 修改表达式树
• 调试

简介

表达式树以树形数据结构表示代码，其中每一个节点都是一种表达式，比如方法调用和 x < y 这样的二元运算等。

　　表达式树还能用于动态语言运行时 (DLR) 以提供动态语言和 .NET Framework 之间的互操作性。

 

一、Lambda 表达式创建表达式树

若 lambda 表达式被分配给 Expression<TDelegate> 类型的变量，则编译器可以发射代码以创建表示该 lambda 表达式的表达式树。

C# 编译器只能从表达式 lambda （或单行 lambda）生成表达式树。

下列代码示例使用关键字 Expression创建表示 lambda 表达式：

1             Expression<Action<int>> actionExpression = n => Console.WriteLine(n);
2             Expression<Func<int, bool>> funcExpression1 = (n) => n < 0;
3             Expression<Func<int, int, bool>> funcExpression2 = (n, m) => n - m == 0;

 

二、API 创建表达式树

通过 API 创建表达式树需要使用 Expression 类

下列代码示例展示如何通过 API 创建表示 lambda 表达式：num => num == 0

1             //通过 Expression 类创建表达式树
2             //  lambda：num => num == 0
3             ParameterExpression pExpression = Expression.Parameter(typeof(int));    //参数：num
4             ConstantExpression cExpression = Expression.Constant(0);    //常量：0
5             BinaryExpression bExpression = Expression.MakeBinary(ExpressionType.Equal, pExpression, cExpression);   //表达式：num == 0
6             Expression<Func<int, bool>> lambda = Expression.Lambda<Func<int, bool>>(bExpression, pExpression);  //lambda 表达式：num => num == 0

代码使用 Expression 类的静态方法进行创建。

 

三、解析表达式树

下列代码示例展示如何分解表示 lambda 表达式 num => num == 0 的表达式树。

1             Expression<Func<int, bool>> funcExpression = num => num == 0;
2 
3             //开始解析
4             ParameterExpression pExpression = funcExpression.Parameters[0]; //lambda 表达式参数
5             BinaryExpression body = (BinaryExpression)funcExpression.Body;  //lambda 表达式主体：num == 0
6 
7             Console.WriteLine($"解析：{pExpression.Name} => {body.Left} {body.NodeType} {body.Right}");

 

 

 

四、表达式树永久性

　　表达式树应具有永久性（类似字符串）。这意味着如果你想修改某个表达式树，则必须复制该表达式树然后替换其中的节点来创建一个新的表达式树。  你可以使用表达式树访问者遍历现有表达式树。第七节介绍了如何修改表达式树。

五、编译表达式树

Expression<TDelegate> 类型提供了 Compile 方法以将表达式树表示的代码编译成可执行委托。

1             //创建表达式树
2             Expression<Func<string, int>> funcExpression = msg => msg.Length;
3             //表达式树编译成委托
4             var lambda = funcExpression.Compile();
5             //调用委托
6             Console.WriteLine(lambda("Hello, World!"));
7 
8             //语法简化
9             Console.WriteLine(funcExpression.Compile()("Hello, World!"));

 

 

 

 

六、执行表达式树

执行表达式树可能会返回一个值，也可能仅执行一个操作（例如调用方法）。

　　只能执行表示 lambda 表达式的表达式树。表示 lambda 表达式的表达式树属于 LambdaExpression 或 Expression<TDelegate> 类型。若要执行这些表达式树，需要调用 Compile 方法来创建一个可执行委托，然后调用该委托。

 1             const int n = 1;
 2             const int m = 2;
 3 
 4             //待执行的表达式树
 5             BinaryExpression bExpression = Expression.Add(Expression.Constant(n), Expression.Constant(m));
 6             //创建 lambda 表达式
 7             Expression<Func<int>> funcExpression = Expression.Lambda<Func<int>>(bExpression);
 8             //编译 lambda 表达式
 9             Func<int> func = funcExpression.Compile();
10 
11             //执行 lambda 表达式
12             Console.WriteLine($"{n} + {m} = {func()}");

 

七、修改表达式树

该类继承 ExpressionVisitor 类，通过 Visit 方法间接调用 VisitBinary 方法将 != 替换成 ==。基类方法构造类似于传入的表达式树的节点，但这些节点将其子目录树替换为访问器递归生成的表达式树。

 1     internal class Program
 2     {
 3         private static void Main(string[] args)
 4         {
 5             Expression<Func<int, bool>> funcExpression = num => num == 0;
 6             Console.WriteLine($"Source: {funcExpression}");
 7 
 8             var visitor = new NotEqualExpressionVisitor();
 9             var expression = visitor.Visit(funcExpression);
10 
11             Console.WriteLine($"Modify: {expression}");
12 
13             Console.Read();
14         }
15 
16         /// <summary>
17         /// 不等表达式树访问器
18         /// </summary>
19         public class NotEqualExpressionVisitor : ExpressionVisitor
20         {
21             public Expression Visit(BinaryExpression node)
22             {
23                 return VisitBinary(node);
24             }
25 
26             protected override Expression VisitBinary(BinaryExpression node)
27             {
28                 return node.NodeType == ExpressionType.Equal
29                     ? Expression.MakeBinary(ExpressionType.NotEqual, node.Left, node.Right) //重新弄个表达式：用 != 代替 ==
30                     : base.VisitBinary(node);
31             }
32         }
33     }

 

 

 

八、调试

8.1 参数表达式

1             ParameterExpression pExpression1 = Expression.Parameter(typeof(string));
2             ParameterExpression pExpression2 = Expression.Parameter(typeof(string), "msg");

图8-1

图8-2

从 DebugView 可知，如果参数没有名称，则会为其分配一个自动生成的名称。

 

1             const int num1 = 250;
2             const float num2 = 250;
3 
4             ConstantExpression cExpression1 = Expression.Constant(num1);
5             ConstantExpression cExpression2 = Expression.Constant(num2);

图8-3

图8-4

从 DebugView 可知，float 比 int 多了个后缀 F。

 

1             Expression lambda1 = Expression.Lambda<Func<int>>(Expression.Constant(250));
2             Expression lambda2 = Expression.Lambda<Func<int>>(Expression.Constant(250), "CustomName", null);

图8-5

图8-6

观察 DebugView ，如果 lambda 表达式没有名称，则会为其分配一个自动生成的名称。

 

 

---

【原文链接】http://www.cnblogs.com/liqingwen/p/5868688.html