全局变量：
 如想传递变量，程序可以在main函数中，利用Congfiguraion类的set函数将一些简单的数据结构放到到Congfiguraion中，map或reduce task任务启动的过程中（比如setup函数）通过Configuration类的get函数读取即可。

 一切的代码和上面都一样，只是加了一个全局变量的特性。
 package com;
 import java.io.File;
 import java.io.IOException;
 import org.apache.hadoop.conf.Configuration;
 import org.apache.hadoop.fs.Path;
 import org.apache.hadoop.io.DoubleWritable;
 import org.apache.hadoop.io.Text;
 import org.apache.hadoop.mapreduce.Job;
 import org.apache.hadoop.mapreduce.Mapper;
 import org.apache.hadoop.mapreduce.Reducer;
 import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
 import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

 public class TopNTestMark_to_win {

     public static class TokenizerMapper extends Mapper<Object, Text, Text, DoubleWritable> {
         String name;
         protected void setup(Context context)
                 throws IOException, InterruptedException {
                 //从全局配置获取配置参数
                 Configuration conf = context.getConfiguration();
                 name = conf.get("name"); //这样就拿到了，但不能设置。想设置用其他方法。这里不深究了
         }
 /*
 o1,p2,250.0
 o2,p3,500.0
 o2,p4,100.0
 o2,p5,700.0
 o3,p1,150.0
 o1,p1,200.0
 */       
 
更多请见：http://www.mark-to-win.com/tutorial/mydb_MapReduce_GlobalVariable.html

LeetCode全局变量问题 - 由构造二叉树发现的
 
今天有小伙伴（好基友）问了我一个问题，他在LeetCode刷到一道题，碰到一个问题一直没想通，也不知道怎么解决，于是过来让我一起看。为了说清楚这个问题，我们先看题目：
 
根据一棵树的前序遍历与中序遍历构造二叉树。
 
注意：你可以假设树中没有重复的元素。
 
例如，给出
 
前序遍历 preorder = [3,9,20,15,7] 
中序遍历 inorder = [9,3,15,20,7]
 
返回如下的二叉树：
 
    3
   / \
  9  20
    /  \
   15   7
 
这道题本身并不难，在LeetCode中的难度定义是中等，很显而易见的思路就是递归构造，因为前序遍历的第一个元素就是根节点，那么在中序遍历中定位到根节点后，根据中序遍历的结果就可以知道左子树和右子树中的节点数，于是就可以递归调用了。小伙伴给出的C代码如下：
 
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){

	if (preorderSize <= 0) return NULL;
	if (inorderSize <= 0) return NULL;

	int idxIn;
	struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	root->val = preorder[0];

	/* find preorder[0] in inorder, the index is idxIn */
	idxIn = 0;
	while (idxIn < inorderSize) {
		if (preorder[0] == inorder[idxIn]) break;
		idxIn++;
	}

	if (idxIn != 0) { // left child exists
		root->left = buildTree(&preorder[1], idxIn, inorder, idxIn);
	} else { // no left child
		root->left = NULL;
	}

	if (idxIn != inorderSize-1) { // right child exists
		root->right = buildTree(&preorder[idxIn+1], inorderSize-idxIn-1, &inorder[idxIn+1], inorderSize-idxIn-1);
	} else { // no right child
		root->right = NULL;
	}

	return root;
}
 
此代码运行没有问题，在LeetCode上提交也通过了。然而小伙伴是一个有钻研精神的人，用一种方法解决问题之后并不死心，又去研究别人的解法。（嗯，此精神值得学习！）
 
很容易就可以发现上面的代码中是直接扫描整个中序遍历的结果并找出根节点的，因为递归调用，会重复找很多次，于是想到可以用一个哈希表来记录结果，这样只需要扫描一次，后面只要直接根据键值查询就可以了，缩短了运行时间。这也没啥，小伙伴一看思路就明白。然而，就在这个时候，他看到了另外一种解法，不用哈希表居然也实现了只扫描一次的效果，小伙伴这回惊呆了！（事实上我听他说到这里也惊呆了，还有这种操作？！）
 
答案是有！小伙伴给出了他按这个思路修改后的C代码：
 
int gIdxPre = 0;
int gIdxIn = 0;
int gLength = 0;

struct TreeNode* buildTreeHelper(int* preorder, int* inorder, long long stopVal) {
	if(gIdxPre == gLength) { // To the end, return
		return NULL;
	}
	if (inorder[gIdxIn] == stopVal) { // if equal to stop value, stop and return
		gIdxIn++;   // this value is used, go to next
		return NULL;
	}
	int rootVal = preorder[gIdxPre++];
	struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	root->val = rootVal;
	root->left = buildTreeHelper(preorder, inorder, rootVal);
	root->right = buildTreeHelper(preorder, inorder, stopVal);
	return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
	gLength = preorderSize;
	return buildTreeHelper(preorder, inorder, 0x7FFFFFFFFFF); // stop value != any value in tree
}
 
此方法中模拟了一个前序遍历的过程，用了一个停止值stopVal来指定子树扫描的停止位置，而初始的停止值是一个与任意树中的元素都不相等的数，所以这里用了一个long long型的超范围值。
 
我知道这个方法不太好理解，所以以LeetCode上的输入为例做了一个动图如下：
 
 从图中可以看出，对输入数组只遍历了一次。
 
说到这里，问题终于要来了，这个代码在本地跑没问题，在LeetCode上执行代码也没问题，然而提交就报错，如下图，同样都是输入空数组（应该是第一个测试用例），点执行代码，输出与预期结果一致；点提交，就报错，而且就是这个输入的报错。
 
 看到这个结果，本来没有LeetCode帐号的我去注册了一个号，亲测了一遍，结果一样，提交就报错。小伙伴很无辜的眼神看着我，问我代码哪里有问题，我也一脸懵啊！
 
想了半天，觉得还是环境的问题。毕竟我们看不到LeetCode上的其他执行部分的代码。不要去纠结为什么同样的代码同样的输入结果就不一样了，肯定是我们看不到的地方有不一致。那么怎么解决呢？
 
LeetCode上也无法直接调试（貌似要会员才可以），从出错结果看是堆栈溢出，那么结合代码看就是不断在malloc，也就是该返回NULL的时候没返回NULL，所以要从这个地方入手。第一个返回NULL的地方就是
 
if(gIdxPre == gLength)
 
可能这个条件没满足，于是把 == 改为了 >= ，再次提交。这次结果有了变化（有变化就好啊），变成了解答错误，出错的用例变了，可见之前的那个用例过了。
 
 当然，执行代码的结果依然是正确的：
 
 这就有意思了，可见就可能是这里出的问题。然而我无法调试，也没有办法加打印。怎么办呢？既然是怀疑这句的问题，那就把这两个值都好好分析一下，gLength 在函数中初始化为 preorderSize，然而 gIdxPre 在函数中并没有初始化，因为全局变量定义时已经初始化了。本着怀疑一切的精神，在 buildTree 函数中加上了一句：
 
gIdxPre = 0;
 
再次提交，还是不行，想到还有一个全局变量，于是再加上
 
gIdxIn = 0;
 
再次提交，终于成功了：
 
 
最终代码如下：
 
int gIdxPre = 0;
int gIdxIn = 0;
int gLength = 0;

struct TreeNode* buildTreeHelper(int* preorder, int* inorder, long long stopVal) {
	if(gIdxPre == gLength) { // To the end, return
		return NULL;
	}
	if (inorder[gIdxIn] == stopVal) { // if equal to stop value, stop and return
		gIdxIn++;   // this value is used, go to next
		return NULL;
	}
	int rootVal = preorder[gIdxPre++];
	struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
	root->val = rootVal;
	root->left = buildTreeHelper(preorder, inorder, rootVal);
	root->right = buildTreeHelper(preorder, inorder, stopVal);
	return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
	gLength = preorderSize;
    gIdxPre = 0;
    gIdxIn = 0;
	return buildTreeHelper(preorder, inorder, 0x7FFFFFFFFFF); // stop value != any value in tree
}
 
由此过程可以发现：LeetCode 提交后运行时代码中的全局变量并没有成功初始化，保险起见，需要在函数中重新初始化全局变量。
 
最后，我的小伙伴带着这个结论愉快地继续去刷题了~

 
1.创建一个全局的HASH表
 
 
initialization
  g_hash := THashedStringList.Create;
finalization
  FreeAndNil(g_hash);
 
 
 
 
 
2.往全局HASH表里面写入 INI文件的指定小节(字符串定义集中放在一个小节里面)读取到的所有行，每次更选择语言以后都要执行此操作。
 
 
ini.ReadSectionValues('messages', g_hash);
 
 
3.所有需要使用字符串变量从这个全局HASH表中检索
 
 
function GetHashStr(const key: string): string;
begin
  Result := GetHash.Values[key];
end;  
 
 
 

 
什么是哈希表？
 
   哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
 
记录的存储位置=f(关键字)
 
这里的对应关系f称为散列函数，又称为哈希（Hash函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。
 
哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）
     而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
 
 
 
数组的特点是：寻址容易，插入和删除困难；
 
而链表的特点是：寻址困难，插入和删除容易。
 
那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：
 

 左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
 
 
 
 Hash的应用
 
1、Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
 
2、查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！
 
举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。
 
3、Hash表在海量数据处理中有着广泛应用。
 
 
 
 
 
Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。
 
hash就是找到一种数据内容和数据存放地址之间的映射关系。
 
散列法：元素特征转变为数组下标的方法。
 
我想大家都在想一个很严重的问题：“如果两个字符串在哈希表中对应的位置相同怎么办？”,毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用“链表”。我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。
 
散列表的查找步骤 
 
当存储记录时，通过散列函数计算出记录的散列地址
 
当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录
 
 
 
关键字——散列函数（哈希函数）——散列地址
 
优点：一对一的查找效率很高；
 
缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。
 
散列冲突：不同的关键字经过散列函数的计算得到了相同的散列地址。
 
好的散列函数=计算简单+分布均匀（计算得到的散列地址分布均匀）
 
哈希表是种数据结构，它可以提供快速的插入操作和查找操作。
 
 
 
优缺点
 
优点：不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。
 
哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
 
如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。
 
缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。
 
 
 
    元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的：
 
1，除法散列法 
 最直观的一种，上图使用的就是这种散列法，公式： 
       index = value % 16 
 学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。
 
2，平方散列法 
 求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式： 
       index = (value * value) >> 28   （右移，除以2^28。记法：左移变大，是乘。右移变小，是除。）
 如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。
 
3，斐波那契（Fibonacci）散列法
 
平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。
 
1，对于16位整数而言，这个乘数是40503 
 2，对于32位整数而言，这个乘数是2654435769 
 3，对于64位整数而言，这个乘数是11400714819323198485
 
    这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。
 
    对我们常见的32位整数而言，公式： 
             index = (value * 2654435769) >> 28
 
    如果用这种斐波那契散列法的话，那上面的图就变成这样了：
 

 注：用斐波那契散列法调整之后会比原来的取摸散列法好很多。 
 
适用范围
     快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。
 
基本原理及要点
     hash函数选择，针对字符串，整数，排列，具体相应的hash方法。 
 碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。
 
 
 
 
 
散列冲突的解决方案：
 
1.建立一个缓冲区，把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时，发现找的不对，就在缓冲区里找。
 
2.进行再探测。就是在其他地方查找。探测的方法也可以有很多种。
 
（1）在找到查找位置的index的index-1，index+1位置查找，index-2，index+2查找，依次类推。这种方法称为线性再探测。
 
（2）在查找位置index周围随机的查找。称为随机在探测。
 
（3）再哈希。就是当冲突时，采用另外一种映射方式来查找。
 
这个程序中是通过取模来模拟查找到重复元素的过程。对待重复元素的方法就是再哈希：对当前key的位置+7。最后，可以通过全局变量来判断需要查找多少次。我这里通过依次查找26个英文字母的小写计算的出了总的查找次数。显然，当总的查找次数/查找的总元素数越接近1时，哈希表更接近于一一映射的函数，查找的效率更高。
 
 
 
扩展 
     d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。
 
 
 
问题实例（海量数据处理） 
     我们知道hash 表在海量数据处理中有着广泛的应用，下面，请看另一道百度面试题：
 题目：海量日志数据，提取出某日访问百度次数最多的那个IP。
 方案：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。