手写简单版HashMap

    手写实现基本功能的HashMap

    1）属性：

• 内部节点类                         Node 
• 存放Node类型数据的数组     hashTable
• 数组的容量                         capacity
• 当前存放数据的数量             count
• 能够存放的数据数量的上限    threshold
• 装载因子                            loadFactor

   

    2）

      功能：

• 添加 put(K key,V value);
• 删除 delete(K key);
• 查找 getV(K key);

   3)理解：

• 能够添加的数据上限：threshold=capacity* loadFactor;
• 默认的loadFactor是2.0f;
• 默认的容量是capacity=100;
• put 判断key是否已经存在的标准解释：由于使用泛型不知道用户的key对象的类型，故使用的是用户对象的equals判别方法，形式：key.equals(已经存在的key)，添加和删除同样是使用了该判别方法
• 测试使用的key为User类   
• User类 重写了Object的hashCode() 方法和equals() 方法
• hashCode(): 以用户的年龄(Int)表示
• equals()  为了方便测试，没有采用Object的指向同意对象的“==”方法，而是根据User 的hashCode 即年龄为标准，年龄相等即表示是equals 返回true
• 系统提供的HashMap 是先添加用户，再判断容量是否超限，自己写的是先判断是否超限再添加，因此在临界数量上如在添加第201个用户时，count判断超限，进行了resize，之后还要经该用户添加到新的hashTable中,防止遗漏

 

代码：User类

public class User {

	private String name;
	private int sex;
	private int age;
	private int phone;
	

	
	public String getName() {
		return name;
	}
	public int getSex() {
		return sex;
	}
	public int getAge() {
		return age;
	}
	public int getPhone() {
		return phone;
	}
	
	public void setName(String name) {
		this.name = name;
	}
	public void setSex(int sex) {
		this.sex = sex;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public void setPhone(int phone) {
		this.phone = phone;
	}
	
	//重写haseCode
	public int hashCode(){
		return this.age;
	}
	
	//重写equals
	public boolean equals(Object o){
		if(o instanceof User){
			User u=(User)o;
			//此处只是简单的进行了判断  以年龄为标准
			if(u.getAge()==this.age){
				return true;
			}
		}
		return false;
	}
}

 

 

MyHashMap：

import java.util.Random;


public class MyHashMap<K,V> {

	/**
	 * 定义自己的哈希表 测试效率问题
	 * @param args
	 */
	
	
	/**
	 * 定义一个内部类
	 * @param args
	 */
	
	
	public class Node<K,V>{
		
		private int keyCode;
		private K key;
		private V value;
		private Node<K,V> next;
		
		/**
		 * 构造函数
		 * @param k
		 * @param v
		 * @param next 在创建新的节点的时候 直接指出下一个节点
		 */
		public Node(int keyCode,K key,V value,Node<K,V> next){
			this.keyCode=keyCode;
			this.key=key;
			this.value=value;
			this.next=next;
		}
		
		
	}
	
	static int DEFAULT_CAPCITY=100;
	//内部数组 ----存放的是Node类型的链表
	private int capacity;
	private Node[] hashTable;
	//定义所有的key-value对的总数
	private int count=0;
	//装载因子
	private float loaderFactor;
	//count的上限
	private int threshold;
	
	/**
	 * 构造函数
	 */
	public MyHashMap(){
		//初始化容量
		capacity=DEFAULT_CAPCITY;
		//初始化hashTable
		hashTable=new Node[capacity];
		//初始化装载因子
		loaderFactor=2.0f;
		//初始化count的上限
		threshold=(int) (capacity*loaderFactor);
	}
	
	
	/**
	 * 添加
	 * @param k
	 * @param v
	 * @return
	 */
	
	public V put(K key,V value){
		//首先是根据K 计算出hash
		int keyCode=key.hashCode();
		int hash=getHash(keyCode);//此处重写K如User的hashCode 
		//判断该hash下是否已经存在该索引  并作出抉择
		//System.out.println("put----1 -----：Hash ="+hash);
		for(Node<K,V> n=hashTable[hash];n!=null;n=n.next){
			
			if(key.equals(n.key)){//如果已经存在该索引 则返回oldValue
				//将就得value改成新的value 索引不用改变
				//以输入对象的equals 判断标准判读
				V oldValue=n.value;
				n.value=value;
				return oldValue;
			}
		}
		//索引并没有存在 
		addNode(key,value,hash);
		return null;
	}
	
