java 集合相關
1 集合架構概述
1.1 出現的背景：
一方面，面向對象語言對事物的展現都是以對象的形式，為了友善對多個對象進行操作，就要對對象進行存儲的容器。另外一方面，使用Array來存儲對象方面具有一些弊端，，一旦建立了，數組的長度就不可以發生變化，而java集合就像一種容器，可以動态的對集合的大小進行擴充。java集合類可以用于存儲數量不等的多個對象，還可以用于儲存具有映射關系的關聯數組。集合，數組是對多個資料進行存儲操作的結構，簡稱Java容器。
說明：此時的存儲，主要是指記憶體層面的存儲，不涉及持久化存儲。
2 數組存儲
- 數組記憶體存儲方面的特點：
- 數組初始化後，長度就确定了。
- 數組聲明的類型，就決定了進行元素初始化時的類型，即數組元素的類型就已經決定了。
- 數組在存儲方面的弊端
- 數組初始化之後，長度就不變了，不便于擴充。
- 數組中提供的屬性方法少，不便于添加，删除，插入等操作，且效率比較低，無法直接擷取存儲元素的個數(實際元素的個數)。
- 存儲特點單一，數組存儲的資料是有序的，可以重複的。對于有些特殊的需求不能滿足。
3 java集合
- Collection接口：單列資料，定義了存取一組對象的方法的集合
- list：元素有序，可重複的集合。
- set：元素無序，不可重複的集合。
- Map接口：雙列資料，儲存具有映射關系的“key-value對”的集合，可以根據key來擷取value，但是一個key不能對應多個value。
2 Collection接口
2.1 Collection接口概述
2.1.1 常見方法
- 添加
- add(Object obj)：将元素添加到集合中，如果是一個集合則會将這個集合當成一個整體。
- addAll(Collection coll)：如果添加的是一個集合，将參數集合中的元素逐個添加到目前集合。
- 擷取有效元素的個數
- int size()：擷取有效元素的個數。
- 清空集合
- void clear()：将集合中的元素指向null，size設定為0
- 是否是空集合
- boolean isEmpty()：判斷目前的size是否為0
- 是否包含某個元素
- boolean contains(Object obj)：是通過元素的equals方法來判斷是否是同一個對象,在判斷的時候是逐個進行對比。
- boolean containsAll(Collection c)：也是調用元素的equals方法來比較的。拿兩個集合的元素逐個比較，要求形參集合中的元素全部都在目前的集合中則傳回true。
- 删除
- boolean remove(Object obj) ：通過元素的equals方法判斷是否是要删除的那個元素。隻會删除找到的第一個元素
- boolean removeAll(Collection coll)：取目前集合的差集
- 取兩個集合的交集
- boolean retainAll(Collection c)：把交集的結果存在目前集合中，不影響c集合。
- 是否相等
- boolean equals(Object obj)：需要判斷元素是否一一對應相等。
- 轉成對象數組
- Object[] toArray()
- 擷取集合對象的哈希值
- hashCode()
- 周遊
-
iterator()：傳回疊代器對象，用于集合周遊。不是容器，隻是一個疊代器。
說明：Iterator對象稱為疊代器(設計模式的一種)，主要用于周遊Collection集合中的元素。GOF給疊代器模式的定義為：提供一種方法通路一個容器對象中各個元素，而又不暴露該對象的内部細節==>疊代器模式，就是為容器而生。 要求往Collection中添加的自定義的類要重寫equals方法,如果不重寫，則會調用Object的equals對比(比較對象的位址值)。
實作原了解析：//執行周遊操作 while(iterator.hasNext()){ Object next = iterator.next(); System.out.println(next); }
2.1.2 周遊Collection集合數組的方式
1）使用疊代器：iterator
@Test
public void testIterator(){
//Iterator()：集合元素的周遊,傳回值是一個疊代器接口
Collection collection=new ArrayList();
collection.add(123);
collection.add(456);
collection.add(new String("Tom"));
collection.add(false);
Iterator iterator = collection.iterator();
//執行周遊操作
while(iterator.hasNext()){
Object next = iterator.next();
if ("Tom".equals(next)){
iterator.remove();
}
System.out.println(next);
}
//會進入死循環，無限輸出第一個。每次調用iterator()就會傳回一個新的iterator，預設遊标在第一個之前。
/* while(collection.iterator().hasNext()){
System.out.println(collection.iterator().next());
}*/
//存在remove方法，可以用來移除集合中的元素。此方法不同于集合調用remove()。
//如果在next之前調用remove或者調用next之後調用remove然後再次調用remove會出現錯誤：IllegalStateException
Iterator iterator1 = collection.iterator();
while (iterator1.hasNext()){
System.out.println(iterator1.next());
}
}
2）JDK5.0新增的foreach循環疊代通路Collection和數組
/**
* foreach周遊集合
*/
@Test
public void testForeach(){
Collection collection=new ArrayList();
collection.add(123);
collection.add(456);
collection.add(new String("Tom"));
collection.add(false);
//for(集合中元素的類型 局部變量：集合對象)
for (Object o:collection) {
System.out.println(o);
}
}
2.1.3 簡單練習
/**
* 練習題：增強for循環通常用來周遊，無法對資料進行修改。
*/
@Test
public void testForeach02(){
String[] strings=new String[]{"MM","MM","MM"};
for (int i = 0; i < strings.length; i++) {
strings[i]="GG";
}
for (int i = 0; i < strings.length; i++) {
//GG
System.out.println(strings[i]);
}
for (String s:strings) {
s="HH";
}
for (int i = 0; i <strings.length; i++) {
//GG
System.out.println(strings[i]);
}
}
2.2 Collection–List接口
2.2.1 List接口概述
- 鑒于Java中數組用來存儲資料的局限性，我們通常使用List接口的實作類來替代數組
- List集合類中元素有序、且可重複，集合中的每個元素都有其對應的順序索引。
- 底層使用動态數組實作，List容器中的元素都對應一個整數型的序号記載其在容器中的位置，可以根據序号存取容器中的元素，此番方式比較快。
- JDK API中List接口的實作類常用的有：ArrayList、LinkedList和Vector。
2.2.2 ArrayList
作為List接口的主要實作類而出現。
- 特點
- 線程不安全的，是以效率比較高。
- 底層使用Object類型的數組進行封裝==>Object[] elementData存儲。
- 對于查詢和修改操作比較多的情況下效率比較高，值得是根據下标來進行查找。
- 因為底層使用數組，是以在記憶體中的存儲是連續的。
2.源碼分析：JDK7和8之中有所不同–>1.8懶加載
JDK7版本：
//1.調用空參構造器建立對象。
public ArrayList() {
//2.調用重載的構造器
this(10);
}
public ArrayList(int initialCapacity) {
super();
//3.判斷初始化容量是否小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
//4.将Object[] elementData進行初始化，初始化容量為10
this.elementData = new Object[initialCapacity];
}
//1.調用添加資料的方法（不夠的情況下）
public boolean add(E e) {
//2.确認容量是否夠，數組容量和已添加的元素個數+1進行比較。
ensureCapacityInternal(size + 1); // Increments modCount!!
//9.添加新的資料到數組中去
elementData[size++] = e;
return true;
}
//3.判斷容量是否足夠的方法
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
//4.如果數組容量不夠了
if (minCapacity - elementData.length > 0)
//5.開始調用擴容的方法
grow(minCapacity);
}
//5.調用擴容的方法。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//6.新的容量的計算。例如舊的容量是10==>新的容量10+5==15，擴容為1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//7.1如果新的容量依舊小于之前容量+1==>将之前容量+1賦給新的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//7.2如果新的容量大于MAX_ARRAY_SIZE
if (newCapacity - MAX_ARRAY_SIZE > 0)
//7.2.1将容量設定為int的最大值
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//8.将數組進行複制到新的數組中去
elementData = Arrays.copyOf(elementData, newCapacity);
}
//7.2.2容量指派為整形最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
總結: > 如果添加資料導緻底層數組的容量不夠，則進行擴容，預設為1.5倍擴容。
> 開發者中建議使用帶參數的構造器。
JDK8**版本**
//1.調用空參構造器
public ArrayList() {
//2.調用預設屬性，并沒有直接建立數組對象，類似于單例模式中的懶漢式
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//2.調用預設屬性
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//1.調用**add**方法添加資料
public boolean add(E e) {
//2.确認容量是否足夠
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//2.**判斷容量是否足夠的方法*
private void ensureCapacityInternal(int minCapacity) {
//3.**判斷是不是第一次添加資料。*
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//4.1**如果是第一次添加資料。進行預設初始化。**DEFAULT_CAPACITY==10*
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//4.2**不是第一次添加資料，判斷容量*
ensureExplicitCapacity(minCapacity);
}
//4.2**判斷容量*
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //初始為0
// overflow-conscious code*
//4.2.1**如果容量小了*
if (minCapacity - elementData.length > 0)
//4.2.2**增加容量*
grow(minCapacity);
}
//**增加容量的方法：和**JDK7.0**一緻
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//**容量**1.5**倍進行增加。
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 結論：
JDK8中調用空參構造器的時候底層Object[] elementData初始化的時候并沒有建立長度為10的數組。在第一次調用add的時候，建立長度為10的數組，将資料添加到其中操作和擴容操作和JDK7保持一緻。1.5倍擴容
JDK8對比JDK7的優點：
- 延遲了數組的建立時間，節省了記憶體。
- JDK7中ArrayList數組的建立類似于餓漢式。
- JDK8中ArrayList數組的建立類似于懶漢式。
- 方法
- void add(int index,E element):指定的下标出添加元素。(index<0||index>size)
-
E get(int index):根據下标擷取指定元素。
E set(int index E element):修改指定索引處的值為參數值，傳回原元素值
- int indexOf(Object o):擷取第一次出現參數值的下标
- int lastIndexOf(Object o):擷取最後一次出現指定參數值的下标。
- E remove(int index):删除指定下标處的元素
@Test
public void test01() {
ArrayList<Object> list = new ArrayList<Object>();
list.add("123");
list.add("456");
list.add("789");
//[123, 456, 789]
System.out.println(list);
list.add(1,"hello");
//[123, hello, 456, 789]
System.out.println(list);
System.out.println(list.get(2));
System.out.println(list.set(2, "world"));
System.out.println(list.get(2));
System.out.println(list.indexOf("hello"));
System.out.println(list.lastIndexOf("hello"));
System.out.println(list.remove(2)); //world
}
@Test
public void test() {
Scanner input=new Scanner(System.in);
System.out.println("請輸入20個字元");
String str=input.next();
char[] chars=str.toCharArray();
ArrayList<Object> list=new ArrayList<>();
for (int i = 0; i < chars.length; i++) {
list.add(chars[i]);
}
System.out.println("輸入的字元串序列為："+list);
ArrayList<Object> list2=new ArrayList<>();
for (int i = 0; i < chars.length; i++) {
if (list2.contains(chars[i])) {
continue;
}
list2.add(chars[i]);
}
System.out.println("去除重複後的字元集合為："+list2);
for (int i = 0; i < list2.size(); i++) {
int nums=0;
for (int j = 0; j < chars.length; j++) {
if ((char)(list2.get(i))==chars[j]) {
nums++;
}
}
System.out.println(list2.get(i)+"出現了:"+nums+"次");
}
}
2.2.3 LinkedList
- 特點
- 底層使用雙向連結清單的方式進行存儲。
- 對于頻發的插入，删除操作效率比ArrayList高。
- 因為底層是雙向連結清單，在記憶體中的存儲是不連續。
- 源碼分析：在JDK7和JDK8之中沒有特别大的差別
//存儲資料的結構是“雙向連結清單”，資料存儲在一個個Node中 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } //構造器 public LinkedList() { } //1.執行添加操作 public boolean add(E e) { //2.調用linkLast方法來執行添加節點的操作。 linkLast(e); return true; } //linkLast方法 // Links e as last element. void linkLast(E e) { final Node<E> l = last; //放入資料，建構新的節點：前一個，目前的，後一個指向null final Node<E> newNode = new Node<>(l, e, null); //将新添的元素作為最後一個。 last = newNode; if (l == null) first = newNode; else l.next = newNode; //節點個數++ size++; modCount++; } - 結論：
LinkList list=new LinkList()，内部聲明了Node類型的first和last屬性，頭尾節點，便于我們直接對頭尾節點進行操作預設值為null，執行添加操作list.add(123)==>實際上是将資料封裝到了node節點中，如果節點是第一個元素，将該節點指派給first節點。
- 常見面試題
1）Arraylist和linkedList之間的差別？
arraylist底層使用數組實作，linkedlist使用雙向連結清單實作，是以如果對于查詢和修改來說，如我們知道該元素的下标，arraylist可以根據下标直接定位到我們需要的元素，可以直接擷取或修改其屬性，在這種情況下，由于linkedList必須一個一個進行比較，直到擷取到我們需要的元素，在這種情況下，arraylist的效率要高于LinkedList。如果直接直接擷取或修改頭尾節點，兩者的效率沒有什麼差别。如果是删除或者新增的操作，linkedlist的效率要高于arraylist，因為數組的特性是一塊連續的存儲空間，是以linkedlist需要對删除或新增位置的以後的元素進行移位，比較消耗性能，而linkedlist隻要連上修改pre和next引用位址即可。
具體操作為：比如要在ab之間插入c，那麼應該c的pre指向a，next指向b，a的next指向c，a的next.next.pre指向c，
2.2.4 Vector
作為List的古老實作類出現，出現于jdk1.0。
- 特點
- 線程安全的，效率比較低
- 底層使用Object類型的數組進行封裝==>Object[] elementData存儲。
- 源碼分析==JDK7和8中沒有什麼不同
//構造器
public Vector() {
//1.數組初始化長度為10
this(10);
}
//2.執行添加資料的操作
public synchronized boolean add(E e) {
modCount++;
//3.判斷容量是否充足
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
//判斷容量的方法
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//擴容
grow(minCapacity);
}
//擴容的方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//初始capacityIncrement==0===>擴容了兩倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 結論：
JDK7和JDK8中Vector(向量類)沒什麼大的改變，預設數組初始化長度為10，首次擴容的時候，預設擴容為之前的兩倍。
2.2.5 List接口中方法測試
- void add(int index, Object ele): 在index 位置插入ele 元素
- boolean addAll(int index, Collection eles): 從index 位置開始将eles中的所有元素添加進來
- Object get(int index): 擷取指定index 位置的元素
- int indexOf(Object obj): 傳回obj在集合中首次出現的索引位置
- int lastIndexOf(Object obj): 傳回obj在目前集合中末次出現的索引位置
- Object remove(int index): 移除指定index位置的元素，并傳回此元素
- Object set(int index, Object ele): 設定指定index位置的元素改為ele
- List subList(int fromIndex, int toIndex): 傳回從fromIndex 到toIndex位置的子集合,左閉右開。
總結：常用方法
- 增：add(Object obj)
- 删：remove(Int index)/remove(Object o)
- 改：set(Int index,Object ele)
- 查：get(Int index)
- 插：add(Int index,Object obj)
- 長度：size()
-
周遊： ①Iterator疊代器方式
②增強for循環
③普通的循環
@Test
public void testListMethods(){
ArrayList<Object> list = new ArrayList<>();
//add(Object o)
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("張三",21));
list.add(456);
//[123, 456, AA, Person{name='張三', age=21}, 456]
System.out.println(list);
//add(int index，Object o)
list.add(1,"李四");
//[123, 李四, 456, AA, Person{name='張三', age=21}, 456]
System.out.println(list);
list.addAll(2, Arrays.asList("王五","趙六","田七"));
//[123, 李四, 王五, 趙六, 田七, 456, AA, Person{name='張三', age=21}, 456]
System.out.println(list);
//趙六
System.out.println(list.get(3));
//5
System.out.println(list.indexOf(456));
//8
System.out.println(list.lastIndexOf(456));
Object remove = list.remove(6);
//AA
System.out.println(remove);
//[123, 李四, 王五, 趙六, 田七, 456, Person{name='張三', age=21}, 456]
System.out.println(list);
list.set(0,"張三");
System.out.println(list);
List<Object> sub = list.subList(0, 5);
//[張三, 李四, 王五, 趙六, 田七]
System.out.println(sub);
//周遊：
//方式一：
Iterator<Object> iterator = list.iterator();
while (iterator.hasNext()){
System.out.print(iterator.next()+"\t");
}
System.out.println("**********");
//方式二
for (Object o:list) {
System.out.print(o+"\t");
}
System.out.println("**********");
//方式三
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+"\t");
}
}
//javaBean
class Person{
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public Person() {
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person person = (Person) o;
if (age != person.age) return false;
return name != null ? name.equals(person.name) : person.name == null;
}
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
}
2.3 Collection–Set接口
Set接口概述
- Set接口是Collection的子接口，内部沒有提供額外的方法。
- Set接口存儲資料是無序的，不可重複的資料，如果試圖添加相同的元素到Set集合中去，則添加操作失敗。
- Set判斷兩個對象是否相等不是使用的==，而是使用的equals方法。
2.3.1 HashSet
作為Set接口的主要實作類
- 特點：
- 線程不安全的==>效率高。
- 可以存儲Null值。
- 無序性不代表是随機性，不代表每次周遊集合都不相同。以HashSet為例，插入順序和讀出順序不一定一緻。
- 插入值的方式：底層使用hashmap實作，即hash的表的結構，首先計算插入元素的hash值，然後hash值和目前哈希桶數量減一相與，擷取其在數組中的位置，然後檢視改為是否存在元素，如果沒有，插入成功，如果存在元素，則逐個對比，如果hashcode值不一緻則添加成功，如果一緻則使用equals方法進行比較，如果不同，添加成功，如果相同進行替換。
- 底層結構是：哈希表，即數組+連結清單
-
添加元素的過程：以HashSet為例
添加過程：調用待添加資料的hashCode()方法，計算hash值，然後此hash值通過某種算法（如散列函數）進行計算存放的位置(索引位置)，判斷該位置是否存在元素：如果該位置沒有元素則存放在此處；當發現存放的位置已經存在元素b了，則進行比較他們的hash值是否相同，不相同則添加成功，一旦相同就調用新元素的equals方法，如果傳回值為true==>就認為兩個元素是相同的元素，添加失敗。不相同的時候則以連結清單的形式進行添加。某位置存在元素的情況下添加元素的規則：JDK7則将新的元素放到舊元素的位置，舊元素下移，JDK8則相反（7上8下）。
注意：
- Object類中的hashCode值是進行随機計算的==>自定義類進行添加的時候需要重寫hashCode()和equals()方法,且這兩個方法盡可能的保持一緻性==>相同的對象必有相同的散列碼。
- 對象中用作equals()方法的field，都應該被用來計算hashCode()==>生産過程中使用ide工具直接自動生成。
- 擴容機制：
底層也是數組進行存儲，初始容量為16，當如果使用率超過0.75，（16*0.75=12）就會擴大容量為原來的2倍。（16擴容為32，依次為64,128…等）。
- 重寫hashCode()，為什麼會存在31這個數字？
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
原因：
- 選擇系數的時候，盡量要選擇大的系數，因為如果計算出來的hash值越大，所謂的“沖突”就越少，查找起來效率比較高(減少哈希碰撞)。
- 并且31隻占用5個bit，相乘造成資料溢出的機率比較小。
- 31可以使用1*31==>（1<<5）-1來表示，很多虛拟機裡面都有相關的優化（提高算法的效率）
- 31是一個素數，素數的作用就是如果我用一個數字來乘以這個數，那麼這個數最多隻能被素數本身和被乘數還有1來整除(減少沖突)。
簡單測試一下：
@Test
public void testSet(){
Set set = new HashSet();
set.add(123);
set.add(456);
set.add("張三");
set.add("張三");
set.add("李四");
System.out.println(set);
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
//重寫了hashCode()
System.out.println("張三".hashCode());
System.out.println("張三".hashCode());
}
輸出結果：
[李四, 張三, 456, 123]
李四
張三
456
123
774889
774889
2.3.2 LinkedHashSet
是HashSet的子類
特點：
- 依舊是無序的。
- 在添加資料的同時每個資料還維護了兩個引用，記錄此資料的前一個和後一個資料，在周遊其内部資料的時候，可以按照添加的順序進行周遊。
- 對于頻繁的增删操作，效率要高于HashSet。
@Test
public void testLinkedHashSet(){
Set set = new LinkedHashSet();
set.add(123);
set.add(456);
set.add("張三");
set.add("張三");
set.add("李四");
System.out.println(set);
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
輸出結果：
[123, 456, 張三, 李四]
123
456
張三
李四
2.3.3 TreeSet
- 特點：
- 使用紅黑二叉樹，平衡二叉樹，進行存儲==>查詢速快。
- 像TreeSet中添加資料，必須存儲同一個類new的對象。
- 該對象可以排序。
- 添加資料：
- 自然排序：比較兩個對象是否相同的标準不再是equals()方法，而是CompareTo()傳回0，一旦他們的。
- 定制排序：
/**
* TreeSet的測試
*/
@Test
public void testTreeSet(){
TreeSet<Object> treeSet = new TreeSet<>();
treeSet.add(123);
treeSet.add(456);
//添加失敗：java.lang.ClassCastException:
// java.lang.Integer cannot be cast to java.lang.String
//treeSet.add("張三");
treeSet.add(-2);
treeSet.add(78);
Iterator<Object> iterator = treeSet.iterator();
while(iterator.hasNext()){
//輸出是排好順序的：-2 78 123 456
System.out.print(iterator.next()+"\t");
}
System.out.println("*************************");
//自然排序：
TreeSet<Object> treeSet1 = new TreeSet<>();
treeSet1.add(new Person("Tom",21));
treeSet1.add(new Person("BB",21));
treeSet1.add(new Person("Tom",18));
treeSet1.add(new Person("AA",21));
treeSet1.add(new Person("Tam",24));
Iterator<Object> iterator1 = treeSet1.iterator();
while (iterator1.hasNext()){
System.out.print(iterator1.next()+"\t");
}
System.out.println();
System.out.println("-----------------");
//存在定制排序：優先使用定制排序的規則。
TreeSet<Object> treeSet2 = new TreeSet<>(new Comparator<Object>() {
@Override
public int compare(Object o1, Object o2) {
if (!(o1 instanceof Person&&o2 instanceof Person)){
try {
throw new Exception("傳入的參數有誤！！");
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
Person person1=(Person) o1;
Person person2=(Person) o2;
//如果名字相同，則年齡從大到小進行排列
if (person1.name.compareTo(person2.name)==0){
return -(new Integer(person1.age).compareTo(person2.age));
}
return person1.name.compareTo(person2.name);
}
});
treeSet2.add(new Person("Tom",21));
treeSet2.add(new Person("BB",21));
treeSet2.add(new Person("Tom",18));
treeSet2.add(new Person("AA",21));
treeSet2.add(new Person("Tam",24));
Iterator<Object> iterator2 = treeSet2.iterator();
while (iterator2.hasNext()){
System.out.print(iterator2.next()+"\t");
}
}
class Person implements Comparable {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public Person() {
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof Person)) {
return false;
}
Person person = (Person) o;
if (age != person.age){
return false;
}
return name != null ? name.equals(person.name) : person.name == null;
}
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
/**
* 名字從小到大，名字相同時，年齡從小到大。
* @param o
* @return
*/
@Override
public int compareTo(Object o) {
if (!(o instanceof Person)){
try {
throw new Exception("傳入的參數有誤！！");
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
Person person=(Person) o;
//如果兩者的名字相同，則進行比較其年齡。
if (this.name.compareTo(person.name)==0){
return new Integer(this.age).compareTo(person.age);
}
return this.name.compareTo(person.name);
}
}
- 常見方法
E first()：獲得第一個元素
E last()：擷取最後一個元素
E floor(E e)：擷取小于參數的最大元素
E ceiling(E e)：擷取大于參數的最大元素
總結：
- Collection中存儲的如果是自定義類的對象，需要自定義類從重寫哪個方法?為什麼？
- List接口的實作類：equals()
- Set接口： HashSet，LinkedHashSet：equals，hashCode（）。
- TreeSet：Comparabe：compareTo（Object o）；Comparator：compare（Object o1,Object o2）。
- ArrayList,LinkedList,Vector三者的相同點，不同點？
- 相同點：都實作了List接口，存儲都是有序的，可重複的。
- 不同點：Vector是線程安全的，ArrayList，linkedList線程不安全。參考知識點。
- List接口中的常用方法有那些？
增：add(Object o)
删：remove(Object o),remove(Int index)==>ArrayList
改：set(Int index,Object o)
查：get(Int index)
插入：add(Int index,Object o )
長度：size(),
周遊：①Iterator
②foreach
③for
- Set存儲資料的特點==>無序，不可重複性，常見實作類==>HashSet，TreeSet，LinkedHashSet
- 一個簡單測試：考察對底層的了解
public static void main(String[] args) {
HashSet set=new HashSet();
Person p1 = new Person(1001, "AA");
Person p2 = new Person(1002, "BB");
set.add(p1);
set.add(p2);
System.out.println(set);
p1.name="CC";
//極大的機率沒找到，删除失敗
System.out.println(set);
set.remove(p1);
//{p1.toString()，p2.toString()}
System.out.println(set);
//添加成功，對比了HashCode添加的位置發生了變化
set.add(new Person(1001,"CC"));
System.out.println(set);
//添加成功，對于了Hashcode然後對比了equals（）
set.add(new Person(1001,"AA"));
//{p1.toString(),p2.toString,CC.toString,AA.toString}
System.out.println(set);
}
class Person{
int id;
String name;
public Person() {
}
public Person(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {return true;}
if (!(o instanceof Person)) {return false;}
Person person = (Person) o;
if (id != person.id) {return false;}
return name != null ? name.equals(person.name) : person.name == null;
}
@Override
public int hashCode() {
int result = id;
result = 31 * result + (name != null ? name.hashCode() : 0);
return result;
}
@Override
public String toString() {
return "Person{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
- 定制排序的使用
public static void main(String[] args) {
TreeSet treeSet = new TreeSet();
Employee e1 = new Employee("liudehua", 55, new MyDate(1965, 5, 4));
Employee e2 =new Employee("zhangxueyou",44,new MyDate(1978,5,4));
Employee e3 =new Employee("guofucheng",44,new MyDate(1978,5,9));
Employee e4 =new Employee("liming",51,new MyDate(1969,5,4));
Employee e5 =new Employee("liangchaowei",21,new MyDate(1999,5,4));
treeSet.add(e1);
treeSet.add(e2);
treeSet.add(e3);
treeSet.add(e4);
treeSet.add(e5);
Iterator iterator = treeSet.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println("***********************************************");
TreeSet treeSet1 = new TreeSet(new Comparator() {
//按照生日進行比較,可以将date這個排序方式放到MyDate類中作為自然排序。
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof Employee&&o2 instanceof Employee){
Employee e1=(Employee)o1;
Employee e2=(Employee)o2;
MyDate b1 = e1.getBirthday();
MyDate b2 = e2.getBirthday();
int minusYear=b1.getYear()-b2.getYear();
if (minusYear!=0){
return minusYear;
}
int minusMonth=b1.getMonth()-b2.getMonth();
if (minusMonth!=0){
return minusMonth;
}
return b1.getDay()-b2.getDay();
}
throw new RuntimeException("傳入的參數有誤！");
}
});
treeSet1.add(e1);
treeSet1.add(e2);
treeSet1.add(e3);
treeSet1.add(e4);
treeSet1.add(e5);
Iterator iterator1 = treeSet1.iterator();
while (iterator1.hasNext()){
System.out.println(iterator1.next());
}
}
class Employee implements Comparable{
private String name;
private int age;
private MyDate birthday;
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;
}
public MyDate getBirthday() {
return birthday;
}
public void setBirthday(MyDate birthday) {
this.birthday = birthday;
}
public Employee(String name, int age, MyDate birthday) {
this.name = name;
this.age = age;
this.birthday = birthday;
}
public Employee() {
}
@Override
public String toString() {
return "Employee{" +
"name='" + name + '\'' +
", age=" + age +
", birthday=" + birthday +
'}';
}
//按照姓名進行排序,如果是漢字的話就就可能會出現問題，拿的是UTF-8來進行計算，不是使用abcd來計算。特殊需求的話找jar包，根據拼音來比較。
@Override
public int compareTo(Object o) {
if (o instanceof Employee){
Employee e=(Employee)o;
return this.name.compareTo(e.name);
}
throw new RuntimeException("傳入參數有誤");
}
}
class MyDate{
private int year;
private int month;
private int day;
public int getYear() {
return year;
}
public void setYear(int year) {
this.year = year;
}
public int getMonth() {
return month;
}
public void setMonth(int month) {
this.month = month;
}
public int getDay() {
return day;
}
public void setDay(int day) {
this.day = day;
}
public MyDate(int year, int month, int day) {
this.year = year;
this.month = month;
this.day = day;
}
public MyDate() {
}
@Override
public String toString() {
return "MyDate{" +
"year=" + year +
", month=" + month +
", day=" + day +
'}';
}
}
3 Map的測試
3.1 map概述–JDK1.2
Map是與Collection并列的存在，用于存儲具有映射關系的雙列資料，存儲key-value鍵值對，可以實任何類型的引用變量，key-value存在單向一對一的關系，即一個key指向唯一的一個value。
3.2 HashMap
map的主要實作類
1 特點：
- 線程不安全的，效率高。
- 可以存儲null的key和value，相key相同的時候，添加的時候是覆寫的操作。
2 Map的key-value的了解
以HashMap的鍵值對為例：key使用Set來進行存儲，即無序的，不可重複的資料==>自定義類需要重寫equals()和hashCode()。value是可以重複的。
Collection存儲所有的value==>要重寫equals()方法，底層contains方法會調用。實際上我們put的時候，将資料封裝到entry對象中（entry：無序，不可重複）。使用Set存儲所有的entry。
3 底層結構
JDK7及之前：數組+連結清單
JDK8：數組+連結清單+紅黑樹
4 HashMap的底層實作原理：
① JDK7版本：
HashMap map=new HashMap();>在執行個體化之後，底層建立了長度為16的一維數組Entry[] table。map.put(key1,value1);>非第一次存放資料，首先調用key1所在類的hashCode()計算key1的哈希值，經過某種算法得到在Entry數組中的存放位置。如果此位置上的資料為空，則表明不存在資料，key1-value1添加成功，如果此位置上的資料不為空，意味着存在一個或者多個資料（連結清單的方式存在），比較目前的key1和目前位置上的key的hash值進行比較，如果都不相同，則可以存儲成功，如果k1和某一個資料的hash值相同了，則使用equals方法進行比較，如果不同，則進行存儲。如果相同則使用value1來進行替換原有的資料。
擴容機制：預設的擴容方式是擴容為原來的兩倍，然後将原有的資料複制過來。
② JDK8相較于JDK7在底層實作方面的不同。
- new HashMap():底層沒有立即建立一個長度為16的數組。
- JDK8 底層的數組是Node[ ] ，而非Entry[ ]
- 首次調用put()方法的時候，底層建立長度為16的數組
-
JDK7底層結構隻有：數組+連結清單。JDK8中底層結構：數組+連結清單+紅黑樹。
注：當數組的某一個索引位置上的元素以連結清單的形式存在的資料個數>8，且目前數組的長度>64，此時此索引位置上的所有資料改為紅黑樹進行存儲。
5 底層源碼==>JDK7和JDK8
//建立HashMap對象
HashMap map=new HashMap();
//1.調用空參構造器
public HashMap() {
//2.調用有參構造器：
//DEFAULT_INITIAL_CAPACITY<==>預設初始化長度
//DEFAULT_LOAD_FACTOR<==>預設加載因子0.75
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//有參構造器
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
//建立初始化長度為2的多少次幂；例如15，則實際建立16
while (capacity < initialCapacity)
capacity <<= 1;
//加載因子：預設值0.75
this.loadFactor = loadFactor;
//計算臨界值=目前容量*加載因子，例如使用預設情況下。臨界值=16*0.75=12，當超過12的時候，就進行擴容操作
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化底層數組：Entry<k,v> table
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
//put()操作：
public V put(K key, V value) {
//可以存放null的key值
if (key == null)
return putForNullKey(value);
//計算hash值
int hash = hash(key);
//計算存放的位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
//計算存放位置的方法
static int indexFor(int h, int length) {
return h & (length-1);
}
//底層存儲的操作
void addEntry(int hash, K key, V value, int bucketIndex) {
//當size>12且該位置不空==>想要生成連結清單則進行擴容操作。
if ((size >= threshold) && (null != table[bucketIndex])) {
//預設擴容為之前的2倍
resize(2 * table.length);
//計算hash值，如果是null則hash值為0，否則計算hash值
hash = (null != key) ? hash(key) : 0;
//擴容之後重新計算索引位置
bucketIndex = indexFor(hash, table.length);
}
//不需要擴容則執行createEntry()
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
//直接将這個位置上的元素取出來。
Entry<K,V> e = table[bucketIndex];
//将新的元素放到該索引位置。将原來數組上的元素放到新的元素next中出現。
//即新的元素next指向老的元素
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
//底層源碼分析==>JDK8版本
//構造器
public HashMap() {
//差別于7，隻有加載因子,并沒有調用有參構造器
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//put方法的調用
public V put(K key, V value) {
//調用putVal的方法
return putVal(hash(key), key, value, false, true);
}
//putVal方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//建立底層數組的方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
6 底層結構涉及到的幾個名詞
- DEFAULT_INITIAL_CAPACITY : HashMap的預設容量，16
- MAXIMUM_CAPACITY ： ： HashMap的最大支援容量，2^30
- DEFAULT_LOAD_FACTOR ：HashMap的預設加載因子
- TREEIFY_THRESHOLD ：Bucket中連結清單長度大于該預設值，轉化為紅黑樹
- UNTREEIFY_THRESHOLD ：Bucket中紅黑樹存儲的Node小于該預設值，轉化為連結清單
- MIN_TREEIFY_CAPACITY ：桶中的Node被樹化時最小的hash表容量。（當桶中Node的數量大到需要變紅黑樹時，若hash表容量小于MIN_TREEIFY_CAPACITY時，此時應執行(64)
- resize擴容操作這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。
- table ：存儲元素的數組，總是2的n次幂
- entrySet： ：存儲具體元素的集
- size ：HashMap中存儲的鍵值對的數量
- modCount ：HashMap擴容和結構改變的次數。
- threshold ：擴容的臨界值，=容量*填充因子
- loadFactor： ：填充因子
7 為什麼預設的加載因子是0.75？
因為滿的概念定義的比較模糊，根據統計學得出的結論：加載因子過小則數組使用率比較低，過大的時候連結清單的長度比較大。最終標明了0.75。
8 常見方法
- V put(k key,V value):往map中存放資料，如果key存在，傳回值為被替換的value；否則為null
- void clear():删除所有的元素（鍵值對）
- boolean containKey(Object key):map中是否包含key
- boolean containValue(Object value):map中是否包含value
- V get(Object key)：通過key來擷取value
- boolean isEmpty():判斷是否為空
- V remove (Object key):根據鍵删除鍵值對，傳回值是被删除的value。
- Set keySet():擷取所有的鍵對應的set
- Collection values():擷取值集合
- Set<Map.Entry<k,v> entrySet()>( )：鍵值對對應的Entry對象
3.3 LinkedHashMap
1 特點：
- 在原有的HashMap的基礎上加了兩個指針，保證在周遊map元素的時候，可以按照添加的順序進行周遊。
- 對于頻繁的周遊操作，執行效率要高于HashMap。
2 底層實作原理
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;可以記錄添加的元素的先後順序。
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
3.4 TreeMap
1 特點：
- 考慮key的自然排序和定制排序，底層是紅黑二叉樹的結構==>保證按照添加的key-value來進行排序，實作排序周遊。
- 向TreeMap中添加key-value，要求key必須是由同一個類建立的對象==>按照key來進行排序。
2 排序的方式：自然排序，定制排序。
/**
* 排序
*/
@Test
public void testTreeMap(){
System.out.println("自然排序:::");
TreeMap treeMap = new TreeMap();
Person p1 = new Person("Tom", 23);
Person p2 = new Person("Jerry", 27);
Person p3 = new Person("Rose",22);
Person p4 = new Person("Jack",20);
Person p5 = new Person("James",18);
Person p6 = new Person("Tom",25);
treeMap.put(p1,"NBA");
treeMap.put(p2,"CBA");
treeMap.put(p3,"nab");
treeMap.put(p4,"qwe");
treeMap.put(p5,123);
treeMap.put(p6,125);
Set set = treeMap.entrySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()){
Object next = iterator.next();
Map.Entry entry=(Map.Entry)next;
System.out.println(entry.getKey()+"="+entry.getValue());
}
System.out.println("定制排序:::");
TreeMap treeMap1 = new TreeMap(new Comparator() {
//直接按照年齡從小到大進行排序
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof Person && o2 instanceof Person) {
Person p1 = (Person) o1;
Person p2 = (Person) o2;
return p1.age - p2.age;
}
throw new RuntimeException("傳入的參數不比對");
}
});
treeMap1.put(p1,"NBA");
treeMap1.put(p2,"CBA");
treeMap1.put(p3,"nab");
treeMap1.put(p4,"qwe");
treeMap1.put(p5,123);
treeMap1.put(p6,125);
Set set1 = treeMap1.entrySet();
Iterator iterator1 = set1.iterator();
while (iterator1.hasNext()){
Object next = iterator1.next();
Map.Entry entry=(Map.Entry)next;
System.out.println(entry.getKey()+"="+entry.getValue());
}
}
class Person implements Comparable{
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public Person() {
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) {return true;}
if (!(o instanceof Person)) {return false;}
Person person = (Person) o;
if (age != person.age) {return false;}
return name != null ? name.equals(person.name) : person.name == null;
}
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
/**
* 自然排序：按照姓名從大到小，年齡從小到大
* @param o
* @return
*/
@Override
public int compareTo(Object o) {
if (o instanceof Person){
Person p=(Person)o;
int i = -this.name.compareTo(p.name);
if (i!=0){
return i;
}else {
return this.age-p.age;
}
}
throw new RuntimeException("傳入的參數有誤！！！");
}
}
3.5 Hashtable
map的古老實作類：出現于JDK1.0
1 特點：
- 線程安全的，效率低。
- 不可以存儲null的key和value。
2 子類之properties：常用來處理配置檔案。key和value都是String類型。
預設的識别目錄為項目下：目前子產品的根目錄，非目前項目的根目錄
@Test
public void testProperties() throws IOException {
Properties properties = new Properties();
//加載流對應的檔案
properties.load(new FileInputStream("JDBC.properties"));
String name = properties.getProperty("name");
String password = properties.getProperty("password");
//james詹姆斯=1997
System.out.println(name+"="+password);
}
3.6 Map中常用的方法
以HashMap為例
- 添加 、 删除、修改操作 ：
- Object put(Object key,Object value)：将指定key-value添加到(或修改)目前map對象中
- void putAll(Map m):将m中的所有key-value對存放到目前map中
- Object remove(Object key)：移除指定key的key-value對，并傳回value
- void clear()：清空目前map中的所有資料
@Test
public void testMap(){
HashMap hashMap = new HashMap();
hashMap.put(null,"張三"); //{null=張三}
hashMap.put(null,"李四"); //null="李四";
System.out.println(hashMap); //{null=李四}
hashMap.put("AA",123);
hashMap.put("BB",456);
//{null=李四, AA=123, BB=456}
System.out.println(hashMap);
HashMap hashMap1 = new HashMap();
hashMap1.put("CC",123);
hashMap1.put("DD",456);
hashMap.putAll(hashMap1);
//{null=李四, AA=123, BB=456, CC=123, DD=456}
System.out.println(hashMap);
Object remove = hashMap.remove(null);
System.out.println(remove); //李四
System.out.println(hashMap); //{AA=123, BB=456, CC=123, DD=456}
//不等同于map=null。清空的是資料
hashMap.clear();
System.out.println(hashMap.size()+"\t"+hashMap); //0 {}
Object aa = hashMap.get("AA");
System.out.println(aa); //null
}
- 元素 查詢的操作：
- Object get(Object key)：擷取指定key對應的value
- boolean containsKey(Object key)：是否包含指定的key
- boolean containsValue(Object value)：是否包含指定的value
- int size()：傳回map中key-value對的個數
- boolean isEmpty()：判斷目前map是否為空
- boolean equals(Object obj)：判斷目前map和參數對象obj是否相等
@Test
public void testMap2(){
HashMap hashMap = new HashMap();
hashMap.put("AA",123);
hashMap.put(45,123);
hashMap.put("BB",56);
hashMap.put("45",345);
//{AA=123, BB=56, 45=345, 45=123}
System.out.println(hashMap);
Object o = hashMap.get(45);
//123
System.out.println(o);
boolean b = hashMap.containsKey(45);
//true
System.out.println(b);
boolean b1 = hashMap.containsValue(123);
//true
System.out.println(b1);
hashMap.clear();
//true
System.out.println(hashMap.isEmpty());
//equals();判斷兩個map是否相同
hashMap.put("AA",123);
hashMap.put("bb",123);
hashMap.put("cc",123);
HashMap hashMap1 = new HashMap();
hashMap1.putAll(hashMap);
boolean equals = hashMap.equals(hashMap1);
//true
System.out.println(equals);
}
- 元視圖操作的方法：
- Set keySet()：傳回所有key構成的Set集合
- Collection values()：傳回所有value構成的Collection集合
- Set entrySet()：傳回所有key-value對構成的Set集合
/**
* 元視圖的操作
*/
@Test
public void testMap03(){
HashMap hashMap = new HashMap();
hashMap.put("AA",123);
hashMap.put("bb",123);
hashMap.put("cc",123);
System.out.println("周遊map方式一：先擷取key，然後根據key擷取value。");
Set set = hashMap.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()){
Object next = iterator.next();
System.out.println(next+"="+hashMap.get(next));
}
System.out.println("周遊map方式二：entrySet()");
Set set1 = hashMap.entrySet();
Iterator iterator1 = set1.iterator();
while (iterator1.hasNext()){
Object next = iterator1.next();
Map.Entry entry=(Map.Entry)next;
System.out.println(entry.getKey()+"="+entry.getValue());
}
}
3.7 練習
- 寫一個方法鍵盤輸入字元串傳回一個map記錄時每個字元出現的次數。
@Test
public void test02() {
//1.從鍵盤中擷取字元串并轉化為char數組
@SuppressWarnings("resource")
Scanner input=new Scanner(System.in);
System.out.println("請輸入一串字元串！！！");
String str=input.next();
char[] chars=str.toCharArray();
//2.周遊數組，并存入到HashMap中去
HashMap<Character,Integer> hashMap = new HashMap<>();
for (int i = 0; i < chars.length; i++) {
hashMap.put(chars[i],hashMap.get(chars[i])==null?new Integer(1):hashMap.get(chars[i])+1);
}
Iterator<Character> iterator = hashMap.keySet().iterator();
while (iterator.hasNext()) {
Character next = iterator.next();
System.out.println(next+"出現了："+hashMap.get(next)+"次");
}
}
- 建立一個學生類：name sex score sid，建立一個map 裝10個學生：鍵是sid值是student對象，給所有女生分數+1，删除分數小于60的鍵值對，擷取平均分。
@Test public void test03() { HashMap<String, Student> hashMap=new HashMap<>(); hashMap.put("1", new Student("1","zhangsan","男",70)); hashMap.put("2", new Student("2","zhangsan","男",70)); hashMap.put("3", new Student("3","zhangsan","男",50)); hashMap.put("4", new Student("4","zhangsan","男",70)); hashMap.put("5", new Student("5","zhangsan","男",70)); hashMap.put("6", new Student("6","zhangsan","女",70)); hashMap.put("7", new Student("7","zhangsan","女",80)); hashMap.put("8", new Student("8","zhangsan","女",30)); hashMap.put("9", new Student("9","zhangsan","女",70)); hashMap.put("10", new Student("10","zhangsan","女",70)); System.out.println("初始hashMap："+hashMap); Set<String> keySet = hashMap.keySet(); Iterator<String> iterator = keySet.iterator(); ArrayList list=new ArrayList<String>(); int sum=0; while (iterator.hasNext()) { String sid=iterator.next(); Student student=hashMap.get(sid); if ("女".equals(student.getSex())) { student.setScore(student.getScore()+1); hashMap.put(sid, student); } student=hashMap.get(sid); if (student.getScore()<60) { list.add(student.getSid()); }else { sum+=student.getScore(); } } System.out.println("修改hashMap："+hashMap); for (int i = 0; i < list.size(); i++) { hashMap.remove(list.get(i)); } System.out.println("删除小于60之後："+hashMap); System.out.println("avg="+(sum*1.0/hashMap.size())); } class Student{ private String sid; private String name; private String sex; private int score; public String getSid() { return sid; } public void setSid(String sid) { this.sid = sid; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String getSex() { return sex; } public void setSex(String sex) { this.sex = sex; } public int getScore() { return score; } public void setScore(int score) { this.score = score; } public Student(String sid, String name, String sex, int score) { super(); this.sid = sid; this.name = name; this.sex = sex; this.score = score; } public Student() { super(); } @Override public String toString() { return "Student [sid=" + sid + ", name=" + name + ", sex=" + sex + ", score=" + score + "]"; } }
4 Collections工具類
4.1 Collections概述
Collections是操作Collection和Map的工具類。其中提供了一些靜态的方法對集合元素進行排序，查詢和修改等操作，還提供了對集合對象設定不可變，對集合對象實作同步控制等方法。
4.2 常用的方法
1 排序操作：（均為static方法）
- reverse(List)：反轉 List 中元素的順序
- shuffle(List)：對 List 集合元素進行随機排序
- sort(List)：根據元素的自然順序對指定 List 集合元素按升序排序
- sort(List，Comparator)：根據指定的 Comparator 産生的順序對 List 集合元素進行排序
- swap(List，int， int)：将指定 list 集合中的 i 處元素和 j 處元素進行交換
@Test
public void testCollections(){
ArrayList arrayList = new ArrayList();
arrayList.add(123);
arrayList.add(234);
arrayList.add(423);
arrayList.add(18);
//[123, 234, 423, 18]
System.out.println(arrayList);
//對集合進行反轉操作
Collections.reverse(arrayList);
//輸出：[18, 423, 234, 123]
System.out.println(arrayList);
//進行随機化處理
Collections.shuffle(arrayList);
System.out.println(arrayList);
//對集合中的元素進行升序排序，還有個重載的方法進行定制排序
Collections.sort(arrayList);
//[18, 123, 234, 423]
System.out.println(arrayList);
//對集合中的兩個位置元素進行換位
Collections.swap(arrayList,1,3);
//[18, 423, 234, 123]
System.out.println(arrayList);
}
2 查找、替換
- Object max(Collection)：根據元素的自然順序，傳回給定集合中的最大元素
- Object max(Collection，Comparator)：根據 Comparator 指定的順序，傳回給定集合中的最大元素
- Object min(Collection)：找出最小的元素
- Object min(Collection，Comparator)：根據比較器的規則找到最小的元素
- int frequency(Collection，Object)：傳回指定集合中指定元素的出現次數
- void copy(List dest,List src)：将src中的内容複制到dest中
- boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替換List對象的所有舊值
@Test
public void testCollections02() {
ArrayList arrayList = new ArrayList();
arrayList.add(123);
arrayList.add(234);
arrayList.add(423);
arrayList.add(423);
arrayList.add(423);
arrayList.add(18);
//傳回指定數的出現的次數
int frequency = Collections.frequency(arrayList, 423);
//3
System.out.println(frequency);
/* ArrayList list = new ArrayList();
Collections.copy(list,arrayList);
//java.lang.IndexOutOfBoundsException: Source does not fit in dest
//源碼
//int srcSize = src.size();
//if (srcSize > dest.size())
//throw new IndexOutOfBoundsException("Source does not fit in dest");
System.out.println(list);*/
//正确的寫法
List<Object> objects = Arrays.asList(new Object[arrayList.size()]);
Collections.copy(objects,arrayList);
System.out.println(objects);
objects.set(1,999);
//java.lang.UnsupportedOperationException:Arrays.asList傳回的list集合不可以進行添加操作==>長度不可變。
System.out.println(objects);
//replaceAll()
Collections.replaceAll(objects,18,180);
System.out.println(objects);
}
3 線程同步的相關操作
@Test
public void testCollections03() {
ArrayList arrayList = new ArrayList();
arrayList.add(123);
arrayList.add(234);
arrayList.add(423);
arrayList.add(423);
arrayList.add(423);
arrayList.add(18);
//傳回的list1是線程安全的list
List list = Collections.synchronizedList(arrayList);
}
總結：
每日一考：
1.Map存儲資料的特點是什麼？并指出key，value，entry存儲資料的特點。
map：雙列資料，存儲Key-Value對
key：無序，不可重複–>Set存儲
value：無序，可重複–>Collection存儲
entry：無序，不可重複–>Set來存儲
2.描述HashMap底層實作結構
JDK7：數組+連結清單
JDK8：數組+連結清單+紅黑二叉樹
3.Map的實作類有那些？各自的特點是什麼。
|–HashMap：map的主要實作類，線程不安全的，效率比較高；可以存儲key為null的鍵值對。
|–LinkedHashMap：對map進行周遊的時候可以按照添加的順序進行周遊==>維持了一對指針。
|–TreeMap：保證按照key-value進行排序，實作排序周遊，key隻能是同一類型的資料
|–Hashtable：map的古老實作類，線程安全的，效率低，不能存儲null值。
|–properties：常用來處理配置檔案，通常key和value是String類型。
4.如何周遊key-value鍵值對？
HashMap map=new HashMap();
Set set=map.keySet();
Iterator iterator=set.iterator();
while(iterator.hasNext()){
Object o=iterator.next(); //此時o是map中的key值。
System.out.printlb(o+"="+map.getValue(o))
}
5.Collection和Collections的差別？
Collection：是單列集合類接口，包含了一些基本操作，是Set和List接口的父接口。
Collections：是操作Collection和map的工具類，存在很多靜态方法。
6.想要使用map，還想要保證線程安全，如何做？
1）使用HashTable，線程安全的，但是由于内部的大部分方法都由synchronized所修飾，導緻效率并不高。
2）使用Collections的synchronized的方法來保證線程安全，其原理是給各個方法加上synchronized關鍵字，是以效率也不高。
3）使用ConcurrentHashmap。在1.7及以前，底層采用了數組（分段數組）加連結清單，使用segment分段鎖來保證線程安全，繼承了Reentranlock，嘗試擷取鎖的時候存在并發競争，自旋，阻塞。在jdk1.8的時候，底層采用了數組加連結清單加紅黑樹的資料結構，鎖采用cas+synchronized，cas失敗的時候保證自旋成功，如果再次失敗使用synchronized的方式保證成功，保證效率。
CAS：compareAndSwap，比較并替換，相當于一個輕量級的鎖，如果并發量比較大的時候，會出現自旋阻塞（存在忙循環），存在ABA的問題，可以使用一個戳或者版本号來進行區分。建議使用狀态機或者鎖。
7.synchronized的原理
1）偏向鎖
2）輕量級的鎖（适用于低并發）
3）自旋鎖（死循環）此過程是可重入鎖
4）重量級鎖
n(objects);
}
3 線程同步的相關操作
```java
@Test
public void testCollections03() {
ArrayList arrayList = new ArrayList();
arrayList.add(123);
arrayList.add(234);
arrayList.add(423);
arrayList.add(423);
arrayList.add(423);
arrayList.add(18);
//傳回的list1是線程安全的list
List list = Collections.synchronizedList(arrayList);
}
總結：
每日一考：
1.Map存儲資料的特點是什麼？并指出key，value，entry存儲資料的特點。
map：雙列資料，存儲Key-Value對
key：無序，不可重複–>Set存儲
value：無序，可重複–>Collection存儲
entry：無序，不可重複–>Set來存儲
2.描述HashMap底層實作結構
JDK7：數組+連結清單
JDK8：數組+連結清單+紅黑二叉樹
3.Map的實作類有那些？各自的特點是什麼。
|–HashMap：map的主要實作類，線程不安全的，效率比較高；可以存儲key為null的鍵值對。
|–LinkedHashMap：對map進行周遊的時候可以按照添加的順序進行周遊==>維持了一對指針。
|–TreeMap：保證按照key-value進行排序，實作排序周遊，key隻能是同一類型的資料
|–Hashtable：map的古老實作類，線程安全的，效率低，不能存儲null值。
|–properties：常用來處理配置檔案，通常key和value是String類型。
4.如何周遊key-value鍵值對？
HashMap map=new HashMap();
Set set=map.keySet();
Iterator iterator=set.iterator();
while(iterator.hasNext()){
Object o=iterator.next(); //此時o是map中的key值。
System.out.printlb(o+"="+map.getValue(o))
}
5.Collection和Collections的差別？
Collection：是單列集合類接口，包含了一些基本操作，是Set和List接口的父接口。
Collections：是操作Collection和map的工具類，存在很多靜态方法。
6.想要使用map，還想要保證線程安全，如何做？
1）使用HashTable，線程安全的，但是由于内部的大部分方法都由synchronized所修飾，導緻效率并不高。
2）使用Collections的synchronized的方法來保證線程安全，其原理是給各個方法加上synchronized關鍵字，是以效率也不高。
3）使用ConcurrentHashmap。在1.7及以前，底層采用了數組（分段數組）加連結清單，使用segment分段鎖來保證線程安全，繼承了Reentranlock，嘗試擷取鎖的時候存在并發競争，自旋，阻塞。在jdk1.8的時候，底層采用了數組加連結清單加紅黑樹的資料結構，鎖采用cas+synchronized，cas失敗的時候保證自旋成功，如果再次失敗使用synchronized的方式保證成功，保證效率。
CAS：compareAndSwap，比較并替換，相當于一個輕量級的鎖，如果并發量比較大的時候，會出現自旋阻塞（存在忙循環），存在ABA的問題，可以使用一個戳或者版本号來進行區分。建議使用狀态機或者鎖。
7.synchronized的原理
1）偏向鎖
2）輕量級的鎖（适用于低并發）
3）自旋鎖（死循環）此過程是可重入鎖
4）重量級鎖