一个简单的java hashMap实现

纯属实验，非线程安全的HashMap实现，性能只有jdk中HashMap的60%左右

package hash;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
import java.util.Random;
import list.LinkList;

/**
 * 链式解决冲突的Hash表简单实现
 * 本类非线程安全，多线程情况下需要外部同步处理
 * 
 * @author junfeng.chen
 *
 * @param <K>
 * @param <V>
 */
public class MyHashMap<K,V> implements Map<K,V>
{
	
	private int capacity =200;
	private Object [] container ;
	private int size = 0;
	private float loadRate;
	private int length_avg_list = 4;
	private int random_number= new Random().nextInt(29);
	private Set<Map.Entry<K,V>> entrySet = new HashSet<Map.Entry<K,V>>();
	private Set<K> keyset = new HashSet<K>();
	public MyHashMap(int initial_capacity)
	{
		container= new Object[initial_capacity];
		capacity  = initial_capacity;
	}
	
	public MyHashMap()
	{
		this(16);
	}
	
	public MyHashMap(Map map)
	{
		int cap = (int) (map.size()/0.75f);
		this.capacity =cap;
		container= new Object[capacity];
		this.putAll(map);
	}

	public void clear() 
	{
		container = new Object[256];
		this.capacity=256;
	}

	public boolean containsKey(Object key) 
	{
		return keyset.contains(key);
	}

	public boolean containsValue(Object value) 
	{
		Iterator<Map.Entry<K, V>> it = entrySet.iterator();
		Entry<K,V> entry = null;
		while(it.hasNext())
		{
			entry = it.next();
			if(entry.getValue().equals(value))
				return true;
		}
		return false;
	}

	public Set<Map.Entry<K, V>> entrySet() {

		return this.entrySet;
	}

	public V get(Object key) {
		
		if(!this.containsKey(key))
			return null;
		
		int indx = locate(key);
		LinkList<StoreObject> list = (LinkList<StoreObject>) container[indx];
		if(list!=null)
		{
         Iterator<StoreObject> iterator = list.iterator();
         while(iterator.hasNext())
         {
        	 StoreObject obj =  iterator.next();
        	 if(key.equals(obj.key))
        		 {
        		 	return (V)obj.value;
        		 }
         }
		}
		return null;
		
	}

	public boolean isEmpty() {
		return size<=0;
	}

	public Set<K> keySet() {
		
		return this.keyset;
	}

	public V put(K key, V value) 
	{
		int indx = locate(key,this.capacity);
		StoreObject obj = new StoreObject(key,value);
		if(this.container[indx]==null)
		{
			LinkList<StoreObject> list = new LinkList<StoreObject>();
			list.append(obj);
			container[indx]=list;
		}
		else
		{
			LinkList<StoreObject> list =  (LinkList<StoreObject>) container[indx];
			list.append(obj);
		}
		size++;
//		entrySet.add(obj);
//		keyset.add(key);
		 if(size()/container.length>=length_avg_list)
		    	this.reHash();
		return value;
	}

	public void putAll(Map m) 
	{
		
	}
	
	public V remove(Object key) 
	{
		if(!this.containsKey(key))
			return null;
		int indx = locate(key);
		LinkList<StoreObject> list = (LinkList<StoreObject>) container[indx];
		if(list!=null)
		{
         Iterator<StoreObject> iterator = list.iterator();
         while(iterator.hasNext())
         {
        	 StoreObject obj =  iterator.next();
        	 if(key.equals(obj.key))
        		 {
        		 iterator.remove();
        		 size--;
        		 entrySet.remove(obj);
        		 keyset.remove(key);
        		 return (V)obj.value;
        		 }
         }
		}
		return null;
	}

	public int size() {
		
		return size;
	}

	public Collection values() 
	{

		return null;
	}
	
	
	//计算key的位置
	private int locate(Object key)
	{
		return locate(key,this.capacity);
	}
	
	//计算key的位置
	private int locate(Object key,int cap)
	{
		int indx = (key.hashCode()*random_number)%cap;
		if(indx<0)
			indx+=cap;
		return indx;
	}
	
