四集合 ——第八节 Map集合，HashMap详解

2022-06-03 本文已影响0人杜艳_66c4

1、Map集合概述

和Collection集合是两套体系，Collection集合是单列集合
java.util.Map<K,V> 集合双列集合，两个泛型

Map集合的特点：
1、Map集合是一个双列集合，一个元素包含两个值，key ，value
2、Map集合中的元素，key和value的数据类型可以相同，也可以不同
3、Map集合中的元素，key不允许重复，value可以重复
4、Map集合中的元素，key和value一一对应

2、Map常用实现类， HashMap 和LinkedHashMap

HashMap

java.util.HashMap<K,V> implements Map<K,V>
特点：
1、HashMap 底层是哈希表，查询速度快，
JDK 1.8之前，由数组+单向链表组成
JDK 1.8之后，由数组+单向链表组成/红黑树（链表的长度超过8 变成红黑树，也是为了提高查询的速度）
2、hashmap集合是一个无序的集合，存储元素和取出元素的顺序可能不一样，

LinkedHashMap

java.util.LinkedHashMap<K,V> extends HashMap<K,V>集合
LinkedHashMap的特点：
1、LinkedHashMap底层是哈希表+链表，保证迭代的顺序
2、LinkedHashMap集合是有序的。因为有链表。存储元素和取出元素的顺序一致

3、Map接口中常用方法

V put(k,v)
V get(key)
V remove(key)
boolean containsKey(key)
遍历map集合
Set<E> keySet
entrySet

package map;

import java.util.HashMap;
import java.util.Map;

/**
 * created by apple on 2020/6/20
 * java.util.Map<K,V> 集合 双列集合
 * Map集合的特点：
 * 1、Map集合是一个双列集合，一个元素包含两个值，key ，value
 * 2、Map集合中的元素，key和value的数据类型可以相同，也可以不同
 * 3、Map集合中的元素，key不允许重复，value可以重复
 * 4、Map集合中的元素，key和value一一对应
 *
 * java.util.HashMap<K,V> implements Map<K,V>
 *     特点：
 *     1、HashMap 底层是哈希表，查询速度快，
 *     JDK 1.8之前，由数组+单向链表组成
 *     JDK 1.8之后，由数组+单向链表组成/红黑树（链表的长度超过8 变成红黑树，也是为了提高查询的速度）
 *     2、无序的集合，存储元素和取出元素的顺序可能不一样，
 * java.util.LinkedHashMap<K,V>  extends HashMap<K,V>集合
 *      LinkedHashMap的特点：
 *      1、LinkedHashMap底层是哈希表+链表，保证迭代的顺序
 *      2、LinkedHashMap集合是有序的。因为有链表。存储元素和取出元素的顺序一致
 */
public class Demo1Map {
    public static void main(String[] args) {
      //  show01();
       //show02();
       // show03();
        show04();
    }

    /*
    boolean contains(Object key) 判断集合中是否包含指定的key，
    包含返回true。不包含返回false
     */
    private static void show04() {
        //创建Mao集合对象
        Map<String,Integer> map = new HashMap<>();
        map.put("赵丽因",168);
        map.put("杨颖",165);
        map.put("林志玲",178);
        System.out.println(map);

        boolean d1 = map.containsKey("杨颖");
        System.out.println("d1:" + d1);  //d1:true

        boolean d2 = map.containsKey("杨");
        System.out.println("d2:" + d2);  //d2:false

    }

    /*
    public V get(Object key): 通过key获取value
    key存在，返回对应的值，
    key不存在，返回null
     */
    private static void show03() {
        //创建Mao集合对象
        Map<String,Integer> map = new HashMap<>();
        map.put("赵丽因",168);
        map.put("杨颖",165);
        map.put("林志玲",178);
        System.out.println(map);  //{林志玲=178, 杨颖=165, 赵丽因=168}

        Integer yy = map.get("杨颖");
        System.out.println("yy:" + yy);  //yy:165 

        Integer v2 = map.get("地理");
        System.out.println("v2:" + v2); //null
    }

