大数据、Java EE 学习资料请关注 B 站:https://space.bilibili.com/204792350

Map 学习笔记(一)

image.png

一、Map的实现类的结构

  • Map:双列数据,存储key-value对的数据

  • HashMap:作为Map的主要实现类;线程不安全的,效率高;存储null的key和value

    • HashMap的底层
      • 数组+链表 (jdk7及之前)
      • 数组+链表+红黑树 (jdk 8)
  • LinkedHashMap:保证在遍历map元素时,可以按照添加的顺序实现遍历。原因:在原有的HashMap底层结构基础上,添加了一对指针,指向前一个和后一个元素。对于频繁的遍历操作,此类执行效率高于HashMap。

  • TreeMap:保证按照添加的key-value对进行排序,实现排序遍历。此时考虑key的自然排序或定制排序
    底层使用红黑树

  • Hashtable:作为古老的实现类;线程安全的,效率低;不能存储null的key和value

    • Properties:常用来处理配置文件。key和value都是String类型

二、Map结构的理解

Map中的key:无序的、不可重复的,使用Set存储所有的key ---> key所在的类要重写equals()和hashCode() (以HashMap为例)
Map中的value:无序的、可重复的,使用Collection存储所有的value --->value所在的类要重写equals()
一个键值对:key-value构成了一个Entry对象。
Map中的entry:无序的、不可重复的,使用Set存储所有的entry

三、HashMap的底层实现原理?

以jdk7为例说明

HashMap map = new HashMap();

在实例化以后,底层创建了长度是16的一维数组Entry[] table。

map.put(key1,value1);
  1. 首先,调用key1所在类的hashCode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Entry数组中的存放位置。
  2. 如果此位置上的数据为空,此时的key1-value1添加成功。 ----情况1
  3. 如果此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据
    的哈希值:
    1. 如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。----情况2
    2. 如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较:调用key1所在类的equals(key2)方法,比较:
      1. 如果equals()返回false:此时key1-value1添加成功。----情况3
      2. 如果equals()返回true:使用value1替换value2

补充:关于情况2和情况3:此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时,扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。

jdk8 相较于jdk7在底层实现方面的不同
首先实例化 HashMap 对象,此时底层没有创建一个长度为 16 的数组,这一点与 JDK 7 不同。

HashMap map = new HashMap();

这一行代码,在 HashMap 对象只处理一个事情,那就是初始化加载因子。这个属性决定后续扩容问题,HashMap 空参构造器的代码:

/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

什么时候会初始化存储容量呢,调用 put 的时候就会初始化,查看源代码可以发现:

/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
*         (A <tt>null</tt> return can also indicate that the map
*         previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

Map 接口的实现类存储数据是无序的,并且 key 是不可重复的。所谓无序不是指随机存储在数组上,而是经过将 key 计算出 hash 值,然后与数组的容量 & 运算,最后会计算出该存储在数组的位置。

紧接着就需要判断各种条件了,比如说容量是否足够,是否为 null 等等情况。

查看 putVal 代码可以具体了解接下来如何处理,这个方法代码有些多,一段段从中摘取出来阅读理解:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // code......
}

首先,声明了几个局部变量,其中 Node<K,V>[] 这个类型是存储链表结构的。在 JDK 8 当中,HashMap 是有三种数据结构来存储数据,其中最根本就是数组,在数组存储有双向链表,也有红黑树。

在数组存储具体是什么数据类型,取决于后续扩容数组的长度,当超过 64,并且每个数组上的链表节点达到 8 以上,就会转换成红黑树。

第一个 if 判断语句中,检查了当前 table 是否为空,默认值为 null,所以这里会进行首次的容量初始化。

查看 resize 方法,初始化的时候,将创建一个 16 容量的数组,并且计算这个容量的阈值。

// ...
newCap = DEFAULT_INITIAL_CAPACITY; // 1 << 4 = 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16
// ...

后面的 if 判断当前计算出来的位置在数组是否有元素,若是没有的话就直接创建一个链表元素写入。

jdk8中底层结构:数组+链表+红黑树。

  1. 形成链表时,七上八下
    • jdk7:新的元素指向旧的元素
    • jdk8:旧的元素指向新的元素
  2. 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,此时此索引位置上的所数据改为使用红黑树存储。

HashMap 类变量
DEFAULT_INITIAL_CAPACITY : HashMap的默认容量,16
DEFAULT_LOAD_FACTOR:HashMap的默认加载因子:0.75
threshold:扩容的临界值,=容量*填充因子:16 0.75 => 12
TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树:8
MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量:64

四、LinkedHashMap的底层实现原理(了解)

源码中:

static class Entry<K,V> extends HashMap.Node<K,V> {
	Entry<K,V> before, after;//能够记录添加的元素的先后顺序
	Entry(int hash, K key, V value, Node<K,V> next) {
	 	super(hash, key, value, next);
	}
}

五、Map中定义的方法

添加、删除、修改操作

Object put(Object key,Object value):将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key):移除指定key的key-value对,并返回value
void clear():清空当前map中的所有数据

元素查询的操作

Object get(Object key):获取指定key对应的value
boolean containsKey(Object key):是否包含指定的key
boolean containsValue(Object value):是否包含指定的value
int size():返回map中key-value对的个数
boolean isEmpty():判断当前map是否为空
boolean equals(Object obj):判断当前map和参数对象obj是否相等

元视图操作的方法

Set keySet():返回所有key构成的Set集合
Collection values():返回所有value构成的Collection集合
Set entrySet():返回所有key-value对构成的Set集合

总结:常用方法

添加:put(Object key,Object value)
删除:remove(Object key)
修改:put(Object key,Object value)
查询:get(Object key)
长度:size()
遍历:keySet() / values() / entrySet()

面试题:

  1. HashMap的底层实现原理?
  2. HashMap 和 Hashtable的异同?
  3. CurrentHashMap 与 Hashtable的异同?
# Java   笔记  

评论

公众号:mumuser

企鹅群:932154986

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×