为什么是哈希表？！

为什么是哈希表？！

1、提出问题：

       这里有一个大的跨国公司，公司中的职员信息全部存储在数据库中。对于其中的任何一个职员来说，他们的唯一标识就是员工号，而这个公司的员工号是按照职员工作的地点以及部门及工作开始时间确定的，比如01-20-09-24-3，这一个职工编号（纯属杜撰，但也有实际作用，因为在像群体查找时会比较方便等），其中的01代表亚洲办公区员工，20表示在研发部门，09-24表示09年9月24号入职，3表示为当天入职的第三个人。这样每一个员工号就代表唯一的一个员工，假如现在我们需要随机抽取20000名员工搞一个什么活动，然后我们需要从数据库取出20000个员工的信息存在一个地方，然后对员工信息进行一系列的操作，无非增、删、改、查，现在就会出现一个问题，我们怎么存储这20000个员工的信息，使得操作的时间更快？

       我们会想到的是什么，数组？链表？

              如果是数组，那我们怎么根据一个员工号来得到员工所在数组的索引，快速返回相应的员工信息呢？

              如果是链表，难道我们每次查找时都要遍历整个链表吗？如果员工数更多，这样可行吗？

       由此就引出为什么是哈希表？

              因为实际中会存在上述的问题，因此哈希表应运而生，在大数据量中进行查找，为了提高速度，我们会选择数组，因为如果知道数据在数组中的索引，那么时间复杂度就是O(1)的，但是对于实际中的这些问题，数组的索引就不是那么好得到的。比如就像上面那样，知道员工号，来找数据，而员工号根本不是索引！所以我们需要根据员工号来生成索引，那么我们给定一个员工号，就会对应一个索引，那么就可以直接找到存储的位置，这样就很好了。

             因此，上面最后所说的由员工号拿到数组的索引的过程，就是一个哈希化过程。哈希化过程：给定关键字，通过哈希函数，生成确定的索引值。

 

2、给出上述问题的解决方法（一步步演示用哈希表处理）：

       我们现在明确一下目标，就是根据职员号生成数组索引，将职员数据存入数组中，快速进行修改！

       哈希表的方法是什么呢？

       哈希表的方法是，对于键值（这里是职员号）给出一个映射，将键值映射到确定的数组索引上，每次查找时，只需要输入键值，然后根据映射找到索引就可以进行操作。因为键值的数据类型各式各样，那么这个映射也是五花八门，没有固定的取法，但是对于这个映射最好满足两个要求：计算方便、产生的索引随机性好！

这样映射在哈希表中称为哈希函数。对于上面的职员号，我们可以简单的定义一个哈希函数为，对于上面的职员号转化为整数，直接对于存储数组的大小进行取余运算，通过这样的方法来生成数组索引。对于存储的数组一般选取的都会比要存储的元素大，对于现在已知所需存储数据的大小，经证明一般来说，当所存储的数据是整个数组的2/3时，效果比较好，因此我们的存储数组大小可以设定为30001，为什么是30001呢？选取质数的原因与后面怎么解决哈希冲突有莫大的关系！

         给出哈希函数如下： 

/**
 * 根据key值，进行hash过程
 * 其中的capacity为数组容量大小
 * @param key	传进来的键值key
 * @return	返回hash函数产生的数组索引值
 */
public int hash(String key){
	int k = Integer.parseInt(key);
	return k % capacity;
}

       那么从上面很容易就会知道，这样的哈希函数，对于不同的键值可能产生相同的数组索引值，这就是所谓的哈希冲突。

 

       对于解决哈希冲突，有两种方法：开放地址法和链地址法。

      （在这里我们使用开放地址法，因为在下一篇分析HashTable和HashMap博客中会分析链地址法）

        一般来说，对于开放地址法，又可以分为：线性探测法、二次探测和再哈希。（不要被名词吓着......其实都很简单）

        首先概述一下对于开放地址法的这三种方法的大体实现思想：

 

        线性探测：当经过hash方法计算产生数组索引后，如果发生冲突，那么就检查索引的下一位数组是否空着，如果空着，那么就将数据放置进去，如果没有空着，则继续向下一位进行检测，知道将数据放入或是数组已经放满。示例代码：

 

public void put(String key,Clerk clerk){
	int index = hash(key);
	while(clerkArray[index] != null){
		++index;
		index %= clerkArray.length;
	}
	clerkArray[index] = clerk;
}

 

        二次探测：同样的类似上面的线性探测，但是这次不是移向下一位，而是这样移动，第一个移动1^2位，如果非空，则继续再移动2^2位，如果还是非空，那么再移动3^2位，以此类推。

 

public void put(String key,Clerk clerk){
	int index = hash(key);
	int step = 1;
	while(clerkArray[index] != null){
		index += Math.pow(step++, 2);
		index %= clerkArray.length;
	}
	clerkArray[index] = clerk;
}

 

           再哈希：对于上面两种处理冲突的方法，只要是映射到同一索引位置，如果发生冲突，所有的冲突元素的移位步长都是相同的，所以为了避免这种情况，才会有了再哈希这个方法，方法是，在冲突时，对于键值，再经过一个hash方法的计算，来生成对于特定键值有特定步长，这样即使是映射到同一索引位置放生冲突，但是对于不同的键值，处理冲突移动的步长会不同。

 

public void put(String key,Clerk clerk){
	int index = hash(key);
	int step = hashStep(key);
	while(clerkArray[index] != null){
		index += step;
		index %= clerkArray.length;
	}
	clerkArray[index] = clerk;
}
	
public int hashStep(String key){
	return 5 - Integer.parseInt(key) % 5;
}

 

        也许我们会问，为什么会有这三种方法呢？产生的原因是什么呢？

        产生这三个方法的原因是，在处理哈希冲突的时候会引起聚焦（就是元素会聚集在发生冲突的地方，从而会影响哈希表的性能），因此这三种方法依次减弱了这种聚焦效应。同时在这里也可以解释为什么数组的长度要选择质数？如果不选择质数，那么总有一个比原数小，而比1大的数整除这个长度，所以当我们按照我们选择的步长去移动时，可能会出现整除数组长度的情况，那么这会使得移动跳过某些空位，而在固定的几个位置上进行检测，但是如果长度是质数，就会避免这种情况。

 

3、问题总结

 

      现在我们可以由上面的结果，就可以实现我们自己的哈希表了，因为上面已经描述了，如何进行哈希化处理得到数组索引，在得到索引冲突时，该如何处理冲突。然后剩下的工作就是围绕这两点展开的，来实现查找，删除或是添加等方法，在这里就不再赘述了。

 

       下一篇博客会来分析自带的Hashtable和HashMap源码，来提高对哈希的进一步认识，及Hashtable和HashMap之间的比较！