手写 Java HashMap 核心源码

3A网络
• 阅读 817

手写 Java HashMap 核心源码

手写 Java HashMap 核心源码

上一章手写 LinkedList 核心源码,本章我们来手写 Java HashMap 的核心源码。 我们来先了解一下 HashMap 的原理。HashMap 字面意思 hash + map,map 是映射的意思,HashMap 就是用 hash 进行映射的意思。不明白?没关系。我们来具体讲解一下 HashMap 的原理。

HashMap 使用分析

//1 存
HashMap<String,String> map = new HashMap<>();
map.put("name","tom");

//2 取
System.out.println(map.get("name"));//输出 tom

使用就是这么简单。

HashMap 原理分析

我们知道,Object 类有一个 hashCode () 方法,返回对象的 hashCode 值,可以理解为返回了对象的内存地址,暂且不管返回的是内存地址或者其它什么也好,先不管,至于 hashCode () 方法回返的数是怎么算的?我们也不管

第 1 我们只需要记住:这个函数返回的是一个数就行了。 第 2 HashMap 内部是用了一个数组来存放数据

1 HashMap 是如何把 name,tom 存放的? 下面我们用一张图来演示

手写 Java HashMap 核心源码

从上图可以看出: 注:上图中数组的大小是 7,是多少都行,只是我们这里就画了 7 个元素,我们就以数组大小为 7 来说明 HashMap 的原理。

  1. 数组的大小是 7,那么数组的索引范围是 [0 , 6]
  2. 取得 key 也就是 "name" 的 hashCode,这是一个数,不管这个数是多少,对 7 进行取余数,那么范围肯定是 [0 , 6],正好和数组的索引是一样的。
  3. "name".hashCode () % 7 的值假如为 2 ,那么 value 也就是 "tom" 应该存放的位置就是 2
  4. data [2] = "tom" , 存到数组中。是不是很巧妙。

2 下面再来看看如何取? 也用一张图来演示底层原理,如下

手写 Java HashMap 核心源码

由上图可知:

  1. 首先也是获取 key 也就是 "name" 的 hashCode 值
  2. 用 hashCode 值对数组的大小 7 进行取余数,和存的时候运行一样,肯定也是 2
  3. 从数组的第 2 个位置把 value 取出,即: String value = data [2]

注:有几点需要注意

  1. 某个对象的 hashCode () 方法返回的值,在任何时候调用,返回的值都是一样的
  2. 对一个数 n 取余数,范围是 [0, n - 1]

注:有几个问题需要解决

  1. 存的时候,如果不同的 key 的 hashCode 对数组取余数,都正好相同了,也就是都映射在了数组的同一位置,怎么办?这就是 hash 冲突问题 比如 9 % 7 == 2 , 16 % 7 == 2 都等于 2 答:数组中存放的是一个节点的数据结构,节点有 next 属性,如果 hash 冲突了,单链表进行存放,取的时候也是一样,遍历链表
  2. 如果数组已经存满了怎么办? 答:和 ArrayList 一样,进行扩容,重新映射
  3. 直接使用 hashCode () 值进行映射,产生 hash 冲突的概论很大,怎么办? 答:参考 JDK 中 HashMap 中的实现,有一个 hash () 函数,再对 hashCode () 的值进行运行一下,再进行映射

由上可知:HashMap 是用一个数组来存放数据,如果遇到映射的位置上面已经有值了,那么就用链表存放在当前的前面。数组 + 链表结构,是 HashMap 的底层结构 假如我们的数组里面存放的元素是 QEntry,如下图:

手写 Java HashMap 核心源码

手写 HashMap 核心源码

上面分析了原理,接下来我们用最少的代码来提示 HashMap 的原理。 我们就叫 QHashMap 类,同时数组里面的元素需要也需要定义一个类,我们定义在 QHashMap 类的内部。就叫 QEntry

QEntry 的定义如下:

    //底层数组中存放的元素类
   public static class QEntry<K, V> {
        K key;      //存放key
        V value;    //存放value
        int hash;   //key对应的hash值

        //hash冲突时,也就是映射的位置上已经有一个元素了
        //那么新加的元素作为链表头,已经存放的放在后面
        //即保存在next中,一句话:添加新元素时,添加在表头
        QEntry<K, V> next;  

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

QEntry 类的定义有了,下面看下 QHashMap 类中需要哪些属性? QHashMap 类的定义如下图:

public class QHashMap<K, V> {
    //默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    //默认的扩容因子,当数据中元素的个数越多时,hash冲突也容易发生
    //所以,需要在数组还没有用完的情况下就开始扩容
    //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容
    //比如数组的大小是100,当里面的元素增加到75的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //存放元素的数组
    private QEntry[] table;

    //数组中元素的个数
    private int size;

    ......
}    

只需要两个常量和两个变量就够了。 下面我们看下 QHashMap 的构造函数,为了简单,只实现一个默认的构造函数

  public QHashMap() {
        //创建一个数组,默认大小为16
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];

        //此时元素个数是0
        size = 0;
    }

