Java容器類研究7：Set

RdouTyping 發(fā)布于2019-08-15 12:19 / 347人閱讀

摘要：繼承自，繼承接口，接口繼承自。的也是使用的的的。中和方法理論上是常數(shù)時(shí)間的復(fù)雜度，前提是元素在中分散比較均勻。并且這些元素在結(jié)構(gòu)中，根據(jù)進(jìn)行了排序，所以用遍歷時(shí)可以按照遞增遞減順序。遍歷訪問(wèn)元素的操作比更為高效，時(shí)間由元素?cái)?shù)量決定。

java.util.Set

HashSet繼承自AbstractSet，繼承接口Set，Set接口繼承自Collection。

null是否可以放在Set中

null可以放在Set中，并且最多只能有一個(gè)。null的hashcode是0。

HashSet用什么結(jié)構(gòu)實(shí)現(xiàn)的

HashSet用了一個(gè)HashMap。。。該HashMap默認(rèn)的負(fù)載因子是0.75。

需要存入的對(duì)象作為HashMap的key存入，而value使用了一個(gè)公共靜態(tài)的ObjectPRESENT來(lái)填充。

HashSet的iterator也是使用的HashMap的key set的iterator。

HashSet中add、remove和contains方法理論上是常數(shù)時(shí)間的復(fù)雜度，前提是元素在bucket中分散比較均勻。迭代訪問(wèn)其中元素的時(shí)間，則是元素?cái)?shù)量+bucket容量，所以在迭代訪問(wèn)操作比較重要時(shí)，不要將set的容量初始為很大。

HashSet不是線程安全的

將其變?yōu)橐粋€(gè)線程安全set的官方方法是：

Set s = Collections.synchronizedSet(new HashSet(...)

TreeSet是用什么結(jié)構(gòu)實(shí)現(xiàn)的

不出所料，是用TreeMap實(shí)現(xiàn)的。并且這些元素在結(jié)構(gòu)中，根據(jù)comparator進(jìn)行了排序，所以用iterator遍歷時(shí)可以按照遞增、遞減順序。

comparator在TreeSet中是比較關(guān)鍵的，這些元素要么是comparable，要么自己提供一個(gè)定制的comparator。并且comparator的實(shí)現(xiàn)一定要和equals方法一致。

對(duì)于add、remove和contains方法，理論上是log(n)時(shí)間復(fù)雜度。

LinkedHashSet與HashSet的區(qū)別

LinkedHashSet繼承自HashSet，但是記錄了元素的插入順序，仍然具有原來(lái)HashSet常數(shù)時(shí)間復(fù)雜度操作的優(yōu)勢(shì)，但是這些操作會(huì)比原來(lái)慢一些，用來(lái)維護(hù)這個(gè)順序。遍歷訪問(wèn)元素的操作比HashSet更為高效，時(shí)間由元素?cái)?shù)量決定。

一樣，LinkedHashSet用LinkedHashMap來(lái)實(shí)現(xiàn)。