Java学习–HashMap从入门到进阶

1、HashMap简介

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

HashMap 是无序的，即不会记录插入的顺序。

HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

2、HashMap简单运用

package com.xmaven.test;

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

/**
 * @Author: Ambition
 * @Description TODO
 * @Date: 2021/9/9 10:30 下午
 * @Version 1.0
 */
public class HashMapDemo {
    
    public static void main(String[] args) {
        // 小明 -> 2000  key/value
        Map<String, Integer> incomeMap = new HashMap<String, Integer>();
        incomeMap.put("小明", 2000);
        incomeMap.put("小王", 3000);
        
        System.out.println("根据我们的键直接获取我们的值");
        // 取出value
        System.out.println(incomeMap.get("小明"));
        System.out.println(incomeMap.get("小王"));
        
        System.out.println("一般方法：for循环迭代我们的entry");
        // 实际上我们存储在hashmap中的是一个封装类型的结构（Entry）所以我们遍历HashMap就是遍历Entry 如图一所示
        for (Entry<String, Integer> entry : incomeMap.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
        
        System.out.println("使用Lambda遍历我们的键值对");
        // JDK8 lambda 提供更快的遍历方式
        incomeMap.forEach((k, v) -> System.out.println(k + " : " + v));
        
        System.out.println("远古方法 使用iterator迭代键值对");
        // 远古方法 iterator 迭代器迭代我们的键值对
        Set<Entry<String, Integer>> set = incomeMap.entrySet();
        Iterator<Entry<String, Integer>> iterator = set.iterator();
        // iterator.hasNext() 这个是判断下一个元素，并不是取得下一个元素
        while (iterator.hasNext()) {
            Entry<String, Integer> next = iterator.next();
            System.out.println(next.getKey() + " : " + next.getValue());
        }
        
        System.out.println("HashMap添加元素");
        // 添加元素 也可以叫更新元素 incomeMap.put("小明", 5555); 这样写会更新小明这个键对应的value
        incomeMap.put("小花", 4000);
        incomeMap.put("小明", 5555);
        // 这里可以直接使用这个打印我们hashmap对象，这个hashmap有个默认方法的重载
        // 基本直接打印对象都会调用这个对面里面的toString方法进行打印
        // 打印的形式 {小明=2000, 小王=3000, 小花=4000}
        // 默认调用我们的 HashMap toString 方法 （这个方法大概在我们的源代码的294行）如图二所示
        // 也可以写成 System.out.println(incomeMap.toString());
        System.out.println(incomeMap);
        
        System.out.println("HashMap删除元素--根据key删除元素");
        incomeMap.remove("小明");
        System.out.println("根据key删除元素后还有: " + incomeMap);
        
        System.out.println("HashMap删除元素--根据key-value删除元素");
        // 注意点，必须key 和 value 一一 对应否者无法删除元素
        incomeMap.remove("小王", 3000);
        System.out.println("根据key-value删除元素后还有: " + incomeMap);
        
    }
    
}

											**图一**

											**图二**

3、HashMap底层执行原理

3.1、HashMap特点

数据的快速存取(put,get)
数据的快速查找 HashMap中查找一个元素的时间复杂度是O(n)如下图三所示
空间弹性可伸缩(空间的自动扩容)

											**图三**

3.2、HashMap的数据结构

主要由以下三种数据结构组成
数组
链表
红黑树（JDK1.8）

借用别人的图（自己无才不想画）

											**图四**

HashMap如果不指定大小，默认是16（HashMap中的 DEFAULT_INITIAL_CAPACITY 决定的）
图四中我们可以看到有些元素是数组存储链表的结构，而有些不是，为什么了？可能你有些好奇？
下面来说⬇️

3.3、Hash冲突

介绍
Hash冲突：不同对象计算出来的数组下标是相同的   展示如下图五
解决方案：
1.单向链表
2.红黑树（JDK1.8）

											**图五**

3.4、Hash算法

方法：用来计算我们数组下标的方法
在我们的Java编程语言当中所有的对象都有hashCode（由JVM提供的）
Hash值（源码图六所示）：(hashCode)^(hashCode >>> 16)
数组下标的计算：
	—— 数组默认大小是16
	—— 数组下标 hash&(16-1) = hash%16

补充介绍

java中有三种移位运算符

<<      :     左移运算符，num << 1,相当于num乘以2

>>      :     右移运算符，num >> 1,相当于num除以2

>>>    :     无符号右移，忽略符号位，空位都以0补齐

Java其他操作符具体详细操作见：https://www.runoob.com/java/java-operators.html

											**图六**

3.5、HashMap扩容（自动扩容）

1、触发条件：数组使用空间达到了75%
2、解决方案：数组的长度X2
3、元素下标重新计算

											**图七**

3.6、红黑树在HashMap中的应用（JDK1.8起）

红黑树：一种二叉树，高效的检索效率 （结构如图八）
触发条件：链表长度大于8 （HashMap源码位置如图九）

											**图八**

											**图九**

											**图十**

4、HashMap源码分析

											**图十一**

这个Node（如图十一）（内部类）定义了我们存储在数组或者链表中每一个元素的数据结构

如果存储的元素没有发生Hash冲突的时候，这个HashMap会把那个Node结构放在数组空间里面，如果发生了Hash冲突就会形成一个链表结构，用Node的下一个指针进行存储元素（如下图所示）

											**图十二**

其他的源码就不一一赘述了

5、红黑树

**学习数据结构网站：**https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

**学习红黑树：**https://www.cs.usfca.edu/~galles/visualization/RedBlack.html