数据结构-Map和Set

1. 搜索树

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它具有以下性质：

1. 节点性质：

   • 每个节点最多有两个子节点，称为左子节点和右子节点。
   • 每个节点的左子树上所有节点的值都小于该节点的值。
   • 每个节点的右子树上所有节点的值都大于该节点的值。

2. 递归性质：

   • 每个子树也是一棵二叉搜索树。

3. 操作：

   • 插入：从根节点开始，与当前节点比较，若小则进入左子树，若大则进入右子树，直到找到合适的空位插入。
   • 删除：分为三种情况：
     1. 删除叶子节点：直接删除。
     2. 删除只有一个子节点的节点：用子节点替代该节点。
     3. 删除有两个子节点的节点：找到该节点的中序后继（右子树中最小的节点）或中序前驱（左子树中最大的节点）替代该节点，然后删除中序后继或前驱。
   • 搜索：从根节点开始，逐层比较，若小则进入左子树，若大则进入右子树，直到找到目标节点或搜索完成。

4. 遍历：

   • 中序遍历：左-根-右，输出的节点值是递增的。
   • 前序遍历：根-左-右。
   • 后序遍历：左-右-根。

5. 应用：

   • 二叉搜索树常用于实现动态集合和查找操作，适用于需要快速插入、删除和查找的场景。

6. 优缺点：

   • 优点：在理想情况下（平衡树），插入、删除和查找操作的时间复杂度为O(log n)。
   • 缺点：在最坏情况下（退化为链表），操作的时间复杂度为O(n)。为此，平衡二叉搜索树（如AVL树和红黑树）被引入以保证操作的效率。

二叉搜索树是一种非常基础的数据结构，广泛用于各种算法和应用中。

模拟实现：

package myDataStructure.BinarySearchTree;import com.sun.source.tree.Tree;import javax.crypto.NullCipher;
import javax.naming.directory.SearchResult;
import javax.xml.crypto.KeySelector;/*** @Author: Author* @CreateTime: 2025-04-18* @Description:*/
public class BinarySearchTree {static class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val){this.val=val;}}public TreeNode root =null;public TreeNode search(int key){return searchRec(root,key);}private TreeNode searchRec(TreeNode root,int key){if (root== null){return null;}if (root.val==key){return root;}if (key<root.val){return searchRec(root.left,key);}else{return searchRec(root.right,key);}}public void insert(int key){root=insertRec(root,key);}private TreeNode insertRec(TreeNode root,int key){if (root==null){root=new TreeNode(key);return root;}if (key< root.val){root.left=insertRec(root.left,key);}else {root.right=insertRec(root.right,key);}return root;}public void remove(int key){root=removeRec(root,key);}// 删除递归实现// 在递归过程中，每一层递归调用都会根据返回值来更新其子树的结构。通过返回更新后的子树根节点，递归可以逐层回溯并最终更新整棵树的结构。private TreeNode removeRec(TreeNode root, int key) {if (root == null) {return root;}// 找到要删除的节点if (key < root.val) {root.left = removeRec(root.left, key);} else if (key > root.val) {root.right = removeRec(root.right, key);} else {// 节点只有一个子节点或没有子节点if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;}// 节点有两个子节点，找到中序后继（右子树的最小节点）root.val = minValue(root.right);// 删除中序后继root.right = removeRec(root.right, root.val);}return root;}// 找到最小值private int minValue(TreeNode root) {int minValue = root.val;while (root.left != null) {minValue = root.left.val;root = root.left;}return minValue;}
}

2. Map

Map 接口表示一个键值对的集合，其中每个键最多只能映射到一个值。它不允许重复的键，但可以有重复的值。常用的实现类包括 HashMap、TreeMap 和 LinkedHashMap。

常用实现类：

1. HashMap：
   • 基于哈希表实现，允许 null 键和 null 值。
   • 无序存储，不能保证顺序。
   • 平均时间复杂度为 O(1)。
2. TreeMap：
   • 基于红黑树实现，键值对有序存储。
   • 不允许 null 键，但允许 null 值。
   • 支持自然排序或自定义排序，时间复杂度为 O(log n)。
