Goal

Finding Similar Items

• 在高维空间上找到那些相近的元素。比如，在做微博文本挖掘的时候，会发现很多微博是高度相似的，因为大量的微博都是转发其他人的微博，并且没有添加评论，导致很多数据是重复或者高度相似的。这给我们进行数据处理带来很大的困扰，我们得想办法把找出这些相似的微博，再对其进行去重处理。
  

Steps

Shingling

Min-Hashing

Convert large sets to short signatures, while preserving similarity.

LSH

General idea: Use a function f(x,y) that tells whether x and y is a candidate pair: a pair of elements whose similarity must be evaluated

我们对签名矩阵按行进行分组，将矩阵分成b组，每组由r行组成.

分组之后，我们对最小签名向量的每一组进行hash，各个组设置不同的桶空间。只要两列有一组的最小签名部分相同，那么这两列就会hash到同一个桶而成为候选相似项。签名的分析我们知道，对于某个具体的行，两个签名相同的概率p =两列的相似度= sim(S1,S2)，然后：

1. 在某个组中所有行的两个签名值都相等概率是p^r;

2. 在某个组中至少有一对签名不相等的概率是1−p^r;

3. 在每一组中至少有一对签名不相等的概率是(1−p^r)^b;

4. 至少有一个组的所有对的签名相等的概率是1−(1−p^r)^b;

于是两列成为候选相似对的概率是1−(1−p^r)^b，它采样值以及曲线如下：

Goal

Finding Similar Items

• 在高维空间上找到那些相近的元素。比如，在做微博文本挖掘的时候，会发现很多微博是高度相似的，因为大量的微博都是转发其他人的微博，并且没有添加评论，导致很多数据是重复或者高度相似的。这给我们进行数据处理带来很大的困扰，我们得想办法把找出这些相似的微博，再对其进行去重处理。
  

Steps

Shingling

Min-Hashing

Convert large sets to short signatures, while preserving similarity.

LSH

General idea: Use a function f(x,y) that tells whether x and y is a candidate pair: a pair of elements whose similarity must be evaluated

我们对签名矩阵按行进行分组，将矩阵分成b组，每组由r行组成.

分组之后，我们对最小签名向量的每一组进行hash，各个组设置不同的桶空间。只要两列有一组的最小签名部分相同，那么这两列就会hash到同一个桶而成为候选相似项。签名的分析我们知道，对于某个具体的行，两个签名相同的概率p =两列的相似度= sim(S1,S2)，然后：

1. 在某个组中所有行的两个签名值都相等概率是p^r;

2. 在某个组中至少有一对签名不相等的概率是1−p^r;

3. 在每一组中至少有一对签名不相等的概率是(1−p^r)^b;

4. 至少有一个组的所有对的签名相等的概率是1−(1−p^r)^b;

于是两列成为候选相似对的概率是1−(1−p^r)^b，它采样值以及曲线如下：

具体情形：这个肥皂厂发现搞牙膏也很赚钱，决定做牙膏。牙膏有高档低档，肥皂也是。现在搞两个厂房，一个生产低档的牙膏和肥皂，一个生产高档的牙膏和肥皂。
比如，厂房一生产中华牙膏、娜爱斯肥皂，厂房二生产黑人牙膏和舒肤佳牙膏

对于上面的结构图，可以看出抽象工厂模式，比前两者更为的复杂和一般性，抽象工厂模式和工厂方法模式的区别就在于需要创建对象的复杂程度上。
抽象工厂模式：给客户端提供一个接口，可以创建多个产品族中的产品对象 ，而且使用抽象工厂模式还要满足一下条件：
1)系统中有多个产品族，而系统一次只可能消费其中一族产品。
2)同属于同一个产品族的产品以其使用。
抽象工厂模式的组成（和工厂方法模式一样）：
1)抽象工厂角色：这是工厂方法模式的核心，它与应用程序无关。是具体工厂角色必须实现的接口或者必须继承的父类。
2)具体工厂角色：它含有和具体业务逻辑有关的代码。由应用程序调用以创建对应的具体产品的对象。
3)抽象产品角色：它是具体产品继承的父类或者是实现的接口。
4)具体产品角色：具体工厂角色所创建的对象就是此角色的实例。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <iostream>
using namespace std;
enum SOAPTYPE {SFJ,XSL,NAS};
enum TOOTHTYPE {HR,ZH};
class SoapBase
{
	public:
	virtual ~SoapBase(){};
	virtual void show() = 0;
};
class SFJSoap:public SoapBase
{
	public:
	void show() {cout<<"SFJ Soap!"<<endl;}
};
class NASSoap:public SoapBase
{
	public:
	void show() {cout<<"NAS Soap!"<<endl;}
};
class ToothBase
{
	public:
	virtual ~ToothBase(){};
	virtual void show() = 0;
};
class HRTooth:public ToothBase
{
	public:
	void show() {cout<<"Hei ren Toothpaste!"<<endl;}
};
class ChinaTooth:public ToothBase
{
	public:
	void show() {cout<<"China Toothpaste!"<<endl;}
};
class FactoryBase
{
	public:
	virtual SoapBase * creatSoap() = 0;
	virtual ToothBase * creatToothpaste() = 0;
};
class FactoryA
{
	public:
	SoapBase * creatSoap()
	{
		return new SFJSoap();
	}
	
