用java分析hash表结构及性能（二）

七，用代码来验证自己写的hash表以及性能分析（之前的rehash方法写错了，现在更正过来了！）

package cn.java1118;
/**
 * 自己写的hashmap类
 * @author acer
 *
 * @param <K>:关键字类
 * @param <V>:数据域类
 */
public class MyHashMap04<K,V> {

	//存放键值对的数组
	private Entry<K,V>[] hashTable;
	//当前容量的大小
	private int numberOfEntries;
	//装载因子
	private static final double MAX_LOAD_FACTOR=0.75;
	//集合初始化的一个大小
	static final int DEFAULT_INITIAL_CAPACITY = 16;
	
	public MyHashMap04(){
		this(DEFAULT_INITIAL_CAPACITY);
	}
	
	public MyHashMap04(int tablesize){
		//实例化数组的大小
		hashTable = new Entry[tablesize];
		//初始化的时候hash表里面什么都木有
		this.numberOfEntries=0;
	}
	/**
	 * 补充哈希函数
	 * @param h:每一个对象都有的hashcode
	 * @return:另一种hashcode
	 */
	static int hash(int h) {
		//直接copyJDK自带的这个算法
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
	
	/**
	 * 根据key取得value值
	 * @param key:键
	 * @return:键所对应的值
	 */
	public V getValue(K key){
		
		//要返回的值
		V result = null;
		//得到要key在数组的下标
		int hash = hash(key.hashCode());
		int index = indexFor(hash, hashTable.length);
		//对键值对链表进行遍历
		for (Entry<K,V> e = hashTable[index]; e != null; e = e.next) {
	            Object k;
	            if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
	                return e.value;
	            }
	        }
		return result;
	}
	/**
	 * 添加元素
	 * @param key
	 * @param value
	 * @return:添加成功则为null，否则返回之前的值
	 */
	public V add(K key,V value){
		//键值为null时的处理方法
		if (key == null)
            return putForNullKey(value);
		//返回值变量
		V oldValue;
		
		//得到这个键在数组中的下标
		int hash = hash(key.hashCode());
		int index = indexFor(hash, hashTable.length);
		//看是否存在一样的键和hashcode
		for (Entry<K,V> e = hashTable[index]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            	//存在这样的键值对了
                oldValue = e.value;
                e.value = value;
               
                return oldValue;
            }
        }
		//插入一个键值对的时候当前的容量会+1
		numberOfEntries++;
		//进行插入
		addEntry(hash, key, value, index);
		return null;
	}
	/**
	 * 当插入的键位null时的处理
	 * @param value:值
	 * @return:插入成功则返回null，不成功则返回这个键原来所对应的值
	 */
	private V putForNullKey(V value) {
        for (Entry<K,V> e = hashTable[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        numberOfEntries++;
        addEntry(0, null, value, 0);
        return null;
    }
	/**
	 * 插入键值对链表
	 * @param hash:hashcode
	 * @param key：键
	 * @param value:值
	 * @param bucketIndex:数组上的下标
	 */
	void addEntry(int hash, K key, V value, int bucketIndex) {
		//将原来的保留
		Entry<K,V> e = hashTable[bucketIndex];
		//在原来的基础上添加
		hashTable[bucketIndex] = new Entry<K,V>(hash, key, value, e);
		if(!isHashTableTooFull()){
			//看是否超出其装载因子
			rehash();
		}
	    }
	
	//检验hash表的装载因子是否大于默认值
	private boolean isHashTableTooFull() {
		//装载因子是有大小限制的
		if(numberOfEntries/hashTable.length>=MAX_LOAD_FACTOR){
			return false;
		}
		return true;
	}

	/**
	 * 再hash的方法
	 */
	private void rehash() {
		//保留原hash表
		Entry<K, V>[] oldHashTable = hashTable;
		int oldSize = hashTable.length;
		//扩大为原来的两倍
		int newSize = oldSize*2;
		hashTable = new Entry[newSize];
		numberOfEntries=0;
		
		//还要遍历原hash表，即将原来放进来的数据重新插入到新的hash表中
		for(int i=0;i<oldHashTable.length;i++){
			Entry<K, V> e = oldHashTable[i];
			if(e!=null){
				do{
					Entry<K, V> next = e.next;
				int index = indexFor(hash(e.hash), newSize);
			addEntry(e.hash, e.key, e.value, index);
			e=next;
				}while(e!=null);
				
			}
		}
	}
	/**
	 * 删除指定key的键值对
	 * @param key：键
	 * @return
	 */
	 public V remove(Object key) {
	        Entry<K,V> e = removeEntryForKey(key);
	        return (e == null ? null : e.value);
	    }
	 /**
	  * 跟查找的过程差不多
	  * @param key
	  * @return
	  */
	 final Entry<K,V> removeEntryForKey(Object key) {
	        int hash = (key == null) ? 0 : hash(key.hashCode());
	        int i = indexFor(hash, hashTable.length);
	        Entry<K,V> prev = hashTable[i];
	        Entry<K,V> e = prev;

	        while (e != null) {
	            Entry<K,V> next = e.next;
	            Object k;
	            if (e.hash == hash &&
	                ((k = e.key) == key || (key != null && key.equals(k)))) {
	                numberOfEntries--;
	                if (prev == e)
	                    hashTable[i] = next;
	                else
	                    prev.next = next;
	                return e;
	            }
	            prev = e;
	            e = next;
	        }

	        return e;
	    }
	 
	/**
	 * 得到在数组中的下标位置
	 * @param h：hashcode
	 * @param length：hash表的长度
	 * @return：下标位置
	 */
	static int indexFor(int h, int length) {
        return h & (length-1);
    }
	/**
	 * 实例化一个装键值对链表
	 * @author acer
	 *
	 * @param <K>
	 * @param <V>
	 */
	private class Entry<K,V>{
		private K key;
		private V value;
		//每一个对象都有一个hashcode，是唯一的，在map中不能存放hashcode一样的对象
		private int hash;
		//下一个键值对节点
		private Entry<K,V> next;
		
		private Entry(int hash,K key,V value,Entry<K,V>next){
			this.key = key;
			this.value = value;
			this.next = next;
			this.hash = hash;
		}

		public K getKey() {
			return key;
		}

		public V getValue() {
			return value;
		}
		//重写equals方法
		 public final boolean equals(Object o) {
	            if (!(o instanceof Entry))
	                return false;
	            Entry e = (Entry)o;
	            //得到两个比较的key值
	            Object k1 = getKey();
	            Object k2 = e.getKey();
	            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
	            	//得到两个比较的value值
	                Object v1 = getValue();
	                Object v2 = e.getValue();
	                if (v1 == v2 || (v1 != null && v1.equals(v2)))
	                    return true;
	            }
	            return false;
	        }
	}
}

 

  

