Linfs's blog

1834

0%

发表于 阅读次数： 本文字数： 0 阅读时长 ≈ 1 分钟

发表于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

1 前言

散列表(hash table)的出现是为了提高存储数据的访问速度，当数据采用数组或者链表进行存储时，要查找一个元素必须进行遍历(当然采用其他技术如二叉搜索树时无需遍历)，当数据量大时耗时巨大；而散列表根据元素的key可快速计算出元素所在位置，无需进行遍历，进而大大提高了数据的访问速度。

散列表的元素以键值(key-value)的形式存储。一般会有一块空间用于存储散列表的数据元素，基于元素的key根据一定的规则计算出该元素应该存放的位置并进行存储；因为关键字为key的元素所在的位置可以通过计算快速计算得到，因此可以实现快速访问。

2 直接寻址表

假设数据元素的关键字key的值取自全域*U={0, 1, 2, ..., m-1}，在直接寻址表(direct-address table)中一般会有一个大小为m的数组，以保证任意元素在直接寻址表中都会有一个位置(或成为槽slot)。在直接寻址表中，数组的下标即为元素的key，因此可根据key快速定位数组中的元素，且对所有的数据元素查找时间恒为O(1)*。

直接寻址表原理简单，实现也不复杂，但当key的全域*U很大但实际上需要存储的数据元素不多时，会造成空间的浪费：比如全域U的取值范围为0 ~ 9999，但数据元素的个数只有100个，根据直接寻址表的套路，其会申请一个大小为10000的数组，在这种情况下，数组的9900个元素空间就浪费了。因而直接寻址表比较适合全域U*范围比较小的情况。

***Note:***直接寻址表并不是散列表的一种，即直接寻址表和散列表是并列关系而非从属关系(有待考证)。

3 散列表

3.1 描述

由于直接寻址表存在以下几个问题：1)当key的全域*U的取值范围0 ~ m很大时，要存储一张大小为m的直接寻址表T可能不切实际；2)待存储的元素个数k可能不多，而key的全域U*的取值范围0 ~ m可能很大，这种情况下采用直接寻址表的方式存储性价比低，因为会浪费大量的存储空间。

相对于直接寻址表，散列表：1)多了一个散列函数(hash function)h(x)，散列函数以元素的key为输入，输出元素存放位置；2)直接寻址表把具有关键字k的元素存放在槽k中，而散列表把它存放在h(k)中，即散列表通过散列函数h(x)把元素映射到散列表*T[0 1, 2 ..., n-1]的各个槽(slot)中，因为散列表的映射位置是根据映射函数h(x)计算的，因而散列表的大小n可比全域U的大小m小得多，而直接寻址表的大小必须和全域U*的大小一样大。

散列表的大小n比*U*的大小m要小，把m个数存入n个槽中(n<=m)，那必然存在2个或多个元素映射到同一个槽中，这就产生了冲突(collision)，因此散列表需要有额外的方式处理冲突，主要有2种：链接法(chaining)和开放寻址法(open addressing)。

3.2 处理冲突

3.2.1 链接法

3.2.1.1 描述

链接法中散列表存储的是一个指向某个链表的指针，当产生冲突时，直接把数据元素追加到链表的末尾。

3.2.1.2 性能分析

看不懂《算法导论》里写的意思，TBC.

3.2.1.2.1 查找

3.2.2 开放寻址法

3.2.2.1 描述

3.2.2.2 性能分析

3.3 散列函数

KuKuXia的散列表介绍

发表于 分类于 阅读次数： 本文字数： 404 阅读时长 ≈ 1 分钟

介绍常见排序算法：插入排序、快速排序等的原理，时间复杂度/空间复杂度分析以及代码实现。

阅读全文 »

发表于 分类于 阅读次数： 本文字数： 232 阅读时长 ≈ 1 分钟

1 openflow switch

