HashMap

用arraylist和linkedlist实现的hashmap

问题：hash冲突时，链表过长，导致get不是o1，

线程安全

refresh 耗内存

class HashNode<K,V> {
	K key;
	V val;
	HashNode next;

	public HashNode(K x, V y){
		this.key = x;
		this.val = y;
		next = null;
	}
}



public class Map<K,V>{

	private List<HashNod<K,V>> list;
	private int capacity;
	private int size;

	public Map(){
		this.list = new ArrayList<>();
		this.capacity = 10;
		this.size = 0;
	}

	public Map(int cp){
		this.list = new ArrayList<>();
		this.capacity = cp;
		this.size = 0;
	}

	public int size(){
		return size;
	}

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

	public V get(K key){
		int index = hashFunc(key);

		HashNode<K,V> head = list.get(index);

		while(head!= null){
			if(head.key.equals(key) || head.key == key){
				return head.val;
			}

			head = head.next;
		}

		return null;
	}	

	public V remove(K key){
		int index = hashFunc(key);

		HashNode<K,V> head = list.get(index);
		HashNode<K,V> cur = head;
		HashNode<K,V> pre = null;
		while(cur != null){
			if(cur.key.equals(key) || cur.key == key)
				break;

			pre = cur;
			cur = cur.next;
		}

		if (cur == null) {
			return -1;
		}

		if(pre != null){
			pre.next = cur.next;
		}else{
			list.set(index,cur.next);
		}

		size--;

		return cur.val;
	}

	//return index 
	private int hashFunc(K key){
		int hascode = hash(key.hasCode());
		int index = hascode % capacity;
		return index;
	}

	public void put(K key, V val){
		int index = hashFunc(key);

		HashNode<K,V> head = list.get(index);

		//check whether key present or not
		HashNode<K,V> cur = head;

		while(cur!=null){
			if (cur.key.equals(key) || cur.key == key) {
				return ;
			}

			cur = cur.next;
		}

		HashNode<K,V> newNode = new HashNode(key,val);

		newNode.next = head.next;
		head.next = newNode;
		size++;
		//check load factor

		if ((1.0 * size) / capacity >= 0.7) {
			//deep copy;

			List<HashNode<K,V>> tmp = list;
			list = new ArrayList<>();

			capacity = capacity*2;

			for (int i = 0; i < capacity ;i++ ) {
				list.add(null);
			}

			for (HashNode<K,V> node : tmp ) {
				while(node != null){
					add(node.key,node.val);
					node = node.next;
				}
			}
		}
	}

}