深入理解Java基础之MAP

标签：MAP Java HashMap Map 链表深入哈希 put 键值

一、MAP 简介

MAP 是 Java 中的一种数据结构，以键值对的形式存储数据，常用于快速查找和操作数据。

Map 集合类存储元素时，采用 “键” 和 “值” 的方式存储。Map 中常见的构造函数定义多样，如Map<String, String> map = new HashMap<String, String>();。Map 的初始化可以通过这种方式进行，其中泛型<k,v>可以是任意对象。

Map 提供了丰富的方法，如添加键值对的put方法、删除键值对的remove方法、获取值的get方法等。以HashMap为例，当要插入一个键值对时，首先通过键的hashCode()方法计算哈希码。然后，通过哈希函数将哈希码映射到数组的一个位置，得到桶的索引。如果桶为空，则直接插入键值对；如果桶不为空，可能存在哈希冲突。

HashMap的内部结构主要由数组和链表（或红黑树）组成。数组用于存储桶（buckets），每个桶存储着一个链表或红黑树，这些链表或红黑树用于解决哈希冲突，即多个键映射到相同桶的情况。在 Java 8 及之后的版本中，当链表长度达到一定阈值时，链表会转换为红黑树，以提高检索性能。

除了HashMap，还有TreeMap等实现类。TreeMap实现了排序（按照 key 递增），依靠comparable，定义的类需要实现comparable接口来实现排序（返回值为负数小于，整数大于，0 等于）。通过红黑二叉树来实现set接口底层实现的hashset和treeset。HashSet实际上是使用了HashMap<k,v>来代替，其中v用一个不变的量来代替。TreeSet则是使用了TreeMap<k,v>。

在使用Map时，需要注意一些事项。比如在创建HashMap时，可以指定初始容量和负载因子。合理选择这两个参数可以影响HashMap的性能。键对象需要正确实现hashCode()和equals()方法，以确保正确的哈希和比较。遍历HashMap的时候要注意，不要在迭代过程中修改HashMap的结构，否则可能抛出ConcurrentModificationException异常。

二、常见实现类

1. HashMap

底层数据结构是散列桶（数组、链表和红黑树）。

HashMap 在 JDK 1.8 之后底层数据结构是数组 + 链表 + 红黑树。链表是为了解决哈希冲突的，当数组中发生哈希冲突的时候，会使用拉链法将冲突的元素连成一个链表，一个链表中都是冲突的元素。当链表长度过长的时候，会将链表自动转换为红黑树，以提高检索性能。在 Java 8 中，当链表的长度大于 8 的时候，链表就会转换为红黑树。当红黑树的节点个数小于 6 的时候，就会将红黑树转换为链表。临界值是 8 的原因是经过实验证明，当临界值设为 8 的时候，可以更好的平衡时间和空间复杂度。在随机哈希的情况下，链表的长度服从泊松分布，各个长度的命中概率是依次递减的，当长度为 8 的时候，其概率仅有 0.00000006，是一个非常小的概率。也就是说常规情况下，发生冲突的长度不会超过 8，如果超过 8 了说明发生冲突的可能性会非常大，也就是说链表长度就会变长，这个时候就会转换为红黑树，以提升查找效率。

特点：数据无序，键和值均允许为 null，非同步。

HashMap 存储的数据是无序的，键和值都可以为 null。它不是线程安全的，在多线程环境下可能会出现数据不一致等问题。

主要方法解析：put ()、get () 等。

put () 方法用于向 HashMap 中插入键值对。首先通过键的 hashCode () 方法计算哈希码，然后通过哈希函数将哈希码映射到数组的一个位置，得到桶的索引。如果桶为空，则直接插入键值对；如果桶不为空，可能存在哈希冲突。当发生哈希冲突时，会将元素添加到链表中。如果链表长度超过 8，并且数组长度大于等于 64，链表会转换为红黑树。

get () 方法用于获取指定键对应的值。通过键的哈希码计算桶的索引，然后在对应的桶中查找键值对。如果是链表，需要遍历链表查找；如果是红黑树，可以利用红黑树的特性快速查找。

2. TreeMap

底层实现：红黑树。

TreeMap 的底层实现是红黑树算法。红黑树是一种自平衡的二叉查找树，每个节点都只能是红色或者黑色，根节点是黑色，每个叶节点（NIL 节点，空节点）是黑色的。如果一个结点是红的，则它两个子节点都是黑的。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

特点：数据有序，比 HashMap 多实现了 NavigableMap 接口，非同步。

TreeMap 中的元素是有序的，可以根据键的顺序进行遍历。它实现了 NavigableMap 接口，支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法。

主要方法解析：put ()、get ()、remove () 等。

put () 方法用于向 TreeMap 中插入键值对。插入操作分为标准的 BST 插入和修复红黑树的平衡性两个步骤。在标准插入之后，通过重新着色和旋转等操作，保持红黑树的五个性质不被破坏。