	/**
	 * 在hash化
	 */
	private void reHash()
	{
		synchronized(this)
		{
			int cap= capacity*2;
			Object [] newContainer = new Object [cap] ;
			Iterator<K> it = this.keyset.iterator();
			K key = null;
		    while(it.hasNext())
		    {
		    	key = it.next();
		    	V value = this.get(key);

		    	int indx = locate(key,cap);//index in new array
				StoreObject obj = new StoreObject(key,value);
				if(newContainer[indx]==null)
				{
					LinkList<StoreObject> list = new LinkList<StoreObject>();
					list.append(obj);
					newContainer[indx]=list;
				}
				else
				{
					LinkList<StoreObject> list =  (LinkList<StoreObject>) newContainer[indx];
					list.append(obj);
				}

		    }
		    container = newContainer;
//		    System.arraycopy(this.container, 0, newContainer, 0, container.length);
		    this.capacity=cap;
//		    System.out.println("reHash to capacity "+capacity);
		}
		
	}
	
	private class StoreObject<K,V> implements Entry<K,V>
	{
		private K key;
		private V value;
		public StoreObject(K k,V v)
		{
			key = k;
			value = v;
		}
		public K getKey()
		{
			return key;
		}
		public V getValue()
		{
			return value;
		}
		public V setValue(V value) {
		
			 this.value = value;
			 return value;
		}
	}
	
	public static void main(String args[]) throws InterruptedException
	{
		testMyHashMap();
		testHashMap();
//		testLink();
//		testMyLink();
//		MyHashMap<String,String> map = new MyHashMap<String,String>();
//		for(int i=0;i<200;i++)
//		{
//			map.put("key_"+i, "value_"+i);
//			if(i%3==0)
//				map.remove("key_"+i);
//		}
//		
//		for(int i=1;i<200;i++)
//		{
//			System.out.println("key_"+i+"="+map.get("key_"+i));
//		}
//	    map.put("key_195", "value_195");
//	   
//	    System.out.println(map.get("key_195"));

	}
	
	static void testMyLink()
	{	long begint = System.currentTimeMillis();
	LinkList list = new LinkList();
		for(int i=0;i<800000;i++)
		{
			list.append("string_"+i);
		}
		long end = System.currentTimeMillis();
		System.out.println("time used = "+(end-begint));
	}
	
	static void testLink()
	{	long begint = System.currentTimeMillis();
		LinkedList list = new LinkedList();
		for(int i=0;i<800000;i++)
		{
			list.add("string_"+i);
		}
		long end = System.currentTimeMillis();
		System.out.println(" time used = "+(end-begint));
	}
	static void testMyHashMap()
	{
		long begint = System.currentTimeMillis();
		Map <Object,String> map = new MyHashMap<Object,String>(100000); 
		int size = 700000;
		for(int i=0;i<size;i++)
		{
			map.put(i+"", "string_"+i);
		}
		
//		System.out.println(map.size());
//		System.out.println(map.get(random.nextInt(size)+""));
		long end = System.currentTimeMillis();
		System.out.println("my hash time used = "+(end-begint));
	}
	
	static void testHashMap()
	{
		long begint = System.currentTimeMillis();
		Map <Object,String> map = new HashMap<Object,String>(100000); 
		int size = 700000;
		for(int i=0;i<size;i++)
		{
			map.put(i+"", "string_"+i);
		}
		
//		System.out.println(map.size());
//		System.out.println(map.get(random.nextInt(size)+""));
		long end = System.currentTimeMillis();
		System.out.println("jdk hash time used = "+(end-begint));
	}
}

这个我以前也写过哦.对着jdk写的..发现写不过人家...

很佩服楼主的造轮子精神....

给个提示吧..把泛型去掉..这个有用了就..jdk的自动拆箱 装箱很费时的...

呵呵 谢谢你的提示，我觉得泛型应该留着吧

留着就是jdk了...在处理大数据量的时候...最好就是处理基本数据类型...

不让int 变成integer ..


有个java高效率框架..专门针对int ===做的hashMap等...

你可以考虑下...不过针对不同类型..应该hashcode计算方式也不一样...这个就需要科学家来讨论了..

都用到HashSet了，还有什么必要自己实现HashMap，一个MyHashMap包了个HashSet，HashSet里头又包了个HashMap

用hashset实现hashmap，性能高就让人奇怪了，好好读一读hashmap的源码吧：数组+链表

真的是好玩，要知道hashset其实就是用hashmap实现的,

你这个是用JDK实现的hashset实现hashmap

而且你用了2个！？  貌似是的吧


那么你再想想吧，你用的实现方式还是hashmap - -  

多谢楼上各位提醒

我以为用了RBTree才进来的

你自己写一个就可以了， 名字叫hashmap 怎么可能是rbtree