【Map】基本方法及其源码理解

1、Map接口的体系结构

Map&＃xff1a;存储Key—value对的数据

​ HashMap&＃xff1a;作为Map的主要实现类&＃xff1b;线程不安全&＃xff1b;效率高&＃xff1b;键和值都可以是null

​ LinkedHashMap&＃xff1a;遍历时&＃xff0c;可以按照添加的顺序进行遍历&＃xff1b;对于频繁的遍历操作&＃xff0c;效率高

​ TreeMap&＃xff1a;可以进行排序&＃xff08;按照key排序&＃xff09;

​ Hashtable&＃xff1a;作为Map古老的实现类&＃xff08;几乎不用&＃xff09;&＃xff1b;线程安全&＃xff1b;效率低&＃xff1b;键和值都不能是null&＃xff0c;如果存&＃xff0c;报空指针异常

​ Properties&＃xff1a;常用来处理配置文件&＃xff1b;键和值都是String类型

2、对key-value的理解

key

​ 无序的&＃xff0c;不可重复

​ 为保证无序&＃xff0c;key所在类要重写equals方法和hashCode方法&＃xff08;针对于HashMap&＃xff09;

value

​ 无序的&＃xff0c;可重复

​ 所在类要重写equals方法&＃xff08;针对于HashMap&＃xff09;

键值对

​ 一个键值对构成一个Node对象&＃xff08;用set存储&＃xff09;

​ put放入的键值对其实是存放到Node对象中&＃xff0c;Node有两个属性key和value

​ Entry是无序的&＃xff0c;不可重复的

3、HashMap的底层实现原理

JDK7&＃xff1a;数组&＃43;链表

HashMap map &＃61; new HashMap(); //实例化以后&＃xff0c;底层创建了长度为16的数组Entry[] tablemap.put(key,value); 首先调用key所在类的hashCode()&＃xff0c;计算key的哈希值&＃xff0c;然后将hash值转换成数组的index&＃xff0c;得到key在数组中的存放位置如果此位置数据为空&＃xff0c;则键值对添加成功如果此位置数据不为空&＃xff08;意味着此位置存放一个或多个数据&＃xff08;链表存储&＃xff09;&＃xff09;&＃xff0c;就比较当前key和这些数据的哈希值&＃xff0c;如果key的哈希值与已经存在的数据哈希值都不相同&＃xff0c;则键值对添加成功如果key的哈希值与已经存在的某个key的哈希值相同&＃xff0c;则调用key所在类的equal方法返回true&＃xff0c;说明key相同&＃xff0c;就用value去替换那个value值返回false&＃xff0c;则键值对添加成功


JDK8&＃xff1a;数组&＃43;链表&＃43;红黑树

HashMap map &＃61; new HashMap(); //在new时&＃xff0c;底层并没有创建长度为16的数组&＃xff1b;
map.put(key,value) //第一次调用put方法时&＃xff0c;底层创建长度为16的数组(懒加载)树化&＃xff1a;添加元素时&＃xff0c;当链表长度大于8并且数组长度大于64时&＃xff0c;将此链表转化为红黑树当前链表长度大于等于7时&＃xff0c;尝试进行树化操作if (binCount >&＃61; TREEIFY_THRESHOLD - 1) // -1 for 1st尝试进行树化操作treeifyBin(tab, hash);显然HashMap认为&＃xff0c;虽然链表长度超过了8&＃xff0c;但是table长度太短&＃xff0c;只需要扩容然后重新散列一下就可以。if (tab &＃61;&＃61; null || (n &＃61; tab.length) < MIN_TREEIFY_CAPACITY)resize();


4、HashMap中的重要常量

HashMap的默认容量&＃xff1a;16
static final int DEFAULT_INITIAL_CAPACITY &＃61; 1 << 4; // aka 16数组可以被树化的最小容量&＃xff1a;64
static final int MIN_TREEIFY_CAPACITY &＃61; 64;HashMap的加载因子&＃xff1a;0.75
static final float DEFAULT_LOAD_FACTOR &＃61; 0.75f;使用红黑树而不使用散列表的临界值
static final int TREEIFY_THRESHOLD &＃61; 8;使用散列表而不使用红黑树的临界值
static final int UNTREEIFY_THRESHOLD &＃61; 6;扩容的临界值 &＃61; 容量 * 加载因子
int threshold;HashMap中存储键值对的个数
transient int size;


5、HashMap的扩容机制

默认的情况下,HashMap 的size一旦大于等于16*0.75&＃61;12的话,
同时每个Entry(或者叫桶)里面至少有一个元素的时候就会进行扩容。

什么时候触发扩容&＃xff0c;扩容之后的 table.length、阀值各是多少

• 当 size > threshold 的时候进行扩容
• 扩容之后的 table.length &＃61; 旧 table.length * 2,
• 扩容之后的 threshold &＃61; 旧 threshold * 2

6、加载因子

为什么加载因子的默认值是 0.75&＃xff0c;并且不推荐我们修改

• 如果loadFactor太小&＃xff0c;那么map中的table需要不断的扩容&＃xff0c;扩容是个耗时的过程
• 如果loadFactor太大&＃xff0c;那么map中table放满了也不不会扩容&＃xff0c;导致冲突越来越多&＃xff0c;解决冲突而起的链表越来越长&＃xff0c;效率越来越低
• 而 0.75 这是一个折中的值&＃xff0c;是一个比较理想的值

5、Map接口中常用方法

V put(K key,V value) 向map中添加数据V remove(Object key) 通过指定key移除键值对void clear() 清空map集合Object get(Object key) 通过key获取指定valueBoolean containsKey(Object key) 是否包含指定的keyBoolean containsValue(Object value) 是否包含指定的valueint size() 返回map键值对的个数Boolean isEmpty() 判断map是否为空Boolean equals(Object obj) 判断两个map是否相等


6、Map的遍历

//遍历所有key
Set keySet &＃61; map.keySet();
Iterator iterator &＃61; keySet.iterator();
while(iterator.hasNext()){System.out.println(iterator.next());
}//遍历所有value
Collection values &＃61; map.values();
Iterator iterator1 &＃61; values.iterator();
while(iterator1.hasNext()){System.out.println(iterator1.next());
}//遍历所有键值对
Set set &＃61; map.entrySet();
for (Object o : set){Map.Entry entry &＃61; (Map.Entry) o;System.out.println(entry.getKey());System.out.println(entry.getValue());
}