    /*
    public V remove(Object key):把指定的键对应的键值对在Map集合中删除，返回被删除的元素的值
    返回值：V
    如果key存在，v返回被删除的值
    如果key不存在，v返回空
     */
    private static void show02() {
//创建MaP集合对象
        Map<String,Integer> map = new HashMap<>();
        map.put("赵丽因",168);
        map.put("杨颖",165);
        map.put("林志玲",178);
        System.out.println(map);  //{林志玲=178, 杨颖=165, 赵丽因=168}

        Integer v1 = map.remove("林志玲");
        System.out.println("v1:" + v1);    //178
        System.out.println(map);  //{杨颖=165, 赵丽因=168}

        Integer v2 = map.remove("林志");
        System.out.println("v2:" + v2);    //null
    }

    /*put 方法  把指定的键值对添加到Map集合中
    public V put(K key,V value)
    返回值：V: key不能重复，value可以重复
    存储键值对的时候，key不重复，返回值v是null，
    存储键值对的时候，key重复，会使用新的value替换Map中重复的value，返回被替换的value
     */
    private static void show01() {
//创建Map集合，多态
        Map<String,String> map = new HashMap<>();
        String v1 = map.put("李晨", "范冰冰");
        System.out.println("v1:" + v1);  //v1:null

        String v2 = map.put("李晨", "范冰冰2");
        System.out.println("v2:" + v2);  // v2:范冰冰 ，返回被替换的value

        System.out.println(map);  //{李晨=范冰冰2}  重写了toString方法

        map.put("冷风","龙小云");
        map.put("杨过","小龙女");
        map.put("王涛","小龙女");
        System.out.println(map);// {杨过=小龙女, 李晨=范冰冰2, 冷风=龙小云, 王涛=小龙女}
    }
}

4、Map集合遍历 —— 键找值方式

键找值

Map集合的第一种遍历方式：通过【键找值】方式
Map集合中的方法：
Set<K>keySet。把key取出来，放在Set集合中
步骤：
*1、使用Map集合中的方法keySet() 把Map集合所有的键取出来，存储到Set集合中
*2、遍历Set集合，获取Map集合的每一个key
*2、通过Map集合的get(Key)，通过key找到value

package map;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * created by apple on 2020/6/20
 * Map集合的第一种遍历方式：通过  【键找值】 的方式
 * Map集合中的方法：
 * Set<K>keySet。  把key取出来，放在Set集合中
 * 步骤：
 * 1、 使用Map集合中的方法keySet() 把Map集合所有的键取出来，存储到Set集合中
 * 2、遍历Set集合，获取Map集合的每一个key
 * 2、通过Map集合的get(Key)，通过key找到value
 */
public class Demo02KeySet {
    public static void main(String[] args) {
        //创建Mao集合对象
        Map<String,Integer> map = new HashMap<>();
        map.put("赵丽因",168);
        map.put("杨颖",165);
        map.put("林志玲",178);
        System.out.println(map);

        //1、使用Map集合中的方法keySet() 把Map集合所有的键取出来，存储到Set集合中
        Set<String> set = map.keySet();

        //遍历Set集合，获取Map集合的每一个key
        // 使用迭代器遍历Set集合
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            String key = it.next();
            //通过Map集合的get(Key)，找到value
            Integer value = map.get(key);
            System.out.println(key + "=" + value);
        }
        System.out.println("----------");
        //增强for循环
        for (String s : set) {
            Integer value2 = map.get(s);
            System.out.println(s + "=" + value2);

        }

    }
}
输出
{林志玲=178, 杨颖=165, 赵丽因=168}
林志玲=178
杨颖=165
赵丽因=168
----------
林志玲=178
杨颖=165
赵丽因=168

5、Entry键值对对象

对象的方法：getKey() getValue()

键值对对象

使用Entry也可以对Map 集合进行遍历

6、Map集合遍历 ——键值对方式

Map集合遍历的第二种方式：使用Entry对象遍历

Map集合中的方法：
Set<Map.Entry<K,V>> entrySet() ,返回Set
实现步骤：
1、使用Map集合中的方法entrySet ，把Map集合中，多个Entry对象取出来，存储到Set集合中
2、遍历Set集合，获取每一个Entry对象
3、使用Entry对象中的方法getKey(), getValue()获取键与值

package map;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * created by apple on 2020/6/20
 * Map集合遍历的第二种方式：使用Entry对象遍历
 * Map集合中的方法：
 * Set<Map.Entry<K,V>> entrySet()  ,返回Set
 * 实现步骤：
 * 1、 使用Map集合中的方法entrySet ，把Map集合中，多个Entry对象取出来，存储到Set集合中
 * 2、遍历Set集合，获取每一个Entry对象
 * 3、 使用Entry对象中的方法getKey(),  getValue()获取键与值
 */
