深入了解Map集合

Java基础

浏览数:236

2019-8-22

注意事项:

使用 entrySet 遍历 Map 类集合 KV,而不是 keySet 方式进行遍历。

说明:keySet 其实是遍历了 2 次,一次是转为 Iterator 对象,另一次是从 hashMap 中取出key 所对应的 value。而 entrySet 只是遍历了一次就把 key 和 value 都放到了 entry 中,效率更高。

正例:values()返回的是 V 值集合,是一个 list 集合对象; keySet()返回的是 K 值集合,是一个 Set 集合对象; entrySet()返回的是 K-V 值组合集合。

一、HashMap  (JDK1.7)

1、父类:AbStractMap

2、父接口:Map, Cloneable, Serializable

3、默认容量大小:DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

4、最大容量大小:MAXIMUM_CAPACITY = 1 << 30;

5、负载因子:DEFAULT_LOAD_FACTOR = 0.75f;(Hsah表中元素的填满的程度.)

    加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。

    加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏(很多空间还没用,就开始扩容了)

6、实际存储对象:Entry[] table = (Entry[]) EMPTY_TABLE;

HashMap源码

数据结构:底层主要是基于数组和链表来实现的,存储是通过计算散列码来决定存储顺序。如果计算得出的hash值相同,就用链表存储来解决hash冲突。如图:

HashMap内部结构图

put()方法流程解析:(参考http://www.cnblogs.com/ITtangtang/p/3948406.html )

HashMap源码

1、如果key为空,则将该键值对添加到table[0]中(如果key为null的对象存在,则覆盖掉,然后在添加addEntry(0,null, value,0))

2、如果key不为null, 则计算该key的哈希值,然后将其添加到哈希值对应的链表中。

3、搜索指定hash值在对应table中的索引(index=hash&(length-1),length是2的整数次幂,所以索引值相对于是hash和length取模;为什么length保证是2的整数次幂,原因:length为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了效率;其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。)

4、循环遍历Entry数组,若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!

5、若key不存在则添加至Entry(addEntry(hash, key, value, i), 先获取索引i对应的entry,然后创建新的entry封装key和value,并将next指向之前索引对应的entry,如果达到了临界值就要进行扩容,HashMap扩容是扩为原来的两倍。)

主要特点:允许key和value为null;线程不安全;

二、LinkedHashMap(JDK1.7)

1、父类:HashMap

2、父接口:Map

3、默认容量大小:跟HashMap一样

4、最大容量大小:跟HashMap一样

5、负载因子:跟HashMap一样

6、实际存储对象:Entry header; 内部结构跟HashMap中的不一样

与HashMap区别:

1. 数据结构不同:LinkedHashMap是双重链表结构;

2.LinkedHashMap 保留了插入的顺序

三、TreeMap

元素是有序的

作者:yuanfy