get () 方法用于获取指定键对应的值。利用红黑树的特性进行快速查找。

remove () 方法用于删除指定键值对。删除操作包括标准的 BST 删除和修复红黑树的平衡性。删除后可能会破坏红黑树的性质，需要通过重新着色和旋转等操作进行修复。

3. LinkedHashMap

底层链表 + 哈希表结构。

LinkedHashMap 的底层结构是基于 HashMap 实现的，但它在 HashMap 的基础上添加了双向链表来维护顺序。每个节点在哈希表中存储数据时，不仅存储了键值对，还存储了指向前一个节点和后一个节点的引用。

特点：有序（存取顺序一致），非同步。

LinkedHashMap 保持键值对的顺序，这个顺序可以是插入顺序（默认）或访问顺序（可选）。与 HashMap 不同，HashMap 无法保证任何顺序。

有序（存取顺序一致），非同步。

当向 LinkedHashMap 插入一个新的键值对时，底层的哈希表会先计算键的哈希值，并确定键值对存储在哈希表中的位置。同时，将新节点添加到链表的尾部。链表通过每个节点的 before 和 after 指针进行链接，维护插入顺序。删除元素时，不仅要从哈希表中移除相应节点，还要更新双向链表的结构。访问元素时，如果是访问顺序模式，会将该元素移动到链表的末尾。迭代元素时，按照链表中的顺序进行访问。LinkedHashMap 还提供了一个钩子方法 removeEldestEntry，允许用户自定义何时自动删除最老的元素，可用于实现 LRU 缓存。

三、常用方法

1. 增加

public V put(K key,V value)：向 Map 集合中添加一个元素（键值对）。

使用put方法可以将指定的键值对添加到 Map 集合中。例如：Map<String, Integer> map = new HashMap<>(); map.put("apple", 5);，这里将键为 "apple"，值为 5 的键值对添加到了 Map 中。

2. 删除

public V remove(Object key)：删除一个键值对（根据键来删除）。

remove方法可以根据指定的键来删除 Map 集合中的键值对。例如：Map<String, Integer> map = new HashMap<>(); map.put("apple", 5); map.remove("apple");，这里先添加了一个键值对，然后根据键 "apple" 将其从 Map 中删除。

3. 改

实际上就是 put方法，只要 put的时候键和 map 集合中原有的键重复，就可以达到改的目的。

当使用put方法且传入的键已经存在于 Map 集合中时，会将原来与该键对应的值替换为新传入的值，从而实现修改的目的。例如：Map<String, Integer> map = new HashMap<>(); map.put("apple", 5); map.put("apple", 8);，这里先将键为 "apple"，值为 5 的键值对添加到 Map 中，然后再次使用put方法将 "apple" 对应的值修改为 8。

4. 查

public V get(Object key)：根据键来查找键所对应的值。

get方法可以根据指定的键来获取 Map 集合中与之对应的值。例如：Map<String, Integer> map = new HashMap<>(); map.put("apple", 5); Integer value = map.get("apple");，这里先添加了一个键值对，然后通过键 "apple" 获取到对应的值 5。如果 Map 中不存在指定的键，则get方法会返回null。写作素材中也有多个关于get方法的用法示例，比如：
“Java 中的 Map 接口的get方法用于检索或获取由参数中提到的特定键映射的值。当映射不包含键的此类映射时，它将返回NULL。用法: thisMap.get(Object key_element)参数：该方法采用对象类型的一个参数key_element，表示应该获取其关联值的键。返回值：该方法返回与此 Map 集合中的key_element关联的值。”
“使用get函数，那么应该有先调用put函数对m表进行存储，不然肯定是返回null；由于m表的存储跟put函数有关，在实际工程应用中get返回值是受到put函数影响的。”

四、遍历方式

1. 以键找值的方法：获取所有的键的集合 map.keySet ()。

在 Java 中，对于 Map 集合可以通过获取所有的键的集合map.keySet()来实现以键找值的遍历方式。具体步骤如下：

使用Map集合中的方法keySet()，把Map集合所有的 key 取出来，存储到一个Set集合中。例如：

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
Set<String> keySet = map.keySet();

遍历Set集合，获取Map集合中的每一个 key。可以使用迭代器遍历或者增强 for 循环遍历。

- 使用迭代器遍历：

   Iterator<String> it = keySet.iterator();
   while (it.hasNext()) {
       String key = it.next();
       Integer value = map.get(key);
       System.out.println(key + "=" + value);
   }

使用增强 for 循环遍历：

   for (String key : keySet) {
       Integer value = map.get(key);
       System.out.println(key + "=" + value);
   }

2. 键值对的方式：public Set<Map.Entry<K,V>> entrySet ()。