3. LinkedHashMap：
   • 继承自 HashMap，维护了一个双向链表以记录插入顺序。
   • 可以按照插入顺序或访问顺序迭代。
   • 允许 null 键和 null 值。

常用方法：

• put(K key, V value)：将指定的值与此映射中的指定键关联。
• get(Object key)：返回指定键所映射的值。
• remove(Object key)：删除键及其对应的值。
• containsKey(Object key)：检查是否包含指定的键。
• containsValue(Object value)：检查是否包含指定的值。
• keySet()：返回所有键的集合。
• values()：返回所有值的集合。
• entrySet()：返回所有键值对的集合。

3. Set

Set 接口表示一个不包含重复元素的集合。它不保证元素的顺序。常用的实现类包括 HashSet、TreeSet 和 LinkedHashSet。

常用实现类：

1. HashSet：
   • 基于 HashMap 实现，使用哈希表存储元素。
   • 不保证顺序，允许 null 元素。
   • 平均时间复杂度为 O(1)。
2. TreeSet：
   • 基于 TreeMap 实现，使用红黑树存储元素。
   • 元素有序，支持自然排序或自定义排序。
   • 不允许 null 元素，时间复杂度为 O(log n)。
3. LinkedHashSet：
   • 继承自 HashSet，维护了一个双向链表以记录插入顺序。
   • 可以按照插入顺序迭代。
   • 允许 null 元素。

常用方法：

• add(E e)：向集合中添加元素。
• remove(Object o)：从集合中移除指定元素。
• contains(Object o)：检查集合中是否包含指定元素。
• size()：返回集合中的元素数量。
• isEmpty()：检查集合是否为空。
• clear()：清空集合中的所有元素。
• iterator()：返回用于遍历集合的迭代器。

4. 哈希表

哈希表是一种数据结构，用于存储键值对（key-value pairs），它通过哈希函数将键映射到数组中的一个位置，以实现快速的数据存取。哈希表的主要特点是能够在平均情况下以常数时间复杂度 O(1) 进行插入、删除和查找操作。

4.1 哈希表的基本概念

1. 哈希函数：

   • 哈希函数用于将键转换为数组的索引。一个好的哈希函数能够均匀地分布键，减少冲突。
   • 常见的哈希函数包括除法散列法、乘法散列法等。

2. 哈希冲突：

   • 当两个不同的键映射到同一个索引时，就发生了哈希冲突。
   • 处理哈希冲突的常用方法有两种：链地址法（链表法）和开放定址法。

3. 负载因子：

   • 负载因子是哈希表中元素数量与表大小的比值，用于衡量哈希表的满度。
   • 一般情况下，负载因子越高，哈希冲突越多，性能越差。因此，通常设定一个阈值，当负载因子超过此阈值时进行扩容。

4.2 哈希表的实现方法

1. 链地址法（Separate Chaining）：

   • 使用链表存储每个索引处的所有元素。
   • 当发生冲突时，将冲突的元素添加到链表的末尾。
   • 优点是简单易实现，缺点是链表可能变得很长，影响性能。

2. 开放定址法（Open Addressing）：

   • 所有元素都存储在数组中，解决冲突的方法是寻找下一个空闲位置。
   • 常用的探查方法包括线性探查、二次探查和双重散列。
   • 优点是节省空间，缺点是探查可能会增大查找时间。

4.3 Java中的哈希表实现

Java中常用的哈希表实现类是 HashMap。HashMap 使用链地址法来处理冲突，并且在负载因子超过默认值（通常为0.75）时进行扩容。它允许 null 键和 null 值。

HashMap 的特点：

• 时间复杂度：平均情况下，插入、删除和查找操作的时间复杂度为 O(1)。
• 非线程安全：HashMap 是非线程安全的，如果需要线程安全的哈希表，可以使用 ConcurrentHashMap。
• 支持动态扩容：当负载因子超过设定值时，HashMap 会自动扩容，以减少冲突。

5. 哈希桶

哈希桶是哈希表中的一个重要概念，它是用来处理哈希冲突的机制之一。在哈希表中，哈希桶通常是指存储在特定哈希索引处的一个容器，用于存放所有映射到该索引的键值对。当多个键通过哈希函数映射到同一索引时，这些键值对就被存储在同一个哈希桶中。

