HashMap

(非红黑数结构)盗版的HashMap--------------------get,put两个方法

底层使用的是数组+单链表

数组:存储空间连续，比较占内存，寻址容易，插入删除复杂

链表:存储空间非连续，占用内存松散，寻址困难，插入删除容易

import java.util.AbstractMap;
import java.util.Arrays;

public class MHashMap<K,V>{
	
	//需要一个类似Entry的类 用来存储 KEY VALUE 以及下个对象
	private class MEntry{
		
		private K KEY;
		private V VALUE;
		private MEntry next;

		public MEntry() {
		}
		public MEntry(K kEY, V vALUE, MHashMap<K, V>.MEntry next) {
			super();
			KEY = kEY;
			VALUE = vALUE;
			this.next = next;
		}
		public K getKEY() {
			return KEY;
		}
		public void setKEY(K kEY) {
			KEY = kEY;
		}
		public V getVALUE() {
			return VALUE;
		}
		public void setVALUE(V vALUE) {
			VALUE = vALUE;
		}
		public MEntry getNext() {
			return next;
		}
		public void setNext(MEntry next) {
			this.next = next;
		}
		@Override
		public String toString() {
			return "MEntry [KEY=" + KEY + ", VALUE=" + VALUE + ", next=" + next + "]";
		}
	}
	
	//初始化操作
	//1.默认数组的大小
	private static final int INIT_CAPATITY=1<<4;
	//2.加载因子
	private static final float INIT_LOADFACTOR=0.75f;
	//3.临界值 就是数组元素个数在多少的时候进行扩容
	private Object[] object = new Object[INIT_CAPATITY];
	//4.容量的值
	private int addCapatity=INIT_CAPATITY;
	//5.设置hashMap的最大值
	//private static final int MAX_PACATITY=65535;
	
	//根据key 获取hashcode
	public int getHashCode(K key) {
		System.out.println("哈希值:"+(key.hashCode()&(addCapatity-1)));
		return key.hashCode()&(addCapatity-1);
	}
	
	//put函数  首先要检查 是否满足扩容
	public void put(K key,V value) {
		//将key和value保存到 这个数组中		 
		MEntry mEntry = new MEntry(key,value,null);
		//计算此时已经存储的个数
		int sum = 0;
		for(int i=0;i<addCapatity;i++) {			
			if(object[i]!=null) {
	     		//遍历 链表 头指针是当前对象 
				@SuppressWarnings("unchecked")
				MEntry head = (MHashMap<K, V>.MEntry) object[i];
				MEntry p = head;
				sum++;
				while(p.next!=null) {
					sum++;
					p = p.next;
				}	
			}
		}

		//如果sum这个值大于等于 临界值 的话  那么就进行扩容  扩为原来的2倍
		if(sum>=addCapatity*INIT_LOADFACTOR) {
			addCapatity = addCapatity*2;
			object = Arrays.copyOf(object, addCapatity);
		}
		//扩容完成 计算哈希值 
		int hashCode = getHashCode(key);
		// 检查该位置的中是否有元素  如果没有元素  那么直接存入数组中
		if(object[hashCode]!=null) {
			//如果有元素
			@SuppressWarnings("unchecked")
			//根据哈希值 找到这个位置的所有元素
			MEntry head = (MHashMap<K, V>.MEntry) object[hashCode];
			MEntry p = head;
			boolean flag = false;
			//遍历所有 这个位置的所有元素
			while(p.next!=null) {
				//如果这个键存在 那么就覆盖这边value 
				if(p.getKEY() == mEntry.getKEY()) {
					//覆盖
					flag = true;
					p.setVALUE(mEntry.getVALUE());
				
					break;
				}
				p = p.next;
			}
			//如果 不存在这样的键 那么直接插入尾巴节点
			if(!flag) {
				p.next = mEntry;
			}
				
		}else {
			//如果是空的 那么就直接存入
			object[hashCode] = mEntry;
			
		}	
	}
	
	public V get(K key) {
		//通过KEY 来进行索引
		@SuppressWarnings("unchecked")
		//根据哈希值 计算出 这个键的哈希值 对应的 所有元素
		MEntry mEntry = (MHashMap<K, V>.MEntry) object[getHashCode(key)];
		//如果头节点是null   就说明不存在  直接返回空  否则的话  就说明 这个数组的头节点 是有值的  那么看一下这个的next域是
		//不是空的 如果是的话就是这个值 直接返回就行 否则就遍历寻找
		System.out.println(mEntry);
		if(mEntry!=null) {
			MEntry head = mEntry;
			MEntry p = head;
			if(p.next!=null) {
				while(p!=null) {
					if(key.equals(p.getKEY())) {
						return p.getVALUE();
					}
					p = p.next;
					}
			}else {
				return p.VALUE;
			}
		}
		return null;
	}
}

结果测试:

		Map<String,String> map = new HashMap<String, String>();
		for (int i=0;i<18;i++) {
			map.put("name"+i, "ZhangSan"+i);
			map.hashCode();
		}
		System.out.println("正版MAP:"+map.get("name3"));
		
		MHashMap<String, String> mHashMap = new MHashMap<String,String>();
		for (int i=0;i<18;i++) {
			mHashMap.put("name"+i, "ZhangSan"+i);
		}
		System.out.println("盗版MAP:"+mHashMap.get("name5"));