openflow switch指的是支持openflow protocol的交换机。如图1所示，openflow switch的组成主要有：1个/多个flow table和1个group table、1个或多个openflow channel。openflow switch基于openflow protocol通过openflow channel和远程的controller进行通信。

openflowSwitch

图1 openflow switch

2 openflow protocol

发表于 分类于 阅读次数： 本文字数： 61 阅读时长 ≈ 1 分钟

1 open vSwitch

open vSwitch是一款基于openflow协议的开源虚拟交换机。

2 open vSwitch架构

发表于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 2 分钟
有东西被加密了, 请输入密码查看.
阅读全文 »

发表于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 3 分钟
有东西被加密了, 请输入密码查看.
阅读全文 »

发表于 分类于 阅读次数： 本文字数： 7.2k 阅读时长 ≈ 7 分钟

本文主要介绍win10下利用Hexo+theme-next+github page搭建个人博客。其中，theme-next是一款简洁而又功能强大的Hexo主题。

1 环境配置

1.1 安装Hexo

安装Hexo前需要安装Node.js和Git。安装好后，在cmd命令行下敲入命令npm install -g hexo-cli即可完成安装。这里有详细的官网安装教程。

1.2 下载/配置主题theme-next

这里有详细的官方配置教程。

要应用主题，需在博客配置文件（即根目录下的_config.yml）里修改配置：

1
2
3
4
# Extensions
## Plugins: https://hexo.io/plugins/
## Themes: https://hexo.io/themes/
theme: next

1.3 将个人博客与github仓库关联

（1）在自己的github账户上创建一个github仓库，命名为username.github.io。
（2）在博客配置文件（即根目录下的_config.yml）里修改配置：

1
2
3
4
5
6
# Deployment
## Docs: https://hexo.io/docs/one-command-deployment
deploy:
  type: git
  repo: https://github.com/username/username.github.io.git
  branch: master

2 博客搭建&美化

2.1 创建菜单栏

打开cmd窗口，执行以下命令创建文件夹（根据需求选择创建哪些文件夹）：

1
2
3
hexo new page home
hexo new page categories
......

检查主题配置文件（即根目录下的_config.next.yml），如果子菜单被注释掉了（如archives/schedule），则取消注释（注：如果想调整子菜单顺序直接在_config.next.yml配置文件里调整即可）。

1
2
3
4
5
6
7
8
9
10
11
12
13
# Usage: `Key: /link/ || icon`
# Key is the name of menu item. If the translation for this item is available, the translated text will be loaded, otherwise the Key name will be used. Key is case-senstive.
# Value before `||` delimiter is the target link, value after `||` delimiter is the name of Font Awesome icon.
# External url should start with http:// or https://
menu:
  home: / || fa fa-home
  categories: /categories/ || fa fa-th
  tags: /tags/ || fa fa-tags
  about: /about/ || fa fa-user
  # archives: /archives/ || fa fa-archive
  # schedule: /schedule/ || fa fa-calendar
  # sitemap: /sitemap.xml || fa fa-sitemap
  # commonweal: /404/ || fa fa-heartbeat

将要添加的头像图片和Logo放在指定的文件夹中，此例中放在/node_modules/hexo-theme-next/source/images/目录下。

2.2.1 设置头像

（1）在_config.next.yml下填入头像的url，但这样头像是正方形的且没有动态效果：

1
2
3
4
5
6
7
8
# Sidebar Avatar
avatar:
  # Replace the default image and set the url here.
  url: /images/cattle.jpg
  # If true, the avatar will be dispalyed in circle.
  rounded: false
  # If true, the avatar will be rotated with the cursor.
  rotated: false

（2）设置圆形头像且与鼠标接触头像能够旋转
找到sidebar-author.styl配置文件，将.site-author-image替换为以下内容：

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
.site-author-image {
  display: block;
  margin: 0 auto;
  padding: $site-author-image-padding;
  max-width: $site-author-image-width;
  height: $site-author-image-height;
  border: $site-author-image-border-width solid $site-author-image-border-color;

  /* 头像圆形 */
  border-radius: 80px;
  -webkit-border-radius: 80px;
  -moz-border-radius: 80px;
  box-shadow: inset 0 -1px 0 #333sf;


  /* 鼠标经过头像旋转360度 */
  -webkit-transition: -webkit-transform 1.0s ease-out;
  -moz-transition: -moz-transform 1.0s ease-out;
  transition: transform 1.0s ease-out;
}

