Java数据结构——Map和Set

目录 引言1. 搜索树1.1 二叉搜索树的概念1.2 二叉搜索树的操作1.2.1 查找1.2.2 插入1.2.3 删除 2. Map2.1 Map的概念2.2 Map接口内部的Entry接口(Map.Entry<K, V>)2.3 Map的常用方法 3. Set3.1 Set 概念3.2 Set常见方法 4. 总结

引言

本篇文章介绍Map和Set类和其实现类TreeMap和TreeSet类的使用。

1. 搜索树

在讲述TreeMap和TreeSet之前，先介绍一下搜索树，java中利用搜索树来实现Map和Set。在这里介绍一下二叉搜索树。

1.1 二叉搜索树的概念

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，也叫二叉排序树。具有如下性质：

左子树上所有节点的值都小于其根节点的值。右子树上所有节点的值都大于其根节点的值。左子树和右子树也都是二叉搜索树。 1.2 二叉搜索树的操作

二叉搜索树的定义和二叉树一致

static class TreeNode { public int val; public TreeNode left;//左孩子的引用 public TreeNode right;//右孩子的引用 public TreeNode(int val) { this.val = val; } } 1.2.1 查找

从根节点开始，比较当前节点的值与目标值。如果目标值小于当前节点的值，则移动到左子树；如果目标值大于当前节点的值，则移动到右子树；如果相等，则返回当前节点。循环继续，直到找到目标值或到达树的末端。

public TreeNode search(int val) { TreeNode cur = root; while (cur != null) { if (cur.val < val) { cur = cur.right; } else if (cur.val > val) { cur = cur.left; } else { return cur; } } return null; } 1.2.2 插入 从根节点开始。如果树为空，则新节点作为根节点。否则，比较新节点的值与当前节点的值： 如果新节点的值小于当前节点的值，则移动到左子树。 如果新节点的值大于当前节点的值，则移动到右子树。重复步骤3，直到找到合适的插入位置。 public void insert(int val) { if (root == null) { root = new TreeNode(val); return; } TreeNode cur = root; TreeNode parent = null; while (cur != null) { if (cur.val < val) { parent = cur; cur = cur.right; } else if (cur.val > val) { parent = cur; cur = cur.left; } else { return; } } if (parent.val < val) { parent.right = new TreeNode(val); } else { parent.left = new TreeNode(val); } } 1.2.3 删除

二叉搜索树的删除操作较为复杂。

查找要删除的节点：从根节点开始，找到要删除的节点及其父节点。删除节点： 要删除的节点没有左子节点： 如果要删除的节点是根节点，直接将根节点设为其右子节点。 否则，更新父节点的指针，将其指向要删除节点的右子节点。要删除的节点没有右子节点： 如果要删除的节点是根节点，直接将根节点设为其左子节点。 否则，更新父节点的指针，将其指向要删除节点的左子节点。要删除的节点有两个子节点： 找到要删除节点的后继节点（右子树中最小的节点）。 用后继节点的值替代要删除节点的值。 删除后继节点，更新其父节点的指针。 public void remove(int val) { TreeNode cur = root; TreeNode parent = null; while (cur != null) { if (cur.val < val) { parent = cur; cur = cur.right; } else if (cur.val > val) { parent = cur; cur = cur.left; }else { removeNode(parent,cur); return; } } } private void removeNode(TreeNode parent, TreeNode cur) { if (cur.left == null){ if(cur == root){ root = cur.right; }else if(cur == parent.left){ parent.left = cur.right; }else{ parent.right = cur.right; } }else if (cur.right == null){ if(cur == root){ root = cur.left; }else if(cur == parent.left){ parent.left = cur.left; }else{ parent.right = cur.left; } }else{ TreeNode target = cur.right; TreeNode targetParent = cur; while(target.left != null){ targetParent = target; target = target.left; } if (target == targetParent.left){ targetParent.left = target.right; }else{ targetParent.right = target.right; } } } 2. Map 2.1 Map的概念

Map是一个接口类，是一种键值对的集合，用于存储键值对的映射关系。该类存储的是<K,V>结构的键值对。 Map接口定义了一系列方法，用于操作键值对，包括插入、删除、获取和遍历等操作。在Map中，每个键对应一个值，键(K)是唯一的，值(V)可以重复。

2.2 Map接口内部的Entry接口(Map.Entry<K, V>)

Map.Entry接口表示Map中的一个键值对（entry），它是Map接口的内部接口。Map.Entry接口定义了操作键值对的方法，允许访问键和值，以及对它们进行操作。 Map.Entry接口包含以下常用方法：

getKey(): 返回该键值对中的键。getValue(): 返回该键值对中的值。setValue(V value): 设置该键值对中的值为指定的值。 2.3 Map的常用方法 V get(Object key)： 根据指定的键获取对应的值。如果键不存在，则返回 null。V getOrDefault(Object key, V defaultValue)： 根据指定的键获取对应的值。如果键不存在，则返回默认值 defaultValue。V put(K key, V value)： 将指定的键值对插入到 Map 中。如果键已经存在，则更新对应的值，并返回旧值。V remove(Object key)： 根据指定的键删除对应的键值对，并返回被删除的值。如果键不存在，则返回 null。Set keySet()： 返回 Map 中所有键的集合。Collection values()： 返回 Map 中所有值的集合。Set<Map.Entry<K, V>> entrySet()： 返回 Map 中所有键值对的集合。boolean containsKey(Object key)： 判断 Map 中是否包含指定的键。boolean containsValue(Object value)： 判断 Map 中是否包含指定的值。

TreeMap示例代码：

public class MapExample { public static void main(String[] args) { Map<String, Integer> map = new TreeMap<>(); // put map.put("one", 1); map.put("two", 2); // get System.out.println("Value for key 'one': " + map.get("one")); // 1 // getOrDefault System.out.println("Value for key 'three' (default 0): " + map.getOrDefault("three", 0)); // 0 // remove System.out.println("Removed value for key 'one': " + map.remove("one"));// 1 // keySet Set<String> keys = map.keySet(); System.out.println("Keys: " + keys); // [two] // values Collection<Integer> values = map.values(); System.out.println("Values: " + values); // [2] // entrySet Set<Map.Entry<String, Integer>> entries = map.entrySet(); System.out.println("Entries: " + entries); // [two=2] // containsKey System.out.println("Contains key 'two': " + map.containsKey("two")); // true // containsValue System.out.println("Contains value 2: " + map.containsValue(2)); // true } } 3. Set 3.1 Set 概念

Set 是 Java 集合框架中的一个接口，它表示一个不包含重复元素的集合。Set 接口继承自 Collection 接口，相较于Map不同的是它只存储了Key。

3.2 Set常见方法 boolean add(E e)： 将指定的元素添加到集合中（如果该元素尚不存在于集合中）。如果集合中已存在该元素，则返回 false。void clear()： 移除集合中的所有元素。boolean contains(Object o)： 如果集合中包含指定的元素，则返回 true。Iterator iterator()： 返回集合中元素的迭代器。boolean remove(Object o)： 如果集合中存在指定的元素，则将其移除，并返回 true。int size()： 返回集合中的元素数量。boolean isEmpty()： 如果集合为空，则返回 true。Object[] toArray()： 返回包含集合中所有元素的数组。boolean containsAll(Collection<?> c)： 如果集合包含指定集合中的所有元素，则返回 true。boolean addAll(Collection<? extends E> c)： 将指定集合中的所有元素添加到集合中（如果这些元素尚不存在于集合中）。如果集合因调用此方法而发生更改，则返回 true。

TreeSet示例代码：

public class SetExample { public static void main(String[] args) { Set<String> set = new TreeSet<>(); // add set.add("one"); set.add("two"); // contains System.out.println("Contains 'one': " + set.contains("one")); // true // iterator Iterator<String> iterator = set.iterator(); System.out.print("Set elements: "); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); // one two } System.out.println(); // remove set.remove("one"); System.out.println("After removing 'one', contains 'one': " + set.contains("one")); // false // size System.out.println("Set size: " + set.size()); // 1 // isEmpty System.out.println("Is set empty: " + set.isEmpty()); // false // toArray Object[] array = set.toArray(); System.out.print("Array elements: "); for (Object obj : array) { System.out.print(obj + " "); // two } System.out.println(); // containsAll Set<String> otherSet = new HashSet<>(); otherSet.add("two"); System.out.println("Contains all elements of otherSet: " + set.containsAll(otherSet)); // true // addAll otherSet.add("three"); set.addAll(otherSet); System.out.print("After addAll, set elements: "); for (String element : set) { System.out.print(element + " "); // two three } System.out.println(); // clear set.clear(); System.out.println("After clear, is set empty: " + set.isEmpty()); // true } } 4. 总结

以上是对搜索树，Map，Set 的简单介绍，在后面会经常用到Map和Set接口，将会更深入的进行介绍。