JavaSe:集合-Map

Map接口

• 并列于Collection

🌟==经典问题==：

1.HashMap的底层实现原理

以jdk7为例说明:

HashMap map = new HashMap( ):在实例化以后，底层创建了长度是16的一维数组Entry[ ] table。…可能已经执行过多次put. . .

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

对于情况2 3 ，新添加的键值对以了链表的方式存储

JDK8中的区别：

1.一开始new的时候没要创建一个长度为16的数组

2.JDK8 底层的数组是Node[] ，而非Entry[];

3.首次调用put方法时，底层创建长度为16的数组（与ArrayList JDK8的新特性相同）。

底层是数组 +链表 (JDK7之前)

底层是数组 +链表+红黑树 (JDK8)

==当数组的某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度 >64时，此时的索引位置上的所有数据改为使用红黑树存储==

@Test
    void t1() {
        HashMap map = new HashMap();
        map.put(new Person(14, "Tom"), "Study");
        map.put("Tom", "Study");
        System.out.println(map);
        map.put("Tom", "LOL");
        map.put(new Person(14, "Tom"), "LOL");
        System.out.println(map);
    }
/*  输出结果
{Tom=Study, Person{age=14, name='Tom'}=Study}
{Tom=LOL, Person{age=14, name='Tom'}=LOL}
*/

2.HashMap和Hashtable的异同

3.CurrentHashMap与Hashtable的异同

Map中的key：无序的，不可重复的，使用Set存储所有的key

要求key所在的类重写equals()方法和hashCode()方法(以HashMap为例)

Map中的value：无序的，可重复的，使用Collection存储所有的value

​ 一个键值对：key-value构成了一个entry对象

​ Map中的entry：无序的，不可重复的，使用Set存储所有的entry

概述

• Map与Collection并列存在。用于保存具有映射关系的数据:key-value

• Map 中的 key 和 value 都可以是任何引用类型的数据

• Map 中的 key 用Set来存放，不允许重复，即同一个 Map 对象所对应的类，须重写hashCode()和equals()方法

常用String类作为Map的“键”

• key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value

• Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和Properties。其中，HashMap是 Map 接口使用频率最高的实现类

💡Map接口：常用方法

1.添加、删除、修改操作：

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中的所有数据

2.元素查询的操作：

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是否相等

3.元视图操作的方法： 用于遍历操作

==Set keySet()：返回所有key构成的Set集合==

==Collection values()：返回所有value构成的Collection集合==

==Set entrySet()：返回所有key-value对构成的Set集合==

@Test
void t2() {
    Map map = new HashMap();
    map.put("DD", 123);
    map.put("HH", 534);
    map.put("AA", 867);
    Set keySet = map.keySet();
    Iterator iterator1 = keySet.iterator();
    while (iterator1.hasNext()) {
        Object key = iterator1.next();
        System.out.println(key + "-->" + map.get(key));
    }
    Set entrySet = map.entrySet();             
    //entrySet集合中的元素都是entry
    Iterator iterator2 = entrySet.iterator();
    while (iterator2.hasNext()) {
        Object o1 = iterator2.next();
        Map.Entry entry = (Map.Entry) o1;
        System.out.println(entry.getKey() + " = " + entry.getValue());
    }
    Collection coll = map.values();
    for (Object o1 : coll) {
        System.out.println(o1);
    }
}

1.HashMap

• HashMap是 Map 接口使用频率最高的实现类。
• HashMap线程不安全，效率高

底层是数组 +链表 (JDK7之前)

底层是数组 +链表+红黑树 (JDK8)

1.允许使用null键和null值，与HashSet一样，不保证映射的顺序。

2.所有的key构成的集合是Set:无序的、不可重复的。所以，key所在的类要重写：equals()和hashCode()

3.所有的value构成的集合是Collection:无序的、可以重复的。所以，value所在的类要重写：equals()

4.一个key-value构成一个entry

5.所有的entry构成的集合是Set:无序的、不可重复的

6.HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。