我们来看下 QHashMap 是如何存放数据的 map.put("name","tom") put () 函数的实现如下:

    /**
     * 1 参数key,value很容易理解
     * 2 返回V,我们知道,HashMap有一个特点,
     * 如果调用了多次 map.put("name","tom"); map.put("name","lilei");
     * 后面的值会把前面的覆盖,如果出现这种情况,返回旧值,在这里返回"tom"
     */
    public V put(K key, V value) {
        //1 为了简单,key不支持null
        if (key == null) {
            throw new RuntimeException("key is null");
        }

        //不直接用key.hashCode(),我们对key.hashCode()再作一次运算作为hash值
        //这个hash()的方法我是直接从HashMap源码拷贝过来的。可以不用关心hash()算法本身
        //只需要知道hash()输入一个数,返回一个数就行了。
        int hash = hash(key.hashCode());

        //用key的hash值和数组的大小,作一次映射,得到应该存放的位置
        int index = indexFor(hash, table.length);

        //看看数组中,有没有已存在的元素的key和参数中的key是相等的
        //相等则把老的值替换成新的,然后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            //先比较hash是否相等,再比较对象是否相等,或者比较equals方法
            //如果相等了,说明有一样的key,这时要更新旧值为新的value,同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        //如果数组中没有元素的key与传的key相等的话
        //把当前位置的元素保存下来
        QEntry<K, V> next = table[index];

        //next有可能为null,也有可能不为null,不管是否为null
        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)
        //然后新的元素保存在了index这个位置
        table[index] = new QEntry<>(key, value, hash, next);

        //如果需要扩容,元素的个数大于 table.length * 0.75 (别问为什么是0.75,经验)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {
            resize();
        }

        return null;
    }

注释很详细,这里有几个函数 hash () 函数是直接从 HashMap 源码中拷贝的,不用纠结这个算法。 indexFor (),传入 hash 和数组的大小,从而知道我们应该去哪个位置查找或保存 这两个函数的源码如下:

   //对hashCode进行运算,JDK中HashMap的实现,直接拷贝过来了
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    //根据 h 求key落在数组的哪个位置
    static int indexFor(int h, int length) {
        //或者  return h & (length-1) 性能更好
        //这里我们用最容易理解的方式,对length取余数,范围就是[0,length - 1]
        //正好是table数组的所有的索引的范围

        h = h > 0 ? h : -h; //防止负数

        return h % length;
    }

还有一个扩容函数。当元素的个数大于 table.length * 0.75 时,我们就开始扩容 resize () 的源码如下 :

  //扩容,元素的个数大于 table.length * 0.75
    //数组扩容到原来大小的2倍
    private void resize() {
        //新建一个数组,大小为原来数组大小的2倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        //遍历旧数组,重新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            //获取旧数组元素
            QEntry<K, V> e = src[j];

            //释放旧数组
            src[j] = null;

            //因为e是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                //把e的下一个节点保存下来
                QEntry<K, V> next = e.next;

                //e这个当前节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 位置上有可能是null,也有可能不为null
                //不管是否为null,都作为e这个节点的下一个节点
                e.next = newTable[i];

                //把e保存在新数组的 i 的位置
                newTable[i] = e;

                //继续e的下一个节点的同样的处理
                e = next;
            }
        }

        //所有的节点都映射到了新数组上,别忘了把新数组的赋值给table
        table = newTable;
    }

相比 put () 函数来说,get () 就简单多了。 只需要通过 hash 值找到相应的数组的位置,再遍历链表,找到一个元素里面的 key 与传的 key 相等就行了。 put () 方法的源码如下:

    //根据key获取value
    public V get(K key) {

        //同样为了简单,key不支持null
        if (key == null) {
            throw new RuntimeException("key is null");
        }

        //对key进行求hash值
        int hash = hash(key.hashCode());

        //用hash值进行映射,得到应该去数组的哪个位置上取数据
        int index = indexFor(hash, table.length);

        //把index位置的元素保存下来进行遍历
        //因为e是一个链表,我们要对链表进行遍历
        //找到和key相等的那个QEntry,并返回value
        QEntry<K, V> e = table[index];
        while (e != null) {

            //比较 hash值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {
                return e.value;
            }

            //如果不相等,继续找下一个    
            e = e.next;
        }

        return null;
    }