通过entrySet()方法可以以键值对的方式遍历Map集合。这个方法返回一个包含Map.Entry<K,V>对象的Set集合，每个Map.Entry对象代表一个键值对。

获取所有键值对的集合：

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();

遍历这个集合获得每一个键值对对象也就是Map.Entry对象。可以使用增强 for 循环或者迭代器遍历。

使用增强 for 循环遍历：

   for (Map.Entry<String, Integer> entry : entrySet) {
       String key = entry.getKey();
       Integer value = entry.getValue();
       System.out.println(key + "," + value);
   }

使用迭代器遍历：

   Iterator<Map.Entry<String, Integer>> iterator = entrySet.iterator();
   while (iterator.hasNext()) {
       Map.Entry<String, Integer> entry = iterator.next();
       String key = entry.getKey();
       Integer value = entry.getValue();
       System.out.println(key + "," + value);
   }

五、不同实现类的比较

HashMap、TreeMap 和 LinkedHashMap 的相同点和不同点。

相同点：

三者在特定的情况下，都会使用红黑树。

底层的 hash 算法相同。

在迭代的过程中，如果 Map 的数据结构被改动，都会报 ConcurrentModificationException 的错误。

不同点：

底层数据结构：

HashMap底层数据结构是数组 + 链表 + 红黑树。在 JDK 1.8 之后，链表是为了解决哈希冲突的，当数组中发生哈希冲突的时候，会使用拉链法将冲突的元素连成一个链表，一个链表中都是冲突的元素。当链表长度过长的时候，会将链表自动转换为红黑树，以提高检索性能。

TreeMap的底层实现是红黑树算法。红黑树是一种自平衡的二叉查找树，每个节点都只能是红色或者黑色，根节点是黑色，每个叶节点（NIL 节点，空节点）是黑色的。如果一个结点是红的，则它两个子节点都是黑的。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

LinkedHashMap的底层结构是基于 HashMap 实现的，但它在 HashMap 的基础上添加了双向链表来维护顺序。每个节点在哈希表中存储数据时，不仅存储了键值对，还存储了指向前一个节点和后一个节点的引用。
特点：

HashMap存储的数据是无序的，键和值都可以为 null。它不是线程安全的，在多线程环境下可能会出现数据不一致等问题。

TreeMap中的元素是有序的，可以根据键的顺序进行遍历。它实现了 NavigableMap 接口，支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法。

LinkedHashMap保持键值对的顺序，这个顺序可以是插入顺序（默认）或访问顺序（可选）。与 HashMap 不同，HashMap 无法保证任何顺序。
主要方法：

三者都有put()、get()、remove()等方法，但具体实现略有不同。

HashMap的put()方法用于向 HashMap 中插入键值对。首先通过键的 hashCode () 方法计算哈希码，然后通过哈希函数将哈希码映射到数组的一个位置，得到桶的索引。如果桶为空，则直接插入键值对；如果桶不为空，可能存在哈希冲突。当发生哈希冲突时，会将元素添加到链表中。如果链表长度超过 8，并且数组长度大于等于 64，链表会转换为红黑树。

TreeMap的put()方法用于向 TreeMap 中插入键值对。插入操作分为标准的 BST 插入和修复红黑树的平衡性两个步骤。在标准插入之后，通过重新着色和旋转等操作，保持红黑树的五个性质不被破坏。

LinkedHashMap的put()方法在向 LinkedHashMap 插入一个新的键值对时，底层的哈希表会先计算键的哈希值，并确定键值对存储在哈希表中的位置。同时，将新节点添加到链表的尾部。链表通过每个节点的 before 和 after 指针进行链接，维护插入顺序。

HashMap的get()方法用于获取指定键对应的值。通过键的哈希码计算桶的索引，然后在对应的桶中查找键值对。如果是链表，需要遍历链表查找；如果是红黑树，可以利用红黑树的特性快速查找。

TreeMap的get()方法用于获取指定键对应的值。利用红黑树的特性进行快速查找。

LinkedHashMap的get()方法在访问元素时，如果是访问顺序模式，会将该元素移动到链表的末尾。迭代元素时，按照链表中的顺序进行访问。

HashMap的remove()方法用于删除指定键值对。删除操作包括标准的 BST 删除和修复红黑树的平衡性。删除后可能会破坏红黑树的性质，需要通过重新着色和旋转等操作进行修复。

TreeMap的remove()方法用于删除指定键值对。删除操作包括标准的 BST 删除和修复红黑树的平衡性。删除后可能会破坏红黑树的性质，需要通过重新着色和旋转等操作进行修复。

LinkedHashMap的remove()方法在删除元素时，不仅要从哈希表中移除相应节点，还要更新双向链表的结构。

标签：MAP,Java,HashMap,Map,链表,深入,哈希,put,键值
From： https://blog.csdn.net/qq_25699299/article/details/144101743