Hash表分析以及Java实现

       这篇博客主要探讨Hash表中的一些原理/概念，及根据这些原理/概念，自己设计一个用来存放/查找数据的Hash表，并且与JDK中的HashMap类进行比较。

我们分一下七个步骤来进行。 

一。    Hash表概念

二 .      Hash构造函数的方法，及适用范围

三.       Hash处理冲突方法，各自特征

四.       Hash查找过程

五.       实现一个使用Hash存数据的场景-------Hash查找算法，插入算法

六.       JDK中HashMap的实现

七.       Hash表与HashMap的对比，性能分析

 

 一。    Hash表概念 

               在查找表中我们已经说过，在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样       我们就能预先知道所查关键字在表中的位置，从而直接通过下标找到记录。使ASL趋近与0.

 

              1)   哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地       址集合的大小不超出允许范围即可；

             2)  由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1¹ key2，而  f            (key1) = f(key2)。

              3).  只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字，       而地址集合的元素仅为哈希表中的地址值

 

       在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一      种“处理冲突” 的方法。

 

二 .     Hash构造函数的方法，及适用范围

• 直接定址法
• 数字分析法
• 平方取中法
• 折叠法
• 除留余数法
• 随机数法      

 

      （1）直接定址法：

                哈希函数为关键字的线性函数，H(key) = key 或者 H(key) = a ´ key + b

              此法仅适合于：地址集合的大小 = = 关键字集合的大小，其中a和b为常数。

     （2）数字分析法：

             假设关键字集合中的每个关键字都是由 s 位数字组成 (u₁, u₂, …, u_s)，分析关键字集中的全体，                  并从中提取分布均匀的若干位或它们的组合作为地址。

             此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

     （3）平方取中法：

               以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同                    时平方值的中间各位又能受到整个关键字中各位的影响。

             此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。

     （4）折叠法：

            将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分                割后的几部分低位对齐相加；间界叠加:从一端沿分割界来回折叠，然后对齐相加。

            此法适于：关键字的数字位数特别多。

     （5）除留余数法：

             设定哈希函数为:H(key) = key MOD p   ( p≤m )，其中， m为表长，p 为不大于 m 的素数，或                 是不含 20 以下的质因子

     （6）随机数法：

           设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数

           此法适于：对长度不等的关键字构造哈希函数。

 

         实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，以及哈希表    长度（哈希地址范围），总的原则是使产生冲突的可能性降到尽可能地小。

三.       Hash处理冲突方法，各自特征

 “处理冲突” 的实际含义是：为产生冲突的关键字寻找下一个哈希地址。

•   开放定址法
•   再哈希法
•   链地址法

      （1）开放定址法：

               为产生冲突的关键字地址 H(key) 求得一个地址序列： H₀, H₁, H₂, …, H_s  1≤s≤m-1，H_i = ( H(key)                 +d_i  ) MOD m，其中： i=1, 2, …, s，H(key)为哈希函数;m为哈希表长;

 

      （2）链地址法：

             将所有哈希地址相同的记录都链接在同一链表中。

 

      （3）再哈希法：

               方法：构造若干个哈希函数，当发生冲突时，根据另一个哈希函数计算下一个哈希地址，直到冲突不再发                  生。即：H_i=Rh_i(key)     i=1,2,……k，其中：Rh_i——不同的哈希函数，特点：计算时间增加

 四.       Hash查找过程

 

        对于给定值 K,计算哈希地址 i = H(K)，若 r[i] = NULL  则查找不成功，若 r[i].key = K  则查找成功， 否则 “求     下一地址 Hi” ，直至r[Hi] = NULL  (查找不成功)  或r[Hi].key = K  (查找成功) 为止。

 

 五.       实现一个使用Hash存数据的场景-------Hash查找算法，插入算法

         假设我们要设计的是一个用来保存中南大学所有在校学生个人信息的数据表。因为在校学生数量也不是特别巨大(8W?)，每个学生的学号是唯一的,因此，我们可以简单的应用直接定址法，声明一个10W大小的数组，每个学生的学号作为主键。然后每次要添加或者查找学生，只需要根据需要去操作即可。

      但是，显然这样做是很脑残的。这样做系统的可拓展性和复用性就非常差了，比如有一天人数超过10W了？如果是用来保存别的数据呢？或者我只需要保存20条记录呢？声明大小为10W的数组显然是太浪费了的。

 

     如果我们是用来保存大数据量（比如银行的用户数，4大的用户数都应该有3-5亿了吧？），这时候我们计算出来的HashCode就很可能会有冲突了， 我们的系统应该有“处理冲突”的能力，此处我们通过挂链法“处理冲突”。

 

     如果我们的数据量非常巨大，并且还持续在增加，如果我们仅仅只是通过挂链法来处理冲突，可能我们的链上挂了上万个数据后，这个时候再通过静态搜索来查找链表，显然性能也是非常低的。所以我们的系统应该还能实现自动扩容，当容量达到某比例后，即自动扩容，使装载因子保存在一个固定的水平上。

 

