文档章节

HashMap深入学习

树上的风筝
 树上的风筝
发布于 2016/05/19 17:13
字数 2406
阅读 184
收藏 4

精选30+云产品,助力企业轻松上云!>>>

        HashMap 是Map接口的常用实现类并且 是以键值对(key,value)采用一种所谓的“Hash算法”,来决定每个元素的存储位置。

HashMap的存储实现    

    当程序试图将多个 key-value 放入 HashMap 中时,以如下代码片段为例: 

        HashMap map = new HashMap();

            map.put("语文",80.0);

            map.put(“数学”,89.0);

            map.put(“英语”,78.2)

当程序执行map.put(“语文”,80.0)时,系统将调用“语文”的hashCode方法得到其HashCode值-每个Java对象都有一个HashCode方法,都可以通过该方法获得它的hashCode值。得到这个对象的hashCode值之后,系统会根据该hashCode值来决定元素的存储位置。

    看一下HashMap类的put()方法源码代码如下。

    public V put(K key, V value) {

        //table 为空则初始化table(Entry[])大小,和hash的掩码值(需要的时候初始化)

    if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }

//key值为空则调用putForNullKey方法进行处理
        if (key == null)
            return putForNullKey(value);

        //根据key的keyCode计算Hash值
        int hash = hash(key);

    //搜索指定的hash值对应table中的索引
        int i = indexFor(hash, table.length);

//如果i索引处的Entry 不为null,通过循环不断遍历e元素的下一个元素
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;

            //找到指定key与需要放入的key相等(hash值相等,通过equals比较返回true)
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

//如果i索引处的Entry为null,表明此处还没有Entry 

        modCount++;

    //将key、value添加到i索引处
        addEntry(hash, key, value, i);
        return null;
    }

 

上面的源码程序中用到了一个重要的内部接口 Map.Entry,每个Map.Entry其实是一个key-value对。当系统决定存储HashMap的key-value对时,完全没有考虑Entry 中的value,而仅仅只是根据key来计算并决定每个Entry的存储位置。

 从上面put方法的源码可以看出,当程序试图将一个key-value对放入HashMap中时,首先根据key的hashcode()返回值决定该Entry的存储对象的位置:如果两个Entry的key的hashcode()返回值相同,那它们的存储位置相同;如果这两个Entry 的key通过equals比较返回true,新添加Entry的value将覆盖集合中的原有的Entry的value,但key不会覆盖;如果这两个Entry 的key通过equals比较返回false,新添加的Entry将与集合中原有的Entry 形成Entry链,而且新添加的Entry位于Entry链的头部-具体看AddEntry()方法说明

注意:当向HashMap中添加key-value对,由其key的hashcode()返回值决定该key-value对(Entry对象)的存储位置。当两个Entry对象的Key的hashcode()返回值相同时,将由key的equeals()比较值决定是采用覆盖行为(返回true执行),还是产生Entry链(返回false执行)

