手写JDK7-HashMap

前言

现在一般都JDK8了,为什么还要说JDK7呢。因为JDK7和JDK8的hashmap实现不一样,JDK7是用数组+链表实现的,而JDK8是红黑树。学习都是个慢慢渐进的过程。

实现

时间复杂度:

读取

插入

删除

数组

O(1)

O(n)

O(n)

链表

O(n)

O(1)

O(1)

上面提到JDK7是用数组+链表实现的,为什么这样做呢?我们知道数组读取速度快,插入慢,而链表读取慢,插入快,hashmap就是充分利用了数组读取快和链表插入快的特点。数组存着元素的下标,元素插入链表中。那么下标怎么生成呢,hashmap嘛,那肯定是和hashcode有关系,我们生成hashcode看看是啥样的。

public class Main {

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            String key = "code" + i;
            System.out.println(key.hashCode());
        }
    }
}

输出:

94834659
94834660
94834661
94834662
94834663
94834664
94834665
94834666
94834667
94834668

看到hashcode的值非常大,如果用于当下标的话,数组就要非常大才能把这些元素给存起来,性能也是大打折扣,那有什么办法缩小一点呢,我想到的一种是取余(JDK并不是这么干)

public class Main {

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            String key = "code" + i;
            int hashCode = key.hashCode();
            int index = hashCode % 8;
            System.out.println(index);
        }
    }
}

输出:

3
4
5
6
7
0
1
2
3
4

下标就控制在8的范围内了,但是又出现了另一个问题:hash冲突了,存在了两个3,两个4。这种情况怎么处理呢?下标一直的都插入到一个链表中,新元素放在头部。(为什么插入头部?因为链表结构插入数据在头部是最快的,只需将指针指向旧的链表即可)

插入后数据结构如下图:

代码

/**
 * 手写简单的hashMap(1.7版)
 *
 * @author DHB
 */
public class MyHashMap<K, V> {

    /**
     * 元素表
     */
    private Entry<K, V>[] table;
    /**
     * 容量
     */
    private static final Integer CAPACITY = 8;
    /**
     * 大小
     */
    private int size = 0;

    public MyHashMap() {
        this.table = new Entry[CAPACITY];
    }

    /**
     * 获取大小
     *
     * @return 大小
     */
    public int size() {
        return this.size;
    }


    /**
     * 根据key获取value
     *
     * @param key jey
     * @return 元素
     */
    public V get(K key) {
        int index = obtainIndex(key);
        for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.k.equals(key)) {
                return entry.v;
            }
        }
        return null;
    }

    /**
     * 插入,当存在这个key的时候会替换,并且返回
     *
     * @param key   key
     * @param value value
     * @return 旧的元素
     */
    public V put(K key, V value) {
        int index = obtainIndex(key);
        for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.k.equals(key)) {
                V oldValue = entry.v;
                entry.v = value;
                return oldValue;
            }
        }
        addEntry(key, value, index);
        return null;
    }

    /**
     * 添加Entry
     *
     * @param key   key
     * @param value value
     * @param index 下标位置
     */
    private void addEntry(K key, V value, int index) {
        table[index] = new Entry(key, value, table[index]);
        size++;
    }

    /**
     * 通过key获取插入的位置
     *
     * @param key key
     * @return 获取位置
     */
    private int obtainIndex(K key) {
        int hashCode = key.hashCode();
        return hashCode % 8;
    }

    /**
     * 链表数据结构
     *
     * @param <K> key
     * @param <V> value
     */
    class Entry<K, V> {

        public Entry(K k, V v, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.next = next;
        }

        private K k;
        private V v;
        /**
         * 指向下一个元素
         */
        private Entry<K, V> next;
    }

}

总结

上面的代码很粗糙,但能大概了解了HashMap的工作原理。有很多问题没有解决,下一个笔记再说,先抛出问题。

  • HashMap的键值可以为Null吗?原理是什么?
  • HashMap扩容机制是怎么样的,JDK7和JDK8有什么不同?
  • JDK8中的HashMap有哪些改动?
  • JDK8中为什么要使用红黑树?
  • 为什么重写对象的Equal方法时,要重写HashCode方法,跟HashMap有什么关系吗?
  • HashMap是线程安全的吗?遇到ConcurrentModificationException异常吗?为什么?出现怎么解决?
  • 在使用HashMap的过程中我们应该注意些什么问题?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Jvm中各种内存溢出情况分析

    oom即OutOfMemoryError,出现这个报错的主要原因是内存空间不足以装下数据导致抛出异常。要探讨JVM出现oom的情况,首先要了解下jvm的内存模型...

    DH镔
  • JVM参数记录

    JVM 参数设置 Is there a way to get which classes a ClassLoader has loaded?

    DH镔
  • 1搭建nacos

    nacos的官方仓库地址:https://github.com/alibaba/nacos.git

    DH镔
  • 【Redis】Redis常用命令

    expire key seconds 当超过过期时间,会自动删除,key在seconds秒后过期 expireat key timest...

    用户5522200
  • Redis学习二(数据操作).

    在 redis-cli 中使用中文时,必须打开 --raw 选项,才能正常显示中文。

    JMCui
  • Redis内存数据库操作命令详解

       rename(oldname, newname):将key由oldname重命名为newname,若newname存在则删除newname表示的key

    数据饕餮
  • Redis常用命令、5种数据类型的内部编码实现以及实用场景

    相信绝大部分人,应该是99%的人都知道Redis的5种的基本类型、它们分别是:字符串、哈希、列表、集合、有序集合,就如同下图这样:

    Java学习录
  • vue和react中循环key的作用

    没用过react开发项目,但想来跟vue在循环渲染中key的作用应该原理是一样的。循环在没有使用key的时候,vue会警告。但是这个key的作用是什么。

    wade
  • Redis命令与配置

        slaveof  127.0.0.1 6379(设置Mater的Host以及Port)

    莫问今朝
  • Redis命令总结及其基础知识讲述

      Redis拥有其他数据库不具备的数据结构,又拥有内存存储(这使得redis的速度非常快),远程操作(使得redis可以与多个客户端和服务器进行连接)、持久化...

    那一叶随风

扫码关注云+社区

领取腾讯云代金券