文档章节

java HashMap源码分析

Lbj虞
 Lbj虞
发布于 2017/05/03 22:23
字数 1515
阅读 56
收藏 6

前段时间面试,被问到HashMap,被虐了一回 下面是HashMap的源码 HashMap的构造方法



//本质上都是调用的这个构造方法
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;//设置容器的增长因子
        threshold = initialCapacity;//设置容器的初始长度
        init();//点过去看发现使个空方法,此方法在HashMap的子类LinkHashMap重写
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR); //给定长度的初始化方法
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
//采用默认长度的16,增长因子为0.75的初始化方法
    }

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {

    //传入map得到新的和原来一样的map,用于map的复制

        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);

        putAllForCreate(m);
    }

先介绍HashMap的一个内部类 Entry

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;     //key 键
        V value;        //值
        Entry<K,V> next; //下一个Entry对象
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

再看看HashMap的put方法

 public V put(K key, V value) {

//static final Entry<?,?>[] EMPTY_TABLE = {};  空的Entry数组
        if (table == EMPTY_TABLE) {
//为空初始化 Entry数组
            inflateTable(threshold);
        }

        if (key == null)
            return putForNullKey(value);//处理为null的key
        int hash = hash(key);//计算key的hashcode
        int i = indexFor(hash, table.length);//获取索引

     //获取数组中索引对应的Entry对象
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        //如果存在,替换原来已有的对象
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }


/
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
      //这个方法是用来返回大于等于最接近toSize的2的冪数,例如size=5,roundUpToPowerOf2(5)则会返回8,因此HashMap的长度只能是2的幂次数

         //计算出下次增长的长度
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

        table = new Entry[capacity]; //设置数组长度
        initHashSeedAsNeeded(capacity); //初始化计算hashcode的随机hashSeed值
    }


final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);  
            //字符串,用了sun.misc.Hashing.stringHash32((String) k);来获取索引值
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);  //高位与低位进行异或操作
    }

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1); //确定数组index:hashcode % table.length取模
    }

在哈希表容量(也就是buckets或slots大小)为length的情况下,为了使每个key都能在冲突最小的情况下映射到[0,length)(注意是左闭右开区间)的索引(index)内,一般有两种做法:
1.让length为素数,然后用hashCode(key) mod length的方法得到索引
2.让length为2的指数倍,然后用hashCode(key) & (length-1)的方法得到索引
HashTable用的是方法1,HashMap用的是方法2。


void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next
    //如果size超过threshold,则扩充table大小。再散列
    if (size++ >= threshold)
            resize(2 * table.length);
}

HashMap的get方法

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }


主要看getEntry方法

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);//根据key拿到hashcode
    //拿到hashcode对应下标的数组元素,迭代循环
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

下面是网上找来的HashMap的数据结构图 输入图片说明

输入图片说明

从上图可以看出,HashMap是链表散列结构的

每次put,都会计算key的Hashcode,得到Entry中的索引,获取Entry数组中对应索引的链表对象,循环链表对象,判断是否存在key相同的,有直接替换,没有直接添加,新添加的对象位于改索引对应数组的最后位

每次get 先拿到key计算Hashcode,得到Entry中的索引,获取Entry数组中对应索引的链表对象,循环链表对象,获取key相同对象

key对应的HashCode一样,不代表key是相同的,java中的HashCode 是java将该对象再内存中的地址以int数来表现,但不是该对象的内存地址,java是不能获取对象在内存中的地址

链表:物理内存地址不连续,非有序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接来实现的 例如:LinkList 双向链表 上一个元素 当前元素 下一个元素 HashMap的子类 LinkedHashMap,有序的put是什么顺序,get就是什么什么,因为它一个运行于所有条目的双重链接列表维护着

散列表(哈希表):通过key value键值对存储数据,根据数据的hashcode对数据进行分组

数组:物理内存连续且有序的存储结构

© 著作权归作者所有

Lbj虞
粉丝 5
博文 30
码字总数 20298
作品 0
南京
程序员
私信 提问
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
2018/08/08
0
0
HashMap 底层实现原理,看完面试不再懵逼。

前言: HashMap是在面试中经常会问的一点,很多时候我们仅仅只是知道HashMap他是允许键值对都是Null,并且是非线程安全的,如果在多线程的环境下使用,是很容易出现问题的。 这是我们通常在面...

Java干货分享
07/10
0
0
【目录导航】JAVA零基础进阶之路

【JAVA零基础入门系列】(已完结)导航目录 Day1 开发环境搭建 Day2 Java集成开发环境IDEA Day3 Java基本数据类型 Day4 变量与常量 Day5 Java中的运算符 Day6 Java字符串 Day7 Java输入与输出...

MFrank
2018/06/21
0
0
泥沙砖瓦浆木匠/java-core-learning-example

感谢赞助的ta们 Java 核心系列教程,关于Java核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。 包括基础语法,OOP,字符串,集合,IO,反射,线程,网络等。 未完成模块:阿里J...

泥沙砖瓦浆木匠
04/02
0
0
HashMap底层实现(源码分析)

一、数据结构 Map将实际数据存储在Entry类的数组中。 代码片段: Java代码 transient Entry[] table;//HashMap的成员变量,存放数据 static class Entry<K,V> implements Map.Entry<K,V> {/......

pricker
2015/07/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

solr

简介:solr是基于全文检索的企业级应用服务器。 solr入门案列。 配置: (1)配置Solr服务器。 1.解压一个Tomcat 2.部署solr服务到Tomcat中 3.添加solr运行依赖的jar包 (2)配置SolrHome。(...

klmkom
26分钟前
2
0
nginx 可以使用 alias 指定 其他目录,做静态服务器

比如 访问 图片,/images 去到 对应的 硬盘地址去获取。 expires 表示 缓存的意思, 这里缓存 一天

之渊
31分钟前
2
0
linux redis后台运行

daemonize no -> yes /usr/local/redis/redis-4.0.10/src/redis-server /usr/local/redis/redis-4.0.10/redis.conf...

八戒八戒八戒
41分钟前
2
0
SSM(SPRING+SPRINGMVC+MYBATIS)框架搭建

一. SSM框架架构及流程介绍 SSM框架,通常是指将spring mvc+spring+mybatis三个框架整合在一起进行工作,spring mvc本身就是spring的一部分,所以这两者之间不用整合,这里主要做的事情就是将...

潜行-L
45分钟前
3
0
django2.2 用户登录练习完整版(待改善)

主要配置: settings.py配置: #数据库配置import pymysqlpymysql.install_as_MySQLdb()DATABASES = {    'default': {        'ENGINE': 'django.db.backends.mysql',  ......

平头哥-Enjoystudy
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部