public class Demo3EntrySet {
    public static void main(String[] args) {
        //创建Mao集合对象
        Map<String,Integer> map = new HashMap<>();
        map.put("赵丽因",168);
        map.put("杨颖",165);
        map.put("林志玲",178);
        System.out.println(map);

        Set<Map.Entry<String, Integer>> set = map.entrySet();
        //遍历Set集合
        //使用迭代器遍历
        Iterator<Map.Entry<String, Integer>> set1 = set.iterator();
        while (set1.hasNext()){
            Map.Entry<String, Integer> entry= set1.next();
            //使用Entry对象中的方法getKey(),  getValue()获取键与值
            System.out.println(entry.getKey() + "= " + entry.getValue());  //
            //System.out.println(entry.getValue());
        }
        System.out.println("=========");
        //s使用增强for循环
        for (Map.Entry<String, Integer> entry : set) {
            System.out.println(entry.getKey() + "= " + entry.getValue()); //
        }
    }
}

{林志玲=178, 杨颖=165, 赵丽因=168}
林志玲= 178
杨颖= 165
赵丽因= 168
=========
林志玲= 178
杨颖= 165
赵丽因= 168

7、HashMap存储自定义类型键值

package map;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * created by apple on 2020/6/21
 * HashMap存储自定义类型键值
 * Map集合保证key是惟一的
 * 作为key的元素，必须重写hashCode方法和equals方法，以保证key唯一
 */
public class Demo1HashMapSavePerson {
    public static void main(String[] args) {
        show01();
        System.out.println("=======");
        show03();
    }
/*
key :Person 类型
    Person 类必须重写hashCode方法和equals方法，可以保证key唯一
    value ： String类型
    value 可以重复（同名，同年龄）
 */
    private static void show03() {
        //创建HashMap集合
        HashMap<Person, String> map = new HashMap<>();
        //往集合中添加元素，  key有重复，会用新的value替换旧的value
        map.put(new Person("ZHANG", 18), "美国");
        map.put(new Person("lisi", 12), "中国");
        map.put(new Person("王五", 19), "韩国");
        map.put(new Person("ZHANG", 18), "俄罗斯");

        //使用EntrySet 增强for 遍历Map集合
        Set<Map.Entry<Person, String>> set1 = map.entrySet();
        for (Map.Entry<Person, String> entry : set1) {
            Person key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key + " = " + value);
          //没有重写hashCode 和equals方法
            // Person{name='lisi', age=12} = 中国
            //Person{name='ZHANG', age=18} = 美国
            //Person{name='ZHANG', age=18} = 俄罗斯
            //Person{name='王五', age=19} = 韩国

            //重写了hashCode和equals方法
            //Person{name='王五', age=19} = 韩国
            //Person{name='lisi', age=12} = 中国
            //Person{name='ZHANG', age=18} = 俄罗斯
        }
    }
    /*
    key :String 类型
    String 类重写hashCode方法和equals方法，可以保证key唯一
    value ： Person类型
    value 可以重复（同名，同年龄视为同一个人）
     */
    private static void show01() {
        //创建HashMap集合
        HashMap<String,Person>  map = new HashMap<>();
       //往集合中添加元素，  key有重复，会用新的value替换旧的value
        map.put("北京",new Person("ZHANG",18));
        map.put("上海",new Person("lisi",12));
        map.put("广州",new Person("王五",19));
        map.put("北京",new Person("lzi",10));

        //使用ketSet 增强for 遍历Map集合
        Set<String> set = map.keySet();
        for (String key : set) {
            Person value = map.get(key);
            System.out.println(key + "--" + value);
//上海--Person{name='lisi', age=12}
//广州--Person{name='王五', age=19}
//北京--Person{name='lzi', age=10}    替换调了 
        }
    }
}

8、LinkedHashMap集合

特点：
底层结构：哈希表和链表（记录元素的顺序）
有序，key不允许重复

package map;

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * created by apple on 2020/6/21
 * java.util.LinkedHashMap<K,V> extends HashMap<K,V>
 *     特点：Map接口的哈希表和链表的实现，有顺序的集合
 *     底层结构：哈希表和链表（记录元素的顺序）
 */
