手写HashMap_c++手写hashmap

最近跟一个朋友聊天，谈到去百度面试让手写HashMap，当时没思路面试就挂了。

想到这里我打算巩固一下自己的基础知识，亲自动手实现一下HashMap.

HashMap底层=数组+链表

HashMap底层源码通过 链表法来解决hash冲突，找到hash值对应位置不为空,维护一个链表。

实现如下：

1.首先定义一个接口

public interfaceERMap<K,V> {
    Vput(K key,V value);
 
    Vget (K key);
 
    intsize();
 
   //定义一个内部接口
   //可以根据Entry对象拿到这个对象的key和value
   interfaceEntry<K,V>{
     KgetKey();
     VgetValue();
   }
}

2.然后定义一个实现类

public class ERHashmap<K,V> implements ERMap<K, V> {
 
            private static Integer defaultLength = 16;//定义数组长度（定义成2的倍数）
 
            private static double defaultLoad=0.75;//定义负载因子(超过这个因子就会扩容)
 
            private Entry<K,V>[] table =null;//定一个数组，盛放Entry对象
 
            private int size=0;//定义一个常量，用来记录数组元素个数
 
            //定义构造函数,
            ERHashmap(int defaultLength,double defaultLoad){
                this.defaultLength=defaultLength;
                this.defaultLoad=defaultLoad;
 
                table=new Entry[defaultLength];//定义一个默认数组，长度就是传过来的长度
            }
 
            ERHashmap(){
                this(defaultLength,defaultLoad);
            }
            public V put(K key, V value) {
                //得到要放的数据的位置:也就是数组的下标
                int index=this.getIndex(key);
                //根据这个下标判断该数据是否有数据
                Entry<K,V> e =table[index];
                if(null==e){
                    table[index]=new Entry(key,value,null,index);
                    size++;//数组长度加1
                }else{
                    Entry newEntry =new Entry(key,value,e,index);
                    table[index] = newEntry;
                }
 
                return table[index].getValue();
            }
 
            //找数组下标的方法
            private int getIndex(K key){
                //除留取余数法
                //m的取值是比数组长度小的质数的最大值
                //这里定义的长度为16，那么m就是13
                int m=this.defaultLength-3;
                return key.hashCode() % m;
 
            }
 
            public V get(K key) {
                //得到要放的数据的位置:也就是数组的下标
                int index=this.getIndex(key);
                Entry entry = table[index];
                V v = null;
                if(entry == null){
                    return null;
                }
                else{
                    while(entry != null)
                        if(entry.getKey() == key){
                            v = entry.getValue();
                            break;
                        }else{
                            entry = entry.next;
                        }
                }
                return v;
            }
 
 
            public int size() {
                return size;
            }
 
 
            class Entry<K,V> implements ERMap.Entry<K, V>{
 
                K key;
 
                V value;
 
                Entry<K,V> next;
 
                int index;//记录下标
 
                Entry(K k,V v,Entry<K,V> n,int inx){
                    key=k;
                    value=v;
                    index=inx;
                    next=n;//数组第一个元素的下一个元素
                }
 
                public K getKey(){
                    return key;
                }
 
                public V getValue(){
                    return value;
                }
            }
        }

3.测试

public class test {
     public static void main (String[] args){
           ERHashmap map = newERHashmap();
           map.put("jiang","tong");
           map.put("zhao", "rui");
           
           
           System.out.println(map.get("jiang"));
           System.out.println(map.get("zhao"));
 
     }
}

经过测试正确输出了key对应的value！！！一个简单的HashMap成功实现，感觉棒棒哒！