侧边栏壁纸
博主头像
Epoch

Java开发、Python爬虫、微服务、分布式、前端

  • 累计撰写 93 篇文章
  • 累计创建 110 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

Java学习--HashMap从入门到进阶

Epoch
2021-09-10 / 0 评论 / 0 点赞 / 302 阅读 / 1,493 字 / 正在检测是否收录...

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

image-20210909225601785

											**图一**

image-20210909232633693

											**图二**

3、HashMap底层执行原理

3.1、HashMap特点

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

image-20210909233437458

											**图三**

3.2、HashMap的数据结构

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

借用别人的图(自己无才不想画)

image-20210909233914481

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

3.3、Hash冲突

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

image-20210909234713746

											**图五**

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

image-20210910000208042

											**图六**

3.5、HashMap扩容(自动扩容)

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

image-20210910001028803

											**图七**

3.6、红黑树在HashMap中的应用(JDK1.8起)

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

image-20210910001515274

											**图八**

image-20210910001656866

											**图九**

image-20210910001945965

											**图十**

4、HashMap源码分析

image-20210910002157042

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

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

image-20210910002944119

											**图十二**

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

5、红黑树

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

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

0

评论区