锐单电子商城 ， 一站式电子元器件采购平台！

  • 电话：400-990-0325

购物车

数据结构

时间：2022-09-17 09:30:01 kk系列连接器连接器s10b

各种数据结构API常用方法

2243690-9cd9c896e0d512ed

数组长度固定。集合长度可变。

数组中存储相同类型的元素，可以存储基本数据类型值。集合存储是对象，对象类型可能不一致。在开发中，当对象较多时，通常使用集合存储。

Arrays

  • Arrays.toString(arr); // 返回数组内容的字符串表示形式
  • Arrays.sort(arr,start,end); // 按数字升序对指定数组的指定范围（默认全部）进行排序
  • Arrays.equals(arr1, arr2); // 用于判断两个数组的长度和相应元素是否相等，内部元素无法判断
  • Arrays.binarySearch(arr, arr[i]); // 用二分法搜索 arr[i] 在 arr 中的索引
  • Arrays.copyOfRange(arr1,start,end); // 复制指定的数组，并指定复制起始和终点索引
  • Arrays.copyOf(arr1,int newLength); // 复制指定数组，并指定新数组的长度
  • Arrays.fill(arr, 1); // 使用元素 i 填充数组 arr
  • Arrays.asList("1", "2", "3"); // 将同一类型的多个元素转化为 List(不是数组)
  • Arrays.stream(arr).max().getAsInt(); // 返回数组中的极大值
  • Arrays.stream(arr).min().getAsInt(); // 返回数组中的极小值
  • array长度不可改变，ArrayList长度可以改变
  • System.arraycopy(arr1, 0, arr2, 1, 3) // 从arr1 的 索引 0 开始复制，复制到 Arr2 的 1 从索引开始，复制 3 个

Array

  • arr.length // length 是数组长度
  • arr[0].length() // length() 是字符串的长度
  • String[] str3 = str1; // str3 与 strs 指向同一数组
  • String[] str2 = str1.clone(); // str2 与 strs 不是同一个数组
  • for (String s : strs) { } // 可使用数组 foreach
  • System.out.println(arr); // 数组直接打印会输出地址值
  • System.out.println(Arrays.toString(arr)); // 输出数组中的所有元素
int[] numbers = new int [5]; numbers[0] = 1; numbers[2] = 3; int[] numbers2 = {3,7,5,4};  String[] strs = new String[3]; strs[0] = "hello";  System.out.println(strs.length);                    // length 是数组长度 System.out.println(strs[0].length());               // length() 是字符串的长度  String[] str3 = strs;                               // str3 与 strs 指向同一数组 String[] str2 = strs.clone();                       // str2 与 strs 不是同一个数组 str2[1] = "world"; // foreach for (String s : strs) {     System.out.println(s); } System.out.println(numbers);                        // 地址值 [I@1b6d3586 // Arrays.toString() System.out.println(Arrays.toString(numbers));       // [1, 0, 3, 0, 0]  // 获得大/小值 System.out.println(Arrays.stream(numbers2).max().getAsInt()); System.out.println(Arrays.stream(numbers2).min().getAsInt()); // 升序排序 Arrays.sort(numbers2); System.out.println(Arrays.toString(numbers2));  // Arrays.equals() 判断两个数组的长度和对应元素是否相等，内部元素无法判断 System.out.println(Arrays.equals(numbers, numbers2)); // Arrays.binarySearch() System.out.println(Arrays.binarySearch(numbers2, 5));   // 返回相应的索引 2 // Arrays.copyOf()  复制指定数组，并指定新数组的长度 int [] numbers3 = Arrays.copyOf(numbers2,10); System.out.println(Arrays.toString(numbers3)); // Arrays.copyOfRange() 复制指定的数组，并指定复制起始和终点索引 int [] numbers4 = Arrays.copyOfRange(numbers2,0,3); System.out.println(Arrays.toString(numbers4)); // Arrays.fill(arr,i)  使用元素 i 填充数组 arr Arrays.fill(numbers4, 1);  // 将同样类型的多个元素转化为 List(不是数组) List stooges = Arrays.asList("Larry", "Moe", "Curly"); System.out.println(stooges);

Collections

  • Collections.sort(list); // 升序排序
  • Collections.reverse(list); // 倒序排序(不是大小倒序)
  • Collections.addAll(list,2,4,8,6); // 在列表中添加新的同类元素(数量不限)
  • Collections.shuffle(list); // 打乱顺序
  • Collections.sort(List ); // 将自定义类型数据添加到列表中进行排序(implements Comparable)
  • Collections.sort(List ,new Comparator ()); // 将自定义类型数据添加到列表中进行排序(new Comparator ()) 
import java.util.ArrayList; import java.util.Collections;  public class Demo02Collection {     public static void main(String[] args) {         ArrayList list = new ArrayList<>();         list.add(1);         list.add(9);         list.add(7);         list.add(3);         Collections.sort(list);              // list = [1, 3, 7, 9]         Collections.reverse(list);           // list = [9, 7, 3, 1]         Collections.addAll(list,2,4,8,6);       // list = [9, 7, 3, 1, 2, 4, 8, 6]         Collections.shuffle(list);     // 打乱顺序         System.out.println(list);          // 自定义类型需要重写排序模式 1         ArrayList personArrayList = new ArrayList<>();         Collections.addAll(personArrayList,                 new Person("Tom",11),                 new Person("Kte",11),
                new Person("Zoy",15),
                new Person("Bob",17));
        Collections.sort(personArrayList);
 		// 自定义类型需要重写排序方式 2
        // personArrayList.sort(new Comparator() {}
        Collections.sort(personArrayList, new Comparator() {
            @Override
            public int compare(Person o1, Person o2) {
                return o1.getName().charAt(0) - o2.getName().charAt(0);   // 按年龄升序排序
            }
        });
        for (Person p : personArrayList) {
            System.out.println(p.getAge() + "  " + p.getName());
        }
    }
    
	// 定义新的数据类型(用于排序)
       	// 1. implements Comparable
    	// 2. 重写 compareTo 方法
    static class Person implements Comparable {
        private String name;
        private int age;
        public Person() { }
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
        public String getName() {return name;}
        public void setName(String name) {this.name = name;}
        public int getAge() {return age;}
        public void setAge(int age) {this.age = age;}
        
        // 重写 compareTo 方法
        @Override
        public int compareTo(Person o) {
            // return this.getAge() - o.getAge();  // 按年龄升序排序
            
            // 自定义顺序
            int result = this.getAge() - o.getAge();
            if (result == 0) {
                result = this.getName().charAt(0) - o.getName().charAt(0);
            }
            return result;
        }
    }
}