7.HashMap 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true

HashMap源码中的==重要常量==

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16

MAXIMUM_CAPACITY ： HashMap的最大支持容量，2^30

DEFAULT_LOAD_FACTOR：HashMap的默认加载因子

TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树

UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，转化为链表

MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。
（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。）

table：存储元素的数组，总是2的n次幂

entrySet：存储具体元素的集

size：HashMap中存储的键值对的数量

modCount：HashMap扩容和结构改变的次数。

threshold：扩容的临界值 =容量*填充因子

loadFactor：填充因子

HashMap的扩容

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？

当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)loadFactor 时 ， 就 会 进 行 数 组 扩 容 ， loadFactor 的默认 值(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过160.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

• HashMap的内部存储结构其实是数组+链表+树的结合。当实例化一个HashMap时，会初始化initialCapacity和loadFactor，在put第一对映射关系时，系统会创建一个长度为initialCapacity的Node数组，这个长度在哈希表中被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。

• 每个bucket中存储一个元素，即一个Node对象，但每一个Node对象可以带一个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Node链。也可能是一个一个TreeNode对象，每一个TreeNode对象可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。

那么HashMap什么时候进行扩容和树形化呢？

• 当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)loadFactor 时 ， 就会进行数组扩容 ， loadFactor 的默认 值 (DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过160.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
• 当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。

关于映射关系的key是否可以修改？answer：不要==修改==

• 映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。

**总结：**JDK1.8相较于之前的变化：

1.HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组

2.当首次调用map.put()时，再创建长度为16的数组

3.数组为Node类型，在jdk7中称为Entry类型

4.形成链表结构时，新添加的key-value对在链表的尾部（七上八下）

5.当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置上的所有key-value对使用红黑树进行存储。

面试题：负载因子值的大小，对HashMap有什么影响

1.负载因子的大小决定了HashMap的数据密度。负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时的比较次数增多，性能会下降。

2.负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。

3.按照其他语言的参考及研究经验，会考虑将==负载因子设置为0.7~0.75==，此时平均检索长度接近于常数。

2.LinkedHashMap

• 保证在遍历map元素时，可以按照添加的顺序实现遍历

  ⭐原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个或后一个元素

💙对于==频繁的遍历操作==，此类执行效率高于 HashMap

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);
	}
}

3.TreeMap

底层使用的是 红黑树

• 保证按照添加的key-value进行排序(按照key排序)，不能存储null的key和value

• 需要保证key的类型相同 ，

• 不能按照value排序

• TreeMap 的 Key 的排序：

  1.自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException

  2.定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现

  Comparable 接口

• TreeMap判断两个==key==相等的标准：两个key通过compareTo()方法或者compare()方法返回0。

package pers.dhx_.java0609;

import pers.dhx_.java0608.Person;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

/**
 * @author Dhx_
 * @className treeMapTest
 * @description TODO 按照key排序
 * @date 2022/6/9 16:09
 */
public class treeMapTest {
    public static void main(String[] args) {
        TreeMap map = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Person && o2 instanceof Person) {
                    return Integer.compare(((Person) o1).getAge(), ((Person) o2).getAge());
                } else throw new RuntimeException("类型错误");
            }
        });
        map.put(new Person(16, "Tom"), 98);
        map.put(new Person(18, "Sarah"), 95);
        map.put(new Person(16, "Amy"), 75);
        map.put(new Person(17, "Mike"), 68);
        map.put(new Person(19, "Dhx"), 100);
        Print(map);
    }
    static void Print(TreeMap map) {
        Set keySet = map.keySet();
        Iterator iterator = keySet.iterator();
        while (iterator.hasNext()) {
            Object o1 = iterator.next();
            System.out.println(o1 + "--->:" + map.get(o1));
        }
    }
}

4.Hashtable

• 古老的实现类，线程安全的，效率低，不能存储 null值的key以及value

1.Hashtable是个古老的 Map 实现类，JDK1.0就提供了。不同于HashMap，