public class Demo04LinkedHashMap {
    public static void main(String[] args) {
        HashMap<String,String> map= new HashMap<>();
        map.put("a","aa");
        map.put("c","cc");
        map.put("b","b");
        map.put("a","d");
        System.out.println(map);  //key不允许重复，无顺序集合{a=d, b=b, c=cc}

        LinkedHashMap<String, String> linked = new LinkedHashMap<>();
        linked.put("a","aa");
        linked.put("c","cc");
        linked.put("b","b");
        linked.put("a","d");
        System.out.println(linked);  //key不允许重复，有序的集合 {a=d, c=cc, b=b}

    }
}

9、Hsahtable 集合

java.util.Hsahtable<K,V>集合 implements Map<K,V>，早期的双链集合

底层也是一个哈希表
特点：
1、类似于HashMap
2、同步的，线程安全的。单线程集合，速度慢
3、不允许有空值
HashMap集合: 底层是哈希表，是一个线程不安全的集合，多线程的集合，速度快，
HashMap集合（之前学的所有集合）：可以存储null值，null键
Hashtable和Vector集合一样，在jdk1.版本之后，被更先进的集合取代了..
取代Vector的是ArrayList<> ,取代Hashtable的是HashMap集合。
Hashtable的子类Properties依然在用
Properties集合是一个唯一和IO流结合的集合

package map;

import java.util.HashMap;
import java.util.Hashtable;

/**
 * created by apple on 2020/6/21
 * java.util.Hsahtable<K,V>集合 implements Map<K,V>，早期的双链集合
 *     底层也是一个哈希表
 * 特点：
 * 1、类似于HashMap
 * 2、同步的，线程安全的。速度慢
 * 3、不允许有空值
 * HashMap集合: 底层是哈希表，是一个线程不安全的集合，多线程的集合，速度快，
 * HashMap集合（之前学的所有集合）：可以存储null值，null键
 *
 * Hashtable和Vector集合一样，在jdk1.2版本之后，被更先进的集合（hashmap ，ArrayList）取代了..
 * 取代Vector的是ArrayList<>  ,取代Hashtable的是HashMap集合。
 * Hashtable的子类Properties依然在用
 * Properties集合是一个唯一和IO流结合的集合
 */
public class Demo05Hashtable {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put(null,"a");
        map.put(null,null);
        map.put("b","b");
        System.out.println(map);  //{null=null, b=b}

        Hashtable<String, String> table = new Hashtable<>();
        table.put(null,"s");  //NullPointerException
        table.put(null,null); //NullPointerException
        table.put("a",null); //NullPointerException
        System.out.println(table); 
    }
}

10、计算一个字符串中每个字符出现的次数

image.png

分析步骤：

1、使用Scanner获取用户输入的字符串
2、创建Map集合，key是字符串中的字符，value是字符的个数
3、遍历字符串，获取每一个字符
4、使用获取到的字符，去Map集合判断key是否存在
key存在：通过字符key，获取到value（字符个数）
value++
put(key,value),把新的value存储到Map集合中
key不存在：
put(key,1)
5、遍历Map集合。输出结果

package map;

import java.util.HashMap;
import java.util.Scanner;

/**
 * created by apple on 2020/6/21
 * 分析步骤：
 * 1、使用Scanner获取用户输入的字符串
 * 2、创建Map集合，key是字符串中的字符，value是字符的个数
 * 3、遍历字符串，获取每一个字符
 * 4、使用获取到的字符，去Map集合判断key是否存在
 *   key存在：通过字符key，获取到value（字符个数）
 *   value++
 *   put(key,value),把新的value存储到Map集合中
 *   key不存在：
 *   put(key,1)
 *  5、遍历Map集合。输出结果
 */
public class Demo06MapTest {
    public static void main(String[] args) {
        //让用户输入字符串
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入字符串");
        String str = scanner.next();

        //1、创建Map集合，key是字符串中的字符，value是字符的个数
        HashMap<Character, Integer> map = new HashMap<>();
        
        //3、遍历字符串，获取每一个字符
        for (Character c : str.toCharArray()) {
            //4、使用获取到的字符，去Map集合判断key是否存在
            if (map.containsKey(c)){
                //key存在
                Integer value = map.get(c);
                value++;
                map.put(c,value);
            }else {
                //key不存在
                map.put(c,1);
            }
        }
        //5、遍历Map集合。输出结果
        for ( Character key : map.keySet()){
            Integer value = map.get(key);
            System.out.print(key + "=" + value); //aaaabbbbcccvdss    a=4b=4c=3s=2d=1v=1
        }
    }
}