Collection

  • public boolean add(E e)：把给定的对象添加到当前集合中
  • public void clear()：清空集合中所有的元素
  • public boolean remove(E e)：把给定的对象在当前集合中删除
  • public boolean contains(E e)：判断当前集合中是否包含给定的对象
  • public boolean isEmpty()：判断当前集合是否为空
  • public int size()：返回集合中元素的个数
  • public object[]toArray()：把集合中的元素，存储到数组中
Collection coll = new ArrayList<>();
// Collection coll = new Vector<>();
// Collection coll = new LinkedList<>();
// Collection coll = new HashSet<>();
// Collection coll = new LinkedHashSet<>();
// Collection coll = new TreeSet<>();

coll.add("a");
coll.add("b");
coll.add("c");
System.out.println(coll);       // [a, b, c]

boolean addResult = coll.add("d");  /// true
boolean removeResult = coll.remove("c"); /// true
System.out.println(coll.contains("c"));       // false
System.out.println(coll.size());       // 3
coll.clear();       // 清空
System.out.println(coll.isEmpty());     // false

for (String s:coll) {               // foreach
    System.out.println(s);
}
coll.clear();       // 清空
接口 使用场景
Collection 这是一个纯粹的接口，用于引用List、Set的实现对象。
List 如果需要保留存储顺序，并且允许保留重复元素，使用List接口的实现类。
如果查询较多，那么使用ArrayList。
如果存取较多，那么使用LinkedList。
如果需要线程安全，那么使用Vector。
Set 如果不需要保留存储顺序，并且需要去掉重复元素，使用Set接口的实现类。
如果我们需要将元素排序，那么使用TreeSet。
如果我们不需要排序，使用HashSet。HashSet比TreeSet效率高。
如果我们需要保留存储顺序，又要过滤重复元素，那么使用LinkedHashSet。
Map 如果需要保留key/value形式数据，使用Map接口的实现类。
如果我们需要将元素排序，那么使用TreeSet。
如果我们不需要排序，使用HashSet。Hashset比Treeset效率高。

ArrayList

数组长度不可改变，ArrayList长度可以变化

ArrayList底层使用数组完成的，所以查询快，增删慢

  • public E get(int index): 获取指定索引处的值

  • public E set(int index, E e) : 替换索引处的值，返回被替换的值

  • public E add(E e)：把给定的对象添加到当前集合中

  • public E remove(E e)：把给定的对象在当前集合中删除

  • public void clear()：清空集合中所有的元素

  • public boolean contains(E e)：判断当前集合中是否包含给定的对象

  • public boolean isEmpty()：判断当前集合是否为空

  • public int size()：返回集合中元素的个数

  • public object[]toArray()：把集合中的元素，存储到数组中

  • 遍历

    • 普通 for 循环

    • 增强 for 循环

    • forEach 遍历

    • 使用迭代器

      Iterator it = list.iterator();
while (it.hasNext()) {
	String s = it.next();
	System.out.println(s);
}
// 定义

ArrayList stringArrayList = new ArrayList<>(10);
// clone()
ArrayList stringArrayList2 = (ArrayList) stringArrayList.clone();

// ---------------------------------- 增 ----------------------------------

// add
stringArrayList.add("a");
stringArrayList.add("b");
stringArrayList.add(0,"e");
stringArrayList.add(1,"d");
stringArrayList.add("f");
stringArrayList.add("g");
stringArrayList.add("e");
System.out.println(stringArrayList);    // [e, d, a, b, f, g, e]

// Collections.addAll()
Collections.addAll(stringArrayList2,"a","b","c");

// ---------------------------------- 删 ----------------------------------

// remove(E e)  remove(int index) removeRange(int fromIndex, int toIndex)
stringArrayList.remove(3);  // 删除索引 3 处的值 b
stringArrayList.remove("a");  // 删除 a

// removeAll()
stringArrayList2.removeAll(stringArrayList2);

// clear()
stringArrayList2.clear();

// ---------------------------------- 改 ----------------------------------

// set(int index, E e)
stringArrayList.set(2, "F");        // f --> F

// Collections.sort(ArrayList)
Collections.sort(stringArrayList);

// sort(new Comparator() @override )
stringArrayList.sort(new Comparator() {
    @Override
    public int compare(String o1, String o2) {
        return o1.charAt(0) - o2.charAt(0);
    }
});

// ---------------------------------- 查 ----------------------------------

System.out.println(stringArrayList);    // [F, d, e, e, g]
// contains(E e)
System.out.println(stringArrayList.contains("b"));  // false
// get(int index)
System.out.println(stringArrayList.get(0));     // F
// isEmpty()
System.out.println(stringArrayList.isEmpty());  // false
// indexOf(E e)
System.out.println(stringArrayList.indexOf("e"));           // 2
// lastIndexOf(E e)
System.out.println(stringArrayList.lastIndexOf("e"));   // 3
// subList(int start, int end)
System.out.println(stringArrayList.subList(0,2));   // [F, d]
// size()
System.out.println(stringArrayList.size());     // 5


// forEach 遍历
stringArrayList.forEach(System.out::println);   // F, d, e, e, g

// 增强 for 循环
for (String s : stringArrayList) {          // F, d, e, e, g
    System.out.println(s);
}

// 迭代器 Iterator
Iterator it = stringArrayList.iterator();   // F, d, e, e, g
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

