自定义一个HashMap

HashMap的结构

在HashMap底层实现原理中，聊过Node<K,V>[]数组的结构，也是HashMap的结构。如下：

自定义一个Node类

package com.msl.mycollection;
/**
 * 用于MslHashMap中
 * @author Senley
 *
 */
public class Node<K,V> {
    int hash;
    K key;
    V value;
    Node next;
}

自定义一个HashMap，体会底层原理

在上述基础上自定义实现一个HashMap，实现如下简单功能：

1. 实现put方法增加键值对；
2. 解决键重复问题和链表生成问题；
3. 实现toString方法，方便查看Map中的键值对信息；
4. 实现get方法，根据键对象获得对应的值对象；
5. 增加泛型。

代码如下：

package com.msl.mycollection;
/**
 * 自定义一个HashMap
 * @author Senley
 *
 */
public class MslHashMap<K,V> {
    Node[] table;  //位桶数组。bucket array
    int size;      //存放的键值对的个数
    
    public static void main(String[] args) {
        MslHashMap<Integer,String> m = new MslHashMap<>();
        m.put(10, "aa");
        m.put(20, "bb");
        m.put(30, "cc");
        m.put(20, "ss");
        
        m.put(53, "ee");
        m.put(69, "ff");
        m.put(85, "gg");
        
        System.out.println(m);
        
//        for(int i=10;i<100;i++) {
//            System.out.println(i+"---"+myHash(i,16)); //53,69,85
//        }
        
        System.out.println(m.get(53));
    }
    
    public MslHashMap() {
        table = new Node[16]; //长度一般定义成2的整数幂
    }
    
    @Override
    public String toString() {
        //{10:aa,20:bb}
        StringBuilder sb = new StringBuilder("{");
        //遍历bucket数组
        for(int i=0;i<table.length;i++) {
            Node temp = table[i];
            //遍历链表
            while(temp!=null) {
                sb.append(temp.key+":"+temp.value+",");
                temp = temp.next;
            }
        }
        sb.setCharAt(sb.length()-1, '}');
        return sb.toString();
    }
    
    public void put(K key,V value) {
        //还需要考虑数组扩容问题！
        
        //定义了新的结点对象
        Node newNode = new Node();
        newNode.hash = myHash(key.hashCode(),table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next = null;
        
        Node temp = table[newNode.hash];
        Node iterLast = null; //正在遍历的最后一个元素
        boolean keyRepeat = false; 
        if(temp == null) {
            //此处数组元素为空，则直接将新结点放进去
            table[newNode.hash] = newNode;
            size++;
        }else {
            //此处数组元素不为空，则遍历对应链表
            while(temp!=null) {
                //判断key如果重复，则覆盖
                if(temp.key.equals(key)) {
                    keyRepeat = true;
                    System.out.println("key重复了");
                    temp.value = value; //只是覆盖value即可，其他的值（hash,key,next）保持不变
                    break;
                }else {
                    //key不重复，则遍历下一个
                    iterLast = temp;
                    temp = temp.next;
                }
            }
            if(!keyRepeat) { //如果没有发生key重复的情况，则添加到链表最后
                iterLast.next = newNode;
                size++;
            }
        }
    }
    
    public V get(K key) {
        int hash = myHash(key.hashCode(),table.length);
        V value = null;
        if(table[hash]!=null) {
            Node temp = table[hash];
            while(temp!=null) {
                if(temp.key.equals(key)) { //如果相等则说明找对了键值对，返回相应的value
                    value = (V) temp.value;
                    break;
                }else {
                    temp = temp.next;
                }
            }
        }
        return value;
    }
    
    public static int myHash(int v,int length) {
//        System.out.println("hash in myHash:"+(v&(length-1))); //直接位运算，效率高
//        System.out.println("hash in myHash:"+(v%(length-1))); //取模运算，效率低
        return v&(length-1);
    }
}

结果如下：

key重复了
{20:ss,53:ee,69:ff,85:gg,10:aa,30:cc}
ee