性能分析代码：

package cn.java1118;

import java.util.HashMap;

public class Test1 {  
	  
    public static void main(String[] args) {  
    	//自己的hashmap
    	MyHashMap04<String, String> mm = new MyHashMap04<String, String>();   
        Long aBeginTime=System.currentTimeMillis();  
        for(int i=0;i<1000000;i++){  
        mm.add(""+i, ""+i*100);  
        }  
        Long aEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("insert time-->"+(aEndTime-aBeginTime));  
          
        Long lBeginTime=System.currentTimeMillis();//记录BeginTime  
        mm.getValue(""+100000);  
        Long lEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("seach time--->"+(lEndTime-lBeginTime));
        
        Long rBeginTime=System.currentTimeMillis();//记录BeginTime  
        mm.remove(""+10000);  
        Long rEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("remove time--->"+(rEndTime-rBeginTime));
    	
    	//系统的hashmap
//    	HashMap<String, String> mm = new HashMap<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));
//        
//        Long rBeginTime=System.currentTimeMillis();//记录BeginTime  
//        mm.remove(""+10000);  
//        Long rEndTime=System.currentTimeMillis();//记录EndTime  
//        System.out.println("remove time--->"+(rEndTime-rBeginTime));
    }  
}  
 

  

 

 

 

系统的测试结果：

insert time-->2148
seach time--->0

我的测试结果：

insert time-->2236
seach time--->0
remove time--->0

看，查找的速度为0呃，插入也只要2秒多。。。

 

还有一个是存储空间的测试：

 

 

 

 

 

<!--EndFragment-->