img:hover {
  /* 鼠标经过停止头像旋转 
  -webkit-animation-play-state:paused;
  animation-play-state:paused; */

  /* 鼠标经过头像旋转360度 */
  -webkit-transform: rotateZ(360deg);
  -moz-transform: rotateZ(360deg);
  transform: rotateZ(360deg);
}

/* Z轴旋转动画 */
@-webkit-keyframes play {
  0% {
    -webkit-transform: rotateZ(0deg);
  }
  100% {
    -webkit-transform: rotateZ(-360deg);
  }
}
@-moz-keyframes play {
  0% {
    -moz-transform: rotateZ(0deg);
  }
  100% {
    -moz-transform: rotateZ(-360deg);
  }
}
@keyframes play {
  0% {
    transform: rotateZ(0deg);
  }
  100% {
    transform: rotateZ(-360deg);
  }
}

.site-author-name {
  color: $site-author-name-color;
  font-weight: $site-author-name-weight;
  margin: $site-author-name-margin;
}

.site-description {
  color: $site-description-color;
  font-size: $site-description-font-size;
  margin-top: $site-description-margin-top;
}

在_config.next.yml文件夹下替换掉Logo图片（可在这里将图片转成16×16/32×32大小）的路径即可，如下所示：

1
2
3
4
5
6
7
# ---------------------------------------------------------------
# Site Information Settings
# ---------------------------------------------------------------

favicon:
  small: /images/circle-cattle-16×16.png
  medium: /images/circle-cattle-32×32.png

2.3 子菜单设置

2.3.1 首页

（1）首页可以自定义（即可以在/home/目录下创建index.md文件，在里面自定义要显示的内容）。默认情况（/home/目录下没有index.md）下点击首页会显示所有博客（默认全文显示）。
（2）首页显示博客摘要

方法1：
直接在文章中需要截断的地方加入：

<!--more-->

那么在首页显示时就会显示<!--more-->前面的内容。

方法2：
在文章中的front-matter中添加description字段，自定义摘要，例子如下：

1
2
3
4
5
title: BGP与邻居建立连接-基于RFC4271
date: 2021-04-04 12:48:42
categories: BGP
tags: BGP
description: 我是摘要.

2.3.2 分类

（1）将categories文件夹下的index.md文件的meta信息中的type设置为categories类型，例子如下：

1
2
3
4
5
---
title: 分类
date: 2021-04-03 21:26:04
type: "categories"
---

（2）将要写的博客归类到某一类，比如将BGP与邻居建立连接-基于RFC4271归类到BGP这一类，即在meta信息中填写categories: BGP，那么该文章就会自动被归类为BGP这一类。

1
2
3
4
5
6
---
title: BGP与邻居建立连接-基于RFC4271
date: 2021-04-04 12:48:42
categories: BGP
tags: BGP
---

当点击分类时，页面显示如下：
分类

2.3.3 标签

设置类似于分类。

2.3.4 添加博客搜索功能

（1）安装插件hexo-generator-searchdb

npm install hexo-generator-searchdb --save

（2）修改主题配置文件，将local_search改为enable

1
2
3
4
# Local Search
# Dependencies: https://github.com/next-theme/hexo-generator-searchdb
local_search:
  enable: true

（3）完成后在菜单栏处会多一个搜索。

2.4 访问量统计

2.4.1 网站总访问量统计

thmem-next主题集成了不蒜子统计，在配置文件（_config_next.yml）里enable一下即可，不蒜子也可以统计单个博文访问量，不过据说不太好用，下面用Leancloud统计单个博客访问量：

