當(dāng)前位置：首頁(yè) > 编程语言 > java >内容正文

java

CoreJava 笔记总结-第九章集合

發(fā)布時(shí)間：2023/12/4 java 35 豆豆

生活随笔收集整理的這篇文章主要介紹了 CoreJava 笔记总结-第九章集合小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

第九章集合

文章目錄

第九章集合
- `Java`集合框架
- - 集合接口與實(shí)現(xiàn)分離
  - `Collection`接口
  - 迭代器
  - 泛型實(shí)用方法
- 集合框架中的接口
- 具體集合
- - 鏈表
  - 數(shù)組列表
  - 散列集
  - 樹(shù)集
  - 優(yōu)先隊(duì)列
- 映射
- - 映射的基本操作
  - 更新映射條目
  - 映射視圖
  - 弱散列試圖
  - 鏈接散列集與映射
  - 枚舉集與映射
  - 標(biāo)識(shí)散列映射
- 視圖與包裝器
- - 小集合
  - 子范圍
  - 不可修改視圖
  - 同步視圖
- 算法
- - 為什么使用泛型算法
  - 排序與混排
  - 二分查找
  - 簡(jiǎn)單算法
  - 批操作
  - 集合和數(shù)組的轉(zhuǎn)換
- 遺留的集合
- - 棧
  - 位集

Java集合框架

集合接口與實(shí)現(xiàn)分離

隊(duì)列,先進(jìn)先出
隊(duì)列接口最簡(jiǎn)形式:

public interface Queue<E>{void add(E element);E remove();int size(); }

隊(duì)列實(shí)現(xiàn): 1. 使用循環(huán)數(shù)組 2. 使用鏈表
public class CirclarArrayQueue<E> implements Queue<E>{private int head;private int tail;CirclarArrayQueue(int capacity);public void add(E element);public E remove();public int size();private E[] element; }

Collection接口

集合類的基本接口是Collection接口

public interface Collection<E>{boolean add(E element);Iterator<E> iterator();... }

迭代器

Iterator接口包含

public interface Iterator<E> {E next();boolean hasNext();void remove();default void forEachRemaining(Consumer<? super E> action); }

訪問(wèn)集合中的元素

Collection<String> c = ...; Iterator<String> iter = c.iterator(); while(iter.hasNext()){String element = iter.next();... }或者直接for(String elem: c){...}

for-each循環(huán)可以處理任何實(shí)現(xiàn)了Iterable接口的對(duì)象

public interface Iterable<E>{Iterator<E> iterator(); }

Collection接口擴(kuò)展了Iterable接口,所以標(biāo)準(zhǔn)庫(kù)中任何集合都有可以使用for-each循環(huán)

也可以forEachRemaining(element->do sth. with element)對(duì)于迭代器每個(gè)元素調(diào)用這個(gè)lambda表達(dá)式直到?jīng)]有元素為止
java迭代器位于兩個(gè)元素之間,調(diào)用next,迭代器越過(guò)下一個(gè)元素, 并且返回剛剛越過(guò)元素的引用
Iterator接口的remove方法將刪除上次調(diào)用next方法返回的元素

Iterator<Stirng> it = c.iterator(); it.next(); it.remove(); //刪除該字符串的第一個(gè)元素

remove方法調(diào)用之前沒(méi)有調(diào)用next方法會(huì)拋出IllegalStateException異常

泛型實(shí)用方法

P372

集合框架中的接口

集合中有兩個(gè)基本接口Collection, Map
在集合中插入元素boolean add(E element); 映射包含鍵值對(duì),插入用V put(K key, V value);
從映射中讀取值V get(K key);
List是一個(gè)有序集合,可以用迭代器訪問(wèn),可以隨機(jī)訪問(wèn)(訪問(wèn)整數(shù)索引)
Set接口等同于Colletion接口,其add方法不允許增加重復(fù)元素, hasCode保證包含相同元素得到相同的散列碼,equals相等

具體集合

鏈表

java中, 所有鏈表實(shí)際上都是雙向鏈接的
先添加3個(gè)元素, 再將第二個(gè)元素刪除
var a = new LinkedList<String>(); a.add("Amy"); a.add("Carl"); a.add("Erica"); Iterator<Stirng> iter = staff.iterator(); String first = iter.next(); String second = iter.next(); iter.remove();
鏈表和泛型集合之間的區(qū)別: 鏈表是一個(gè)有序集合, LinkList.add方法將對(duì)象添加到鏈表尾部
反向遍歷鏈表: LinkIterator接口: E previous(); boolean hasPrevious();
為了避免并發(fā)修改異常:可以根據(jù)需要為集合關(guān)聯(lián)過(guò)多個(gè)迭代器,但是迭代器只能讀取集合
LinkedList類提供了get方法訪問(wèn)某個(gè)特定元素,但是效率不高