	/**
	 * 查找
	 * @param k
	 * @return
	 */
	public V getV(K key){
		//根据输入的Key 计算出hash
		int hash=getHash(key.hashCode());
		//从header遍历
		for(Node<K,V> node=hashTable[hash];node!=null;node=node.next){
			if(key.equals(node.key)){//此处采用的是用来查找的key 自身的equals方法  所以需要重写equals()
				//其实此处最好是这样 泛型的K key只能是使用Object 的== 判断  （指向）
				return node.value;
			}
		}
		//如果没有该key  返回null
		return null;
	}
	/**
	 * 删除
	 * @param k
	 * @return
	 */
	public boolean delete(K key){
		
		//首先是查找是否存在该key
		int hash=getHash(key.hashCode());
	
		//存放上一个Node 
		Node<K,V> pre=null;
		Node<K,V> n=hashTable[hash];
		
		for( ;n!=null;n=n.next){
			if(key.equals(n.key)){
				//删除
				if(pre==null){//删除header
					hashTable[hash]=n.next;
					return true;
				}else{
					pre.next=n.next;
					n=null;
					return true;
				}
			}
			pre=n;
		}
		
		return false;
	}
	
	
	/**
	 * 计算hash值
	 * @param num 输入的数值 相当于key的hashCode
	 * @return
	 */
	private int getHash(int num){
		return num%capacity;
	}
	
	/**
	 * 添加节点
	 * @param k
	 * @param v
	 * @param bucketIndex 指明添加的索引
	 * @return
	 */
	private void addNode(K key,V value,int bucketIndex){
	    
		if(count<threshold){//小于上限
		//取得链表的head
		Node<K,V> n=hashTable[bucketIndex];
		//改变链表的head
		int keyCode=key.hashCode();
		hashTable[bucketIndex]=new Node<K,V>(keyCode,key,value,n);
		count++;
		//System.out.println("addNode---2----  此时的count="+count);
		}else{//大于上限
		//重新建表
		resize();
		//系统的map是不管是否超限  先添加上再判断 此处要先判断的话 就要在重新建表后  将该用户添加上
		//这种问题总是出现在衔接的地方  
		//取得链表的head
		Node<K,V> n=hashTable[bucketIndex];
		hashTable[bucketIndex]=new Node<K,V>(key.hashCode(),key,value,n);
		count++;
	}
		
	}
	/**
	 * 处理冲突 重新建表
	 */
	private void resize(){
	//	System.out.println("需要重新建表....count="+count);
		//容量增加一倍  capacity 增加到200 或者其他  有个好处不用将所有的用户重新存放
		capacity=capacity*2;
		//新建
		Node [] newHashTable=new Node[capacity];
		//遍历
		for(int i=0;i<hashTable.length;i++ ){
			
			
			Node<K,V> oldNode=hashTable[i];
			while(oldNode!=null){
			//准备工作---依次取出
			Node<K,V> next=oldNode.next;
			
			//改变旧的地盘
			hashTable[i]=next;
			//安排新的地盘
			int newHash=getHash(oldNode.keyCode);
			Node<K,V> newNext=newHashTable[newHash];
			oldNode.next=newNext;
			newHashTable[newHash]=oldNode;
			
			//重新指向
			oldNode=hashTable[i];
			}
			
		}
		//循环过后 table 已经全部是指向了null
		hashTable=newHashTable;
		//改变上限 在这出错
		threshold=(int) (capacity*loaderFactor);
		
	}
	}

 

 简单测试一把，按照顺序插入100万用户，是3200毫秒，系统的是2100。查找时间数量大系统的11毫秒，自己测试17毫秒。 使用了随机数，数据不一样，查看了系统的在计算hash值的时候不是采用取余，而是按位&，结果一样但是效率高，当然系统采用的默认容量是16，之后容量扩充时是2倍和默认装载因子0.75，是有其他考虑......