hashmap与hashtable的比较

首先补充一点：

前面写的一些有关于hashmap的结构分析的时候，后面进行了性能的测试，忘记说一点了，之前我用1000000个数据去测试的时候老是报“Exception in thread "main" java.lang.OutOfMemoryError: Java heap space ”错误，结果在网上搜了一下出错的原因和解决方法

原因是：eclipse在虚拟机上进行数据处理的存储空间不足，导致有堆空间的溢出；

解决办法为：首先， 打开Eclipse软件，选择菜单栏run,在二级菜单中选择 Debug Configurations，然后：在弹出的窗口中选择（x）=arguments选项卡，VM arguments中输入所需要的内存最大占用量，比如输入-Xmx800m即可。
还有eclipse中console输出控制台，输出限定大小，可通过windows—Run/Debug—Console中的Console buffer size大小进行修改，这样可以使得console的空间变成size大小。

 

好吧，进入这一节的主题hashmap与hashtable的比较

前面讲了hashmap的结构，其实hashtable的结构与hashmap的差不多，就只有两点区别：

1、hashtable可以进行线程同步处理，而hashmap就不行

2、Hashtable不允许插入关键字为null的键值对，而hashmap可以

好了，废话少说，看代码吧！

这里是自己写的hashtable：

     

package cn.java1118;
/**
 * 自己写的hashtable类
 * @author acer
 *
 * @param <K>关键字的类型
 * @param <V>数据域的类型
 */

public class MyHashTable<K,V> {
	
	//存放键值对的链表节点数组
	private Entry[] table;
	//table中实际存放的数据的个数
	private int count;
	//装载因子
	private float loadFactor;
	//在当前的装载因子下所能存放的数据量，即数据存放容量
	private int threshold;

	/**
	 * 构造函数，初始化hashtable的大小和装载因子的大小
	 * @param initialCapacity:初始化容量数组的大小
	 * @param loadFactor:装载因子
	 */
	public MyHashTable(int initialCapacity, float loadFactor) {
		//容量小于0的时候报错
		if (initialCapacity < 0)
		    throw new IllegalArgumentException("Illegal Capacity: "+
	                                               initialCapacity);
		//装载因子小于0或者不是一个数值的时候也报错
	        if (loadFactor <= 0 || Float.isNaN(loadFactor))
	            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
	        //当容量为0的时候，系统默认容量为1
	        if (initialCapacity==0)
	            initialCapacity = 1;
	        //实例化节点数组
		this.loadFactor = loadFactor;
		table = new Entry[initialCapacity];
		threshold = (int)(initialCapacity * loadFactor);
	    }
	//默认的装载因子为0.75的构造函数
	public MyHashTable(int initialCapacity) {
		this(initialCapacity, 0.75f);
	    }
	//初始化容量为11和装载因子为0.75的默认构造函数
	public MyHashTable() {
		this(11, 0.75f);
	    }
	//hashtable的大小
	public synchronized int size() {
		return count;
	    }
	//判断hashtable是否为空
	public synchronized boolean isEmpty() {
		return count == 0;
	    }
	/**
	 * 根据键取值
	 * @param key:键
	 * @return:值
	 */
	public synchronized V get(Object key) {
//		Entry tab[] = table;
		//取得系统提供的hashcode
		int hash = key.hashCode();
		//根据系统提供的算法将这个hashcode转化为哈希地址
		int index = (hash & 0x7FFFFFFF) % table.length;
		//根据关键字取得值
		for (Entry<K,V> e = table[index] ; e != null ; e = e.next) {
		    if ((e.hash == hash) && e.key.equals(key)) {
			return e.value;
		    }
		}
		return null;
	    }
	/**
	 * 再哈希的过程
	 */
	protected void rehash() {
		int oldCapacity = table.length;
		Entry[] oldMap = table;
		//容量扩大为原来的两倍+1
		int newCapacity = oldCapacity * 2 + 1;
		Entry[] newMap = new Entry[newCapacity];

		threshold = (int)(newCapacity * loadFactor);
		table = newMap;
		//将原来hashtable中的键值对重新放入到新的hashtable中去
		for (int i = oldCapacity ; i-- > 0 ;) {
		    for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
			Entry<K,V> e = old;
			old = old.next;
			//再哈希之后，计算新的哈希地址
			int index = (e.hash & 0x7FFFFFFF) % newCapacity;
			e.next = newMap[index];
			newMap[index] = e;
		    }
		}
	    }
	/**
	 * 插入键值对
	 * @param key:键
	 * @param value:值
	 * @return
	 */
	 public synchronized V put(K key, V value) {
			// 当关键字为null的时候就报错
			if (value == null) {
			    throw new NullPointerException();
			}

			//不能出现重复的
//			Entry tab[] = table;
			int hash = key.hashCode();
			int index = (hash & 0x7FFFFFFF) % table.length;
			for (Entry<K,V> e = table[index] ; e != null ; e = e.next) {
			    if ((e.hash == hash) && e.key.equals(key)) {
				V old = e.value;
				e.value = value;
				return old;
			    }
			}

			//现在存放的数据量是否已经超出了在目前装载因子的情况下最大的容量，超过了就要再哈希
			if (count >= threshold) {
			    rehash();
			    //table是再哈希了的hashtable
//		        tab = table;
		        index = (hash & 0x7FFFFFFF) % table.length;
			}

			//建立一个新的键值对的节点
			Entry<K,V> e = table[index];
			table[index] = new Entry<K,V>(hash, key, value, e);
			count++;
			return null;
		    }
	 /**
	  * 移除数据
	  * @param key:键
	  * @return:值
	  */
	 public synchronized V remove(Object key) {
//			Entry tab[] = table;
			int hash = key.hashCode();
			int index = (hash & 0x7FFFFFFF) % table.length;
			//检查这个关键字是否存在
			for (Entry<K,V> e = table[index], prev = null ;
					e != null ; prev = e, e = e.next) {
			    if ((e.hash == hash) && e.key.equals(key)) {
			    	//移除e这个节点
				if (prev != null) {
				    prev.next = e.next;
				} else {
					table[index] = e.next;
				}
				count--;
				//消除节点e对象
				V oldValue = e.value;
				e.value = null;
				return oldValue;
			    }
			}
			return null;
		    }
	
	//节点内部类
	 private static class Entry<K,V>{
		 //该节点的hashcode
		int hash;
		//关键字
		K key;
		//数据域
		V value;
		//下一个节点
		Entry<K,V> next;
		//构造函数，设置hashcode，关键字和数据域，下一个节点
		private Entry(int hash, K key, V value, Entry<K,V> next) {
		    this.hash = hash;
		    this.key = key;
		    this.value = value;
		    this.next = next;
		}
		// 设置和取得这些属性的方法
		public K getKey() {
		    return key;
		}
		public V getValue() {
		    return value;
		}
		//判断两个接点是不是相等
		public boolean equals(Object o) {
		    if (!(o instanceof Entry))
			return false;
		    Entry e = (Entry)o;
		    //关键字和数据域的值都要相等
		    return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
		       (value==null ? e.getValue()==null : value.equals(e.getValue()));
		}
	    }
}

 

 同步测试的代码：