package chapter9_set.linkedList;import java.util.*;public class LinkedListTest {public static void main(String[] args) {var a = new LinkedList<String>();a.add("Amy");a.add("Carl");a.add("Erica");var b = new LinkedList<String>();b.add("Bob");b.add("Doug");b.add("Frances");b.add("Gloria");//merge the words from b into aListIterator<String> aIter = a.listIterator();Iterator<String> bIter = b.iterator();while (bIter.hasNext()) {if(aIter.hasNext()) aIter.next();aIter.add(bIter.next());}/*for (String s : b) {if (aIter.hasNext()) aIter.next();aIter.add(s);}*/System.out.println(a);//remove every second word from bbIter = b.iterator();while (bIter.hasNext()) {bIter.next();if (bIter.hasNext()) {bIter.next();bIter.remove();}}System.out.println(b);//bulk operation: remove all words in b from aa.removeAll(b);System.out.println(a);} } /* Connected to the target VM, address: '127.0.0.1:54324', transport: 'socket' [Amy, Bob, Carl, Doug, Erica, Frances, Gloria] [Bob, Frances] [Amy, Carl, Doug, Erica, Gloria] Disconnected from the target VM, address: '127.0.0.1:54324', transport: 'socket' */

數(shù)組列表

ArrayList封裝了一個(gè)動(dòng)態(tài)再分配的對(duì)象數(shù)組
Vector類創(chuàng)建動(dòng)態(tài)數(shù)組,其所有方法都是同步的,如果只是一個(gè)線程的話用ArrayList

散列集

散列表用鏈表數(shù)組實(shí)現(xiàn)
每個(gè)列表被稱為桶,計(jì)算散列碼,與桶的總數(shù)取余,得到的結(jié)果就是保存這個(gè)元素桶的索引
裝填因子(一般0.75)確定何時(shí)對(duì)于這個(gè)表進(jìn)行再散列

樹(shù)集

樹(shù)集是一個(gè)有序集合
任意順序插入,但是遍歷時(shí),值按照排序過(guò)后的方式呈現(xiàn)

package chapter9_set.treeSet;import java.util.*;public class TreeSetTest {public static void main(String[] args) {var parts = new TreeSet<Item>();parts.add(new Item("Toaster", 1234));parts.add(new Item("Widget", 4562));parts.add(new Item("Modem", 9912));System.out.println(parts);var sortByDescription = new TreeSet<Item>(Comparator.comparing(Item::getDescription));sortByDescription.addAll(parts);System.out.println(sortByDescription);} }package chapter9_set.treeSet;import java.util.*;public class Item implements Comparable<Item> {private String description;private int partNumber;public Item(String aDescription, int aPartNumber) {description = aDescription;partNumber = aPartNumber;}public String getDescription() {return description;}public String toString() {return "[description = " + description + ", partNumber = " + partNumber + " ]";}public boolean equals(Object otherObject) {if (this == otherObject) return true;if(otherObject == null) return false;if(getClass() != otherObject.getClass()) return false;var other = (Item) otherObject;return Objects.equals(description, other.description) && partNumber == other.partNumber;}public int hasCode() {return Objects.hash(description, partNumber);}public int compareTo(Item other) {int diff = Integer.compare(partNumber, other.partNumber);return diff != 0 ? diff : description.compareTo(other.description);} }

優(yōu)先隊(duì)列

優(yōu)先隊(duì)列中元素可以按照任意順序插入,但會(huì)按照有序順序檢索
只要調(diào)用remove方法,總會(huì)獲得當(dāng)前優(yōu)先隊(duì)列中最小的元素
優(yōu)先隊(duì)列使用堆,其添加和刪除操作將最小元素移動(dòng)到根
這里迭代并沒(méi)有按照順序來(lái)訪問(wèn)元素,刪除操作卻總是刪除剩余元素中最小的那個(gè)

package chapter9_set.priorityQueue_Heap;import java.util.*; import java.time.*;public class PriorityQueueTest {public static void main(String[] args) {var pq = new PriorityQueue<LocalDate>();pq.add(LocalDate.of(1906, 12, 9));pq.add(LocalDate.of(1806, 12, 9));pq.add(LocalDate.of(1206, 12, 9));pq.add(LocalDate.of(1826, 12, 9));pq.add(LocalDate.of(1826, 2, 9));pq.add(LocalDate.of(1826, 1, 10));System.out.println("Iterating over elements...");for (LocalDate date : pq) {System.out.println(date);}System.out.println("Removing elements...");while (!pq.isEmpty())System.out.println(pq.remove());} }

映射

map映射存放鍵值對(duì)

映射的基本操作

HashMao, TreeMap: 散列映射稍快,不需要按照有序順序訪問(wèn)鍵選擇散列映射
鍵必須唯一
remove刪除給定鍵對(duì)應(yīng)的元素, size方法返回映射中元素?cái)?shù)
迭代處理映射的鍵和值,使用forEach方法

