JDK 学习之(一)HashMap 的实现

已经有很多如何深入学习认识HashMap 的文章了,我就不重复了.
我就自己实现了简单的 HashMap,仅供学习了解 HashMap 核心思想之用

1. 底层采用数组+链表的形式来存储 键值对
2. 键值对使用 Entity 对象存储,数组存储 LinkedList
3. 如果 hash 值重复,则在该 index 对象(LinkedList)头部插入新的元素

以上可以勾勒出如下图所示的一幅结构:

屏幕快照 2017-12-15 下午10.36.37.png

下面我们来看一下具体的实现
如下代码是内部类,用来存放键值对,两个 Object 对象,没什么好说的

    /**
     * 内部类用来存放键值对
     */
    class MyEntry {
        private Object key;
        private Object value;
        private MyEntry(Object key, Object value) {
            this.key = key;
            this.value = value;
        }
        //省略 get,set 方法
    }

如下是用到的几个字段

    private static int default_length = 999;//不涉及到扩容,这里写死这个容量
    private int size = 0;//初始容器大小
    private Object[] arr = new Object[default_length];//声明一个数组用来存放键值对

提供以下API 操作
boolean put(Object key,Object value)
Object get(Object key)
int size()
内部还有两个私有方法
boolean containsKey(Object key, int index)查看指定位置是否包含指定 key
int hash(Object key)计算 key 的 hash 值,即该 key 在数组中的位置

具体详细代码如下

    private static int default_length = 999;
    private int size = 0;

    private Object[] arr = new Object[default_length];

    /**
     * 放入键值对
     * @param key
     * @param value
     */
    public void put(Object key, Object value) {
        int index = hash(key);
        if (arr[index] == null) {
            // 如果当前槽位是空的,直接放进去就可以了
            List linkedList = new LinkedList();
            linkedList.add(new MyEntry(key, value));
            arr[index] = linkedList;
        } else {
            //如果不为空,检查当前 key 是否已存在
            //如果已经存在,替换 value, 否则在链表头部插入新的元素
            if (containsKey(key, index)) {
                LinkedList linkedList = (LinkedList) arr[index];
                for (Object o : linkedList) {
                    MyEntry entry = (MyEntry) o;
                    if (entry.getKey().equals(key)) {
                        entry.setValue(value);
                    }
                }
                return;
            } else {
                //链表头部插入元素
                ((LinkedList) arr[index]).add(0, new MyEntry(key, value));
            }
        }
        size++;
    }


    /**
     * hashMap 中指定位置是否包含指定key
     * @param key
     * @param index
     * @return
     */
    private boolean containsKey(Object key, int index) {
        Object o = arr[index];
        if (o == null) {
            return false;
        }
        LinkedList linkedList = (LinkedList) o;
        for (Object o1 : linkedList) {
            if (o1 == null && key == null) {
                return true;
            }
            MyEntry entry = (MyEntry) o1;
            if (entry.getKey().equals(key)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 根据 key 获取 value
     * 如果 key==null,特殊处理,放在了第一个位置
     * 获得 key 的 hash 值,就确定了在 数组中的位置.
     * 遍历该链表
     * @param key
     * @return
     */
    public Object get(Object key) {
        if (key == null) {
            return ((MyEntry) ((LinkedList) arr[0]).getFirst()).getValue();
        }
        int index = hash(key);
        Object o = arr[index];
        if (o == null) {
            return null;
        }
        LinkedList linkedList = (LinkedList) o;
        for (Object o1 : linkedList) {
            if (o1 == null) {
                return null;
            }
            MyEntry entry = (MyEntry) o1;
            if (entry.getKey().equals(key)) {
                return entry.getValue();
            }
        }
        return null;
    }

    /**
     * 给定一个对象计算其 hash 值
     *
     * @param key
     * @return
     */
    private int hash(Object key) {
        if (key == null) {
            return 0;
        }
        return key.hashCode() & default_length;
    }

注意:真实的 HashMap 还有个字段阈值,用来控制 hashMap 的负载默认75%,即:容量达到数组的75%时进行扩容操作,举个例子:容量16,当放入第13个元素的时候进行扩容操作.
代码在这里 GitHub

多多评论,多多指教