	ToothBase * creatToothpaste()
	{
		return new HRTooth();
	}
};
class FactoryB
{
	public:
	SoapBase * creatSoap()
	{
		return new NASSoap();
	}
	
	ToothBase * creatToothpaste()
	{
		return new ChinaTooth();
	}
};
int main()
{
	FactoryA factory1;
	FactoryB factory2;
	SoapBase *pSoap1 = NULL;
	ToothBase *pToothpaste1 = NULL;
	pSoap1 = factory1.creatSoap();
	pToothpaste1 = factory1.creatToothpaste();
	pSoap1->show();
	pToothpaste1->show();
	
	SoapBase *pSoap2 = NULL;
	ToothBase *pToothpaste2 = NULL;
	pSoap2 = factory2.creatSoap();
	pToothpaste2 = factory2.creatToothpaste();
	pSoap2->show();
	pToothpaste2->show();
	
	delete pSoap1;
	delete pSoap2;
	delete pToothpaste1;
	delete pToothpaste2;
	
	return 0;
}

运行结果:

具体情形：最近莫名肥皂需求激增!！ 于是要独立每个生产线，每个生产线只生产一种肥皂。

其实这才是真正的工厂模式，简单工厂模式只能算是“坑爹版”的工厂模式。我们能很容易看出工厂方法模式和简单工厂模式的区别之处。工厂方法模式的应用并不是只是为了封装对象的创建，而是要把对象的创建放到子类中实现：Factory中只是提供了对象创建的接口，其实现将放在Factory的子类ConcreteFactory中进行。
对于工厂方法模式的组成：
1)抽象工厂角色： 这是工厂方法模式的核心，它与应用程序无关。是具体工厂角色必须实现的接口或者必须继承的父类。
2)具体工厂角色：它含有和具体业务逻辑有关的代码。由应用程序调用以创建对应的具体产品的对象。
3)抽象产品角色：它是具体产品继承的父类或者是实现的接口。
4)具体产品角色：具体工厂角色所创建的对象就是此角色的实例。
缺点：每增加一种产品，就需要增加一个对象的工厂。如果这家公司发展迅速，推出了很多新的处理器核，那么就要开设相应的新工厂。在C++实现中，就是要定义一个个的工厂类。显然，相比简单工厂模式，工厂方法模式需要更多的类定义。
代码实现：

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

#include <iostream>
using namespace std;
enum SOAPTYPE {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 FactoryBase
{
	public:
	virtual soapBase * creatSoap() = 0;
};
class SFJFactory:public FactoryBase
{
	public:
	soapBase * creatSoap()
	{
		return new SFJSoap();
	}
};
class XSLFactory:public FactoryBase
{
	public:
	soapBase * creatSoap()
	{
		return new XSLSoap();
	}
};
class NASFactory:public FactoryBase
{
	public:
	soapBase * creatSoap()
	{
		return new NASSoap();
	}
};
int main()
{
	SFJFactory factory1;
	soapBase* pSoap1 = factory1.creatSoap();
	pSoap1->show();
	XSLFactory factory2;
	soapBase* pSoap2 = factory2.creatSoap();
	pSoap2->show();
	NASFactory factory3;
	soapBase* pSoap3 = factory3.creatSoap();
	pSoap3->show();
	delete pSoap1;
	delete pSoap2;
	delete pSoap3;
	return 0;
}

运行结果:

哈希表

散列表（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散列表。