目录
一、映射（Map）
映射（Maps）用于存储键值对，常见的实现有 HashMap 和 TreeMap。
在Java方法中可以直接调用
Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> treeMap = new TreeMap<>();HashMap:
- 特点： 基于哈希表实现的键值对存储结构。
- 优点： 高效的查找、插入和删除操作。
- 缺点： 无序，不保证顺序。
TreeMap:
- 特点： 基于红黑树实现的有序键值对存储结构。
- 优点： 有序，支持按照键的顺序遍历。
- 缺点： 插入和删除相对较慢。
映射是存储数据对（key,value）的数据结构
根据键（key）,寻找值（value）
二、代码实现
1.建立接口
package com.algo.lesson.lesson05.map;
public interface SelfMap<K,V> {
//判断集合是否为空
boolean isEmpty();
//获取集合中元素的个数
int getSize();
//判断key是否存在
boolean containsKey(K key);
//根据key获取值
V fetValueByKey(K key);
//向集合中添加元素
void put(K key,V val);
//删除集合中的元素（根据key删除）
boolean removeByKey(K key);
//修改key修改值
void set(K key ,V val);
//打印map集合中的所有元素【key：val】
void show();
}
2.方法实现
（1）映射的建立
键（key）和值（val）的建立
K key;
V val;
Node next;
public Node(K key, V val) {
this.key = key;
this.val = val;
this.next = null;
}
public Node(K key, V val, Node next) {
this(key, val);
this.next = next;
}
private Node<K, V> head;
private int size;重写toString方法
打印的时候，为了能方便我们观察，我们可以重写toString方法，按照我们希望的格式去输出
@Override
public String toString() {
return "[" + this.key + ":" + this.val + "]";
}
}（2）构造方法
public LinkedData() {
Node<K, V> dummyHead = new Node(null, null);
this.head = dummyHead;
this.size = 0;
}（3）判断是否为空
public boolean isEmpty() {
return this.size == 0;
}（4）添加元素
头部添加
public void addHead(K key, V val) {
add(0, key, val);
}
public void add(int index, K key, V val) {
if (index < 0 || index > this.size) {
throw new IllegalArgumentException("index is invalid.");
}
Node<K, V> node = new Node(key, val);
Node<K, V> pre = this.head;
for (int i = 1; i <= index; i++) {
pre = pre.next;
}
node.next = pre.next;
pre.next = node;
this.size++;
}（5）修改元素
传入键和值，返回boolean类型判断是否修改成功
public boolean set(K key,V val){
Node<K, V> curNode = this.head.next;
while (curNode != null) {
if (curNode.key.equals(key)) {
curNode.val=val;
return true;
}
curNode = curNode.next;
}
return false;
}（6）打印映射
@Override
public String toString() {
Node<K, V> curNode = this.head.next;
StringBuilder sb = new StringBuilder();
while (curNode != null) {
sb.append(curNode + "-->");
curNode = curNode.next;
}
sb.append("null");
return sb.toString();
}（7）判断元素是否存在
public boolean contain(K key) {
Node<K, V> curNode = this.head.next;
while (curNode != null) {
if (curNode.key.equals(key)) {
return true;
}
curNode = curNode.next;
}
return false;
}（8）获取元素个数
public int getSize() {
return this.size;
}
（9）获取元素
根据键（key）获取值（val）
public V get(K key) {
Node<K, V> curNode = this.head.next;
while (curNode != null) {
if (curNode.key.equals(key)) {
return curNode.val;
}
curNode = curNode.next;
}
return null;
}（10）删除元素
返回boolean值，判断是否删除成功
public boolean remove(K key) {
Node<K, V> pre = this.head;
while (pre.next != null) {
Node<K, V> delNode = pre.next;
if (delNode.key.equals(key)) {
pre.next = pre.next.next;
delNode.next = null;
this.size--;
return true;
}
pre = pre.next;
}
return false;
}3.方法调用
继承SelfMap的接口，将其中的方法全部重写，然后进行调用，调取自己已经写好的代码，以此来实现Map
package com.algo.lesson.lesson05.map;
public class LinkedMap<K, V> implements SelfMap<K, V> {
private LinkedData<K, V> data;
public LinkedMap(){
this.data=new LinkedData<>();
}
@Override
public boolean isEmpty() {
return this.data.isEmpty();
}
@Override
public int getSize() {
return this.data.getSize();
}
@Override
public boolean containsKey(K key) {
return this.data.contain(key);
}
@Override
public V fetValueByKey(K key) {
return this.data.get(key);
}
@Override
public void put(K key, V val) {
this.data.addHead(key,val);
}
@Override
public boolean removeByKey(K key) {
return this.data.remove(key);
}
@Override
public void set(K key, V val) {
boolean ret= this.data.set(key,val);
System.out.println(ret?"successful":"failed");
}
@Override
public void show() {
System.out.println(this.data);
}
}
三、对应题目
350. 两个数组的交集 II力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目利用映射（哈希表）来解决，感兴趣可以去LeetCode上尝试一下
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if(nums1.length>nums2.length){
return intersect(nums2,nums1);
}
Map<Integer,Integer>map=new HashMap<Integer,Integer>();
for(int num:nums1){
int count=map.getOrDefault(num,0)+1;
map.put(num,count);
}
int[]intersection=new int[nums1.length];
int index=0;
for(int num:nums2){
int count=map.getOrDefault(num,0);
if(count>0){
intersection[index++]=num;
count--;
if(count>0){
map.put(num,count);
}else{
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection,0,index);
}
}
