文档章节

HashMap深入学习

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

        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的值。。如果程序比较关系内存的开销。内存比较紧张,可以适当的增加负载因子;如果程序比较关心时间开销,内存比较宽裕,则可以适当地减少负载因子,通常情况下。程序员不需要改变负载因子的值

© 著作权归作者所有

共有 人打赏支持
树上的风筝
粉丝 1
博文 38
码字总数 20210
作品 0
朝阳
程序员
私信 提问
Java:HashMap和Hashset的实现

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

樂天
2015/06/28
0
2
mybatis学习旅程

了解了MYSQL的大致流程,也会用mybatis做为中间件与mysql交互, 1.但是从spring--》mybatis-->mysql的流程还是不理解, 2.对mybatis黑箱操作也不敢说精通, 3.以及spring和mybatis怎么用事务...

杭电任宇翔
2016/09/28
38
0
JAVA面试题「社招篇」

1. hashcode跟equals 2. hashmap的实现原理 3. 如何扩容,为什么要扩容 4. 1.6 1.7 1.8之间的区别 5. 1.8用了树解决冲突,既然是树就有排序,那是怎么排序的 6. 1.8为什么要换成树,什么是h...

JAVA丶学习
2017/12/25
0
0
Java-深入HashMap原理及内部存储结构

本文将通过如下简单的代码来分析HashMap的内部数据结构的变化过程。 1 数据结构说明 HashMap中本文需要用到的几个字段如下: 下面说明一下几个字段的含义 1)table Node的结构如下: 可以发现...

小刀爱编程
01/22
0
0
HashMap多线程下死循环的坑记录

PS:不得不说Java编程思想这本书是真心强大.. 学习内容: 1.HashMap<K,V>在多线程的情况下出现的死循环现象 当初学Java的时候只是知道HashMap<K,V>在并发的情况下使用的话,会出现线程安全问题...

java_龙
2018/01/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java框架学习日志-13(Mybatis基本概念和简单的例子)

在mybatis初次学习Mybatis的时候,遇到了很多问题,虽然阿里云的视频有教学,但是视频教学所使用的软件和我自己使用的软件不用,我自己用的数据库是oracle数据库,开发环境是idea。而且视频中...

白话
今天
4
0
Java基础:String、StringBuffer和StringBuilder的区别

1 String String:字符串常量,字符串长度不可变。Java中String是immutable(不可变)的。 String类的包含如下定义: /** The value is used for character storage. */private final cha...

watermelon11
今天
2
0
mogodb服务

部署MongoDB 官网: https://www.mongodb.com/download-center/community 创建mongo数据目录 mkdir /data/mongodb 二进制部署 wget -c https://fastdl.mongodb.org/linux/mongodb-linux-x8......

以谁为师
昨天
5
0
大神教你Debian GNU/Linux 9.7 “Stretch” Live和安装镜像开放下载

Debian项目团队于昨天发布了Debian GNU/Linux 9 "Stretch" 的第7个维护版本更新,重点修复了APT软件管理器中存在的安全漏洞。在敦促每位用户尽快升级系统的同时,Debian团队还发布了Debian ...

linux-tao
昨天
4
0
PHP 相关配置

1. php-fpm的pool 编辑php-fpm配置文件php-fpm.con vim /usr/local/php/etc/php-fpm.conf //在[global]部分增加以下内容 include = etc/php-fpm.d/*.conf # 相当与Nginx的虚拟主机文件 “vho......

Yue_Chen
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部