综上所述，我们对这个Hash容器的基本要求应该有如下几点：

             满足Hash表的查找要求（废话）

             能支持从小数据量到大数据量的自动转变（自动扩容）

             使用挂链法解决冲突

 

 

好了，既然都分析到这一步了，咱就闲话少叙，直接开始上代码吧。

 

package cn.javamzd.collection.search;

public class MyMap<K, V> {
	private int size;// 当前容量
	private static int INIT_CAPACITY = 16;// 默认容量
	private Entry<K, V>[] container;// 实际存储数据的数组对象
	private static float LOAD_FACTOR = 0.75f;// 装载因子
	private int max;// 能存的最大的数=capacity*factor

	// 自己设置容量和装载因子的构造器
	public MyMap(int init_Capaticy, float load_factor) {
		if (init_Capaticy < 0)
			throw new IllegalArgumentException("Illegal initial capacity: "
					+ init_Capaticy);
		if (load_factor <= 0 || Float.isNaN(load_factor))
			throw new IllegalArgumentException("Illegal load factor: "
					+ load_factor);
		this.LOAD_FACTOR = load_factor;
		max = (int) (init_Capaticy * load_factor);
		container = new Entry[init_Capaticy];
	}

	// 使用默认参数的构造器
	public MyMap() {
		this(INIT_CAPACITY, LOAD_FACTOR);
	}

	/**
	 * 存
	 * 
	 * @param k
	 * @param v
	 * @return
	 */
	public boolean put(K k, V v) {
		// 1.计算K的hash值
		// 因为自己很难写出对不同的类型都适用的Hash算法，故调用JDK给出的hashCode()方法来计算hash值
		int hash = k.hashCode();
		//将所有信息封装为一个Entry
		Entry<K,V> temp=new Entry(k,v,hash);
            if(setEntry(temp, container)){
            	// 大小加一
        		size++;
        		return true;
            }
            return false;
	}


	/**
	 * 扩容的方法
	 * 
	 * @param newSize
	 *            新的容器大小
	 */
	private void reSize(int newSize) {
		// 1.声明新数组
		Entry<K, V>[] newTable = new Entry[newSize];
		max = (int) (newSize * LOAD_FACTOR);
		// 2.复制已有元素,即遍历所有元素，每个元素再存一遍
		for (int j = 0; j < container.length; j++) {
			Entry<K, V> entry = container[j];
			//因为每个数组元素其实为链表，所以…………
			while (null != entry) {
				setEntry(entry, newTable);
				entry = entry.next;
			}
		}
		// 3.改变指向
		container = newTable;
		
	}
	
	/**
	 *将指定的结点temp添加到指定的hash表table当中
	 * 添加时判断该结点是否已经存在
	 * 如果已经存在，返回false
	 * 添加成功返回true
	 * @param temp
	 * @param table
	 * @return
	 */
	private boolean setEntry(Entry<K,V> temp,Entry[] table){
		// 根据hash值找到下标
		int index = indexFor(temp.hash, table.length);
		//根据下标找到对应元素
		Entry<K, V> entry = table[index];
		// 3.若存在
		if (null != entry) {
			// 3.1遍历整个链表，判断是否相等
			while (null != entry) {
				//判断相等的条件时应该注意，除了比较地址相同外，引用传递的相等用equals()方法比较
				//相等则不存，返回false
				if ((temp.key == entry.key||temp.key.equals(entry.key)) && temp.hash == entry.hash&&(temp.value==entry.value||temp.value.equals(entry.value))) {
					return false;
				}
				//不相等则比较下一个元素
				else if (temp.key != entry.key && temp.value != entry.value) {
						//到达队尾，中断循环
						if(null==entry.next){
							break;
						}
						// 没有到达队尾，继续遍历下一个元素
						entry = entry.next;
				}
			}
			// 3.2当遍历到了队尾，如果都没有相同的元素，则将该元素挂在队尾
			addEntry2Last(entry,temp);
				
		}
		// 4.若不存在,直接设置初始化元素
		setFirstEntry(temp,index,table);
		return true;
	}
	
