文档章节

JDK源码阅读系列---HashMap

B
 BaronChen
发布于 2016/11/23 23:37
字数 1686
阅读 13
收藏 0

JDK8的HashMap的bucket内部引入了treeify,链表过长(>8),影响查询,JDK将把bucket内部元素从Node变为TreeNode(实现红黑树))

HashMap作为一个经常用到的类,先从此类开始阅读。

####存储原理图 输入图片说明

####一、 成员变量

  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    默认的桶数量

  2. static final int MAXIMUM_CAPACITY = 1 << 30;
    桶的最大数量

  3. static final float DEFAULT_LOAD_FACTOR = 0.75f;
    默认负载系数

  4. static final int TREEIFY_THRESHOLD = 8;
    桶内元素树化的最少个数

  5. static final int UNTREEIFY_THRESHOLD = 6;
    反树化时, 桶内元素的最多个数

  6. final float loadFactor;
    设置的负载系数

  7. static final int MIN_TREEIFY_CAPACITY = 64;
    桶内元素就行树化的时候,整个容器的需要达到的最小容量

  8. transient int modCount;
    容器内部发生结构性改变的次数(用于iterator遍历)

  9. transient int size;
    容器内部存储的元素个数

  10. transient Node<K,V>[] table;
    存储桶的数组,这个是HashMap的核心

  11. int threshold;
    进行再次内存分配的时候。元素需要达到的个数

  12. transient Set<Map.Entry<K,V>> entrySet; 提供map的访问接口

####二、公有方法

  1. public void clear() 清空内部元素。

  2. public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
    获取与key对应的value,并且将它们作为参数调用remappingFunction(),得到新的value。
    如果key原来不存在的话,将新的key,value添加进去,但是value不能为空值。

  3. public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
    根据key去查找node. 分为以下几种情况 :

  1. node不存在的话,就添加新的node,key为key,value为mappingFunction.apply(key),添加的时候可能会对bucket内元素进行treeify
  2. node存在,且值不为空,直接返回
  3. node存在,值为空,使用mappingFunction(key)进行计算,然后更新值
  1. public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
    根据key去查找node,若node存在,则使用mappingFunction(key)去更新值,不存在立刻返回。

  2. public boolean containsKey(Object key)
    根据key去查找node,调用内部的getNode方法

  3. public V put(K key, V value)
    将键值对放入bucket内部,此处注意可能要进行treeify。

  4. public boolean containsValue(Object value)
    遍历table,并且遍历每个bucket

  5. public Set<Map.Entry<K,V>> entrySet()
    返回一个EntrySet类型对象,EntrySet类型继承自AbstractSet,我们主要用这个类来进行对HashMap的遍历

  6. public void forEach(BiConsumer<? super K, ? super V> action)
    针对每一个内部存储的元素,调用action.accept()方法,在调用过程中,modCount不能改变,这就是为什么HashMap的迭代是failFast的,如果改变就会抛出异常。

  7. public V get(Object key)
    获取key对应的value

  8. public V getOrDefault(Object key, V defaultValue)
    JDK8新方法,如果value为null,返回defaultValue。

  9. public boolean isEmpty()
    返回size == 0

  10. public Set<K> keySet()
    返回一个包含所有key的Set,可以对这个set进行迭代,然后遍历

  11. public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)
    通过key去查询一个已存在的键值对,并且将oldValue与newValue传递给remappingFunction进行计算后重新赋值给对应key

  12. public V put(K key, V value)
    将键值对存入map内,涉及到resize以及treeify

  13. public void putAll(Map<? extends K, ? extends V> m)
    通过entrySet()遍历m,将m内的所有元素插入新的map

  14. public V putIfAbsent(K key, V value)
    如果key对象的键值对不存在,则存入新的键值对

  15. public V remove(Object key)
    通过key去检索键值对,并且删除

  16. public boolean remove(Object key, Object value)
    通过key去检索键值对,并且通过equals方法比较检索出来的value,若value相等则移除

  17. public boolean replace(K key, V oldValue, V newValue)
    如果key对应的map内的value为oldValue,则将其替换为newValue

  18. public V replace(K key, V value)
    强key对象的值替换为value

  19. public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function)
    对于所有的键值对调用function,apply()方法,并将返回值作为新的value

  20. public int size()
    返回大小

  21. public Collection<V> values()
    获取所有的值的Collection(但是并不是说把所有的值存储在了类似于List这样的集合里面了,我们只是可以调用Collection的接口而已)