Map<String, Integer>scores = ...; int score = scores.getOrDeaufault(id, 0);scores.forEach((k. v) -> System.out.println("key" + k + ", value=" + v)); //lambda package chapter9_set.map;import java.util.HashMap;public class MapTest {public static void main(String[] args) {var staff = new HashMap<String, Employee>();staff.put("123-15-1555", new Employee("Amy Lee"));staff.put("157-58-9999", new Employee("Harry Hacker"));staff.put("154-87-9999", new Employee("Ou Kunnan"));staff.put("548-84-1111", new Employee("Da Bendan"));System.out.println(staff.toString());//System.out.println(staff);staff.remove("123-15-1555");staff.put("999-99-9999", new Employee("Hee"));System.out.println(staff.get("999-99-9999"));staff.forEach((key, value) -> System.out.println("key=" + key + ", values=" + value));} }package chapter9_set.map;public class Employee {private String name;public Employee(String name) {this.name = name;}public String getName() {return name;} }

更新映射條目

counts.put(word, counts.get(word) + 1); //第一次看到word會(huì)出現(xiàn)`NullPointerException`counts.put(words, counts.getOrDefault(word, 0) + 1);counts.putIfAbsent(word, 0); counts.put(word, counts.get(word) + 1);counts.merge(word, 1, Integer::sum);

映射視圖

3種視圖: 鍵集, 值集, 鍵值集

Set keySet();

Collection values();

Set<Map, Entry<K, V>> entrySet();

