首页 > 其他 > 详细

HashMap源码分析笔记(一)

时间:2019-01-23 16:31:12      阅读:193      评论:0      收藏:0      [点我收藏+]

一、结构

HashMap的结构由数组和链表组成,可以说是一个链表类型的数组:

技术分享图片

快速定位方式:key值得hash变换作为数组索引快速找到对应数组块,之后通过hash值对比从链表中查找到匹配项。

hash函数:

技术分享图片hash()

key的hash值是实际是key的hashCode值的低16位与高16位异或结果。之所以这样是为了减少数组定位时发生哈希碰撞。

数组下标是这样确定的:

i =(n-1)& hash //n=tab.length(),hash = hash(key)

从数组下标确定算法可以看出,实际参与运算的基本都是hash的低位,这样发生哈希冲突的可能性就比较高,所以hash函数中才会用hashcode值高低位取异或;

 

 

二、默认参数

 1 /**
 2  * The default initial capacity - MUST be a power of two.
 3  */
 4 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 5 
 6 /**
 7  * The maximum capacity, used if a higher value is implicitly specified
 8  * by either of the constructors with arguments.
 9  * MUST be a power of two <= 1<<30.
10  */
11 static final int MAXIMUM_CAPACITY = 1 << 30;
12 
13 /**
14  * The load factor used when none specified in constructor.
15  */
16 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

规定HashMap容量总为2的幂次方,最小16,最大2的30次方;

DEFAULT_LOAD_FACTOR 默认的负载因子,参与通过无参构造的HashMap初始容量计算。

三、属性

1 transient Node<K,V>[] table;
2 transient Set<Map.Entry<K,V>> entrySet;
3 transient int size;
4 //容量阈值
5 int threshold;
6 //负载因子
7 final float loadFactor;

当通过无参构造函数初始化时,loadFactor = DEFAULT_LOAD_FACTOR。实际上通过无参构造HashMap时,初始容量为 = DEFAULT_INITIAL_CAPACITY * loadFactor(见方法rsize())。

四、构造函数

hashMap有4个构造函数;

一个无参构造,初始容量和负载因子都取默认值;

一个通过已有Map构造;

两个自定义容量构造;

jdk1.8的构造函数并没有初始化table,table初始化放在了第一次put中。

 

 1 public HashMap(int initialCapacity, float loadFactor) {
 2     if (initialCapacity < 0)
 3         throw new IllegalArgumentException("Illegal initial capacity: " +
 4                                            initialCapacity);
 5     if (initialCapacity > MAXIMUM_CAPACITY)
 6         initialCapacity = MAXIMUM_CAPACITY;
 7     if (loadFactor <= 0 || Float.isNaN(loadFactor))
 8         throw new IllegalArgumentException("Illegal load factor: " +
 9                                            loadFactor);
10     this.loadFactor = loadFactor;
11     this.threshold = tableSizeFor(initialCapacity);
12 }

 

除了无参构造,都应用到一个方法tableSizeFor();

技术分享图片tableSizeFor

此算法计算出大于等于入参的最小2的幂次方,由于规定map容量必须为2的幂次方,所以经由此方法得出自定义的最佳容量。

 

HashMap源码分析笔记(一)

原文:https://www.cnblogs.com/caster-xzn/p/10309314.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!