    private void addEntry2Last(Entry<K, V> entry, Entry<K, V> temp) {
    	if (size > max) {
			reSize(container.length * 4);
		}
    	entry.next=temp;
		
	}

	/**
     * 将指定结点temp，添加到指定的hash表table的指定下标index中
     * @param temp
     * @param index
     * @param table
     */
	private void setFirstEntry(Entry<K, V> temp, int index, Entry[] table) {
		// 1.判断当前容量是否超标，如果超标，调用扩容方法
		if (size > max) {
			reSize(table.length * 4);
		}
		// 2.不超标，或者扩容以后，设置元素
		table[index] = temp;
		//！！！！！！！！！！！！！！！
		//因为每次设置后都是新的链表，需要将其后接的结点都去掉
		 //NND，少这一行代码卡了哥哥7个小时（代码重构）
		temp.next=null;
	}

	/**
	 * 取
	 * 
	 * @param k
	 * @return
	 */
	public V get(K k) {
		Entry<K, V> entry = null;
		// 1.计算K的hash值
		int hash = k.hashCode();
		// 2.根据hash值找到下标
		int index = indexFor(hash, container.length);
		// 3。根据index找到链表
		entry = container[index];
		// 3。若链表为空，返回null
		if (null == entry) {
			return null;
		}
		// 4。若不为空，遍历链表，比较k是否相等,如果k相等，则返回该value
		while (null != entry) {
			if (k == entry.key||entry.key.equals(k)) {
				return entry.value;
			}
			entry = entry.next;
		}
		// 如果遍历完了不相等，则返回空
		return null;

	}

	/**
	 * 根据hash码，容器数组的长度,计算该哈希码在容器数组中的下标值
	 * 
	 * @param hashcode
	 * @param containerLength
	 * @return
	 */
	public int indexFor(int hashcode, int containerLength) {
		return hashcode & (containerLength - 1);

	}

	/**
	 * 用来实际保存数据的内部类,因为采用挂链法解决冲突，此内部类设计为链表形式
	 * 
	 * @param <K>key
	 * @param <V>
	 *            value
	 */
	class Entry<K, V> {
		Entry<K, V> next;// 下一个结点
		K key;// key
		V value;// value
		int hash;// 这个key对应的hash码，作为一个成员变量，当下次需要用的时候可以不用重新计算

		// 构造方法
		Entry(K k, V v, int hash) {
			this.key = k;
			this.value = v;
			this.hash = hash;

		}

		//相应的getter()方法

	}
}

 

 代码中有相当清楚的注释了

 

在文章的最后这里，我要强烈的宣泄下感情

MLGBD，本来以为分析的挺到位了，写出这个东西也就最多需要个把小时吧

结果因为通宵作业，脑袋运转不灵

硬是花了哥三个小时才写出了

好不容易些出来了

我日

看着代码比较混乱

然后就对代码重构了下

把逻辑抽象清楚，进行重构就花了个多小时

好不容易构造好了

就开始了TMD的一直报错了----------大数据量测试时到大概5000就死循环了

各种调试，各种分析都觉得没错误

 最后花了哥7个小时终于找出来了

我擦

 

第一次初始化加的时候，因为每个元素的next都是空的

而扩充容量resize()时，因为冲突处理是链式结构的

当将他们重新hash添加的时候，重复的这些鸟元素的next是有元素的

一定要设置为null

 

 

七.性能分析：

      1.因为冲突的存在，其查找长度不可能达到O(1)

      2哈希表的平均查找长度是装载因子a 的函数，而不是 n 的函数。

      3.用哈希表构造查找表时，可以选择一个适当的装填因子  ，使得平均查找长度限定在某个范围内。

  
   最后给出我们这个HashMap的性能

  测试代码

public class Test {

	public static void main(String[] args) {
		MyMap<String, String> mm = new MyMap<String, String>();	
		Long aBeginTime=System.currentTimeMillis();//记录BeginTime
		for(int i=0;i<1000000;i++){
        mm.put(""+i, ""+i*100);
		}
		Long aEndTime=System.currentTimeMillis();//记录EndTime
		System.out.println("insert time-->"+(aEndTime-aBeginTime));
		
		Long lBeginTime=System.currentTimeMillis();//记录BeginTime
		mm.get(""+100000);
		Long lEndTime=System.currentTimeMillis();//记录EndTime
		System.out.println("seach time--->"+(lEndTime-lBeginTime));
	}
}

  100W个数据时，全部存储时间为1S多一点，而搜寻时间为0 