因为这里hashtable里面是每一个方法进行了同步，也就是说每一个方法只允许一个线程操作！这里我用了插入和查询来说明这个同步的问题吧！

测试的时候跟线程的随机性有关！所以我测出来的情况是这样的，用10个线程测试，9个进行插入，一个作为查找，当用hashmap的时候，查询报空的概率大一些，当用hashtable的时候，查询报空的概率小一些。。。暂时也只能测到这个样子。。。的、看代码吧：

 

package cn.java1118;

/**
 * 测试hashmap和hashtable的线程处理的同步性能
 * @author acer
 *
 */
public class TestSynchronized01 extends Thread{
	
	public static void main(String[] args) {
		//实例化一个hashmap，并进行初始化
		MyHashMap04<Integer, String> mm = new MyHashMap04<Integer, String>();
		for(int j=0;j<100;j++){
			mm.add(j, "数据域"+j);
//			System.out.println("执行了！！！");
		}
//		System.out.println(">>>>>"+mm.getValue(4));
//		TestSynchronized01 test1 = new TestSynchronized01(2, 4,mm);
//		TestSynchronized01 test2 = new TestSynchronized01(2, 5,mm);
//		TestSynchronized01 test4 = new TestSynchronized01(2, 8,mm);
//		TestSynchronized01 test5 = new TestSynchronized01(2, 6,mm);
//		TestSynchronized01 test6 = new TestSynchronized01(2, 7,mm);
//		TestSynchronized01 test3 = new TestSynchronized01(1, 7,mm);
//		test1.start();
//		test2.start();
//		test3.start();
//		test4.start();
//		test5.start();
//		test6.start();
		for(int i=0;i<10;i++){
			TestSynchronized01 test;
			if(i==3){
				test = new TestSynchronized01(1, 9,mm);
			}else{
				test = new TestSynchronized01(2, 4+i,mm);
			}
			test.start();
		}
	}
	