上面程序中还调用了addEntry(hash,key,value,i);代码,其中addEntry是hashMap提供的一个包的访问权限的方法,该方法仅用于添加一个key-value对,下面是该方法的源码

 void addEntry(int hash, K key, V value, int bucketIndex) {

    //如果Map中的key-value对数量超过了极限,当size>=threshold时,HashMap会自动调用resize方法扩充HashMap的容量。每扩充一次,hashMap就增大一倍。
        if ((size >= threshold) && (null != table[bucketIndex])) {

            //把table对象的长度扩充2倍
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

 

void createEntry(int hash, K key, V value, int bucketIndex) {

    //获取指定bucketIndex索引处的Entry
        Entry e = table[bucketIndex];  //1

    //将创建的Entry仿佛bucketIndex索引处,并让新的Entry指向原来的Entry
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

上面的源代码很简单,系统将新添加的Entry对象放入table数组的bucketIndex索引处,如果bucketIndex索引出已经有一个Entry对象,新添加的Entry对象指向原有的Entry对象(产生一个Entry链);如果bucketIndex索引处没有Entry对象,也就是1处的e变量为null,即新放入的Entry对象指向null,就没有产生Entry链。(注意:在同一个bucketIndex存储Entry链的情况下,新放入的Entry总是位于bucketIndex索引中,而最早放入该bucketIndex索引位置的Entry则位于Entry链的最末端)

 size:改变量保存了该HashMap中所有包含key-value对的数量。

threshold:该变量包含了HashMap能容纳的key-value对的极限,它的值等于HashMap容量乘以负载因子(DEFAULT_LOAD_FACTOR)

table是一个普通的数组,每个数组都有一个固定的长度,这个数组的长度就是HashMap的容量。

jdk1.7以前,创建HashMap时,系统会自动创建一个table数组来保存HashMap 的Entry。jdk1.7中是当掉用put方法时才对创建table数组。下面源码:

jdk1.6HashMap构造方法

public HashMap(int initialCapacity, float loadFactor) {

        //初始容量不能为负数
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);

        //如果初始容量大于最大容量,让初始容量等于最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        //负载因子必须是大于0的数值
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        //========以下方法是jdk1.7以前版本的内容。

    //计算出大于initialCapacity的最小的2的n次方值   

     int capacity =1;

        while(capacity<initialCapacity)

            capacity<<=1;

        this.loadFactor = loadFactor;

//    设置容量极限等于容量乘以负载因子

        threshold =(int)(capacity*loadFactory);

    table = new Entry[capacity];

//=========================

      this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

jdk1.7的put方法:

  public V put(K key, V value) {

    //如果table值为空则创建
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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;
    }

对于HashMap和子类而言,它们采用Hash算法来决定集合中元素的存储位置。当系统开始初始化HashMap时(jdk1.7以前版本)或者调用put(key,value)(jdk1.7以上版本)方法时。系统会创建一个长度为capacity的Entry数组。这个数组存储元素的位置被称为“桶(bucket)”,每个bucket都有指定的索引,系统可以根据其索引快速访问该bucket里存储的元素。

无论何时,HashMap的每个“桶”只能存储一个元素(即一个Entry),由于Entry对象包含一个引用变量(就是entry构造器的最后一个参数)用于指向下一个Entry,因此可能出现:HashMap的bucket中的只有一个Entry,但这个Entry指向另一个Entry----形成一个Entry链。如下图:

当HashMap的每个bucket里存储的Entry只是单个Entry,即没有通过指针产生Entry链时,此时的HashMap具有最好的性能。当程序通过key取出对应的value值时,系统只要先计算出该key的hashcode()返回值,在根据系统HashCode返回值找出该key在table数组中的索引,然后取出该索引出的Entry,最后返回该key对应的value。HashMap对应的get(K key)方法源码如下:

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

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

 

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

        int hash = (key == null) ? 0 : hash(key);
        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;
    }

 

private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

代码中可以看出,如果hashMap的每个bucket里只有一个Entry,HashMap可以根据索引快速的取出该bucket里的Entry.在发生Entry冲突情况下,单个bucket里存储的不是一个Entry,而是一个Entry链,系统只能按书序遍历每个Entry,直到直到想要的Entry为止。如果下号要搜索的Entry位于该Entry链的末端(该Entry最早放入该bucket链,那么系统必须循环到最后才能找到元素)。

总结:HashMap在底层将key-value当成一个整体进行处理。这个整体是一个Entry对象。HashMap底层采用一个Entry[]数组来保存所有的key-value对,当需要存储一个Entry对象时,会根据Hash算法来决定其存储位置;当需要取出一个Entry时,也会根据算法找到其存储位置,直接取出该Entry。由此可见,HashMap之所以能快速存、取它所包含的Entry,完全类似于现实生活中的:不同的东西放在不同的位置,需要时才能快速找到它。

当创建HashMap时,有一个默认的负载因子(load factor),其默认值为0.75.这是时间和空间成本的一种折中;增大负载因子可以减少Hash表(减少Entry数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的操作(HashMap 的get()与put()方法都要用到查询);减小负载因子会提高数据的查询性能,但会降低Hash表所占的内存空间。

掌握了上面的知识。可以在创建HashMap的时候根据实际情况适当地调整load factor的值。。如果程序比较关系内存的开销。内存比较紧张,可以适当的增加负载因子;如果程序比较关心时间开销,内存比较宽裕,则可以适当地减少负载因子,通常情况下。程序员不需要改变负载因子的值

树上的风筝
粉丝 2
博文 38
码字总数 20218
作品 0
朝阳
程序员
私信 提问
加载中
请先登录后再评论。
字节跳动面试官揪着源码一直问,然后......

最近,我的一位朋友在找工作,已经拿到了美团、快手等公司的Offer,准备选择其中一家入职了。 后来他又接到了字节跳动的电话,通知他去参加三面。从二面到三面之间隔了挺久的,他以为都没戏了...

Java架构师追风
2019/07/23
0
0
Java:HashMap和Hashset的实现

深入Java集合学习系列:HashMap的实现原理 深入Java集合学习系列:HashSet的实现原理 HashSet基于HashMap实现。

樂天
2015/06/28
339
2
技术的洞察力

很多时候,我在学技术时候,好像学了很多,但是并没有获得一流的见解(让自己顿悟的见解)和常识,学习质量很低,甚至连技术本身都没有理解透,只是囫囵吞枣,我也很“努力”,写几个API做做样...

osc_4snbwzam
05/03
6
0
Java:HashMap的死循环

基础一些: 深入Java集合学习系列:HashMap的实现原理 HashMap与Hashtable的区别 非线程安全的HashMap如何产生死循环: 疫苗:Java HashMap的死循环 HashMap 死循环的探究 不正当使用HashMap...

樂天
2015/06/29
42
0
java源码

Java 集合深入理解:ArrayList 回归基础,Java 集合深入理解系列,持续更新~ JVM 源码分析之 System.currentTimeMillis 及 nanoTime 原理详解 JVM 源码分析之 System.currentTimeMillis 及 ...

掘金官方
2017/12/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

define()与const - define() vs. const

问题: In PHP, when do you use 在PHP中,何时使用 define('FOO', 1); and when do you use 以及何时使用 const FOO = 1; ? ? What are the main differences between those two? 两者之......

法国红酒甜
18分钟前
26
0
将Node.js升级到最新版本 - Upgrading Node.js to latest version

问题: So, I have Node.js installed and now when I tried to install Mongoosejs I got an error telling me that I don't have the needed version of Node.js (I have v0.4.11 and v0.4......

javail
今天
17
0
等到所有jQuery Ajax请求都完成了吗? - Wait until all jQuery Ajax requests are done?

问题: How do I make a function wait until all jQuery Ajax requests are done inside another function? 我如何让一个函数等到所有jQuery Ajax请求都在另一个函数中完成之后? In short...

富含淀粉
今天
17
0
OSChina 周日乱弹 —— 那么长的绳子,你这是放风筝呢

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @ 巴拉迪维:黑豹乐队的单曲《无地自容》 耳畔突然响起旋律,是那首老歌。中国摇滚有了《一无所有》不再一无所有;中国摇滚有了《无地自容》不...

小小编辑
今天
69
1
《吐血整理》-顶级程序员书单集

你知道的越多,你不知道的越多 给岁月以文明,而不是给文明以岁月 前言 王潇:格局决定了一个人的梦想,梦想反过来决定行为。 那格局是什么呢? 格局是你能够看见的深度、广度和密度。 王潇认...

敖丙
2019/12/11
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部