A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© li2443484536 初级黑马   /  2019-1-23 16:53  /  742 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

一、结构
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值高低位取异或;


二、默认参数[url=][/url]
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;[url=][/url]


规定HashMap容量总为2的幂次方,最小16,最大2的30次方;
DEFAULT_LOAD_FACTOR 默认的负载因子,参与通过无参构造的HashMap初始容量计算。
三、属性[url=][/url]
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;[url=][/url]

当通过无参构造函数初始化时,loadFactor = DEFAULT_LOAD_FACTOR。实际上通过无参构造HashMap时,初始容量为 = DEFAULT_INITIAL_CAPACITY * loadFactor(见方法rsize())。
四、构造函数
hashMap有4个构造函数;
一个无参构造,初始容量和负载因子都取默认值;
一个通过已有Map构造;
两个自定义容量构造;
jdk1.8的构造函数并没有初始化table,table初始化放在了第一次put中。

[url=][/url]
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 }[url=][/url]


除了无参构造,都应用到一个方法tableSizeFor();
tableSizeFor
此算法计算出大于等于入参的最小2的幂次方,由于规定map容量必须为2的幂次方,所以经由此方法得出自定义的最佳容量。

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马