	//实例化一个hashmap
	public MyHashMap04<Integer, String> maps;
	//hashmap的操作标识：1为查询，2为删除，3为添加
	public int i;
	//要操作的关键字
	public Integer key;

	/**
	 * 初始化hashmap要执行的操作的构造函数
	 */
	public TestSynchronized01(int i,Integer key,MyHashMap04<Integer, String>maps){
		this.maps = maps;
		this.i = i;
		this.key = key;
//		System.out.println("key的值为:"+key);
	}
	
	public void run(){
		if(i==1){
//			try {
//				//延长修改的时间
//				Thread.sleep(2000);
//			} catch (InterruptedException e) {
//				e.printStackTrace();
//			}
			String value = maps.getValue(key);
			System.out.println(">>>>>>>查询的数据域为:"+value);
		}else if(i==2){
//			try {
//				//延长修改的时间
//				Thread.sleep(1000);
//			} catch (InterruptedException e) {
//				e.printStackTrace();
//			}
			String value = maps.remove(key);
			System.out.println(">>>>>>>移除的数据域为:"+value);
			
		}else if(i==3){
			maps.add(key, "新添加上的值");
		}else if(i==4){
//			maps.add(key);
		}
	}
}

 

结果为：

>>>>>>>移除的数据域为:数据域4

>>>>>>>移除的数据域为:数据域6

>>>>>>>移除的数据域为:数据域5

>>>>>>>移除的数据域为:数据域7

>>>>>>>查询的数据域为:null

>>>>>>>移除的数据域为:数据域8

<!--EndFragment-->

 

 

hashtable同步测试

代码：

 

package cn.java1118;

import java.util.Hashtable;

/**
 * 测试hashmap和hashtable的线程处理的同步性能
 * @author acer
 *
 */
public class TestSynchronized02 extends Thread{
	
	public static void main(String[] args) {
		//实例化一个hashmap，并进行初始化
		MyHashTable<Integer, String> mm = new MyHashTable<Integer, String>();
		for(int j=0;j<100;j++){
			mm.put(j, "数据域"+j);
		}
//		System.out.println(">>>>>"+mm.get(4));
//		TestSynchronized02 test1 = new TestSynchronized02(2, 4,mm);
//		TestSynchronized02 test2 = new TestSynchronized02(2, 5,mm);
//		TestSynchronized02 test4 = new TestSynchronized02(2, 6,mm);
//		TestSynchronized02 test5 = new TestSynchronized02(2, 7,mm);
//		TestSynchronized02 test6 = new TestSynchronized02(2, 8,mm);
//		TestSynchronized02 test3 = new TestSynchronized02(1, 8,mm);
//		test1.start();
//		test2.start();
//		test3.start();
//		test4.start();
//		test5.start();
//		test6.start();
		for(int i=0;i<10;i++){
			TestSynchronized02 test;
			if(i==3){
				test = new TestSynchronized02(1, 9,mm);
			}else{
				test = new TestSynchronized02(2, 4+i,mm);
			}
			test.start();
		}
	}
	
	//实例化一个hashmap
	public MyHashTable<Integer, String> maps;
	//hashmap的操作标识：1为查询，2为删除，3为添加
	public int i;
	//要操作的关键字
	public Integer key;

	/**
	 * 初始化hashmap要执行的操作的构造函数
	 */
	public TestSynchronized02(int i,Integer key,MyHashTable<Integer, String>maps){
		this.maps = maps;
		this.i = i;
		this.key = key;
	}
	
	public void run(){
		if(i==1){
//			try {
//				//延长修改的时间
//				Thread.sleep(2000);
//			} catch (InterruptedException e) {
//				e.printStackTrace();
//			}
			String value = maps.get(key);
			System.out.println(">>>>>>>查询的数据域为:"+value);
		}else if(i==2){
//			try {
//				//延长修改的时间
//				Thread.sleep(1000);
//			} catch (InterruptedException e) {
//				e.printStackTrace();
//			}
			String value = maps.remove(key);
			
			System.out.println(">>>>>>>移除的数据域为:"+value);
//			try {
//				//延长修改的时间
//				Thread.sleep(1000);
//			} catch (InterruptedException e) {
//				e.printStackTrace();
//			}
			
		}else if(i==3){
			maps.put(key, "新添加上的值");
		}
	}
}

 

结果为：

 

>>>>>数据域4

>>>>>>>移除的数据域为:数据域4

>>>>>>>查询的数据域为:数据域8

>>>>>>>移除的数据域为:数据域6

>>>>>>>移除的数据域为:数据域5

>>>>>>>移除的数据域为:数据域7

>>>>>>>移除的数据域为:数据域8

<!--EndFragment--><!--EndFragment-->