输出
请输入字符串
aaaabbbbcccvdss
a=4b=4c=3s=2d=1v=1

10.1、例子：在给定的数组中，查找出现次数最多的数组元素和其出现的次数

package con.day13.demo05.demoSpead;

import javax.swing.plaf.IconUIResource;
import java.util.*;

public class MaxNum {
    public static void main(String[] args) {
        int[] arr = { 2, 3, 1, 2, 2, 5, 6, 8, 2, 3, 2, 4, 2 };

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int value : arr) {
            if (map.containsKey(value)) {
                int count = map.get(value);
                count++;
                map.put(value, count);
            } else {
                map.put(value, 1);
            }
        }

        //得到value为maxcount 的key,
        Collection<Integer> values = map.values();
        System.out.println(values);

        Integer max = Collections.max(values);
        System.out.println(max);

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();

        for (Map.Entry<Integer, Integer> entry : entries) {
            if (max.equals(entry.getValue())){
                System.out.println("最多出现的值：" + entry.getKey() + "，  出现次数：" + entry.getValue()); //
            }

        }

    }
    }

结果
[1, 6, 2, 1, 1, 1, 1]
6
最多出现的值：2，  出现次数：6

11、JDK9对集合添加的优化_of方法

*JDK9 的新特性

List接口， Set接口， Map接口里面增加了一个静态方法of，可以一次性给集合添加多个元素
Static <E> List<E> of (E . . . elements) 用的是可变参数
使用前提：
当集合中存储的元素的个数已经确定了，不再改变时使用。
注意：
1、of方法只适用于List Set Map 接口，不适用于接口的实现类，ArrayList, Hashset ,hashmap不能用
2、of方法返回值是一个不能改变的集合。集合不能再使用add，put方法添加元素，会抛出异常
3、Set Map 集合在调用of方法时，不能有重重复的元素，否则抛出异常。

of方法

十、HashMap详解，在hashset里面也解释了

数据结构图：

数据结构

hashmap数据插入原理

1、判断数组是否为空，为空进行初始化;
2、不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
3、查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
4、存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
5、如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；
6、如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8，大于的话链表转换为红黑树；
7、插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

JDK 1.8之前，由数组+单向链表组成
JDK 1.8之后，由数组+单向链表组成/红黑树（链表的长度超过8 变成红黑树，也是为了提高查询的速度）

由数组和链表组合构成
大概如下，数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node。

本身位置为null，在put 插入时根据key的hash 计算一个index的值，比如put("帅丙",520)通过hash函数计算出插入的位置

当两个值计算出的hash值一样的时候，就形成链表。数组长度有限，有限的长度内用hash

链表：新的节点在插入链表的时候，怎么插入的？

java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上面的例子一样，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。

但是，在java8之后，都是所用尾部插入了。

为啥用尾插入呢

首先我们看下HashMap的扩容机制：
帅丙提到过了，数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize。

什么时候resize呢？

那HashMap设定初始容量大小：一般如果new HashMap() 不传值，默认大小是16

有两个因素：
** Capacity：HashMap当前长度。
** LoadFactor：负载因子，默认值0.75f。

怎么理解呢，就比如当前的容量大小为100，当你存进第76个的时候，判断发现需要进行resize了，那就进行扩容，但是HashMap的扩容也不是简单的扩大点容量这么简单的。

扩容？它是怎么扩容的呢？

分为两步
扩容：创建一个新的Entry空数组，长度是原数组的2倍。
ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组

为什么要重新Hash呢，直接复制过去不香么？

Hash的公式---> index = HashCode（Key） & （Length - 1）
扩容后，hash的规则也变啦，所以要重新hash，不能直接复制

说完扩容机制我们言归正传，为啥之前用头插法，java8之后改成尾插了呢？

我先举个例子吧，我们现在往一个容量大小为2的put两个值，负载因子是0.75是不是我们在put第二个的时候就会进行resize？
2*0.75 = 1 所以插入第二个就要resize了