博主都是部署在cnaaa服务器上的上面就是 QHashMap 的核心源码,我们没有实现删除。 下面是把 QHashMap 整个类的源码发出来

QHashMap 完整源码如下:

public class QHashMap<K, V> {
    //默认的数组的大小
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    //默认的扩容因子,当数组的大小大于或者等于当前容量 * 0.75的时候,就开始扩容
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //底层用一个数组来存放数据
    private QEntry[] table;

    //数组大小
    private int size;

    //一个点节,数组中存放的单位
    public static class QEntry<K, V> {
        K key;
        V value;
        int hash;
        QEntry<K, V> next;

        public QEntry(K key, V value, int hash, QEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }

    public QHashMap() {
        table = new QEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    //根据key获取value
    public V get(K key) {

        //同样为了简单,key不支持null
        if (key == null) {
            throw new RuntimeException("key is null");
        }

        //对key进行求hash值
        int hash = hash(key.hashCode());

        //用hash值进行映射,得到应该去数组的哪个位置上取数据
        int index = indexFor(hash, table.length);

        //把index位置的元素保存下来进行遍历
        //因为e是一个链表,我们要对链表进行遍历
        //找到和key相等的那个QEntry,并返回value
        QEntry<K, V> e = table[index];
        while (e != null) {

            //比较 hash值是否相等
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {
                return e.value;
            }

            //如果不相等,继续找下一个    
            e = e.next;
        }

        return null;
    }

    /**
     * 1 参数key,value很容易理解
     * 2 返回V,我们知道,HashMap有一个特点,
     * 如果调用了多次 map.put("name","tom"); map.put("name","lilei");
     * 后面的值会把前面的覆盖,如果出现这种情况,返回旧值,在这里返回"tom"
     */
    public V put(K key, V value) {
        //1 为了简单,key不支持null
        if (key == null) {
            throw new RuntimeException("key is null");
        }

        //不直接用key.hashCode(),我们对key.hashCode()再作一次运算作为hash值
        //这个hash()的方法我是直接从HashMap源码拷贝过来的。可以不用关心hash()算法本身
        //只需要知道hash()输入一个数,返回一个数就行了。
        int hash = hash(key.hashCode());

        //用key的hash值和数组的大小,作一次映射,得到应该存放的位置
        int index = indexFor(hash, table.length);

        //看看数组中,有没有已存在的元素的key和参数中的key是相等的
        //相等则把老的值替换成新的,然后返回旧值
        QEntry<K, V> e = table[index];
        while (e != null) {
            //先比较hash是否相等,再比较对象是否相等,或者比较equals方法
            //如果相等了,说明有一样的key,这时要更新旧值为新的value,同时返回旧的值
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }

        //如果数组中没有元素的key与传的key相等的话
        //把当前位置的元素保存下来
        QEntry<K, V> next = table[index];

        //next有可能为null,也有可能不为null,不管是否为null
        //next都要作为新元素的下一个节点(next传给了QEntry的构造函数)
        //然后新的元素保存在了index这个位置
        table[index] = new QEntry<>(key, value, hash, next);

        //如果需要扩容,元素的个数大于 table.length * 0.75 (别问为什么是0.75,经验)
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {
            resize();
        }

        return null;
    }

    //扩容,元素的个数大于 table.length * 0.75
    //数组扩容到原来大小的2倍
    private void resize() {
        //新建一个数组,大小为原来数组大小的2倍
        int newCapacity = table.length * 2;
        QEntry[] newTable = new QEntry[newCapacity];

        QEntry[] src = table;

        //遍历旧数组,重新映射到新的数组中
        for (int j = 0; j < src.length; j++) {
            //获取旧数组元素
            QEntry<K, V> e = src[j];

            //释放旧数组
            src[j] = null;

            //因为e是一个链表,有可能有多个节点,循环遍历进行映射
            while (e != null) {
                //把e的下一个节点保存下来
                QEntry<K, V> next = e.next;

                //e这个当前节点进行在新的数组中映射
                int i = indexFor(e.hash, newCapacity);

                //newTable[i] 位置上有可能是null,也有可能不为null
                //不管是否为null,都作为e这个节点的下一个节点
                e.next = newTable[i];

                //把e保存在新数组的 i 的位置
                newTable[i] = e;

                //继续e的下一个节点的同样的处理
                e = next;
            }
        }

        //所有的节点都映射到了新数组上,别忘了把新数组的赋值给table
        table = newTable;
    }

    //对hashCode进行运算,JDK中HashMap的实现,直接拷贝过来了
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    //根据 h 求key落在数组的哪个位置
    static int indexFor(int h, int length) {
        //或者  return h & (length-1) 性能更好
        //这里我们用最容易理解的方式,对length取余数,范围就是[0,length - 1]
        //正好是table数组的所有的索引的范围

        h = h > 0 ? h : -h; //防止负数

        return h % length;
    }

}

上面就是 QHashMap 的原理。下面我们写一段测试代码来看下我们的 QHashMap 能不能正常运行。测试代码如下:

 public static void main(String[] args) {
        QHashMap<String, String> map = new QHashMap<>();
        map.put("name", "tom");
        map.put("age", "23");
        map.put("address", "beijing");
        String oldValue = map.put("address", "shanghai"); //key一样,返回旧值,保存新值

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));

        System.out.println("旧值=" + oldValue);
        System.out.println("新值=" + map.get("address"));
    }

输出如下:

tom
23
旧值=beijing
新值=shanghai

通过上面的简单的实现了 QHashMap, 还有好多功能没有实现,比较 remove,clear,containsKey () 等,还有遍历相关,有兴趣的读者可以自己实现

点赞
收藏
评论区
推荐文章
九路 九路
4年前
1 手写ArrayList核心源码
手写ArrayList核心源码ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet,Queue,PriorityQueue等等,我们将手写这些常用的数据结构的核心源码,用尽量少的代码来揭示核心原理。下面我们来手写ArrayList的核心源码首先
九路 九路
4年前
3 手写Java HashMap核心源码
手写JavaHashMap核心源码上一章手写LinkedList核心源码,本章我们来手写JavaHashMap的核心源码。我们来先了解一下HashMap的原理。HashMap字面意思hashmap,map是映射的意思,HashMap就是用hash进行映射的意思。不明白?没关系。我们来具体讲解一下HashMap的原理。HashMap
3A网络 3A网络
2年前
手写 ArrayList 核心源码
手写ArrayList核心源码手写ArrayList核心源码ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet
待兔 待兔
5个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
九路 九路
4年前
4.1 手写Java PriorityQueue 核心源码
本章先讲解优先级队列和二叉堆的结构。下一篇代码实现从一个需求开始假设有这样一个需求:在一个子线程中,不停的从一个队列中取出一个任务,执行这个任务,直到这个任务处理完毕,再取出下一个任务,再执行。其实和Android的Handler机制中的Looper不停的从MessageQueue中取出一个消息然后处理是一样的。不过这个需
九路 九路
4年前
4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下PriorityQueue的原理以最大堆为例来介绍1.PriorityQueue是用一棵完全二叉树实现的。2.不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大3.PriorityQueue底层是用数组来保存这棵完全二叉树的。如下图,是一棵最大堆。
九路 九路
4年前
5 手写Java Stack 核心源码
Stack是Java中常用的数据结构之一,Stack具有"后进先出(LIFO)"的性质。只能在一端进行插入或者删除,即压栈与出栈栈的实现比较简单,性质也简单。可以用一个数组来实现栈结构。1.入栈的时候,只在数组尾部插入2.出栈的时候,只在数组尾部删除我们来看一下Stack的用法:如下publicstaticvoidmai
九路 九路
4年前
6 手写Java LinkedHashMap 核心源码
概述LinkedHashMap是Java中常用的数据结构之一,安卓中的LruCache缓存,底层使用的就是LinkedHashMap,LRU(LeastRecentlyUsed)算法,即最近最少使用算法,核心思想就是当缓存满时,会优先淘汰那些近期最少使用的缓存对象LruCache的缓存算法LruCache采用的缓存算法为LRU(LeastRe
九路 九路
4年前
2 手写Java LinkedList核心源码
上一章我们手写了ArrayList的核心源码,ArrayList底层是用了一个数组来保存数据,数组保存数据的优点就是查找效率高,但是删除效率特别低,最坏的情况下需要移动所有的元素。在查找需求比较重要的情况下可以用ArrayList,如果是删除操作比较多的情况下,用ArrayList就不太合适了。Java为我们提供了LinkedList,是用链接来实现的,我们