Github issues:https://github.com/littlejoyo/Blog/issues/
個(gè)人博客：https://littlejoyo.github.io/
微信公眾號(hào)：Joyo說(shuō)
Collectionjava中最基本的集合接口晤郑，它存放在java.util包中，實(shí)現(xiàn)它的接口主要有List先改、Set掠抬、Queue欢摄，他們的實(shí)現(xiàn)細(xì)節(jié)有很大的不同，下面逐個(gè)介紹它們的主要作用和區(qū)別，還有Map不屬于Collection的內(nèi)容扶歪，Map的框架圖如下：
Collection集合框架圖
Collection框架圖
Map接口框架圖
List
- 元素是有序的、可重復(fù)摄闸，可以對(duì)列表中每個(gè)元素的插入位置進(jìn)行精確地控制善镰。
- 是一個(gè)有序容器，保持了每個(gè)元素的插入順序年枕，輸出的順序就是插入的順序炫欺。
- 常用的實(shí)現(xiàn)類有 ArrayList、LinkedList 和 Vector熏兄。
List接口的實(shí)現(xiàn)類
ArrayList
- ArrayList底層使用了Object的數(shù)組作為容器去存儲(chǔ)數(shù)據(jù)
- ArrayList 提供了使用索引的隨意訪問(wèn)數(shù)據(jù)
- ArrayList 是線程非安全的品洛，效率較高，查詢速度高
LinkedList
- LinkedList底層使用了鏈表的數(shù)據(jù)結(jié)構(gòu)
- LinkedList隨機(jī)位置插入摩桶、刪除數(shù)據(jù)時(shí)比線性表快桥状，遍歷比線性表慢。
- 相對(duì)于ArrayList硝清，LinkedList 對(duì)于經(jīng)常需要從 List 中添加或刪除元素的場(chǎng)合更為合適辅斟。
- 和LinkedList一樣，ArrayList也是非同步的（unsynchronized）
Vector
- Vector非常類似ArrayList芦拿，但是Vector是同步的砾肺，效率相對(duì)比較低
- Vector的底層結(jié)構(gòu)也是數(shù)組，但是它們對(duì)數(shù)組的擴(kuò)容方式不同
- 當(dāng)Vector或ArrayList中的元素超過(guò)它的初始大小時(shí),Vector會(huì)將它的容量翻倍,而ArrayList只增加50%的大小防嗡，這樣ArrayList就有利于節(jié)約內(nèi)存空間变汪。
即Vector增長(zhǎng)原來(lái)的一倍，ArrayList增加原來(lái)的0.5倍蚁趁。
Stack棧繼承于Vector裙盾，棧的存儲(chǔ)特點(diǎn)是后進(jìn)先出，
它基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的一個(gè)線程安全的棧，所以棧是線程安全的番官。
Set
- 元素?zé)o序的庐完、不可重復(fù)。
- 無(wú)序容器徘熔，你無(wú)法保證每個(gè)元素的存儲(chǔ)順序门躯，但是其中的TreeSet是特別的，TreeSet通過(guò) Comparator 或者 Comparable 維護(hù)了一個(gè)排序順序酷师。
- 取出元素的方法只有迭代器和增強(qiáng)型for讶凉。
- 只允許一個(gè) null 元素
- Set 接口最流行的幾個(gè)實(shí)現(xiàn)類是 HashSet、LinkedHashSet 以及 TreeSet山孔。
- Set和Map的底層聯(lián)系密切懂讯，可以說(shuō)想要了解Set直接先了解好Map即可
- Set說(shuō)白了就是對(duì)Map的功能的限制
HashSet
- HashSet底層實(shí)現(xiàn)其實(shí)是HashMap(看源碼可以知道)
- HashSet實(shí)現(xiàn)了Set接口，它不允許集合中出現(xiàn)重復(fù)元素台颠。
- 將對(duì)象存儲(chǔ)在HashSet之前褐望，要確保重寫(xiě)hashCode（）方法和equals（）方法，這樣才能比較對(duì)象的值是否相等串前，確保集合中沒(méi)有儲(chǔ)存相同的對(duì)象瘫里。
- HashSet實(shí)現(xiàn)Set接口，由哈希表（實(shí)際上是一個(gè)HashMap實(shí)例）支持荡碾。
- 在HashSet中谨读，元素都存到HashMap鍵值對(duì)的Key上面，而Value時(shí)有一個(gè)統(tǒng)一的值private static final Object PRESENT = new Object();
- 當(dāng)有新值加入時(shí)玩荠，底層的HashMap會(huì)判斷Key值是否存在
-
線程非安全的
HashSet源碼
HashSet源碼介紹
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
// 底層使用HashMap來(lái)保存HashSet中所有元素漆腌。
private transient HashMap<E,Object> map;
// 定義一個(gè)虛擬的Object對(duì)象作為HashMap的value贼邓，將此對(duì)象定義為static final阶冈。
private static final Object PRESENT = new Object();
/**
* 默認(rèn)的無(wú)參構(gòu)造器，構(gòu)造一個(gè)空的HashSet塑径。
*
* 實(shí)際底層會(huì)初始化一個(gè)空的HashMap女坑，并使用默認(rèn)初始容量為16和加載因子0.75。
*/
public HashSet() {
map = new HashMap<E,Object>();
}
/**
* 構(gòu)造一個(gè)包含指定collection中的元素的新set统舀。
*
* 實(shí)際底層使用默認(rèn)的加載因子0.75和足以包含指定
* collection中所有元素的初始容量來(lái)創(chuàng)建一個(gè)HashMap匆骗。
* @param c 其中的元素將存放在此set中的collection。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)空的HashSet誉简。
*
* 實(shí)際底層以相應(yīng)的參數(shù)構(gòu)造一個(gè)空的HashMap碉就。
* @param initialCapacity 初始容量。
* @param loadFactor 加載因子闷串。
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 以指定的initialCapacity構(gòu)造一個(gè)空的HashSet瓮钥。
*
* 實(shí)際底層以相應(yīng)的參數(shù)及加載因子loadFactor為0.75構(gòu)造一個(gè)空的HashMap。
* @param initialCapacity 初始容量。
*/
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
/**
* 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)新的空鏈接哈希集合碉熄。
* 此構(gòu)造函數(shù)為包訪問(wèn)權(quán)限桨武，不對(duì)外公開(kāi)，實(shí)際只是是對(duì)LinkedHashSet的支持锈津。
*
* 實(shí)際底層會(huì)以指定的參數(shù)構(gòu)造一個(gè)空LinkedHashMap實(shí)例來(lái)實(shí)現(xiàn)呀酸。
* @param initialCapacity 初始容量。
* @param loadFactor 加載因子琼梆。
* @param dummy 標(biāo)記性誉。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 返回對(duì)此set中元素進(jìn)行迭代的迭代器。返回元素的順序并不是特定的叮叹。
*
* 底層實(shí)際調(diào)用底層HashMap的keySet來(lái)返回所有的key艾栋。
* 可見(jiàn)HashSet中的元素，只是存放在了底層HashMap的key上蛉顽，
* value使用一個(gè)static final的Object對(duì)象標(biāo)識(shí)蝗砾。
* @return 對(duì)此set中元素進(jìn)行迭代的Iterator。
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
/**
* 返回此set中的元素的數(shù)量（set的容量）携冤。
*
* 底層實(shí)際調(diào)用HashMap的size()方法返回Entry的數(shù)量悼粮，就得到該Set中元素的個(gè)數(shù)。
* @return 此set中的元素的數(shù)量（set的容量）曾棕。
*/
public int size() {
return map.size();
}
/**
* 如果此set不包含任何元素扣猫，則返回true。
*
* 底層實(shí)際調(diào)用HashMap的isEmpty()判斷該HashSet是否為空翘地。
* @return 如果此set不包含任何元素申尤，則返回true。
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* 如果此set包含指定元素衙耕，則返回true昧穿。
* 更確切地講，當(dāng)且僅當(dāng)此set包含一個(gè)滿足(o==null ? e==null : o.equals(e))
* 的e元素時(shí)橙喘，返回true时鸵。
*
* 底層實(shí)際調(diào)用HashMap的containsKey判斷是否包含指定key。
* @param o 在此set中的存在已得到測(cè)試的元素厅瞎。
* @return 如果此set包含指定元素饰潜，則返回true。
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 如果此set中尚未包含指定元素和簸，則添加指定元素彭雾。
* 更確切地講，如果此 set 沒(méi)有包含滿足(e==null ? e2==null : e.equals(e2))
* 的元素e2锁保，則向此set 添加指定的元素e薯酝。
* 如果此set已包含該元素南誊，則該調(diào)用不更改set并返回false。
*
* 底層實(shí)際將將該元素作為key放入HashMap蜜托。
* 由于HashMap的put()方法添加key-value對(duì)時(shí)抄囚，當(dāng)新放入HashMap的Entry中key
* 與集合中原有Entry的key相同（hashCode()返回值相等，通過(guò)equals比較也返回true）橄务，
* 新添加的Entry的value會(huì)將覆蓋原來(lái)Entry的value幔托，但key不會(huì)有任何改變，
* 因此如果向HashSet中添加一個(gè)已經(jīng)存在的元素時(shí)蜂挪，新添加的集合元素將不會(huì)被放入HashMap中重挑，
* 原來(lái)的元素也不會(huì)有任何改變，這也就滿足了Set中元素不重復(fù)的特性棠涮。
* @param e 將添加到此set中的元素谬哀。
* @return 如果此set尚未包含指定元素，則返回true严肪。
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* 如果指定元素存在于此set中史煎，則將其移除。
* 更確切地講驳糯，如果此set包含一個(gè)滿足(o==null ? e==null : o.equals(e))的元素e篇梭，
* 則將其移除。如果此set已包含該元素酝枢，則返回true
* （或者：如果此set因調(diào)用而發(fā)生更改恬偷，則返回true）。（一旦調(diào)用返回帘睦，則此set不再包含該元素）袍患。
*
* 底層實(shí)際調(diào)用HashMap的remove方法刪除指定Entry。
* @param o 如果存在于此set中則需要將其移除的對(duì)象竣付。
* @return 如果set包含指定元素诡延，則返回true。
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* 從此set中移除所有元素卑笨。此調(diào)用返回后孕暇，該set將為空仑撞。
*
* 底層實(shí)際調(diào)用HashMap的clear方法清空Entry中所有元素赤兴。
*/
public void clear() {
map.clear();
}
/**
* 返回此HashSet實(shí)例的淺表副本：并沒(méi)有復(fù)制這些元素本身。
*
* 底層實(shí)際調(diào)用HashMap的clone()方法隧哮，獲取HashMap的淺表副本桶良，并設(shè)置到HashSet中。
*/
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
}
LinkedHashSet
- LinkedHashSet集合同樣是根據(jù)元素的hashCode值來(lái)決定元素的存儲(chǔ)位置
- 它同時(shí)使用鏈表維護(hù)元素的次序沮翔。
- LinkedHashSet在迭代訪問(wèn)Set中的全部元素時(shí)陨帆，性能比HashSet好，但是插入時(shí)性能稍微遜色于HashSet。
- LinkedHashSet取出元素的順序和存入的順序一致
- LinkedHashSet的底層實(shí)現(xiàn)是繼承了HashSet
TreeSet
- TreeSet類型唯一可實(shí)現(xiàn)自動(dòng)排序的類型疲牵，即是取出的元素是經(jīng)過(guò)排序后輸出
- TreeSet是SortedSet接口的唯一實(shí)現(xiàn)類承二，TreeSet可以確保集合元素處于排序狀態(tài)。
- TreeSet判斷兩個(gè)對(duì)象不相等的方式是兩個(gè)對(duì)象通過(guò)equals方法返回false纲爸，或者通過(guò)CompareTo方法比較沒(méi)有返回0
- TreeSet的底層實(shí)現(xiàn)是TreeMap的變形
HashSet亥鸠、LinkedHashSet、TreeSet取出元素的區(qū)別
Set中不能存放重復(fù)的代碼识啦，但是對(duì)于存取的方式它們也是存在著不同负蚊，這里做一個(gè)對(duì)比，關(guān)于取出元素的不同：
HashSet取出元素不能保證順序
HashSet<String> set = new HashSet<String>();
set.add("555");
set.add("222");
set.add("111");
set.add("333");
for (String s:set
) {
System.out.println(s);
}
輸出結(jié)果：
222
111
333
555
LinedHashSet取出元素和存入順序一致
LinkedHashSet<String> set = new LinkedHashSet<String>();
set.add("555");
set.add("222");
set.add("111");
set.add("333");
for (String s:set
) {
System.out.println(s);
}
輸出結(jié)果：
555
222
111
333
TreeSet取出元素是經(jīng)過(guò)自然排序的
TreeSet<String> set = new TreeSet<String>();
set.add("555");
set.add("222");
set.add("111");
set.add("333");
for (String s:set
) {
System.out.println(s);
}
輸出結(jié)果：
111
222
333
555
Set存放對(duì)象颓哮，重寫(xiě)hashcode和equal判斷不同對(duì)象的實(shí)例
如果不對(duì)hashcode和equal進(jìn)行重寫(xiě)家妆，這兩個(gè)方法會(huì)照循Object基類的方法來(lái)進(jìn)行對(duì)象的判斷，但是這樣無(wú)法滿足我們自定義類是否相同的判斷冕茅。
不重寫(xiě)hashcode和equals
class Student {
private String sid;//學(xué)生學(xué)號(hào)
private String name;//學(xué)生姓名
private String age;//學(xué)生年齡
}
public class Main {
public static void main(String[] args) {
Student s1 = new Student("111","小明","18");
Student s2 = new Student("111","小明","18");
System.out.println(s1.equals(s2));
Set<Student> set = new HashSet<Student>();
set.add(s1);
set.add(s2);
for (Student s:set
) {
System.out.println(s.getName());
}
}
輸出結(jié)果：
false
小明
小明
事實(shí)上伤极，這兩個(gè)學(xué)生是同一個(gè)的，但是由于不重寫(xiě)所以按照Object的方法進(jìn)行判斷姨伤，s1和s2是兩個(gè)不同的對(duì)象
因此為了實(shí)現(xiàn)對(duì)自定義類進(jìn)行判斷就需要進(jìn)行對(duì)hashcode和equals的判斷
class Student {
private String sid;//學(xué)生學(xué)號(hào)
private String name;//學(xué)生姓名
private String age;//學(xué)生年齡
@Override
public int hashCode() {
Student stu = (Student) this;
return sid.hashCode();
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Student)
{
Student stu = (Student) obj;
return (sid.equals(stu.sid));
}
return super.equals(obj);
}
}
public class Main {
public static void main(String[] args) {
Student s1 = new Student("111","小明","18");
Student s2 = new Student("111","小明","18");
System.out.println(s1.equals(s2));
Set<Student> set = new HashSet<Student>();
set.add(s1);
set.add(s2);
for (Student s:set
) {
System.out.println(s.getName());
}
}
輸出結(jié)果：
true
小明
Map
- 用于存儲(chǔ)健值對(duì)塑荒、根據(jù)鍵得到值、
- 不允許鍵重復(fù)(重復(fù)了覆蓋了),但允許值重復(fù)
- 實(shí)現(xiàn)類主要是HashMap姜挺、 HashTable 齿税、LinkedHashMap 和 TreeMap
HashTable和HashMap的對(duì)比
- HashTable產(chǎn)生于JDK 1.1，而HashMap產(chǎn)生于JDK 1.2
- HashTable的底層存儲(chǔ)是使用了數(shù)組+鏈表炊豪，1.7及之前HashMap使用數(shù)組+鏈表凌箕，1.8使用了數(shù)組+紅黑樹(shù)
- Hashtable是線程安全的，HashMap是線程不安全的词渤，所以HashMap比Hashtable的性能高一點(diǎn)
- Hashtable不允許使用null作為key和value牵舱；但HashMap可以使用null作為key或value。
- 關(guān)于HashMap中缺虐，在jdk1.8之前是插入頭部的芜壁，在jdk1.8中是插入尾部的。
LinkedHashMap
- LinkedHashMap保存了記錄的插入順序高氮、在用Iterator遍歷LinkedHashMap時(shí)慧妄、先得到的記錄肯定是先插入的.也可以在構(gòu)造時(shí)用帶參數(shù)、按照應(yīng)用次數(shù)排序剪芍、在遍歷的時(shí)候會(huì)比HashMap慢
- LinkedHashMap的遍歷速度只和實(shí)際數(shù)據(jù)有關(guān)塞淹、和容量無(wú)關(guān)、而HashMap的遍歷速度和他的容量有關(guān)
TreeMap
- TreeMap實(shí)現(xiàn)SortMap接口罪裹、能夠把它保存的記錄根據(jù)鍵排序,默認(rèn)是按鍵值的升序排序
- 當(dāng)用Iterator 遍歷TreeMap時(shí)饱普、得到的記錄是排過(guò)序的
- TreeMap取出來(lái)的是排序后的鍵值對(duì)运挫、但如果您要按自然順序或自定義順序遍歷鍵、那么TreeMap會(huì)更好
- LinkedHashMap 是HashMap的一個(gè)子類套耕、如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實(shí)現(xiàn),它還可以按讀取順序來(lái)排列
- TreeMap的底層實(shí)現(xiàn)是紅黑樹(shù)
HashMap谁帕、LinkedHashMap、TreeMap取出元素的情況和Set的實(shí)現(xiàn)類是一樣的冯袍，這里就不再舉例雇卷。
微信公眾號(hào)
掃一掃關(guān)注Joyo說(shuō)公眾號(hào)，共同學(xué)習(xí)和研究開(kāi)發(fā)技術(shù)颠猴。
關(guān)注我