Hashtable是线程安全的。

2.Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询

速度快，很多情况下可以互用。

3.与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value

4.与HashMap一样，Hashtable 也不能保证其中 Key-Value 对的顺序

5.Hashtable判断两个key相等、两个value相等的标准，与HashMap一致。

5.Properties

• 常用来处理配置文件，是Hahtable的子类 ，key以及value都是==String==类型

1.Properties 类是 Hashtable 的子类，该对象用于处理属性文件

2.由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型

3.存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法

package pers.dhx_.java0609;

import java.io.FileInputStream;
import java.util.Properties;

/**
 * @author Dhx_
 * @className PropertiesTest
 * @description TODO  Properties 主要用来处理配置文件，key 以及value 都是String类型
 * @date 2022/6/9 16:26
 */
public class PropertiesTest {
    public static void main(String[] args) throws Exception {
        Properties pros = new Properties();
        FileInputStream fis = new FileInputStream("0609.properties");

        pros.load(fis);//加载流对应文件
        String name = pros.getProperty("name");
        String pwd = pros.getProperty("password");
        System.out.println("name=" + name + " password=" + pwd);
    }
}

0609.properties

name=1744765994
password=abc123

Collections工具类

Collections 是一个接口，Collections是操作Collection的工具类

1.Collections 是一个操作 Set、List 和 Map 等集合的工具类

2.Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，

还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

排序操作：（均为==static==方法）

reverse(List)：反转 List 中元素的顺序

==shuffle(List)==：对 List 集合元素进行随机排序

==sort(List)==：根据元素的自然顺序对指定 List 集合元素按升序排序

==sort(List，Comparator)==：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序

swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

Collections常用方法

查找、替换

• Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素

• Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素

Object min(Collection) 用法与max()==一致==

Object min(Collection，Comparator)

• int frequency(Collection，Object)：返回指定集合中指定元素的出现次数

• void copy(List dest,List src)：将src中的内容复制到dest中 ，会清除原本的元素

  @Test
  void t2() {
      List list = new ArrayList();
      list.add(123);
      list.add(5346);
      list.add(7567);
      list.add(157543623);
      list.add(-4353);
      list.add(5);
      list.add(2);
      List l1 = new ArrayList();
      for(int i-0;i<6;i++)
      	l1.add(1);
      System.out.println(l1);
      //size() 返回的是元素的个数
      Collections.copy(l1, list);
      System.out.println(l1);
      /*keypoint
           [1, 1, 1, 1, 1, 1, 1]
          [123, 5346, 7567, 157543623, -4353, 5, 2]*/
  }

  标准写法：

  @Test
  void t3() {
      List list = new ArrayList();
      list.add(123);
      list.add(5346);
      list.add(7567);
      list.add(157543623);
      list.add(-4353);
      list.add(5);
      list.add(2);
      List l1 = Arrays.asList(new Object[list.size()]);
      Collections.copy(l1, list);
      System.out.println(l1);
  //[123, 5346, 7567, 157543623, -4353, 5, 2]
  }

• boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换List 对象的所有旧值

@Test
    void t1() {
        Comparator cmp = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Integer && o2 instanceof Integer) {
                    if (((Integer) o1).intValue() > ((Integer) o2).intValue()) return 1;
                    else return -1;
                } else throw new RuntimeException("类型异常");
            }
        };
        List list = new ArrayList();
        list.add(123);
        list.add(5346);
        list.add(7567);
        list.add(157543623);
        list.add(-4353);
        list.add(5);
        list.add(2);
        list.add(2);
        System.out.println(list);
        Collections.reverse(list); //反转
        Collections.shuffle(list); //每次都随机排序
        Collections.sort(list, cmp);
        list.sort(cmp);
        System.out.println(Collections.frequency(list, 2));
        System.out.println(list);
    }

Collections常用方法：同步控制

Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使==将指定集==

==合包装成线程同步的集合==，从而可以解决多线程并发访问集合时的线程安全

问题

List l1=Collections.synchronizedList(list);