// 普通 for 循环
for (int i = 0; i < stringArrayList.size(); i++) {
    System.out.println(stringArrayList.get(i));

LinkedList

// 查询
public E element() : 返回此列表的第一个元素
public E getFirst() : 返回此列表的第一个元素
public E peek() : 返回此列表的第一个元素
public E peekFirst() : 返回此列表的第一个元素
public E getLast() : 返回此列表的最后一个元素
public E peekLast() : 返回此列表的最后一个元素
public E get(int index): 获取指定索引处的值
// 增加    
public E add(E e)：把给定的对象添加到当前集合中 
public E offer(E e)：把给定的对象添加到当前集合中 
public E add(int index, E e)：把给定的对象添加到当前集合指定索引处    
public E addFirst(E e) : 将指定元素插入此列表的开头
public E offerFirst(E e) : 将指定元素插入此列表的开头
public E push(E e) : 将元素推入此列表所表示的堆栈(开头)
public E addlast(E e) : 将指定元素添加到此列表的结尾
public E offerFirst(E e) : 将指定元素添加到此列表的结尾
// 删除  
public E remove()：把给定的对象在当前集合中删除
public E remove(int index)：把给定索引处的对象在集合中删除
pubLic E removeFirst() : 移除并返回此列表的第一个元素
pubLic E pop() : 从此列表所表示的堆栈处弹出一个元素
pubLic E poll() : 从此列表所表示的堆栈处弹出一个元素
pubLic E pollFirst() : 移除并返回此列表的第一个元素
public boolean remove(E e) : 删指定元素，并返回删除结果
public boolean removeFirstOccurrence(E e) : 删除第一次出现的元素，并返回删除结果
public boolean removeLastOccurrence(E e) : 删除最后一次出现的元素，并返回删除结果
pubLic E removeLast() : 移除并返回此列表的最后一个元素
pubLic E pollLast() : 移除并返回此列表的最后一个元素

public E set(int index, E e) : 替换索引处的值，返回被替换的值
public void clear()：清空集合中所有的元素
public boolean contains(E e)：判断当前集合中是否包含给定的对象
public boolean isEmpty()：判断当前集合是否为空
public int size()：返回集合中元素的个数

// 遍历：普通 for 循环、增强 for 循环、forEach 遍历、使用迭代器
// 定义
LinkedList stringLinkedList = new LinkedList<>();
LinkedList stringLinkedList3 = new LinkedList<>();

// ---------------------------------- 增 ----------------------------------
// add
stringLinkedList.add("a");
stringLinkedList.add("b");
stringLinkedList.add(0,"e");
stringLinkedList.add(1,"d");
stringLinkedList.add("f");
stringLinkedList.add("g");
stringLinkedList.add("e");

System.out.println(stringLinkedList);    // [e, d, a, b, f, g, e]

// ---------------------------------- 删 ----------------------------------

// remove(E e)  remove(int index) removeRange(int fromIndex, int toIndex)
stringLinkedList.remove(3);  // 删除索引 3 处的值 b
stringLinkedList.remove("a");  // 删除 a

// ---------------------------------- 改 ----------------------------------

// set(int index, E e)
stringLinkedList.set(2, "F");        // f --> F

// Collections.sort(LinkedList)
Collections.sort(stringLinkedList);

// sort(new Comparator() @override )
stringLinkedList.sort(new Comparator() {
    @Override
    public int compare(String o1, String o2) {
        return o1.charAt(0) - o2.charAt(0);
    }
});

// clone()
LinkedList stringLinkedList2 = (LinkedList) stringLinkedList.clone();
// clear()
stringLinkedList2.clear();
// Collections.addAll()
Collections.addAll(stringLinkedList2,"a","b","c");
// removeAll()
stringLinkedList2.removeAll(stringLinkedList2);

// ---------------------------------- 查 ----------------------------------
System.out.println(stringLinkedList);    // [F, d, e, e, g]
// contains(E e)
System.out.println(stringLinkedList.contains("b"));  // false
// get(int index)
System.out.println(stringLinkedList.get(0));     // F
// isEmpty()
System.out.println(stringLinkedList.isEmpty());  // false
// indexOf(E e)
System.out.println(stringLinkedList.indexOf("e"));           // 2
// lastIndexOf(E e)
System.out.println(stringLinkedList.lastIndexOf("e"));   // 3
// subList(int start, int end)
System.out.println(stringLinkedList.subList(0,2));   // [F, d]
// size()
System.out.println(stringLinkedList.size());     // 5

// forEach 遍历
stringLinkedList.forEach(System.out::println);   // F, d, e, e, g

// 增强 for 循环
for (String s : stringLinkedList) {          // F, d, e, e, g
    System.out.println(s);
}

// 迭代器 Iterator
Iterator it = stringLinkedList.iterator();   // F, d, e, e, g
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

// 普通 for 循环
for (int i = 0; i < stringLinkedList.size(); i++) {
    System.out.println(stringLinkedList.get(i));
}

// =================== 此处上方方法 linkedList 方法与ArrayList 相同 ===================

// -- 增：

// 正常插入(后边)
stringLinkedList3.add("add");
stringLinkedList3.offer("offer");
// 插在前边
stringLinkedList3.add(0,"add0");
stringLinkedList3.addFirst("addFirst");
stringLinkedList3.push("push");
stringLinkedList3.offerFirst("offerFirst");
// 插在后边
stringLinkedList3.addLast("addLast");
stringLinkedList3.offerLast("offerLast");
// 输出结果
System.out.println(stringLinkedList3);  // [offerFirst, push, addFirst, add0, add, offer, addLast, offerLast]
// 重新排序
Collections.sort(stringLinkedList3);
System.out.println("重新排序后： " + stringLinkedList3);

// -- 查：
System.out.println("element :\t" + stringLinkedList3.element());
System.out.println("getFirst :\t" + stringLinkedList3.getFirst());
System.out.println("peek :\t" + stringLinkedList3.peek());
System.out.println("peekFirst :\t" + stringLinkedList3.peekFirst());
System.out.println("getLast :\t" + stringLinkedList3.getLast());
System.out.println("peekLast :\t" + stringLinkedList3.peekLast());

// -- 删：

// 添加 addLast 使其重复
stringLinkedList3.clear();
Collections.addAll(stringLinkedList3,
	"a", "a", "b", "b", "c", "c", "d", "d", "e0", "e", "e1", "e", "e2", "e", "e3", "f", "f", "g", "g");
System.out.println("删除之前的顺序 " + stringLinkedList3);
// [a, a, b, b, c, c, d, d, e0, e, e1, e, e2, e, e3, f, f, g, g]

String s1 = stringLinkedList3.remove();		// 默认删除第一个元素
String s2 = stringLinkedList3.remove(0);	// 指定删除第一个元素
String s3 = stringLinkedList3.removeFirst();	// 删除第一个元素
String s4 = stringLinkedList3.pop();		// 弹出第一个元素
String s5 = stringLinkedList3.poll();		// 检索并删除第一个元素
String s6 = stringLinkedList3.pollFirst();	// 检索并删除第一个元素

System.out.println("第一次删除后的顺序 " + stringLinkedList3);       
// [d, d, e0, e, e1, e, e2, e, e3, f, f, g, g]
boolean s7 = stringLinkedList3.remove("e");		// 删除 e
boolean s8 = stringLinkedList3.removeFirstOccurrence("e");		// 删除第一次出现的 e
boolean s9 = stringLinkedList3.removeLastOccurrence("e");		// 删除最后一次出现的 e
System.out.println("第二次删除后的顺序 " + stringLinkedList3);   // [d, d, e0, e1, e2, e3, f, f, g, g]
String s10 = stringLinkedList3.removeLast();	// 删除最后一个元素
String s11 = stringLinkedList3.pollLast();		// 检索并删除最后一个元素
System.out.println("删除之后的顺序 " + stringLinkedList3); // [d, d, e0, e1, e2, e3, f, f]
System.out.printf("被删除的元素依次为：\n%s, %s, %s, %s, %s, %s, %s, %s, %s, %s, %s",
                  s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11);
// a, a, b, b, c, c, true, true, true, g, g

Vector

Vector是同步的， 如果不需要线程安全的实现，建议使用ArrayList代替Vector

  • public E get(int index): 获取指定索引处的值

  • public E set(int index, E e) : 替换索引处的值，返回被替换的值

  • public E add(E e)：把给定的对象添加到当前集合中

  • public E remove(E e)：把给定的对象在当前集合中删除

  • public void clear()：清空集合中所有的元素

  • public boolean contains(E e)：判断当前集合中是否包含给定的对象

  • public boolean isEmpty()：判断当前集合是否为空

  • public int size()：返回集合中元素的个数

  • public object[]toArray()：把集合中的元素，存储到数组中

  • 遍历

    • 普通 for 循环

    • 增强 for 循环

    • forEach 遍历

    • 使用迭代器

      Iterator it = list.iterator();
while (it.hasNext()) {
	String s = it.next();
	System.out.println(s);
}
// 与 ArrayList 方法相同

// 定义
Vector stringVector = new Vector<>();


// ---------------------------------- 增 ----------------------------------
// add
stringVector.add("a");
stringVector.add("b");
stringVector.add(0,"e");
stringVector.add(1,"d");
stringVector.add("f");
stringVector.add("g");
stringVector.add("e");

System.out.println(stringVector);    // [e, d, a, b, f, g, e]

// ---------------------------------- 删 ----------------------------------

// remove(E e)  remove(int index) removeRange(int fromIndex, int toIndex)
stringVector.remove(3);  // 删除索引 3 处的值 b
stringVector.remove("a");  // 删除 a

// ---------------------------------- 改 ----------------------------------

// set(int index, E e)
stringVector.set(2, "F");        // f --> F

// Collections.sort(stringVector)
Collections.sort(stringVector);

// sort(new Comparator() @override )
stringVector.sort(new Comparator() {
    @Override
    public int compare(String o1, String o2) {
        return o1.charAt(0) - o2.charAt(0);
    }
});

// clone()
Vector stringVector1 = (Vector) stringVector.clone();
// clear()
stringVector1.clear();
// Collections.addAll()
Collections.addAll(stringVector1,"a","b","c");
// removeAll()
stringVector1.removeAll(stringVector1);

// ---------------------------------- 查 ----------------------------------
System.out.println(stringVector);    // [F, d, e, e, g]
// contains(E e)
System.out.println(stringVector.contains("b"));  // false
// get(int index)
System.out.println(stringVector.get(0));     // F
// isEmpty()
System.out.println(stringVector.isEmpty());  // false
// indexOf(E e)
System.out.println(stringVector.indexOf("e"));           // 2
// lastIndexOf(E e)
System.out.println(stringVector.lastIndexOf("e"));   // 3
// subList(int start, int end)
System.out.println(stringVector.subList(0,2));   // [F, d]
// size()
System.out.println(stringVector.size());     // 5

// forEach 遍历
stringVector.forEach(System.out::println);   // F, d, e, e, g

// 增强 for 循环
for (String s : stringVector) {          // F, d, e, e, g
    System.out.println(s);
}

// 迭代器 Iterator
Iterator it = stringVector.iterator();   // F, d, e, e, g
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

// 普通 for 循环
for (int i = 0; i < stringVector.size(); i++) {
    System.out.println(stringVector.get(i));

Stack

注意：遍历栈，栈内元素不会减少，出栈才会减少

Stack stack = new Stack();

stack.add("a");
stack.add("e");
stack.add("d");
stack.add("c");
stack.add("b");
stack.addElement("E");
stack.push("p");
stack.add(0,"F"); // 栈底索引是 0

stack.forEach(System.out::print);
System.out.println();

System.out.println(stack.size());
System.out.println(stack.isEmpty());
System.out.println(stack.empty());
System.out.println(stack.peek());
System.out.println(stack.get(0));
System.out.println(stack.indexOf("p"));

// 从 1 开始, 返回距堆栈顶部最靠近堆栈顶部的距离; 堆栈中最上面的项目被认为是距离 1
System.out.println(stack.search("F"));  


stack.set(1, "m");
System.out.println(stack.pop());
stack.remove("a");

System.out.println(stack);
for (int i = 0; i < stack.size(); i++) {
    System.out.println(stack.get(i));
}

// 迭代器 Iterator 循环
Iterator it = stack.iterator();   // F, d, e, e, g
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

// 排序
stack.sort(new Comparator() {
    @Override
    public int compare(String o1, String o2) {
        return o1.charAt(0) - o2.charAt(0);
    }
});

for (String s : stack) {
    System.out.println(s);
}

stack.clear();
stack.setSize(1);
System.out.println(stack.get(0) == null);
// System.out.println(stack.get(1) == null);        // 报错

HashSet

HashSet数据结构：把元素进行分组，相同哈希值的元素是一组，链表/红黑树把相同哈希值的元素连接到一起

HashSet 若需要同步，可使用 Set s = Collections.synchronizedSet(new HashSet(...)); (多线程)

HashSet hashSet = new HashSet(16, 0.75F);
HashSet hashSet2 = new HashSet();

// ---------------------------------- 增 ----------------------------------
// add
hashSet.add("a");
hashSet.add("b");
hashSet.add("f");
hashSet.add("g");
hashSet.add("e");

// Collections.addAll()
Collections.addAll(hashSet2,"a","b","c");   // [a, b, c]
System.out.println(hashSet);    // [a, b, e, f, g]

// ---------------------------------- 删 ----------------------------------
hashSet.remove("a");  // 删除 a
// removeAll()
hashSet2.removeAll(hashSet2);   // []
// clear()
hashSet2.clear();   // []

// ---------------------------------- 查 ----------------------------------
System.out.println(hashSet);    // [b, e, f, g]
// contains(E e)
System.out.println(hashSet.contains("b"));  // true
// isEmpty()
System.out.println(hashSet.isEmpty());  // false
// size()
System.out.println(hashSet.size());     // 4

// forEach 遍历
hashSet.forEach(System.out::println);   // b e f g

// 增强 for 循环
for (String s : hashSet) {          // b e f g
    System.out.println(s);
}

// 迭代器 Iterator
Iterator it = hashSet.iterator();   // b e f g
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

// 不可以使用普通的 fori 循环，因为 set 没有顺序

LinkedHashSet

处理 Set 时，可将其有序化 Set copy = new LinkedHashSet(s);

// 以下使用方法均与 HashSet 相同

LinkedHashSet linkedHashSet = new LinkedHashSet<>();
LinkedHashSet linkedHashSet2 = new LinkedHashSet<>();

// ---------------------------------- 增 ----------------------------------
// add
linkedHashSet.add("a");
linkedHashSet.add("b");
linkedHashSet.add("f");
linkedHashSet.add("g");
linkedHashSet.add("e");

// Collections.addAll()
Collections.addAll(linkedHashSet2,"a","b","c");   // [a, b, c]
System.out.println(linkedHashSet);    // [a, b, e, f, g]

// ---------------------------------- 删 ----------------------------------
linkedHashSet.remove("a");  // 删除 a
// removeAll()
linkedHashSet2.removeAll(linkedHashSet2);   // []
// clear()
linkedHashSet2.clear();   // []

// ---------------------------------- 查 ----------------------------------
System.out.println(linkedHashSet);    // [b, e, f, g]
// contains(E e)
System.out.println(linkedHashSet.contains("b"));  // true
// isEmpty()
System.out.println(linkedHashSet.isEmpty());  // false
// size()
System.out.println(linkedHashSet.size());     // 4

// forEach 遍历
linkedHashSet.forEach(System.out::println);   // b e f g

// 增强 for 循环
for (String s : linkedHashSet) {          // b e f g
    System.out.println(s);
}

// 迭代器 Iterator
Iterator it = linkedHashSet.iterator();   // b e f g
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

TreeSet

// 以下使用方法均与 HashSet 相同

TreeSet treeSet = new TreeSet<>();
TreeSet treeSet2 = (TreeSet) treeSet.clone();

// ---------------------------------- 增 ----------------------------------
// add
treeSet.add("a");
treeSet.add("b");
treeSet.add("f");
treeSet.add("g");
treeSet.add("e");

// Collections.addAll()
Collections.addAll(treeSet2,"a","b","c");   // [a, b, c]
System.out.println(treeSet);    // [a, b, e, f, g]

// ---------------------------------- 删 ----------------------------------
treeSet.remove("a");  // 删除 a
// removeAll()
treeSet2.removeAll(treeSet2);   // []
// clear()
treeSet2.clear();   // []

// ---------------------------------- 查 ----------------------------------
System.out.println(treeSet);    // [b, e, f, g]
// contains(E e)
System.out.println(treeSet.contains("b"));  // true
// isEmpty()
System.out.println(treeSet.isEmpty());  // false
// size()
System.out.println(treeSet.size());     // 4

// forEach 遍历
treeSet.forEach(System.out::println);   // b e f g

// 增强 for 循环
for (String s : treeSet) {          // b e f g
    System.out.println(s);
}

// 迭代器 Iterator
Iterator it = treeSet.iterator();   // b e f g
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

Map

public V put(K key，v value)：把指定的键与指定的值添加到Map集合中。
public v remove(object key)：把指定的键所对应的键值对元素在Map集合中删除，返回被删除元素的值。
public v get(object key)根据指定的键，在Map集合中获取对应的值。
public boolean containsKey(object key) 检查 map 中是否含有键 key
public Setkeyset()：获取Map集合中所有的键，存储到Set集合中。
public Set> entrySet()：获取到Map集合中所有的键值对对象的集合(Set集合)。
public void clear(): 清空 map

    Map map = new HashMap<>();
Map map2 = new HashMap<>();


map.put("1", "a");
map.put("2", "b");
map.put("3", "c");
System.out.println(map);    // {1=a, 2=b, 3=c}
String s = map.put("3", "d");
System.out.println(map);    // {1=a, 2=b, 3=d}
System.out.println(s);      // c
System.out.println(map.get("1"));   // a

map.remove("1");
System.out.println(map);    // {2=b, 3=d}

map2.put("Kite", 15);
map2.put("Lee", 17);

System.out.println(map2.keySet());  // [Kite, Lee]
System.out.println(map2);               // {Kite=15, Lee=17}
Integer n1 = map2.remove("Kite");
System.out.println(map2);           // {Lee=17}
System.out.println(n1);         // 15

Integer n2 = map2.remove("KK");
// int n2 = map2.remove("KK");          // 使用 int 会自动拆箱，会报错 NullPointerException (空指针异常)
System.out.println(map2);           // {Lee=17}
System.out.println(n2);             // null

boolean b = map2.containsKey("Kite");
System.out.println(b);


map2.clear();
map2.put("Kite", 15);
map2.put("Lee", 17);
map2.put("Alice", 25);

System.out.println("======================");
Set set = map2.keySet();
Iterator it = set.iterator();
while (it.hasNext()) {
    String key = it.next();
    Integer value = map2.get(key);
    System.out.println(key + " " + value);
}
System.out.println("======================");
for (String key : set) {
    Integer value = map2.get(key);
    System.out.println(key + " " + value);
}

System.out.println("======================");
Set set2 = map2.keySet();
for (String key : set2) {
    Integer value = map2.get(key);
    System.out.println(key + " " + value);
}

// \\ // \\ // \\ // \\ EntrySet // \\ // \\ // \\  // \\ 

System.out.println("- - - - - - - - - - - - - - !!!!!!");

Set> sets = map2.entrySet();

Iterator> its = sets.iterator();
while (its.hasNext()) {
    Map.Entry entry = its.next();
    String keys = entry.getKey();
    Integer values = entry.getValue();
    System.out.println(keys + "  " + values);
}

for (Map.Entry entry : sets) {
    String keys = entry.getKey();
    Integer values = entry.getValue();
    System.out.println(keys + "  " + values);
}

HashMap

package com.lee.method;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

public class Demo11HashMap {
    public static void main(String[] args) {

        HashMap map = new HashMap<>();


        map.put("北京", new Person("Kite",25));
        map.put("大连", new Person("Lee",18));
        map.put("菏泽", new Person("Alice",36));
        map.put("南京", new Person("Bob",49));
        map.put("天津", new Person("Candy",64));
        map.put("苏州", new Person("David",88));
        map.put("北京", new Person("Lin",25));

        Set set = map.keySet();
        for (String key : set) {
            Person value = map.get(key);
            System.out.println(key + " " + value);
        }

        System.out.println("=====================================");

        HashMap map2 = new HashMap<>();

        map2.put(new Person("Kite",25), "北京");
        map2.put(new Person("Lee",18), "大连");
        map2.put(new Person("Alice",36), "菏泽");
        map2.put(new Person("Bob",49), "南京");
        map2.put(new Person("Candy",64), "天津");
        map2.put(new Person("David",88), "苏州");
        // 不重写 equals 和 hashcode 方法，西安和北京就会共存
        map2.put(new Person("Kite",25), "西安");


        Set> set2 = map2.entrySet();
        for (Map.Entry entry : set2) {
            Person key2 = entry.getKey();
            String value2 = entry.getValue();
            System.out.println(key2 + " " + value2);
        }

        System.out.println("---------------------------");
        Set set22 = map2.keySet();
        for (Person key22 : set22) {
            String value22 = map2.get(key22);
            System.out.println(key22 + " " + value22);
        }
    }
}

class Person {

    private String name;
    private int age;

    public Person() { }
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    // 不重写 equals 和 hashcode 方法，西安和北京就会共存
//    @Override
//    public boolean equals(Object o) {
//        if (this == o) return true;
//        if (o == null || getClass() != o.getClass()) return false;
//        Person person = (Person) o;
//        return age == person.age && name.equals(person.name);
//    }
//
//    @Override
//    public int hashCode() {
//        return Objects.hash(name, age);
//    }

    // 不重写 toString 方法，打印 Person 只能输出地址值
    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

LinkedHashMap

LinkedHashMap map = new LinkedHashMap<>();

map.put("a", "a");
map.put("b", "b");
map.put("c", "c");
map.put("a", "d");

System.out.println(map);    // {a=d, b=b, c=c}  不允许重复, 有序

TreeMap

Hashtable

Hashtable 是线程安全的(单线程)

Hashtable 已经逐渐淘汰，它的子类 Properties 还在被使用(Properties 是唯一一个与 IO 相结合的集合)

// Hashtable 不可以存储 null  (前文集合均可)

Hashtable table = new Hashtable<>();
// 以下三个全都是空指针异常 NullPointerException 
table.put(null, "a");   
table.put("a", null);
table.put(null, null);

BlockingQueue

方式 抛出异常 有返回值 阻塞等待 超时等待
添加 add("a") offer("a") put("a") offer("a",2,TimeUnit.SECONDS)
移除 remove() poll() take() poll(2,TimeUnit.SECONDS)
检测队列首尾 element() peek() - - 
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.TimeUnit;

public class BlockQueueTest {
    public static void main(String[] args) throws InterruptedException {
        System.out.println("############### test01() #####################");
        test01();
        System.out.println("############### test02() #####################");
        test02();
        System.out.println("############### test03() #####################");
        test03();
        System.out.println("############### test04() #####################");
        test04();}

/*
 会报出异常：
    1. // Queue full
    2. // java.util.NoSuchElementException
 */
public static void test01() {

    ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
    System.out.println(blockingQueue.add("a"));     // true
    System.out.println(blockingQueue.add("b"));     // true
    System.out.println(blockingQueue.add("c"));     // true
    // System.out.println(blockingQueue.add("d"));  // Queue full

    // 队首
    System.out.println(blockingQueue.element());    // a
    System.out.println("===========================");

    System.out.println(blockingQueue.remove());     // a
    System.out.println(blockingQueue.remove());     // b
    System.out.println(blockingQueue.remove());     // c
    // System.out.println(blockingQueue.remove());  // java.util.NoSuchElementException

}

/*
 有返回值，没有异常
 */
public static void test02() {

    ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
    System.out.println(blockingQueue.offer("a"));     // true
    System.out.println(blockingQueue.offer("b"));     // true
    System.out.println(blockingQueue.offer("c"));     // true
    System.out.println(blockingQueue.offer("d"));     // false

    System.out.println(blockingQueue.peek());    // a
    System.out.println("===========================");

    System.out.println(blockingQueue.poll());       // a
    System.out.println(blockingQueue.poll());       // b
    System.out.println(blockingQueue.poll());       // c
    System.out.println(blockingQueue.poll());       // null

}

/*
  阻塞等待(一直阻塞)
 */
public static void test03() throws InterruptedException {

    ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
    blockingQueue.put("a");     // void
    blockingQueue.put("b");     // void
    blockingQueue.put("c");     // void
    // blockingQueue.put("d");     // 一直阻塞，没有异常

    System.out.println("===========================");

    System.out.println(blockingQueue.take());       // a
    System.out.println(blockingQueue.take());       // b
    System.out.println(blockingQueue.take());       // c
    // System.out.println(blockingQueue.take());       // 一直阻塞，没有异常

}

/*
 等待2秒，超时结束等待，有返回值
 */
public static void test04() throws InterruptedException {

    ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
    System.out.println(blockingQueue.offer("a"));     // true
    System.out.println(blockingQueue.offer("b"));     // true
    System.out.println(blockingQueue.offer("c"));     // true
    System.out.println(blockingQueue.offer("d",2, TimeUnit.SECONDS)); // false

    System.out.println("===========================");

    System.out.println(blockingQueue.poll());       // a
    System.out.println(blockingQueue.poll());       // b
    System.out.println(blockingQueue.poll());       // c
    System.out.println(blockingQueue.poll(2,TimeUnit.SECONDS));       // null

}

}

补充：

JDK9 集合添加优化

  • of 方法只适用于 List 接口, Set 接口，Map 接口，不适用于接接口的实现类
  • of 方法的返回值是一个不能改变的集合，集合不能再使用 add，put 方法添加元素，会抛出异常
  • Set 接口和 Map 接口在调用 of 方法的时候，不能有重复的元素，否则会抛出异常

树

树的特点:

  • 每个结点有零个或多个子结点
  • 没有父结点的结点为根结点
  • 每一个非根结点只有一个父结点
  • 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树

树的相关术语：

  • 结点的度：一个结点含有的子树的个数称为该结点的度
  • 叶结点：度为0的结点称为叶结点，也可以叫做终端结点
  • 分支结点：度不为0的结点称为分支结点，也可以叫做非终端结点
  • 结点的层次：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
  • 结点的层序编号：将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数
  • 树的度：树中所有结点的度的最大值
  • 树的高度(深度)：树中结点的最大层次
  • 森林：m(m>=0)个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树
  • 孩子结点：一个结点的直接后继结点称为该节点的孩子结点
  • 双亲结点(父结点)：一个结点的直接前驱称为该节点的双亲结点
  • 兄弟结点：同一双亲结点的孩子结点间互称兄弟结点
  • 二叉树：度不超过2的树(每个结点最多有两个子结点)
  • 满二叉树：一个二叉树每一个层的结点树都达到最大值
  • 完全二叉树：叶结点只能出现在最下层或次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二叉树的基础遍历

  • 前序遍历：先访问根结点，然后再访问左子树，最后访问右子树
  • 中序遍历：先访问左子树，中间访问根节点，最后访问右子树
  • 后序遍历：先访问左子树，再访问右子树，最后访问根节点

平衡树

2-3查找树

2-3查找树插入

  • 2-3查找树：一颗 2-3 查找树要么为空，要么满足下面两个要求：
    • 2-结点：含有一个键(及其对应的值)和两条链，左连接指向2-3查找树中的键都小于该结点，右链指向的2-3树中的键都大于该结点。
    • 3-结点：含有两个键(及其对应的值)和三条链，左链指向2-3树中的键都小于该结点，中链指向的2-3树中的键都位于该结点的两个键之间，右链指向的2-3树中的键都大于该结点。

1. 向2-结点中插入新键

2. 向一颗只含有一个3-结点的树中插入新键

3. 向一个父结点为2-结点的3-结点中插入新键

4. 向一个父结点为3-结点的3-结点中插入新键

5. 分解根结点

2-3查找树的性质

通过对2-3树插入操作的分析，我们发现在插入的时候，2-3树需要做一些局部的变换来保持2-3树的平衡。
一棵完全平衡的2-3树具有以下性质：

  1. 任意空链接到根结点的路径长度都是相等的。
  2. 4-结点变换为3-结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1。
  3. 2-3树与普通二叉查找树最大的区别在于，普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。

红黑树

红黑树的定义

红黑树是含有红黑链接并满足下列条件的二叉查找树：

  1. 红链接均为左链接；
  2. 没有任何一个结点同时和两条红链接相连；
  3. 该树是完美黑色平衡的，即任意空链接到根结点的路径的黑链接数量相同

下面是红黑树与2-3树的对应关系：

平衡化

在对红黑树进行一些增删改查的操作店，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。

左旋

当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。前提：当前结点为h，它的右子结点为×；

左旋过程：

  1. 让x的左子结点变为h的右子结点：h.right=x.left
  2. 让h成为x的左子结点：x.left=h;
  3. 让h的color属性变为x的color属性值：x.color=h.color;
  4. 让h的color属性变为RED：h.color=true

右旋

当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋前提：当前结点为h，它的左子结点为x；

右旋过程：

  1. 让x的右子结点成为h的左子结点：h.left=x.right;
  2. 让h成为x的右子结点：x.right=h；
  3. 让x的color变为h的color属性值：x.color=h.colorp
  4. 让h的color为RED

红黑树插入

1. 向单个2-结点中插入新键

新键小于当前结点

新键大于当前结点

2. 向底部的2-结点插入新键

3. 颜色反转

4. 向一颗双键树(即一个3-结点)中插入新键

新键大于原树中的两个键

(若有指向 b 的链接，要变为红色)

新键小于原树中的两个键

新键介于原树中的两个键之间

5. 根结点的颜色总是黑色

每次插入操作后，都需要把根结点的颜色设置为黑色

6. 向树底部的3-结点插入新键

假设在树的底部的一个3-结点下加入一个新的结点。前面我们所讲的3种情况都会出现。指向新结点的链接可能是3-结点的右链接(此时我们只需要转换颜色即可)，或是左链接(此时我们需要进行右旋转然后再转换)，或是中链接(此时需要先左旋转然后再右旋转，最后转换颜色)。颜色转换会使中间结点的颜色变红，相当于将它送入了父结点。这意味着父结点中继续插入一个新键，我们只需要使用相同的方法解决即可，直到遇到一个2-结点或者根结点为止。

B树

B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。

B树的特性

B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M，来
构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：

  1. 每个结点最多有M-1个key，并且以升序排列；
  2. 每个结点最多能有M个子结点；
  3. 根结点至少有两个子结点；

B树存储数据

B树在磁盘中的应用

磁盘用磁头来读写存储在盘片表面的位，而磁头连接到一个移动臂上，移动臂沿着盘片半径前后移动，可以将磁头定位到任何磁道上，这称之为寻道操作。一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到该位的值，也可以修改值。对磁盘的访问时间分为寻道时间，旋转时间，以及传送时间。
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘1/0，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，因此预读可以提高/O效率。
页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(1024个字节或其整数倍)，预读的长度一般为页的整倍数。主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
文件系统的设计者利用了磁盘预读原理，将一个结点的大小设为等于一个页(1024个字节或其整数倍)，这样每个结点只需要一次I/O
就可以完全载入。那么3层的B树可以容纳1024 * 1024 * 1024差不多10亿个数据，如果换成二叉查找树，则需要30层！假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在10亿个数据中查找目标值，只需要小于3次硬盘读取就可以找到目标值，但红黑树需要小于30次，因此B树大大提高了IO的操作效率。

B+树

B+树的特性

B+树是对B树的一种变形树，它与B树的差异在于：

  1. 非叶结点仅具有索引作用，也就是说，非叶子结点只存储key，不存储value
  2. 树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据

B+树存储数据

B+树与B树的区别

B+树的优点在于：

  1. 由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key
  2. B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并相连，所以便于
    区间查找和搜索。而B树则需要进行每一层的递归遍历

B树的优点在于：
由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value

B+树在数据库中的应用

未建立主键索引查询

执行select * from user where id = 18需要从第一条数据开始，一直查询到第六条，发现id = 18，此时才能查询出目标结果，共需要比较6次

建立主键索引查询

区间查询

执行select*from user where id>=12 and id<=18,如果有了索引，由于B+树的叶子结点形成了一个有序链表，所以我们只需要找到id为12的叶子结点，按照遍历链表的方式顺序往后查即可，效率非常高。

并查集

并查集是一种树型的数据结构，并查集可以高效地进行如下操作：

  • 查询元素p和元素g是否属干同一组
  • 合并元素p和元素q所在的组

并查集结构

并查集也是一种树型结构，但这棵树跟我们之前讲的二叉树、红黑树、B树等都不一样，这种树的要求比较简单：

  1. 每个元素都唯一的对应一个结点；

  2. 每一组数据中的多个元素都在同一颗树中；

  3. 一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系；

  4. 元素在树中并没有子父级关系的硬性要求；

并查集API设计

UF_Tree 算法优化

元素 p 所在分组的标识符

public int find(int p) {
    while (true) {
        if (p == eleAndGroup[p]) {
            return p;
        }
        p = eleAndGroup[p];
    }
}

union (int p, int q) 合并方法实现

public void union(int p, int q) {
    // 找到 p 元素和 q 元素所在组对应的树的根结点
    int pRoot = find(p);
    int qRoot = find(q);

    // 如果 p 和 q 已经在同一分组，则不需要合并了
    if (pRoot == qRoot) {
        return;
    }
    // 让 p 所在的树的根结点的父结点为 q 所在树的根结点即可
    eleAndGroup[pRoot] = qRoot;

    // 租的数量 -1
    this.count--;
}
  1. 找到p元素所在树的根结点
  2. 找到q元素所在树的根结点
  3. 如果p和q已经在同一个树中，则无需合并；
  4. 如果p和q不在同一个分组，则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可；
  5. 分组数量-1

优化后的性能分析

我们优化后的算法union，如果要把并查集中所有的数据连通，仍然至少要调用N-1次union方法，但是，我们发现union方法中已经没
有了for循环，所以union算法的时间复杂度由O(N2)变为了O(N)。

但是这个算法仍然有问题，因为我们之前不仅修改了union算法，还修改了find算法。我们修改前的find算法的时间复杂度在任何情况下都为O(1)，但修改后的find算法在最坏情况下是O(N)：

在 union 方法中调用了 find 方法，所以在最坏情况下 union 算法的时间复杂度仍然为O(N^2)

路径压缩

public void union(int p, int q) {
        // 找到 p 元素和 q 元素所在组对应的树的根结点
        int pRoot = find(p);
        int qRoot = find(q);
        // 如果 p 和 q 已经在同一分组，则不需要合并了
        if (pRoot == qRoot) {
            return;
        }
     
//        // 让 p 所在的树的根结点的父结点为 q 所在树的根结点即可
//        eleAndGroup[pRoot] = qRoot;
     
        // 判断 pRoot 对应的树大还是 qRoot 对应树大，最终需要把较小的树合并到较大的树中
        if (sz[pRoot] < sz[qRoot]) {
            eleAndGroup[pRoot] = qRoot;
            sz[qRoot] += pRoot;
        } else {
            eleAndGroup[qRoot] = pRoot;
            sz[pRoot] += qRoot;
        }
        // 租的数量 -1
        this.count--;
    }

案例-畅通工程

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府”畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路可达即可)。问最少还需要建设多少条道路？

解题思路：

  1. 创建一个并查集UF_Tree_Weighted(20);
  2. 分别调用union(0,1),union(6,9)union(3,8),union(5,11),union(2,12),union(6,10),union(4,8),表示已经修建好的道路把对应的城市
    连接起来；
  3. 如果城市全部连接起来，那么并查集中剩余的分
锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

相关文章