欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashMap的实现原理及源码分析

程序员文章站 2022-05-11 22:21:09
...

一、HashMap概述

    HashMap通过键值的方式存储数据,为非线程安全的类,键和值可以为null,键不能重复,继承了AbstractMap并实现了Map接口

 

二、源码分析(基于JDK1.7)

 

1. HashMap中的主要成员变量

 

DEFAULT_INITIAL_CAPACITY:静态整型常量,默认初始化的容量,其值为16(必须是2的指数倍)

MAXIMUM_CAPACITY:静态整型常量,表示最大容量为2的30次方。如果通过构造器传入的容量大于最大容量,会被此最大容量值替换

DEFAULT_LOAD_FACTOR:静态浮点型常量,表示默认的加载因子,其值为0.75f;如果在构造器中没有指定加载因子,则使用此默认值

table:存储数据的Entry数组(Entry<K,V>[]),会做必要的调整,长度是2的指数倍

size:HashMap的大小,是保存在HashMap里key-value键值对的数量

threshold:HashMap的阈值,用于判断是否要调整HashMap的容量,其值等于容量*加载因子

loadFactor:加载因子实际大小,常量

modCount:HashMap被改变的次数

 

2. HashMap中的读取(get方法)

2.1 如果传入的键(key)为null,则从Entry数组table中索引下标为0的链表中查找key为null的值并返回,未找到则返回null

2.2 如果传入的键(key)不为null,则获取key对应的哈希值hash

2.3 通过哈希值hash获取对应在table数组中的索引下标(h & (length-1))

2.4 循环遍历table数组中该索引下标对应的Entry链表

2.5 如果传入的键(key)的哈希值(hash)等于该Entry的哈希值(hash),

     并且传入的键(key)等于(==)或等同于(equals)该Entry的key,

     则此Entry便是要查找的Entry对象,遍历完该Entry链表如果还未查找到,则返回null

2.6 返回查找到的Entry对象的值(value),未查找到则返回null

 

3. HashMap中存入键值(put方法)

3.1 如果key为null,则从Entry数组table中索引下标为0的链表中,

     查找是否已经存在了key为null的Entry,如果存在则替换这个Entry的值为新的值,并返回旧值;

     如果不存在key为null的Entry,则先把修改数(modCount)自增1,然后添加一个新的Entry,

     key为null,value为传入的值,并把该Entry放入table[0]位置上链表的头部,并返回null。

3.2 如果key不为null,先获取key的哈希值hash,并通过hash确定Entry数组table的索引下标i

     对table[i]位置的链表进行循环遍历,查找是否已经存在key值相同的Entry(传入key的哈希值

     与该Entry的哈希值相等,并且传入key等于或等同于Entry的key),如果存在则把它的值替换

     成新值,并返回旧值;

     如果不存在,则先把修改数(modCount)自增1,然后在table[i]对应的链表的头部添加一个Entry

     并返回null。

 

三、要点分析

 

1. 链表的原理和实现

    HashMap中的链表由Entry类组成,Entry包含三个元素:key,value和next(指向下一个Entry的)

    在HashMap中的链表加入新的Entry,会放在链表头部位置,新的Entry的next元素指向原来在链表头部的Entry

 

2. modCount的作用

    modCount为修改次数,在进行put、remove、clear等操作时会修改数modCount加1

    HashMap中不是线程安全的,如果在使用迭代器的过程中有其他线程修改了HashMap,那么将抛出ConcurrentModificationException,即Fail-Fast策略

    在迭代过程中,是通过modCount跟expectedModCount是否相等来判定其他线程有没有修改的,如果不相等,说明其他线程修改了

 

四、总结

 

1. HashMap是基于哈希表的Map接口的非同步实现,允许key和vaue为null

2. HashMap内部是有数组和链表实现的,通过key的哈希值找到在数组中位置,

    并遍历该位置的链表,找到key值相同的Entry。

3. 当我们往hashmap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置(即下标),

    然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了,

    那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。

    从hashmap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元素,

    然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到,

    如果每个位置上的链表只有一个元素,那么hashmap的get效率将是最高的