哈希表

散列表（Hash table，也叫哈希表），是根据关键字（Key value）而直接访问在内存存储位置的数据结构。也就是说，它通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

基本概念

• 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
• 对不同的关键字可能得到同一散列地址，即k_1 != k_2，而f(k_1)=f(k_2)，这种现象称为碰撞（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理碰撞的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少碰撞。

  构造散列函数

  散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。

1. 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k或hash(k)=a*k + b，其中a\,b为常数（这种散列函数叫做自身函数）
2. 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
3. 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
4. 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
5. 随机数法
6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即hash(k)=k mod p, p <= m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生碰撞。

处理碰撞

为了知道碰撞产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对碰撞结果进行处理。而不发生碰撞的可能性是非常之小的，所以通常对碰撞进行处理。常用方法有以下几种：

• 开放地址法
• 单独链表法
• 双散列
• 再散列

查找效率

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

1. 散列函数是否均匀；
2. 处理冲突的方法；
3. 散列表的载荷因子（英语：load factor）。

   载荷因子

   散列表的载荷因子定义为：a = 填入表中的元素个数 / 散列表的长度

a是散列表装满程度的标志因子。由于表长是定值，a与“填入表中的元素个数”成正比，所以，a越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，a越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子a的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

哈希表

散列表（Hash table，也叫哈希表），是根据关键字（Key value）而直接访问在内存存储位置的数据结构。也就是说，它通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

基本概念

• 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
• 对不同的关键字可能得到同一散列地址，即k_1 != k_2，而f(k_1)=f(k_2)，这种现象称为碰撞（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理碰撞的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少碰撞。

  构造散列函数

  散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。

1. 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k或hash(k)=a*k + b，其中a\,b为常数（这种散列函数叫做自身函数）
2. 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
3. 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
4. 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
5. 随机数法
6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即hash(k)=k mod p, p <= m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生碰撞。

处理碰撞

为了知道碰撞产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对碰撞结果进行处理。而不发生碰撞的可能性是非常之小的，所以通常对碰撞进行处理。常用方法有以下几种：

• 开放地址法
• 单独链表法
• 双散列
• 再散列

查找效率

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

1. 散列函数是否均匀；
2. 处理冲突的方法；
3. 散列表的载荷因子（英语：load factor）。

   载荷因子

   散列表的载荷因子定义为：a = 填入表中的元素个数 / 散列表的长度

a是散列表装满程度的标志因子。由于表长是定值，a与“填入表中的元素个数”成正比，所以，a越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，a越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子a的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

引出工厂模式的设计问题

1.为了提高内聚（Cohesion）和松耦合（Coupling），我们经常会抽象出一些类的公共接口以形成抽象基类或者接口。这样我们可以通过声明一个指向基类的指针来指向实际的子类实现，达到了多态的目的。这里很容易出现的一个问题 n 多的子类继承自抽象基类，我们不得不在每次要用到子类的地方就编写诸如 new ×××;的代码。这里带来两个问题：
客户程序员必须知道实际子类的名称（当系统复杂后，命名将是一个很不好处理的问题，为了处理可能的名字冲突，有的命名可能并不是具有很好的可读性和可记忆性，就姑且不论不同程序员千奇百怪的个人偏好了）。
程序的扩展性和维护变得越来越困难。
2.还有一种情况就是在父类中并不知道具体要实例化哪一个具体的子类。这里的意思为：假设我们在类 A 中要使用到类 B，B 是一个抽象父类，在 A 中并不知道具体要实例化那一个 B 的子类，但是在类 A 的子类 D 中是可以知道的。在 A 中我们没有办法直接使用类似于 new ×××的语句，因为根本就不知道×××是什么。
以上两个问题也就引出了工厂模式的两个最重要的功能：
定义创建对象的接口，封装了对象的创建；
使得具体化类的工作延迟到了子类中。
对于工厂模式，为了使其能更好的解决多种情况的问题，将其分为三类：简单工厂模式（Simple Factory），工厂方法模式（Factory Method），抽象工厂模式（Abstract Factory）。下面来一一搞定。

简单工厂

具体情形：有一个肥皂厂，生产各种肥皂，有舒肤佳，夏士莲，娜爱斯等。给这个肥皂厂建模。

对于简单设计模式的结构图，我们可以很清晰的看到它的组成：
1) 工厂类角色：这是本模式的核心，含有一定的商业逻辑和判断逻辑。
2) 抽象产品角色：它一般是具体产品继承的父类或者实现的接口。
3) 具体产品角色：工厂类所创建的对象就是此角色的实例。
简单设计模式存在的目的很简单：定义一个用于创建对象的接口。
缺点：对修改不封闭，新增加产品您要修改工厂。违法了鼎鼎大名的开闭法则（OCP）。
代码实现：

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

#include <iostream>
using namespace std;
enum PRODUCTTYPE {SFJ,XSL,NAS};
class soapBase
{
	public:
	virtual ~soapBase(){};
	virtual void show() = 0;
};
class SFJSoap:public soapBase
{
	public:
	void show() {cout<<"SFJ Soap!"<<endl;}
};
class XSLSoap:public soapBase
{
	public:
	void show() {cout<<"XSL Soap!"<<endl;}
};
class NASSoap:public soapBase
{
	public:
	void show() {cout<<"NAS Soap!"<<endl;}
};
class Factory
{
	public:
	soapBase * creatSoap(PRODUCTTYPE type)
	{
		switch(type)
		{
			case SFJ: 
				return new SFJSoap();
				break;
			case XSL:
				return new XSLSoap();
				break;
			case NAS:
				return new NASSoap();
				break;
			default:break;
		}
		
	}
};
int main()
{
	Factory factory;
	soapBase* pSoap1 = factory.creatSoap(SFJ);
	pSoap1->show();
	soapBase* pSoap2 = factory.creatSoap(XSL);
	pSoap2->show();
	soapBase* pSoap3 = factory.creatSoap(NAS);
	pSoap3->show();
	delete pSoap1;
	delete pSoap2;
	delete pSoap3;
	return 0;
}

运行结果:

最近感觉自己像死了一样。事情有很多，但自己却懒于去做。
主要是缺少一个明确的计划和实施计划的执行力。
生活其实可以变得更好一些。

工作

是的，我需要一份好的工作来支撑我的生活。
为了准备找工作，我需要做一些努力。
刷题，每天一道。
我还需要专业上的一些进展。多和老师沟通，看能不能写一些文章出来。

生活

日常的锻炼是必不可少的。锻炼会让人做事更加坚定，果断。锻炼也是反省自己的好地方，而不是在床上。

社交

不要仅仅只关注身边的事物，多出去走走看看。

单个回车
视为空格。

连续回车

才能分段。

行尾加两个空格，这里->
即可段内换行。

这些文字显示为斜体

这些文字显示为粗体

表示引用文字内容。

表示这是一级标题

表示这是二级标题

表示这是三级标题

……

最小是六级标题

也可以这样表示大标题
=

这样表示小标题
-

1
2
3
4
5
6

//这里显示一些代码，在正文显示中会自动识别语言，进行代码染色，这是一段C#代码
public class Blog
{
     public int Id { get; set; }
     public string Subject { get; set; }
}

C#:

//这里显示一些代码，在正文显示中会自动识别语言，进行代码染色，这是一段C#代码
public class Blog
{
     public int Id { get; set; }
     public string Subject { get; set; }
}

直接把一个URL显示为超级连接：

也可以这样：图灵社区

图像和链接非常类似，区别在开头加一个惊叹号：

此外，还可以以索引方式把url都列在文章的最后，例如这样：

图灵社区