枚舉映射條目:
for(Map.Entry<String, Employee> entry : staff.entrySet()){//for(var entry : staff.entrySet())String k = entry.getKey();Employee v = entry.getValue();...... }
在鍵集視圖可以調(diào)用remove,會(huì)刪除鍵值對(duì), 但是不能添加元素(會(huì)拋出UnsupportedOperationException)
映射條目集視圖也有同樣的限制

弱散列試圖

WeakHashMap使用弱引用保存鍵
P400

鏈接散列集與映射

LinkedHashSet, LinkedHashMap會(huì)記住元素插入順序

var staff = new LinkedHashMap<String, Employee>(); staff.put("153156", new Employee("BJv")); staff.put("2516256", new Employee("Dv")); staff.put("5453156", new Employee("AJv")); staff.put("953156", new Employee("BAJVJv"));var it = staff.keySet().iterator(); while(it.hasNext()){System.out.println(it.next()); } // staff.values().iterator()

最近最少使用原則: 訪問(wèn)頻率高的放在內(nèi)存種,訪問(wèn)頻率低的放在數(shù)據(jù)庫(kù)

var cache = new LinkedHashMap<K, V>(128, 0.75F, true){protected boolean removeEldestEntry(Map.Entry<K, V> eldest){return size() > 100;} }

枚舉集與映射

EnumSet沒(méi)有公共構(gòu)造器,使用靜態(tài)工廠方法構(gòu)造這個(gè)集:

enum Weekday{MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY}; EnumSet<Weekday> a = EnumSet.allOf(Weekday.class); ...

EnumMap是一個(gè)鍵類型為枚舉類型的映射

var a = new EnumMap<Weekday, Employee>(Weekday.class);

標(biāo)識(shí)散列映射

類IdenetityHashMap: 鍵值不是使用函數(shù)hadCode, 而是方法System.identityHashCode
根據(jù)內(nèi)存地址計(jì)算散列碼
兩個(gè)對(duì)象進(jìn)行比較時(shí),使用==, 而不使用equals

視圖與包裝器

keySet方法返回了一個(gè)實(shí)現(xiàn)了Set接口的類對(duì)象,由這個(gè)類的方法操縱原映射.這種集合稱為視圖
視圖: 根據(jù)用戶觀點(diǎn)所定義的數(shù)據(jù)結(jié)構(gòu)

小集合

List<String> names = List.of("Peter", "Paul", "Mary"); Set<Integer> numbers = Set.of(2, 3, 5);Map<String, Integer> scores = Map.of("Peter", 2, "Paul", 3, "Mary", 5);
以上集合不可更改,需要更改的話

var names = new ArrayList<>(List.of("Peter", "Paul", "Mary"));

子范圍

可以為很多集合建立子范圍視圖

List<Employee> group2 = staff.subList(10, 20); //10~19group2.clear(); // 元素會(huì)自動(dòng)的從staff中刪除SortedSet<E> subSet(E from, E to);// 返回大于from, 小于to的所有元素構(gòu)成的子集

不可修改視圖

這些視圖對(duì)現(xiàn)有的集合增加了一個(gè)運(yùn)行檢查.如果發(fā)現(xiàn)試圖對(duì)集合修改,拋出異常
P406

同步視圖

Collections類的靜態(tài)方法synchronizedMap方法可以將任何一個(gè)映射轉(zhuǎn)換成有同步訪問(wèn)方法的Map

var map = Collections.synchronizedMap(new HashMaP<String, Employee>());

算法

為什么使用泛型算法

數(shù)組中最大元素:

if(a.length == 0) throw new NoSuchElementException(); T largest = a[0];for (int i = 0; i < a.length; i++) {if (largest.compareTo(a[i]) < 0) {largest = a[i];} }

數(shù)組列表中最大元素

if(a.size() == 0) throw new NoSuchElementException(); T largest = a.get(0);for (int i = 0; i < a.size(); i++) {if (largest.compareTo(a.get(i)) < 0) {largest = a.get(i);} }

鏈表沒(méi)有高效隨機(jī)訪問(wèn)操作,可以使用迭代器

if (l.isEmpty()) throw new NoSuchElementException(); Iterator<T> it = l.iterator(); T largest = it.next(); while (it.hasNext()) {T next = it.next();if (largest.compareTo(next) < 0) {largest = next;} }

可以使用max方法實(shí)現(xiàn)能夠接受任何實(shí)現(xiàn)了Collection接口的對(duì)象

public static <T extends Comparable> T max(Collection<T> collection) {if (collection.isEmpty()) throw new NoSuchElementException();Iterator<T> iter = collection.iterator();T largest = iter.next();while (iter.hasNext()) {T next = iter.next();if (largest.compareTo(next) < 0) {largest = next;}}return largest; }

排序與混排

sort方法對(duì)實(shí)現(xiàn)了List接口的集合排序

Colletion.sort(staff);

列表元素實(shí)現(xiàn)了Comparable接口

staff.sort(Comparator.comparingDouble(Employee::getSalary))

逆序Collection.reverseOrder()
staff.sort(Comparator.comparingDouble(Employee::getSalary).reversed())
列表是可修改的支持set方法,可改變大小的支持add, remove方法

package chapter9_set.shuffle;import java.util.*;public class ShuffleTest {public static void main(String[] args) {var numbers = new ArrayList<Integer>();for (int i = 1; i < 49; i++) {numbers.add(i);}Collections.shuffle(numbers);List<Integer> winningCombination = numbers.subList(0, 10);Collections.sort(winningCombination);System.out.println(winningCombination);} }

二分查找

Collection的binarySearch方法實(shí)現(xiàn)了二分查找算法,要求集合必須有序
集合必須實(shí)現(xiàn)List接口, 如果沒(méi)有采用Comparable接口的CompareTo方法進(jìn)行排序,那么需要提供一個(gè)比較器對(duì)象

i = Collection.binarySearch(c, element, comparator);

返回非負(fù)值:匹配對(duì)象的索引; 返回負(fù)值, 插入位置為-i-1

如果提供的是鏈表則退化為線性查找

簡(jiǎn)單算法

P416

批操作

l1.retainAll(l2); l1.removeAll(l2);
鍵集是映射的一個(gè)視圖,staff.keySet().removeAll(terminatedIDs);鍵和相關(guān)的員工名字會(huì)自動(dòng)的從映射中刪除

集合和數(shù)組的轉(zhuǎn)換

數(shù)組轉(zhuǎn)換為集合:

String[] names = ; var name = new HashSet<>(List.of(names));

集合得到數(shù)組使用toArray方法,返回對(duì)象數(shù)組

String[] values = staff.toArray(new String[0));

遺留的集合

棧

Stack類,有pop, push方法, 擴(kuò)展了Vector類
peek返回棧頂元素

位集

BitSet: 高效存儲(chǔ)位序列

//計(jì)算前兩百萬(wàn)位素?cái)?shù)數(shù)量計(jì)數(shù)使用時(shí)間 package chapter9_set.sieve;import java.util.*;public class Sieve {public static void main(String[] args) {int n = 2000000;long start = System.currentTimeMillis();int i;int count = 0;var bitSet = new BitSet(n + 1);for (i = 2; i <= n; i++)bitSet.set(i);i = 2;while (i * i <= n) {if (bitSet.get(i)) {count++;int k = 2 * i;while (k <= n) {bitSet.clear(k);k += i;}}i++;}// i = sqrt(n);while (i <= n) {if (bitSet.get(i))count++;i++;}long end = System.currentTimeMillis();System.out.println("From 2~2000000, there are " + count + " primes.");System.out.println("Time consumed:" + (end - start));} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的CoreJava 笔记总结-第九章集合的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。