迷你版HashMap

红太狼 2022-07-15 12:58 220阅读 0赞

## 1:map父类 ##

package jav.qq.mymap;
    
    /**
     * 类描述:HashMap父类
     *
     * @author fengyong
     * @version 1.0
     * @since 1.0
     * Created by fengyong on 16/9/10 下午5:24.
     */
    public class MyAbsMap {
        int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    
        int indexFor(int h, int length) {
            return h & (length-1);//二进制与运算,理论上运算完之后均匀分布,并且比取余运算速度快
       }
    }

## 2:MyMap接口 ##

package jav.qq.mymap;
    
    /**
     * 类描述:
     *
     * @author fengyong
     * @version 1.0
     * @since 1.0
     * Created by fengyong on 16/9/10 下午4:21.
     */
    public interface MyMap<K,V> {
        V put(K k,V v);
        V get(K k);
        int size();
        V remove(K k);
        interface Entry<K,V>{
        }
    }

## 3:迷你版HashMap ##

package jav.qq.mymap;
    
    /**
     * 类描述:参考java6,简易HashMap
     *
     * @author fengyong
     * @version 1.0
     * @since 1.0
     * Created by fengyong on 16/9/10 下午4:23.
     */
    public class MyHashMap<K, V> extends MyAbsMap implements MyMap<K, V> {
    
        //默认的容器大小
        static final int DEFAULT_INITIAL_CAPACITY = 16;
        //默认的负载因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        //集合中的个数
        private int size = 0;
        //容器大小
        private int capacity = 0;
    
        private float factor = DEFAULT_LOAD_FACTOR;
        //数组    数组中的对象中包含了next对象,为链表
        private Node<K, V>[] tables = null;
    
        @Override
        public V put(K k, V v) {
            //如果tables为空,创建
            if (null == tables)
                createDefTable();
            //如果k为null
            if (null == k)
                return putNull(v);
            int hash = hash(k);
            addNode(hash, k, v, indexFor(hash, tables.length));
            return null;
        }
    
        @Override
        public V get(K k) {
            if (size == 0)
                return null;
            if (null == k)
                return getNull();
            return getNode(k);
        }
    
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public V remove(K k) {
            if (size == 0)
                return null;
            int hash = hash(k);
            int index = indexFor(hash, tables.length);
    
            Node<K, V> node = tables[index];
            Node<K, V> e = node;
    
            while (e != null) {
                Node<K, V> next = e.next;
    
                if (hash == hash(e.key) && (k == e || (k != null && k.equals(e.key)))) {
                    size--;
                    if (e == node)
                        tables[index] = next;
                    else
                        node.next = next;
                    return e.value;
                }
                node = e;
                e = next;
            }
            return null;
        }
        //比较难理解的方法,扩容时调用
        private void createTable() {
            Node<K, V>[] newTables = new Node[tables.length * 2];
            for (Node<K, V> e : tables) {
                while (null != e) {
                    Node<K, V> next = e.next;
                    int index = indexFor(e.hash, newTables.length);
                    e.next = newTables[index];//newTables[index]已经有数据,将原有的数据放在e的next中,再将e放到newTables[index]中,完成链表操作
                    newTables[index] = e;
                    e = next;//链表
                }
            }
            tables = newTables;
            capacity = tables.length;
        }
        private V getNode(K k) {
            int hash = hash(k);
            for (Node<K, V> e = tables[indexFor(hash, tables.length)]; e != null; e = e.next) {
                if (hash == hash(e.key) && (k == e.key || k.equals(e.key))) {
                    return e.value;
                }
            }
            return null;
        }
        private V getNull() {
            for (Node<K, V> e = tables[0]; e != null; e = e.next) {
                if (e.key == null && e.hash == 0) {
                    return e.value;
                }
            }
            return null;
        }
        private void createDefTable() {
            tables = new Node[DEFAULT_INITIAL_CAPACITY];
        }
        private V putNull(V v) {
            if (size >= (factor * tables.length))
                createTable();
            for (Node<K, V> e = tables[0]; e != null; e = e.next) {
                if (null == e.key) {
                    V oldValue = e.value;
                    e.value = v;
                    return oldValue;
                }
            }
            addNode(0, null, v, 0);
            return null;
        }
        private void addNode(int hash, K k, V v, int index) {
            if (size >= (factor * tables.length))
                createTable();
            Node<K, V> node = tables[index];
            tables[index] = new Node(hash, k, v, node);
            size++;
        }
        class Node<K, V> implements MyMap.Entry<K, V> {
    
            int hash;
            K key;
            V value;
            Node<K, V> next;
    
            public Node(int hash, K key, V value, Node<K, V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
        }
    }