####三、简单实现

package com.braon.jdk;

public class SimpleHashMap<K, V> {
    private Node<K, V>[] table;
    private int capacity = 4;
    private float loadFactor = 0.75f;
    private int threshold = 3;
    private int size;

    public SimpleHashMap() {
        init();
    }

    public SimpleHashMap(int capacity, int loadFactor) {
        this.capacity = capacity;
        this.loadFactor = loadFactor;
        this.threshold = capacity * loadFactor;
        init();
    }

    @SuppressWarnings("unchecked")
    private void init() {
        capacity = 1 << 4;
        table = new Node[capacity];
        size = 0;
    }

    public void clear() {
        init();
    }

    public void put(K K, V V) {
        if (K == null || V == null) {
            return;
        }
        // space is narrow
        else if (size + 1 > threshold) {
            resize();
        }

        Node<K, V> newNode = new Node<>();
        newNode.setK(K);
        newNode.setV(V);
        newNode.setHash(K.hashCode() & (capacity - 1));
        newNode.setNext(null);

        if (putNode(newNode))
            size++;
    }

    public V get(K K) {
        // calculate store place
        int hash = K.hashCode() & (capacity - 1);
        Node<K, V> first = table[hash];

        if (first != null) {
            do {
                if (first.getK().equals(K))
                    return first.getV();
            } while ((first = first.next) != null);
            return null;
        } // if
        else
            return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        // recaculate the array size
        capacity = capacity << 1;
        threshold = (int) (loadFactor * capacity);

        // keep the old one, and renew a new table
        Node<K, V>[] oldTable = table;
        table = new Node[capacity];
        // relay the elements
        for (Node<K, V> first : oldTable) {
            while (first != null) {
                first.setHash(first.getK().hashCode() & (capacity - 1));
                this.putNode(first);

                // we need to remove the link
                Node<K, V> next = first.next;
                first.next = null;
                first = next;
            } // while
        } // for
    }

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return capacity;
    }

    private boolean putNode(Node<K, V> newNode) {
        Node<K, V> first = table[newNode.getHash()];
        if (first == null) {
            table[newNode.getHash()] = newNode;
        } else {
            while (first.next != null) {
                // two absolute equivalent K, we need to update the V
                if (first.getK().equals(newNode.getK())) {
                    first.setV(newNode.getV());
                    return false;
                }
                first = first.next;
            }

            if (first.getK().equals(newNode.getK())) {
                first.setV(newNode.getV());
                return false;
            } else
                first.next = newNode;
        }
        return true;
    }

    public void print() {
        System.out.println(toString() + "\r\n");
    }

    public void remove(K k) {
        if (k == null)
            return;

        int hash = k.hashCode() & (capacity - 1);
        Node<K, V> prev = table[hash];
        Node<K, V> cur = table[hash].next;

        if (prev.getK().equals(k)) {
            table[hash] = table[hash].next;
            size--;
            return;
        }
        while (cur != null) {
            if (cur.getK().equals(k)) {
                prev.next = cur.next;
                size--;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        for (Node<K, V> node : table) {
            if (node != null) {
                do {
                    sb = sb.append("hashCode: " + node.getHash() + ", K: " + node.getK() + ", V: "
                            + node.getV() + "   ");
                } while ((node = node.next) != null);
                sb.append("\r\n");
            }
        }
        return sb.toString();
    }
}

class Node<K, V> {
    Node<K, V> next;
    private K k;
    private V v;
    private int hash;

    public Node() {
    }

    public Node(K k, V v) {
        this.k = k;
        this.v = v;
    }

    public int getHash() {
        return hash;
    }

    public void setHash(int hash) {
        this.hash = hash;
    }

    public K getK() {
        return k;
    }

    public void setK(K k) {
        this.k = k;
    }

    public Node<K, V> getNext() {
        return next;
    }

    public void setNext(Node<K, V> next) {
        this.next = next;
    }

    public V getV() {
        return v;
    }

    public void setV(V v) {
        this.v = v;
    }
}

####注意点 1、需要同时重载equals和hashCode方法
2、size增长后又减小,但是capacity不会减小
3、使用entrySet()进行遍历,比较快,使用keySet()遍历,相对较慢
4、hashCode方法的编写需要注意,最好不要有多个值产生相同的hashCode,不然对查询产生影响
5、loadfactor最好不要改变
6、查询次数较多,插入次数相对较少,且元素hashCode相对集中,请使用TreeHashMap
7、values()方法获取的返回值并没有存储了任何一个value的引用,只是我们可以用Collection接口的方法去调用这个返回值而已
8、耗时较多的插入一般都是因为需要resize或者treeify

© 著作权归作者所有

B
粉丝 0
博文 11
码字总数 6676
作品 0
南京
私信 提问
集合系列开篇:为什么要学集合?

集合可以说是学习 Java 中最重要的一块知识点了,无论做任何业务系统,集合总是最为基础的那块 API。我第一次接触集合,是在我大三的时候,那时候去面试,面试官问我:你了解过集合吗?可惜那...

陈树义
08/23
0
0
Java源码--JDK 1.8 HashMap 重点源码部分剖析

注:感谢 美团点评技术团队 的分享~~,博客部分内容摘抄自其中。侵删! 今天我们来探究一下 HashMap 的内部实现机制。 明确 JDK 1.8 中的 HashMap 使用数组 + 链表 + 红黑树的结构进行实现。...

珩翊
2018/04/20
0
0
Java 集合系列目录(Category)

Java 集合系列目录(Category) 下面是最近总结的Java集合(JDK1.6.0_45)相关文章的目录。 01. Java 集合系列01之 总体框架 02. Java 集合系列02之 Collection架构 03. Java 集合系列03之 Arra...

foxeye
2016/02/29
79
0
Java集合 --- LinkedHashMap底层实现和原理(源码解析)

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 LinkedHashMap,见...

起个名忒难
2017/09/24
0
0
容器类源码解析系列(三)—— HashMap 源码分析(最新版)

容器类源码解析系列(三)—— HashMap 源码分析(最新版) 前言 本篇文章是《Java容器类源码解析》系列的第三篇文章,主要是对HashMap的源码实现进行分析。强烈建议阅读本文之前,先看看该系列...

MRYangY
04/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用原生css+js+html实现打印A4纸张的功能页面

有时候我们需要使用html+css实现打印A4纸张的功能页面,以下代码实现 <!DOCTYPE html><html lang="zh-CN"> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatibl......

b0cloud
26分钟前
4
0
读组件化之MGJRouter源码第二次的收获与思考

上一次我们写好了一个自定义的 路由类 ,然后我们来制作自己的 库 ,可以用来被 pod 引入 : 库的制作参考:https://www.jianshu.com/p/928d2ab053be 以下是我创建的: 利用上篇提到的 ,组件...

T型人才追梦者
28分钟前
2
0
spring cache、ehcache的使用及集成

项目中需要加缓存,故学习了 1、spring cache、ehcache的使用及集成 2、缓存的命中率等统计数据 一、spring cache 1、概述 Spring 3.1 引入了基于注解(annotation)的缓存(cache)技术 2、...

qkKing
29分钟前
4
0
Windows 10上源码编译Poco并编写httpserver和tcpserver | compile and install poco cpp library on windows

本文首发于个人博客https://kezunlin.me/post/9587bb47/,欢迎阅读! compile and install poco cpp library on windows Series guide to compile and install poco cpp library on windows g......

kezunlin
30分钟前
4
0
if-else-if-else与switch的区别

if-else-if-else: 适合分支较少 判断条件类型不单一 支持取 boolean 类型的所有运算 满足条件即停止对后续分支语句的执行 switch: 适合分支较多 判断条件类型单一,JDK 1.7 之前仅支持 in...

ConstXiong
30分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部