手写简单版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类
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;//初始化hashTablehashTable=new Node[capacity];//初始化装载因子loaderFactor=2.0f;//初始化count的上限threshold=(int) (capacity*loaderFactor);}/** * 添加 * @param k * @param v * @return */public V put(K key,V value){//首先是根据K 计算出hashint 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 计算出hashint 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 返回nullreturn null;}/** * 删除 * @param k * @return */public boolean delete(K key){//首先是查找是否存在该keyint 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){//删除headerhashTable[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){//小于上限//取得链表的headNode<K,V> n=hashTable[bucketIndex];//改变链表的headint keyCode=key.hashCode();hashTable[bucketIndex]=new Node<K,V>(keyCode,key,value,n);count++;//System.out.println("addNode---2---- 此时的count="+count);}else{//大于上限//重新建表resize();//系统的map是不管是否超限 先添加上再判断 此处要先判断的话 就要在重新建表后 将该用户添加上//这种问题总是出现在衔接的地方 //取得链表的headNode<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 已经全部是指向了nullhashTable=newHashTable;//改变上限 在这出错threshold=(int) (capacity*loaderFactor);}}?
?简单测试一把，按照顺序插入100万用户，是3200毫秒，系统的是2100。查找时间数量大系统的11毫秒，自己测试17毫秒。 使用了随机数，数据不一样，查看了系统的在计算hash值的时候不是采用取余，而是按位&，结果一样但是效率高，当然系统采用的默认容量是16，之后容量扩充时是2倍和默认装载因子0.75，是有其他考虑......
?
?