哈希桶的实现方式

1. 链地址法（Separate Chaining）：

   • 每个哈希桶是一个链表或其他数据结构（如平衡树）。
   • 当发生哈希冲突时，新的键值对被添加到该链表中。
   • 优点是简单易实现，且在负载因子较高时性能依然较好。
   • HashMap 在 Java 8 之后，当链表长度超过一定阈值时，会将链表转换为红黑树，以提高性能。

2. 开放定址法（Open Addressing）：

   • 哈希桶实际上是一个单独的存储位置，冲突时通过探查其他位置解决。
   • 不在同一个桶中存储多个元素，而是寻找下一个空闲桶。
   • 常用的探查方法有线性探查、二次探查和双重散列。

哈希桶的作用

• 解决冲突：通过哈希桶，可以有效处理哈希冲突，使得多个键值对能够共存于同一个索引。
• 提高效率：在冲突发生时，哈希桶允许快速插入和查找操作，尤其是在链地址法中，链表的操作复杂度为 O(1)。
• 动态调整：在一些实现中（如 Java 的 HashMap），当链表过长时，会自动转换为更高效的数据结构（如红黑树），从而提高性能。

哈希桶的应用

哈希桶在许多哈希表的实现中被广泛使用，尤其是在需要处理大量数据且存在高概率冲突的情况下。它们在数据库索引、缓存系统、符号表等领域中发挥着重要作用。通过合理的哈希函数与哈希桶的设计，可以显著提高哈希表的性能和效率。

模拟实现

package myDataStructure.HashBucket;/*** @Author: Author* @CreateTime: 2025-04-18* @Description:*/
public class HashBucket {static class Node{public int key;public int val;public Node next;public Node(int key,int val){this.key=key;this.val=val;}}public Node[] array;public int usedSize;public double loadFactor=0.75;public HashBucket(){array=new Node[10];}public void put(int key,int val){int index=key%array.length;Node cur=array[index];//1. 遍历当前链表，是否存在当前值while (cur!=null){if (cur.key==key){cur.val=val;return;}cur=cur.next;}//2. 说明没有当前值，此时进行头插Node node=new Node(key,val);node.next=array[index];array[index]=node;usedSize++;//3.if(loadFactorCount()>=loadFactor){// 扩容resize();}}private void resize(){Node[] newArray=new Node[array.length*2];for (int i=0;i<array.length;i++){Node cur=array[i];// 开始遍历链表while (cur!=null){int newIndex=cur.key%newArray.length;// 把数组存放在新的数组的 newIndex位置Node curN=cur.next;cur.next=newArray[newIndex];newArray[newIndex]=cur;cur=curN;}}array=newArray;}private double loadFactorCount(){return usedSize*1.0/array.length;}public int get(int key){int index=key%array.length;Node cur=array[index];//1. 遍历当前链表 是否存在当前值while(cur!=null){if (cur.key==key){return cur.val;}cur=cur.next;}return -1;}public static void main(String[] args) {HashBucket hashBucket = new HashBucket();// 测试 put 方法hashBucket.put(1, 100);hashBucket.put(2, 200);hashBucket.put(3, 300);hashBucket.put(11, 1100); // 这个键会导致哈希冲突// 测试 get 方法System.out.println("Value for key 1: " + hashBucket.get(1)); // 应该输出 100System.out.println("Value for key 2: " + hashBucket.get(2)); // 应该输出 200System.out.println("Value for key 3: " + hashBucket.get(3)); // 应该输出 300System.out.println("Value for key 11: " + hashBucket.get(11)); // 应该输出 1100// 测试更新值hashBucket.put(1, 101);System.out.println("Updated value for key 1: " + hashBucket.get(1)); // 应该输出 101// 测试不存在的键System.out.println("Value for non-existent key 4: " + hashBucket.get(4)); // 应该输出 -1// 测试负载因子和扩容for (int i = 0; i < 20; i++) {hashBucket.put(i, i * 10);}System.out.println("Value for key 19 after resizing: " + hashBucket.get(19)); // 应该输出 190}
}