insert time-->1536
seach time--->0

 

 

好了，牢骚发完了

本来今天想写个有关大访问量处理的一些基本概念的文章

全泡汤了,明天写吧

 

评论

12 楼 程序员是怎么炼成的 2016-05-05  

initCacpcity和loadFactor为什么要static ？ 会不会有影响？

11 楼 gc00001 2015-09-13  

有几个bug
1.没有判断key相同value不同的情况 否则会死循环
2.109行那少了return true 否则addEntry2Last后又会执行setFirstEntry
3.resize要一个一个重新setEntry(entry, newTable); 的时候你140行把temp.next=null;导致66行entry.next变为null了,这样只往新table里放了个链头元素,我试着用了下深克隆发现性能很差所以可以这样改进，65行改为setEntry(new Entry(entry.key,entry.value,entry.hash), newTable);

10 楼 Wuaner 2012-09-16  

文章不错 ， 把HashMap copy了一遍，辛苦！

9 楼 xichao1929 2011-11-22  

学长：
（5）除留余数法：

             设定哈希函数为:H(key) = key MOD p   ( p≤m )，其中， m为表长，p 为不大于 m 的素数，或是不含 20 以下的质因子


“是不含 20 以下的质因子”这句话怎样理解？

8 楼 dengyi04405 2010-12-16  

错了...是mm.get(""+36309) 为null，在最后resize的时候挂在9的一起，然后丢失了。

setEntry(entry, newTable);   ----entry在first时next=null
entry = entry.next;---永远是null

7 楼 dengyi04405 2010-12-16  

resize()好像还是有bug，挂在一个链地址下的数据resize时只能取出第一个，后面的数据就丢失了。
for(int i=0;i<90000;i++) 循环后mm.get(""+100000)   是null
不知道是不是，楼主看看  

6 楼 java_mzd 2010-12-01  

heng_aa 写道

无聊又测了一下，死循环是因为while没有这种情况的判断，我是加上这些代码的：
else if(temp.key == entry.key && temp.value != entry.value) {
entry.value = temp.value;
return true;
}

还有我查找不到数据，应该是在109行那里少加了这句吧，return true;因为没有这句下面的setFirstEntry(temp,index,table); 还会执行。  
看看是不是这样！！！

恩~~确实需要加上这个判断~
不然当传入相同的key不同的value的时候，不会覆盖掉原理的value
这时候linked里面就会有相同的key，不同的value，后面那个value就没意义了。
  只是，这样还是没有死循环吖。。囧

恩，无论如何，这个BUG是确实需要改进的。

5 楼 heng_aa 2010-11-30  

无聊又测了一下，死循环是因为while没有这种情况的判断，我是加上这些代码的：
else if(temp.key == entry.key && temp.value != entry.value) {
entry.value = temp.value;
return true;
}

还有我查找不到数据，应该是在109行那里少加了这句吧，return true;因为没有这句下面的setFirstEntry(temp,index,table); 还会执行。  
看看是不是这样！！！

4 楼 java_mzd 2010-11-30  

heng_aa 写道

我测试了一下，发现几个问题。如果放入相同的key不同的value,程序就死循环了！还有扩容后，indexFor（）的算值就不同了，也就是说通过这个算法查找不到值了。无聊试一下而已，不过我也学到了不少东西，看这些问题能不能改进？？

谢谢提醒哦

分几点分析吧
扩容后，通过indexFor()计算的值肯定是需要变化的啊，因为这个时候计算规则变了啊
需要把每个元素重新散列到数组里去啊，这时候通过get()再取的时候，计算的时候，indexFor()是按照新的数组大小来的，所以肯定还是能找到的啊

至于死循环的问题，在重构代码前我测试是正常的，重构后忘了测试这个问题了。。
囧。。。等晚上再测试下再回答你吧。

3 楼 heng_aa 2010-11-30  

我测试了一下，发现几个问题。如果放入相同的key不同的value,程序就死循环了！还有扩容后，indexFor（）的算值就不同了，也就是说通过这个算法查找不到值了。无聊试一下而已，不过我也学到了不少东西，看这些问题能不能改进？？

2 楼 java_mzd 2010-11-29  

smithfox 写道

好文，对动态大数据量的Hash处理很有用.
幸苦了，注意身体呀!

多谢关照~~

1 楼 smithfox 2010-11-29  

好文，对动态大数据量的Hash处理很有用.
幸苦了，注意身体呀!