11.集合
- 集合框架的描述
一.集合框架的概述
1.集合,數(shù)組都是對多個數(shù)據(jù)進(jìn)行存儲操作的結(jié)構(gòu),簡稱Java容器
說明: 此時的存儲,主要指的是內(nèi)存層面的存儲,不涉及到(硬盤)持久化的存儲(.txt,.jpg,,avi,數(shù)據(jù)庫中)
2.1.數(shù)組在存儲多個數(shù)據(jù)方面的特點:
一旦初始化以后,其長度就確定了.
數(shù)組一旦定義好,其元素的類型也就確定了.也就只能操作指定類型的數(shù)據(jù)了.
比如: String[] arr;int[] arr1; Ojbect[] arr2; 還能往父類中裝子類數(shù)據(jù)
2.2.數(shù)組在存儲多個數(shù)據(jù)方面的缺點:
一旦初始化后,其長度就不可修改
數(shù)組中提供的方法非常有限,對于添加,刪除,插入數(shù)據(jù)等操作,非常不便,同時效率不高
獲取數(shù)組中實際元素的個數(shù)的需求,數(shù)組沒有現(xiàn)成的屬性或方法可用
數(shù)組存儲數(shù)據(jù)的特點: 有序,可重復(fù).對于無序,不可重復(fù)的需求,不能滿足
- 集合框架及涉及到的api
二.集合框架
Collection接口: 單列集合,用來存儲一個一個的對象
List接口: 存儲有序的,可重復(fù)的數(shù)據(jù). --> "動態(tài)"數(shù)組
ArrayList,LinkedList,Vector
Set接口: 存儲無序的,不可重復(fù)的數(shù)據(jù) --> 高中的"集合"
HashSet,LinkedHashedSet,TreeSet
Map接口: 雙列集合,用來存儲一對(key-value)一對的數(shù)據(jù) --> 高中函數(shù): y = f(x)
HashMap,LinkedHashMap,TreeMap,Hashtable,Properties
- Collection接口的常用方法
結(jié)論:
向Collection接口的實現(xiàn)類的對象中添加數(shù)據(jù)obj時,要求obj所在類要重寫equals()
public class CollectionTest {
// 修改了原集合
@Test
public void test4(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
//7.hashcode():返回當(dāng)前對象的哈希值,因為方法定義在Object類中,所有對象都可以調(diào)該方法
System.out.println(coll.hashCode());
// 8.集合轉(zhuǎn)化為數(shù)組: toArray():
Object[] arr = coll.toArray();// 返回Object類型數(shù)組
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
// 拓展: 數(shù)組 --> 集合: 調(diào)用Arrays類的靜態(tài)方法asList()
// asList的形參是可變參數(shù),相當(dāng)于數(shù)組,所以也可以傳入數(shù)組,返回具體的List,是List肯定是Collection,因為數(shù)組對應(yīng)的集合就是List
List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
System.out.println(list);
List arr1 = Arrays.asList(new int[]{1, 2, 3});// 集合不能存基本數(shù)據(jù)類型,集合把這個整個當(dāng)成一個參數(shù)了
System.out.println(arr1.size());// 1
List arr2 = Arrays.asList(123,456);
System.out.println(arr2.size());// 2
// iterator(): 返回Iterator接口的實例,用于遍歷集合元素.放在IteratorTest.java中測試
}
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 5.retainAll(Collection coll): 交集,獲取當(dāng)前集合和coll1集合的交集,并修改當(dāng)前集合;保留一樣的,刪除不一樣的
// 保留兩個集合都有的元素
// Collection coll1 = Arrays.asList(123, 456, 789);
// coll.retainAll(coll1);
System.out.println(coll);
// 6.equals(Object obj): 要想返回true,需要當(dāng)前集合和形參集合的元素都相同,關(guān)于有沒有序看實現(xiàn)類是誰
// 集合與集合比較,并且集合元素都一樣才能退返回true,一個一個元素比較,也會涉及到相關(guān)元素所在類equals方法的調(diào)用
// coll1元素順序改變,返回false,因為ArrayList實現(xiàn)類是有序的
Collection coll1 = new ArrayList();
coll1.add(123);
coll1.add(456);
coll1.add(new Person("jerry", 20));
coll1.add(new String("tom"));
coll1.add(false);
System.out.println(coll.equals(coll1));// true
}
@Test
public void test2(){
//3.remove(Object obj): 從當(dāng)前集合中移除obj元素,返回布爾值
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
coll.remove(123);// 也調(diào)用equals方法
System.out.println(coll);
coll.remove(new Person("jerry", 20));// Person類重寫了equals方法移除成功
// 4.removeAll(Collection coll1): 差集,從當(dāng)前集合中移除coll1中所有的元素, 該方法調(diào)了coll1集合中元素的equals方法
// 移除兩個集合都有的元素
Collection coll1 = Arrays.asList(123, 456);
coll.removeAll(coll1);
System.out.println(coll);
}
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);// 傳入包裝類對象,自動裝箱成Integer類
coll.add(456);
coll.add(new Person("jerry", 20));// contains方法判斷得到結(jié)果后終止調(diào)用equals方法
coll.add(new String("tom"));
coll.add(false);// Boolean類型
// 自定義類型
/*Person p = new Person("jerry", 20);
coll.add(p);*/
// 1.contains(Object e): 判斷當(dāng)前集合中是否包含obj(對象)
// 在判斷時會調(diào)用obj對象所在類的equals方法
boolean contains = coll.contains(123);
System.out.println(contains);// true
System.out.println(coll.contains(new String("tom")));// true;因為String重寫了equals方法,比的是內(nèi)容
// System.out.println(coll.contains(p));// true 比較用 == 或 equals都是true,同一個引用
System.out.println(coll.contains(new Person("jerry", 20)));// false-->true,因為比內(nèi)容的前提是Person類自己重寫了equals方法,沒有則調(diào)用Object的
//2.containsAll(Collection coll1): 判斷形參coll1中的所有元素是否都存在于coll集合中.
Collection coll1 = Arrays.asList(123,456);// 工具類中的方法,返回是ArrayList類型對象,
System.out.println(coll.containsAll(coll1));// true
}
@Test
public void test(){
Collection coll = new ArrayList();// 用ArrayList作為他的子接口的實現(xiàn)類進(jìn)行測試
// 1.add(Ojbect e): 將元素e添加到集合coll中
coll.add("AA");
coll.add("BB");
coll.add(123);// 基本數(shù)據(jù)類型,自動裝箱,轉(zhuǎn)換包裝類了
coll.add(new Date());
// 2.size(): 獲取添加的元素個數(shù)
System.out.println(coll.size());// 4
// 3.addAll(Collection coll1): 將coll1集合中的元素添加到當(dāng)前的集合中
Collection coll1 = new ArrayList();
coll1.add(456);
coll1.add("CC");
coll.add(coll1);
System.out.println(coll.size());// 6
System.out.println(coll.toString());// toString是ArrayList實現(xiàn)類重寫過的
// clear(): 清空集合元素
coll.clear();
// isEmpty(): 判斷當(dāng)前集合是否為空(元素個數(shù))
System.out.println(coll.isEmpty());// false
}
}
11.3.迭代器Iterator接口
集合元素的遍歷操作,使用迭代器Iterator接口
1.內(nèi)部方法: hasNext()和next()
2.集合對象每次調(diào)用iterator()方法都得到一個全新的迭代器對象,默認(rèn)游標(biāo)都在集合的第一個元素之前
3.內(nèi)部定義了remove(),可以在遍歷的時候,刪除集合中的元素.此方法不同于Collection集合直接調(diào)用remove()
- 使用iterator遍歷Collection
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 獲取迭代器對象
// 方式一:
Iterator iterator = coll.iterator();// 他是迭代器不是容器,只用于遍歷
/*System.out.println(iterator.next());
System.out.println(iterator.next());
System.out.println(iterator.next());
System.out.println(iterator.next());
System.out.println(iterator.next());
// 報異常 NoSuchElementException
System.out.println(iterator.next());*/
// 方式二: 不推薦
/*for (int i = 0; i < coll.size(); i++) {
System.out.println(iterator.next());
}*/
// 方式三: 推薦
// hasNext():判斷是否還有下一個元素
while (iterator.hasNext()){
// next(): 指針下移,將下移以后集合位置上的元素返回
System.out.println(iterator.next());
}
}
- 迭代器iterator的執(zhí)行原理
- iterator遍歷集合的錯誤寫法
@Test
public void test2(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 錯誤方式一: 間隔輸出,并且報異常
/* Iterator iterator = coll.iterator();
while (iterator.next() != null){
System.out.println(iterator.next());
}*/
// 錯誤方式二: 集合對象每次調(diào)用iterator()方法都得到一個全新的迭代器對象,默認(rèn)游標(biāo)都在集合的第一個元素之前
while (coll.iterator().hasNext()){// 每調(diào)一次iterator方法,都返回一個迭代器對象,新指針就會在開頭
System.out.println(coll.iterator().next());// 始終輸出第一個元素
}
}
- 迭代器iterator remove()的使用
// 測試Iterator中的remove(): 刪除當(dāng)前指針指向的集合元素
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 刪除集合中"tom"
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
// iterator.remove();// 報異常
// next值用Object類型的對象接收,因為返回值是Object類型
Object obj = iterator.next();
// 先寫tom健壯性更好一些
if ("tom".equals(obj)){// 如果obj存null的話,拿obj調(diào)就空指針了
iterator.remove();// 移除當(dāng)前數(shù)據(jù)
iterator.remove();// 報異常
}
}
// 重新遍歷要重新獲取迭代器對象
iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
- 新特性foreach循環(huán)遍歷
public class ForTest {
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// for (集合元素類型 局部變量 : 集合對象(變量))
// 遍歷集合:把集合里的每個元素賦給obj,輸出
// 內(nèi)部仍然調(diào)用了迭代器
for (Object obj : coll){// obj:局部變量,相當(dāng)于int i,可隨意指定
System.out.println(obj);
}
}
@Test
public void test2(){
int[] arr = new int[]{1, 2, 3, 4, 5, 6};
// for(數(shù)組元素的類型 局部變量 : 數(shù)組對象)
for (int i : arr) {
System.out.println(i);
}
}
@Test
public void test3(){
String[] arr = new String[]{"MM", "MM", "MM", "MM"};
// 方式一: 普通for賦值
for (int i = 0; i < arr.length; i++) {
arr[i] = "GG";// 用本身數(shù)組元素做修改,用字面量修改,原數(shù)組在常量池里重新指向新空間區(qū)域
}
// 方式二: 增強(qiáng)for循環(huán)
for (String s : arr) {
s = "GG";// 把原數(shù)組元素取出賦值給新設(shè)定的局部變量s,在s里修改,arr的元素不變
}
for (int i = 0; i < arr.length; i++) {
// 普通for循環(huán)輸出GG,增強(qiáng)for循環(huán)輸出MM
System.out.println(arr[i]);
}
}
}
11.4.Collection的子接口之一: List接口
Collection接口: 單列集合,用來存儲一個一個的對象
List接口: 存儲有序的,可重復(fù)的數(shù)據(jù). --> "動態(tài)"數(shù)組,替換原有的數(shù)組,本質(zhì)替換的是List接口
ArrayList: 作為List接口的主要實現(xiàn)類: 線程不安全的,效率高;底層用Object[] elementData存儲封裝
LinkedList: 對于頻繁的插入,刪除操作,用此類效率比ArrayList高;底層用雙向鏈表存儲
Vector: 作為List接口的古老實現(xiàn)類: 線程安全的,效率低;底層用Object[] elementData存儲
2.ArrayList的源碼分析:
2.1.jdk7情況下
ArrayList list = new ArrayList();// 底層創(chuàng)建了長度是10的Object[]數(shù)組elementData
list.add(123);// elementData[0] = new Integer(123);
....
list.add(11);// 如果此次的添加導(dǎo)致底層elementData數(shù)組容量不夠,則擴(kuò)容.
默認(rèn)情況下,擴(kuò)容(新造一個數(shù)組)為原來的容量的1.5倍(10>>1 = 5,10+5=15,15/10 = 1.5倍),同時要將原有的數(shù)組中的數(shù)據(jù)復(fù)制到新的數(shù)組中,這個新數(shù)組就作為目前的elementData的新值完成擴(kuò)容
結(jié)論: 知道ArrayList中基本要放多少數(shù)據(jù),建議開發(fā)中用帶參構(gòu)造器: ArrayList list = new ArrayList(int capacity),因為底層不用給你擴(kuò)容了,提高效率
2.2.jdk8中的ArrayList的變化:
ArrayList list = new ArrayList();// 底層創(chuàng)建了長度是10的Object[]數(shù)組elementData初始化為{},并沒有創(chuàng)建長度
list.add(123);// 第一次調(diào)用add()時,底層才創(chuàng)建了長度10的數(shù)組,并將數(shù)據(jù)123天假到elementData[0]
...
后續(xù)的添加和擴(kuò)容操作與jdk7 無異
2.3.小結(jié): jdk7中的ArrayList的對象創(chuàng)建類似于單例的餓漢式,而jdk8中的ArrayList的對象的創(chuàng)建類似于單例的懶漢式,延遲了數(shù)組的創(chuàng)建,節(jié)省內(nèi)存.
3.LinkedList的源碼分析:
LinkedList list new LinkedList();// 內(nèi)部聲明了Node類型的first和last屬性,默認(rèn)值為null
list.add(123);//將123封裝到Node中,創(chuàng)建了Node對象
其中,Node定義為: 體現(xiàn)了LinkedList的雙向鏈表的說法
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;
}
}
4.Vector的源碼分析: jdk7和jdk8中通過Vector()構(gòu)造器創(chuàng)建對象時,底層都創(chuàng)建了長度為10的數(shù)組.
在擴(kuò)容方面,默認(rèn)擴(kuò)容為原來的數(shù)組長度的2倍.
總結(jié)常用方法
增: add(Object obj)
刪: remove(int index)/remove(Object obj)
改: set(index, Object ele)
查: get(int index)
插: add(int index,Object ele)
面試題: ArrayList,LinkedList,Vector三者的異同?
同: 三個類都是實現(xiàn)了List接口,存儲數(shù)據(jù)的特點相同他: 存儲有序的,可重復(fù)的數(shù)據(jù)
不同: 見上
public class ListTest {
@Test
public void test3(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("tom",20));
list.add(456);
//方式一: Iterator迭代器方式
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("================");
// 方式二: 增強(qiáng)for循環(huán)
for (Object obj : list){
System.out.println(obj);
}
System.out.println("=================");
// 方式三: 普通for循環(huán)
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
@Test
public void test2(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("tom",20));
list.add(456);
// int indexOf(Object obj): 返回obj在集合中首次出現(xiàn)的位置.如不存在,返回-1
int index = list.indexOf(456);
System.out.println(index);// 1
System.out.println(list.lastIndexOf(456));// 4,如不存在返回-1
// Object remove(int index): 移除指定index位置的元素,并返回被移除的元素, 是該方法為重載方法,不是重寫,因為形參不一樣
Object obj = list.remove(0);
System.out.println(obj);// 123
System.out.println(list);
// Object set(index, Object ele): 把指定index位置的元素改為ele
list.set(1,"CC");
System.out.println(list);
// List subList(int fromIndex, int toIndex):返回從fromIndex到toIndex位置的左閉右開子集合,相當(dāng)于提供當(dāng)前l(fā)ist的子list
List subList = list.subList(2,4);
System.out.println(subList);
System.out.println(list);// 原list不變
}
@Test
public void test1(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("tom",20));
list.add(456);
System.out.println(list);
// void add(int index,Object ele): 在index位置插入ele元素
list.add(1, "BB");
System.out.println(list);
// boolean addAll(int index, Collection eles):從index位置開始將eles中的所有元素添加進(jìn)來
// List list1 = Arrays.asList(new int[]{1, 2, 3});// 整個參數(shù)被當(dāng)做一個整體
List list1 = Arrays.asList(1,2,3);// 自動裝箱作為包裝類傳入
//list.addAll(list1);// 把list1的所有元素當(dāng)做一個整體參數(shù)
list.addAll(list1);// 把元素都加到集合中
System.out.println(list);// 打印元素個數(shù)
// Object get(int index): 獲取index位置的元素
System.out.println(list.get(0));//123
}
}
11.5.Collection子接口之二: Set接口
- Set接口的實現(xiàn)類的對比
- Set接口的框架:
Collection接口: 單列集合,用來存儲一個一個的對象
Set接口: 存儲無序的,不可重復(fù)的數(shù)據(jù) --> 高中的"集合"
HashSet: 作為Set接口的主要實現(xiàn)類: 線程不安全的;可以存儲null值
LinkedHashedSet: 作為HashSet的子類;遍歷其內(nèi)部數(shù)據(jù)時,可以按照添加的順序遍歷,為頻繁遍歷操作準(zhǔn)備的一個類
對于頻繁的遍歷操作,LinkedHashSet效率高于HashSet
TreeSet: 可以按照添加對象的指定屬性,進(jìn)行排序.
- Set的無序性和不可重復(fù)性的理解
1.Set接口中沒有額外定義新的方法,用的都是Collection中聲明過的方法.Set無序也就沒有索引了,也就沒有新的方法
Set接口: 存儲無序的,不可重復(fù)的數(shù)據(jù)
1.無序性: 不等于隨機(jī)性,有固定順序.存儲的數(shù)據(jù)在底層數(shù)組中并非按照數(shù)組索引的順序添加,而是根據(jù)數(shù)據(jù)的哈希值決定的.
指添加的時候,存放的位置不是一個挨一個的順序放的
2.不可重復(fù)性: 保證添加的元素按照equals()判斷時,不能返回true.即: 相同的元素只能添加一個
@Test
public void test1(){
// 實例化HashSet實現(xiàn)類
// 哈希值用對象屬性來計算的
Set set = new HashSet();
set.add(456);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("tom",20));
set.add(new User("tom",20));
set.add(129);
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
public class User implements Comparable{
private String name;
private int age;
@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
", 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;
}
public User(String name, int age) {
this.name = name;
this.age = age;
}
public User() {
}
@Override
public boolean equals(Object o) {
System.out.println("User equals()...");
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
if (age != user.age) return false;
return name != null ? name.equals(user.name) : user.name == null;
}
// 如果User類沒有重寫hashcode方法,則會調(diào)用Object類的hashcode方法,而Object中的方法是隨機(jī)計算的,所以就算是相同元素都會計算出不同的哈希值
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
// 重寫排序方法,按照姓名從大到小排列,年齡從小到大排列
@Override
public int compareTo(Object o) {
if (o instanceof User){
User user = (User) o;
int compare = -this.name.compareTo(user.name);
if (compare != 0){
return compare;
}else{
return Integer.compare(this.age, user.age);
}
}else{
throw new RuntimeException("輸入類型不匹配");
}
}
}
- HashSet中元素添加的過程
二.添加元素的過程: 以HashSet為例:
向HashSet中添加元素a,首先調(diào)用元素a所在類的hashcode方法,計算元素a的哈希值,
此哈希值接著通過某種算法計算出在HashSet底層數(shù)組中的存放位置(即為: 索引位置),判斷
數(shù)組此位置上是否已經(jīng)有元素:
如果此位置上沒有其他元素,則元素a添加成功. --> 情況1
如果此位置上有其他元素b(或以鏈表形式存在的多個元素), 則比較元素a與元素b的hash值:
如果hash值不相同,則元素a添加成功. --> 情況2
如果hash值相同,進(jìn)而需要調(diào)用元素a所在類的equals方法:
equals()返回true,元素a添加失敗
equals()返回false,則元素a添加成功. --> 情況3
對于添加成功的情況2和情況3而言: 元素a 與已經(jīng)存在指定索引位置上數(shù)據(jù)以鏈表的方式存儲.
jdk7: 元素a放到數(shù)組中,指向原來的元素.(頭插法)
jdk8: 原來的元素在數(shù)組中,指向元素a.(尾插法)
總結(jié): 七上八下
HashSet底層: 數(shù)組+鏈表的結(jié)構(gòu)
- 關(guān)于hashcode()和equals()的重寫
2.要求:
①向Set中添加的數(shù)據(jù),其所在的類一定要重寫hashcode方法和equals方法
②重寫的hashcode方法和equals方法盡可能保持一致性,相等的對象必須具有相等的散列碼(哈希值)
如果兩個對象equals方法比較的屬性不一樣,算出的哈希值不要一樣,如果比較的equals方法的屬性相同,讓他們算出的哈希值也一樣
重寫兩個方法的小技巧: 對象中用作equals()方法比較的Field,都應(yīng)該用來計算hashcode
- LinkedHashSet的使用
// LinkedHashSet的使用
//LinkedHashSet作為HashSet的子類,在添加數(shù)據(jù)的同時,每個數(shù)據(jù)還維護(hù)了兩個引用,記錄此數(shù)據(jù)的前一個數(shù)據(jù)和后一個數(shù)據(jù).
// 優(yōu)點: 對于頻繁的遍歷操作,LinkedHashSet效率高于HashSet
// 缺點: 空間內(nèi)存大
@Test
public void test2(){
Set set = new LinkedHashSet();
set.add(456);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("tom",20));
set.add(new User("tom",20));
set.add(129);
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
- TreeSet的使用
向TreeSet中添加的數(shù)據(jù),要求是相同類的對象
兩種排序方式: Java比較器: 自然排序(實現(xiàn)Comparable接口) 和 定制排序
自然排序中,比較兩個對象是否相同的標(biāo)準(zhǔn)為: compareTo()返回0,不再是用equals().言外之意,TreeSet不能放相同的數(shù)據(jù)
定制排序中,比較兩個對象是否相同的標(biāo)準(zhǔn)為: compare()返回0,不再是用equals()
- TreeSet的自然排序
@Test
public void test1(){
TreeSet set = new TreeSet();
//失敗: 不能添加不同類的對象
/* set.add(123);
set.add(456);
set.add("AA");
set.add(new User("tom",12));*/
// 舉例一: Integer類型排序,包裝類已經(jīng)重寫過compareTo方法,默認(rèn)從小到大排序
/*set.add(34);
set.add(-35);
set.add(12);
set.add(6);*/
// 舉例二: 自定義類排序,直接運(yùn)行報錯,沒有實現(xiàn)Comparable接口,
// 自定義類要實現(xiàn)Comparable接口并且重寫compareTo方法
set.add(new User("Tom", 12));
set.add(new User("Tom", 12));
set.add(new User("Jerry", 32));
set.add(new User("Jim", 65));
set.add(new User("Jack", 33));
// 下面這一條數(shù)據(jù)沒有輸出,因為在User類中通過compareTo方法比較name屬性的時候,判斷這兩個對象是一樣的,
//相當(dāng)于在User類里return -this.name.compareTo(user.name);語句中的compareTo方法中返回了0,所以兩個對象相等
// 在TreeSet中,判斷兩個對象相同不相同的標(biāo)準(zhǔn)不再是equals方法,不同于HashSet,LinkedHashedSet,比較是否相同本質(zhì)上是equals,
// TreeSet本質(zhì)上,比較是用compareTo方法,若返回0,則兩對象相同
set.add(new User("Jack", 56));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
- TreeSet的定制排序
// 定制排序
@Test
public void test2(){
// 創(chuàng)建一個Comparator接口的匿名實現(xiàn)類的非匿名對象
Comparator com = new Comparator() {
// 按照年齡從小到大排序
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof User && o2 instanceof User) {
User u1 = (User) o1;
User u2 = (User) o2;
return Integer.compare(u1.getAge(), u2.getAge());
}else{
throw new RuntimeException("輸入類型不匹配");
}
}
};
TreeSet set = new TreeSet(com);// 不傳入?yún)?shù)則按照自然排序來排,加上參數(shù)就按參數(shù)方式來排
set.add(new User("Tom", 12));
set.add(new User("Jerry", 32));
set.add(new User("Jim", 65));
// 當(dāng)要比較的屬性一樣時,則會先來的輸出,后來的去除
set.add(new User("Mary", 33));
set.add(new User("Jack", 33));
set.add(new User("Jack", 56));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
11.6.Map接口
大廠面試只要說出康師傅講的和什么時候轉(zhuǎn)化成紅黑樹即可，小廠被直接問到ConcurrentHashMap底層如何實現(xiàn)，完全不會
- Map接口及其多個實現(xiàn)類的對比
一.Map的實現(xiàn)類的結(jié)構(gòu):
Map: 雙列數(shù)據(jù), 存儲key-value對的數(shù)據(jù) --類似于高中的函數(shù): y = f(x)
HashMap實現(xiàn)類: 作為Map的主要實現(xiàn)類: 線程不安全的,效率高; 可以存儲null的key和value
LinkedHashMap(HashMap的子類): 保證在遍歷map元素時,可以按照添加的順序?qū)崿F(xiàn)遍歷
原因: 在原有的HashMap底層結(jié)構(gòu)基礎(chǔ)上,添加了一對指針,指向前一個和后一個元素.相當(dāng)于記錄了當(dāng)前添加的key-value的前一個是誰后一個是誰,使得就能按順序遍歷,查找更方便了
對于頻繁的遍歷操作,此類執(zhí)行效率高于HashMap.
TreeMap實現(xiàn)類: 類似于TreeSet,保證按照添加的key-value對進(jìn)行排序,實現(xiàn)排序遍歷.此時考慮key的自然排序或定制排序
底層使用紅黑樹(平衡二叉查找樹)
Hashtable實現(xiàn)類: 作為古老的實現(xiàn)類: 線程安全的,效率低; 不能存儲null的key和value
Properties(Hashtable的子類): 常用來處理配置文件. key和value都是String類型
HashMap的底層: 數(shù)組+鏈表 (jdk7及之前)
數(shù)組+鏈表+紅黑樹;為了提高效率(jdk8)
- Map中存儲的key-value的特點
二.Map結(jié)構(gòu)的理解:
Map中的key: 無序的,不可重復(fù)的,用Set存儲所有的key,如果是HashMap就用HashSet存,若是LinkedHashMap就用LinkedHashMap存 --> 要求key所在的類要重寫equals()和hashcode() (以HashMap為例),重寫hashcode是為了效率高點或找key方便點
Map中的value: 無序的,可重復(fù)的,用Collection存儲所有的value --> value所在的類要重寫equals(),判斷有沒有,為了實現(xiàn)通過value找key的方法
一個鍵值對: key-value構(gòu)成一個entry對象,key和value相當(dāng)于entry的兩個屬性
Map中的Entry: 無序的,不可重復(fù)的,用Set存儲所有的Entry
- HashMap在jdk7中底層的實現(xiàn)原理
三.HashMap的底層實現(xiàn)原理? 以jdk7為例說明:
HashMap map = new HashMap();
在實例化以后,底層創(chuàng)建了長度是16的一維數(shù)組Entry[] table
...之前可能已經(jīng)執(zhí)行過多次put...
map.put(key1,value1): 添加操作
首先,調(diào)用key1所在類的hashcode()計算key1哈希值,此哈希值經(jīng)過某種算法計算以后,得到在Entry數(shù)組中的存放位置.(跟HashSet有點像)
若此位置上的數(shù)據(jù)為空,此時的key1-value1添加成功. -- 情況1;實際上添到數(shù)組上的數(shù)據(jù)是entry,理論上是雙列數(shù)據(jù),實際上還是一個一個的,比的都是entry,只不過用entry中的key來判斷存在哪的一個標(biāo)準(zhǔn),實際上是entry添加成功
若此位置上的數(shù)據(jù)不為空,(意味著此位置上存在一個或多個數(shù)據(jù)(以鏈表形式存在)),比較key1和已經(jīng)存在的一個或多個數(shù)據(jù)的哈希值:
若key1的哈希值與已經(jīng)存在數(shù)據(jù)的哈希值不相同,此時key1-value1添加成功.-- 情況2
若key1的哈希值和已經(jīng)存在的某一個數(shù)據(jù)(key2-value2)的哈希值相同,繼續(xù)比較: 調(diào)用key1所在類的equals(key2)方法,比較:
若equals()返回false:此時key1-value1添加成功.-- 情況3
若equals()返回true: 用value1替換(覆蓋)value2
補(bǔ)充: 關(guān)于情況2和情況3: 此時key1-value1和原來的數(shù)據(jù)以鏈表的方式存儲
在不斷地添加過程中,會涉及到擴(kuò)容問題,當(dāng)超出臨界值(且要存放的位置非空)時,擴(kuò)容.默認(rèn)的擴(kuò)容方式: 擴(kuò)容為原來容量的2倍,并將原有的數(shù)據(jù)復(fù)制過來
- HashMap在jdk8中底層的實現(xiàn)原理
jdk8相較于jdk7在底層實現(xiàn)方面的不同:
1.new HashMap(): 底層沒有創(chuàng)建一個長度為16的數(shù)組
2.jdk8底層的數(shù)組是: Node[], 而非Entry[]
3.首次調(diào)用put()方法時,底層創(chuàng)建長度為16的數(shù)組
4.jdk7底層結(jié)構(gòu)只有: 數(shù)組+鏈表. jdk8中底層結(jié)構(gòu): 數(shù)組+鏈表+紅黑樹
當(dāng)數(shù)組的某一個索引位置刪的元素以鏈表形式存在的數(shù)據(jù)個數(shù) > 8 且當(dāng)前數(shù)組的長度 > 64時,
此時此索引位置上的所有數(shù)據(jù)改為用紅黑樹存儲.采用二分查找的方式,提高查詢效率
HashMap在jdk7中的源碼分析
HashMap在jdk8中的源碼分析
DEFAULT_INITIAL_ CAPACITY : HashMap的默認(rèn)容量，16
DEFAULT_LOAD_FACTOR: HashMap的默認(rèn)加載因子:0.75
DEFAULT_INITIAL_ CAPACITY : HashMap的默認(rèn)容量，16DEFAULT_LOAD_FACTOR: HashMap的默認(rèn)加載因子:0.75
threshold:擴(kuò)容的臨界值，=容量填充因子:16 0.75 =>12
TREEIEY_ THRESHOLD: Bucket中鏈表長度大于該默認(rèn)值，轉(zhuǎn)化為紅黑樹:8
MIN_TREEIFY_CAPACITY:桶中的Node被樹化時最小的hash表容量:64
- LinkedHashMap的底層實現(xiàn)原理
四.LinkedHashMap的底層實現(xiàn)原理(了解)
LinkedHashMap底層使用的結(jié)構(gòu)與HashMap相同，因為LinkedHashMap繼承于HashMap.
區(qū)別就在于: LinkedHashMap內(nèi)部提供了Entry，替換HashMap中的Node.
HashMap中的內(nèi)部類:Node
源碼中:
static class Node<K,V> implements Map.Entry<K,V> {
fina1 int hash;
final K key; value;
Node<K,V>next;
}
LinkedHashMap中的內(nèi)部類: Entry
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);
}
}
- Map中常用的方法
public class MapTest {
@Test
public void test5(){
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 123);
map.put("BB", 56);
// keySet(): 遍歷所有的key構(gòu)成的集合, set是所有的key構(gòu)成的
Set set = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("=========");
// values(): 遍歷所有的value集,和key一一對應(yīng)
Collection values = map.values();
for (Object obj : values){
System.out.println(obj);
}
System.out.println("=========");
// 遍歷所有的key-value,可以單獨把key或value值取出
// 方式一:
// entrySet(): 獲取所有的entry構(gòu)成的Set集合
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()) {
Object obj = iterator1.next();
// entrySet集合中的元素都是entry,所以可以把obj向下強(qiáng)轉(zhuǎn)
// 向下強(qiáng)轉(zhuǎn)可以單獨拿到key和value
Map.Entry entry = (Map.Entry) obj;// Entry接口類型的引用,不是實例對象,接口引用指向?qū)崿F(xiàn)類的對象，多態(tài)
System.out.println(entry.getKey() + "-->" + entry.getValue());
}
// 方式二:
Set keySet = map.keySet();
Iterator iterator2 = keySet.iterator();
while (iterator2.hasNext()) {
Object key = iterator2.next();// 獲取map的key值
Object value = map.get(key);// 通過指定的key獲取對應(yīng)的value
System.out.println(key + "==>" + value);
}
}
@Test
public void test4(){
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 123);
map.put("BB", 56);
// Object get(Object key): 獲取指定key對應(yīng)的value,key不存在返回null
System.out.println(map.get(45));// 123
// containsKey(Object key): 是否包含指定的key
boolean isExist = map.containsKey("BB");// 先通過哈希值找到指定key在數(shù)組中的位置,再通過equals方法找到對應(yīng)的key
// containsValue(Object key): 是否包含指定的value,若有多個相同的value,只要找到一個是true后就終止
isExist = map.containsValue(123);
// int size(): 返回map的key-value對的個數(shù)
// boolean isEmpty(): 判斷當(dāng)前map是否為空
map.clear();// 只是清空table中的元素,new的對象仍然存在
System.out.println(map.isEmpty());// true 判斷是否為空,只要判斷size是否為0
// boolean equals(Object obj): 判斷當(dāng)前map和參數(shù)對象obj是否相等,類型相同,內(nèi)容相同
}
@Test
public void test3(){
Map map = new HashMap();
// 一般情況下,key-value類型都是確定的
//添加
map.put("AA", 123);
map.put(45, 123);
map.put("BB", 56);
// 修改,替換原有的
map.put("AA", 87);
System.out.println(map);
// putAll()
Map map1 = new HashMap();
map1.put("CC", 123);
map1.put("DD", 123);
map.putAll(map1);
System.out.println(map);
// remove(Object key): 移除指定的key的key-value對,并返回value
Object value = map.remove("CC");//存在返回對應(yīng)value,不存在返回null
System.out.println(value);
System.out.println(map);
// clear(): 將map中所有元素清空
map.clear();// 與map = null 操作不同,Collection集合clear之后調(diào)isEmpty不會空指針異常,
System.out.println(map.size());// 元素個數(shù) 0
System.out.println(map);// {}
}
@Test
public void test2(){
// 無序性: 數(shù)組放的元素不是一個一個緊挨著的
Map map = new HashMap();
map = new LinkedHashMap();// 按照添加順序來能夠記錄誰先加誰后加
map.put(123,"AA");
map.put(345,"BB");
map.put(12,"CC");
System.out.println(map);
}
@Test
public void test1(){
Map map = new HashMap();
// map = new Hashtable();// 報錯
map.put(null, null);
}
}
- TreeMap兩種添加方式的使用
向TreeMap中添加key-value,要求key必須是由同一個類創(chuàng)建的對象
因為要按照key進(jìn)行排序: 自然排序,定制排序,不能按照value排序
// 自然排序
@Test
public void test1(){
TreeMap map = new TreeMap();// 自然排序調(diào)空參構(gòu)造器
User u1 = new User("Tom", 23);
User u2 = new User("Jerry", 32);
User u3 = new User("Jack", 20);
User u4 = new User("Rose", 18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
// 遍歷集合
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "-->" + entry.getValue());
}
}
// TreeMap的定制排序,按年齡從小到大排
@Test
public void test2(){
// 創(chuàng)建TreeMap中的比較器的匿名實現(xiàn)類的匿名對象
TreeMap map = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 判斷比較的對象是否屬于User類
if (o1 instanceof User && o2 instanceof User) {
// 向下強(qiáng)轉(zhuǎn)
User u1 = (User) o1;
User u2 = (User) o2;
// 通過年齡,從小到大排序
return Integer.compare(u1.getAge(), u2.getAge());
}else{
// 如果比較類型不是User類型
throw new RuntimeException("輸入類型不匹配");
}
}
});
User u1 = new User("Tom", 23);
User u2 = new User("Jerry", 32);
User u3 = new User("Jack", 20);
User u4 = new User("Rose", 18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
// 遍歷集合
// 創(chuàng)建遍歷key-value集合的對象
Set entrySet = map.entrySet();
// 創(chuàng)建遍歷集合對象的迭代器
Iterator iterator = entrySet.iterator();
// 循環(huán)遍歷,判斷是否有下一個元素
while (iterator.hasNext()) {
// 得到遍歷的每個元素,并向下強(qiáng)轉(zhuǎn)
Object obj = iterator.next();
Map.Entry entry = (Map.Entry) obj;
// 輸出每個元素所以在entry對象
System.out.println(entry.getKey() + "-->" + entry.getValue());
}
}
- Properties處理屬性配置文件
public class PropertiesTest {
// Properties: 常用來處理配置文件.key和value都是String類型
public static void main(String[] args) {
FileInputStream fis = null;
try {
// 造一個對象,代碼中把配置信息讀進(jìn)來
Properties pros = new Properties();
// 創(chuàng)建文件流對象
fis = new FileInputStream("/jdbc.properties");
// 加載流對應(yīng)的文件
pros.load(fis);
// 讀取文件中的數(shù)據(jù)
String name = pros.getProperty("name");
String password = pros.getProperty("password");
System.out.println("name = " + name + " password = " + password);
} catch (IOException e) {
e.printStackTrace();
}finally {
if (fis != null)
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
- Collections工具類常用方法的測試
面試題: Collection 和 Collections的區(qū)別?
Collection是一個存儲單列集合的接口, Collections是一個Collection,Map的工具類
public class CollectionsTest {
@Test
public void test1(){
// reverse(List): 反轉(zhuǎn)List中的元素的順序
List list = new ArrayList();
list.add(132);
list.add(46);
list.add(654);
list.add(-34);
list.add(0);
System.out.println(list);
Collections.reverse(list);// 把原list修改了
System.out.println(list);
// shffle(List): 對List集合的元素隨機(jī)排序
Collections.shuffle(list);
System.out.println(list);
// sort(List): 根據(jù)元素的自然排序,對指定的list集合元素從小到大排序
Collections.sort(list);// 調(diào)用集合元素所在類的compareTo方法
System.out.println(list);
// swap(List int, int): 交換指定list中指定索引位置上的兩個元素
Collections.swap(list,1,2);
// Object max(Collection): 根據(jù)元素的自然排序?qū)χ付╨ist集合按從小到大排序并返回最大值
// Object max(Collection,Comparator): 根據(jù)元素的定制排序?qū)χ付╨ist集合按從大到小排序,并返回最大值
// int frequency(Collection, Object): 返回指定集合中指定元素的出現(xiàn)次數(shù)
int frequency = Collections.frequency(list, 132);
System.out.println(frequency);// 1
}
@Test
public void test2(){
List list = new ArrayList();
list.add(132);
list.add(46);
list.add(654);
list.add(-34);
list.add(0);
// void copy(List dest, List src): 將src中的內(nèi)容復(fù)制到dest中
// 報錯,IndexOutOfBoundsException: Source does not fit in dest
/*List dest = new ArrayList();
Collections.copy(dest, list);
System.out.println(dest);*/
// 正確的: 通過asList把dest集合撐開,造了一個Object數(shù)組,長度是list.size(),里面相當(dāng)于有size個元素,只不過每個位置都是null
List dest = Arrays.asList(new Object[list.size()]);
System.out.println(dest.size());// 等于list.size()
System.out.println(dest);
Collections.copy(dest, list);
System.out.println(dest);
// boolean replaceAll(List list, Object oldVal, Object newVal): 用新值替換
/*
Collections類中提供了多個synchronizedXxx()方法,
該方法可使將指定集合包裝秤線程同步的集合,
從而可以解決多線程并發(fā)訪問集合時的線程安全問題
*/
// 把ArrayList的對象list作為參數(shù)傳入方法中,返回一個線程安全的list1對象
// 即為線程安全的list,就可以在多個線程中操作list了
List list1 = Collections.synchronizedList(list);
}
}
