JAVA---手写HashMap

JAVA—手写HashMap

Map接口

public interface Map {

    void put(Object key,Object value);

    Object get(Object key);

    int size();

    boolean isEmpty();

    //定义内部接口
    interface Entry{
        Object getKey();

        Object getValue();

    }
}

Map类

public class HashMap implements Map {
    static final int DEFAULT_INITIAL_CAPACITY = 16;  //初始的主数组的长度
    transient int size;        //键值对的数量 ，Entry的数量
    transient Entry[] table;      //数组的引用，用来指向一个数组的，哈希表的主数组


    public HashMap() {
        //数组长度初始为16
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
    }

    @Override
    public void put(Object key, Object value) {
        //计算哈希码
        int hash = key.hashCode();
        //计算存储的位置
        int index = hash % table.length;
        //存储到指定的位置
        if (table[index] == null){
            //该位置还没有元素
            table[index] = new Entry(key,value,null,hash);
            size++;
        }else {  //该位置已经存储了元素
            //查询是否存在相同key的Entry
            Entry entry = table[index];  //指向链表的第一个元素
            while (entry != null){
                //比较
                if (entry.hash == hash && entry.getKey().equals(key)){
                    //如果找到了相同的key,使用新的value将旧的value替换掉
                    entry.value = value;
                    return;
                }
                //指向下一个结点,继续循环判断
                entry = entry.next;
            }
            //如果没有相同的key,添加新的结点,下一个结点就是原来的第一个结点，也就是table[index],添加到链表的第一个位置(table[index])
            table[index] = new Entry(key,value,table[index],hash);
            size++;
        }
    }

    @Override
    public Object get(Object key) {
        Entry e = null;   //默认不存在

        //计算哈希码
        int hash = key.hashCode();
        //计算存储的位置
        int index = hash % table.length;
        //存储到指定的位置
        if (table[index] != null){  //该位置存储了元素
            Entry entry = table[index];       //先指向第一个元素
            while (entry != null){
                //比较
                if (entry.hash == hash && entry.getKey().equals(key)){   //找到了这个key
                    e = entry;
                    break;
                }
                //指向下一个结点,继续循环判断
                entry = entry.next;
            }
        }
        return e == null ? null : e.getValue();
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("{");
        for (int i = 0;i < table.length;i++){  //外层循环主数组
            if (table[i] != null){
                Entry entry = table[i];  //让entry指向链表的第一个元素
                while (entry != null){    //内层循环循环链表
                    sb.append(entry.key + "=" + entry.value + ",");
                    //指向下一个结点,继续循环判断
                    entry = entry.next;
                }
            }
        }
        if (size != 0){      //如果有元素就把最后一个逗号去掉
            sb.deleteCharAt(sb.length() - 1);
        }
        sb.append("}");
        return sb.toString();
    }

    class Entry implements Map.Entry{
        final Object key;
        Object value;
        Entry next;   //下一个结点
        int hash;   //key的哈希码

        public Entry(Object key, Object value, Entry next, int hash) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.hash = hash;
        }

        @Override
        public Object getKey() {
            return key;
        }

        @Override
        public Object getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "Entry{" +
                    "key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    ", hash=" + hash +
                    '}';
        }
    }
}