现在我们要在容量为2的容器里面用不同线程插入A，B，C，假如我们在resize之前打个短点，那意味着数据都插入了但是还没resize那扩容前可能是这样的。
我们可以看到链表的指向A->B->C

Tip：A的下一个指针是指向B的

因为resize的赋值方式，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

就可能出现下面的情况，大家发现问题没有？
B的下一个指针指向了A

一旦几个线程都调整完成，就可能出现环形链表

那1.8的尾插是怎么样的呢？

因为java8之后链表有红黑树的部分，大家可以看到代码已经多了很多if else的逻辑判断了，红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。

使用头插会改变链表上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

就是说原本是A->B，在扩容后那个链表还是A->B

Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。

Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

那是不是意味着Java8就可以把HashMap用在多线程中呢？hashmap是线程安全的嘛

不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题，以1.8为例，当A线程判断index位置为空后正好挂起，B线程开始往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；还有++size这个地方也会造成多线程同时扩容等问题。

我认为即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

HashMap的默认初始化长度是多少？ ——16

重写equals方法的时候需要重写hashCode方法呢？你能用HashMap给我举个例子么？

因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。

在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样

********对于值对象，==比较的是两个对象的值
********对于引用对象，比较的是两个对象的地址

HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”帅丙“和”丙帅“的index都可能是2，在一个链表上的。

我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”帅丙“还是”丙帅“呢？

equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。
不然一个链表的对象，你哪里知道你要找的是哪个，到时候发现hashCode都一样，这不是完犊子嘛。

他是线程不安全的，那你能跟我聊聊你们是怎么处理HashMap在线程安全的场景么？

面试官，在这样的场景，我们一般都会使用HashTable或者ConcurrentHashMap，但是因为前者的并发度的原因基本上没啥使用场景了，所以存在线程不安全的场景我们都使用的是ConcurrentHashMap。

HashTable我看过他的源码，很简单粗暴，直接在方法上锁，锁住整个数组，并发度很低，最多同时允许一个线程访问，ConcurrentHashMap就好很多了，1.7和1.8有较大的不同，不过并发度都比前者好太多了。

   public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

1.8还有下面主要的优化：

1、数组+链表改成了数组+链表或红黑树；
2、链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；
3、扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
4、在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；

你分别跟我讲讲为什么要做这几点优化；

1、防止发生hash冲突，链表长度过长，将时间复杂度由
O(n)降为O(logn);

2、因为1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环；

A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环，如下图所示：

头插入形成环

你前面提到链表转红黑树是链表长度达到阈值，这个阈值是多少？

阈值是8，红黑树转链表阈值为6

HashMap内部节点是有序的吗？

是无序的，根据hash值随机插入

那有没有有序的Map？

LinkedHashMap 和 TreeMap
LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。

四集合 ——第八节 Map集合，HashMap详解

1、Map集合概述

2、Map常用实现类， HashMap 和LinkedHashMap

HashMap

LinkedHashMap

3、Map接口中常用方法

4、Map集合遍历 —— 键找值方式

5、Entry键值对对象

6、Map集合遍历 ——键值对方式

7、HashMap存储自定义类型键值

8、LinkedHashMap集合

9、Hsahtable 集合

10、计算一个字符串中每个字符出现的次数

10.1、例子：在给定的数组中，查找出现次数最多的数组元素和其出现的次数

11、JDK9对集合添加的优化_of方法

十、HashMap详解，在hashset里面也解释了

Tip：A的下一个指针是指向B的

猜你喜欢

热点阅读

四 集合 ——第八节 Map集合，HashMap详解

1、Map集合概述

2、Map常用实现类， HashMap 和LinkedHashMap

HashMap

LinkedHashMap

3、Map接口中常用方法

4、Map集合遍历 —— 键找值方式

5、Entry键值对对象

6、Map集合遍历 ——键值对方式

7、HashMap存储自定义类型键值

8、LinkedHashMap集合

9、Hsahtable 集合

10、计算一个字符串中每个字符出现的次数

10.1、例子：在给定的数组中，查找出现次数最多的数组元素和其出现的次数

11、JDK9对集合添加的优化_of方法

十、HashMap详解，在hashset里面也解释了

Tip：A的下一个指针是指向B的

猜你喜欢

热点阅读

四集合 ——第八节 Map集合，HashMap详解