1
2
3
4
5
6
7
8
9
10
# Show Views / Visitors of the website / page with busuanzi.
# For more information: http://ibruce.info/2015/04/04/busuanzi/
busuanzi_count:
  enable: enable
  total_visitors: true
  total_visitors_icon: fa fa-user
  total_views: true
  total_views_icon: fa fa-eye
  post_views: false
  post_views_icon: far fa-eye

2.4.2 单个博客访问量统计

theme-next也已集成了Leancloud访问量统计功能，只需在_config.next.yml配置文件里enable一下即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
# Show number of visitors of each article.
# You can visit https://www.leancloud.cn to get AppID and AppKey.
leancloud_visitors:
  enable: true
  app_id: **********************
  app_key: **********************
  # Required for apps from CN region
  server_url: # <your server url>
  # Dependencies: https://github.com/theme-next/hexo-leancloud-counter-security
  # If you don't care about security in leancloud counter and just want to use it directly
  # (without hexo-leancloud-counter-security plugin), set `security` to `false`.
  security: true
  visitor: true

上述配置中需要app_id和app_key，可以到Leancloud上注册账号并注册应用获取。

2.4.3 文章加密访问

（1）安装插件npm install hexo-blog-encrypt
（2）在hexo根目录下的配置文件_config.yml下添加一下内容，更多详情请看这里：

1
2
3
4
5
6
7
8
# Security
encrypt:
    enable: true
    abstract: 有东西被加密了, 请输入密码查看.
    message: 您好, 这里需要密码.
    theme: shrink
    wrong_pass_message: 抱歉, 这个密码看着不太对, 请再试试.
    wrong_hash_message: 抱歉, 这个文章不能被校验, 不过您还是能看看解密后的内容.

（3）在需要加密的文章里添加password字段，例子如下：

1
2
3
4
5
6
7
title: Blog encrypt test
date: 2021-04-10 13:21:00
categories: Blog encrypt test
tags: Blog encrypt test
password: **********
abstract: Welcome to my blog, enter password to read.
message: Welcome to my blog, enter password to read.

2.4.4 取消theme-next主题目录自动编号

在theme-next主题中，在左侧栏文章目录中会为标题自动编号，如果在文章中也想显示目录的序号，那么在文章目录中的标题编号就会重复，如下图所示：

theme-next目录自动编号

如果希望在文章中显示标题编号，同时想让文章目录也好看一点，那就取消theme-next的目录自动编号，即修改主题配置文件_config.next.yml的number属性为false：

1
2
3
4
5
6
# Table of Contents in the Sidebar
# Front-matter variable (unsupport wrap expand_all).
toc:
  enable: true
  # Automatically add list number to toc.
  number: false

效果如下：

theme-next取消目录自动编号

2.4.5 图片点击放大功能

如果在文章中插入图片，由于某些原因图片可能看不清，此时就需要点击放大预览功能，在theme-next中已经内置了fancybox，在_config.next.yml中把fancybox置为true即可：

1
2
3
# FancyBox is a tool that offers a nice and elegant way to add zooming functionality for images.
# For more information: https://fancyapps.com/fancybox/
fancybox: true

3 本地&github page部署

3.1 本地部署

（1）hexo g可生成静态文件（生成到/public目录下）；
（2）hexo clean清理（即删除/public目录）；
（3）hexo s可在本地启动，浏览器输入localhost:4000可访问博客。

3.2 github page部署

直接执行hexo d即可部署到github上。

4 写作

支持Markdown。

发表于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 2 分钟

1 BGP的状态机

    BGP是根据状态机进行运转的，搞清楚了BGP的状态机，对BGP工作原理的理解会有帮助。
    限于篇幅，本文只讨论一切步骤都完美正常执行的情况（即收到的包都是正确的，与peer建立TCP连接一次成功等等）。当然RFC文档种还详细介绍了各种突发状况、各种处理方法等，实在是有点多，下篇文章再完整地叙述。

阅读全文 »