list的轉(zhuǎn)map的另一種猜想
Java8使用lambda表達(dá)式進(jìn)行函數(shù)式編程可以對集合進(jìn)行非常方便的操作医舆。一個比較常見的操作是將list轉(zhuǎn)換成map激蹲，一般使用Collectors的toMap()方法進(jìn)行轉(zhuǎn)換底靠。一個比較常見的問題是當(dāng)list中含有相同元素的時候壤短，如果不指定取哪一個螃宙，則會拋出異常。因此置济，這個指定是必須的解恰。Java面試寶典PDF完整版
當(dāng)然，使用toMap()的另一個重載方法浙于，可以直接指定护盈。這里，我們想討論的是另一種方法：在進(jìn)行轉(zhuǎn)map的操作之前羞酗，能不能使用distinct()先把list的重復(fù)元素過濾掉腐宋，然后轉(zhuǎn)map的時候就不用考慮重復(fù)元素的問題了。
使用distinct()給list去重
直接使用distinct()，失敗
package example.mystream;
import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class ListToMap {
@AllArgsConstructor
@NoArgsConstructor
@ToString
private static class VideoInfo {
@Getter
String id;
int width;
int height;
}
public static void main(String [] args) {
List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));
// preferred: handle duplicated data when toMap()
Map<String, VideoInfo> id2VideoInfo = list.stream().collect(
Collectors.toMap(VideoInfo::getId, x -> x,
(oldValue, newValue) -> newValue)
);
System.out.println("No Duplicated1: ");
id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
// handle duplicated data using distinct(), before toMap()
Map<String, VideoInfo> id2VideoInfo2 = list.stream().distinct().collect(
Collectors.toMap(VideoInfo::getId, x -> x)
);
System.out.println("No Duplicated2: ");
id2VideoInfo2.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
}
}
list里總共有三個元素胸竞，其中有兩個我們認(rèn)為是重復(fù)的欺嗤。第一種轉(zhuǎn)換是使用toMap()直接指定了對重復(fù)key的處理情況，因此可以正常轉(zhuǎn)換成map撤师。而第二種轉(zhuǎn)換是想先對list進(jìn)行去重剂府，然后再轉(zhuǎn)換成map，結(jié)果還是失敗了剃盾，拋出了IllegalStateException，所以distinct()應(yīng)該是失敗了淤袜。
No Duplicated1:
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
Exception in thread "main" java.lang.IllegalStateException: Duplicate key ListToMap.VideoInfo(id=123, width=1, height=2)
at java.util.stream.Collectors.lambda$throwingMerger$0(Collectors.java:133)
at java.util.HashMap.merge(HashMap.java:1253)
at java.util.stream.Collectors.lambda$toMap$58(Collectors.java:1320)
at java.util.stream.ReduceOps$3ReducingSink.accept(ReduceOps.java:169)
at java.util.stream.DistinctOps$1$2.accept(DistinctOps.java:175)
at java.util.Spliterators$ArraySpliterator.forEachRemaining(Spliterators.java:948)
at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481)
at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471)
at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708)
at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499)
at example.mystream.ListToMap.main(ListToMap.java:79)
原因：distinct()依賴于equals()
查看distinct()的API痒谴，可以看到如下介紹：
Returns a stream consisting of the distinct elements (according to {@link Object#equals(Object)}) of this stream.
顯然，distinct()對對象進(jìn)行去重時铡羡，是根據(jù)對象的equals()方法去處理的积蔚。如果我們的VideoInfo類不overrride超類Object的equals()方法，就會使用Object的烦周。
但是Object的equals()方法只有在兩個對象完全相同時才返回true尽爆。而我們想要的效果是只要VideoInfo的id/width/height均相同，就認(rèn)為兩個videoInfo對象是同一個读慎。所以我們比如重寫屬于videoInfo的equals()方法漱贱。
重寫equals()的注意事項
我們設(shè)計VideoInfo的equals()如下：
@Override
public boolean equals(Object obj) {
if (!(obj instanceof VideoInfo)) {
return false;
}
VideoInfo vi = (VideoInfo) obj;
return this.id.equals(vi.id)
&& this.width == vi.width
&& this.height == vi.height;
}
這樣一來，只要兩個videoInfo對象的三個屬性都相同夭委，這兩個對象就相同了幅狮。歡天喜地去運(yùn)行程序，依舊失斨昃摹崇摄！why？
《Effective Java》是本好書慌烧，連Java之父James Gosling都說逐抑，這是一本連他都需要的Java教程。在這本書中屹蚊，作者指出厕氨，如果重寫了一個類的equals()方法，那么就必須一起重寫它的hashCode()方法淑翼！必須腐巢！沒有商量的余地！
必須使得重寫后的equals()滿足如下條件：
根據(jù)equals()進(jìn)行比較玄括，相等的兩個對象冯丙，hashCode()的值也必須相同；
根據(jù)equals()進(jìn)行比較，不相等的兩個對象胃惜，hashCode()的值可以相同泞莉，也可以不同；
因為這是Java的規(guī)定船殉，違背這些規(guī)定將導(dǎo)致Java程序運(yùn)行不再正常鲫趁。
具體更多的細(xì)節(jié)，建議大家讀讀原書利虫，必定獲益匪淺挨厚。強(qiáng)烈推薦！
最終糠惫，我按照神書的指導(dǎo)設(shè)計VideoInfo的hashCode()方法如下：
@Override
public int hashCode() {
int n = 31;
n = n * 31 + this.id.hashCode();
n = n * 31 + this.height;
n = n * 31 + this.width;
return n;
}
終于疫剃，distinct()成功過濾了list中的重復(fù)元素，此時使用兩種toMap()將list轉(zhuǎn)換成map都是沒問題的：
No Duplicated1:
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
No Duplicated2:
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
引申
既然說distinct()是調(diào)用equals()進(jìn)行比較的硼讽，那按照我的理解巢价，list的3個元素至少需要比較3次吧。那是不是就調(diào)用了3次equals()呢固阁？
在equals()中加入一句打印壤躲，這樣就可以知道了。加后的equals()如下：
@Override
public boolean equals(Object obj) {
if (! (obj instanceof VideoInfo)) {
return false;
}
VideoInfo vi = (VideoInfo) obj;
System.out.println("<===> Invoke equals() ==> " + this.toString() + " vs. " + vi.toString());
return this.id.equals(vi.id) && this.width == vi.width && this.height == vi.height;
}
結(jié)果：
No Duplicated1:
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
<===> Invoke equals() ==> ListToMap.VideoInfo(id=123, width=1, height=2) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
No Duplicated2:
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
結(jié)果發(fā)現(xiàn)才調(diào)用了一次equals()备燃。為什么不是3次呢碉克？仔細(xì)想想，根據(jù)hashCode()進(jìn)行比較赚爵，hashCode()相同的情況就一次棉胀，就是list的第一個元素和第三個元素（都是VideoInfo(id=123, width=1, height=2)）會出現(xiàn)hashCode()相同的情況冀膝。
所以我們是不是可以這么猜想：只有當(dāng)hashCode()返回的hashCode相同的時候唁奢，才會調(diào)用equals()進(jìn)行更進(jìn)一步的判斷窝剖。如果連hashCode()返回的hashCode都不同，那么可以認(rèn)為這兩個對象一定就是不同的了赐纱！
驗證猜想：
更改hashCode()如下：
@Override
public int hashCode() {
return 1;
}
這樣一來脊奋，所有的對象的hashCode()返回值都是相同的疙描。當(dāng)然，這樣搞是符合Java規(guī)范的起胰，因為Java只規(guī)定equals()相同的對象的hashCode必須相同久又，但是不同的對象的hashCode未必會不同。
結(jié)果：
No Duplicated1:
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
<===> Invoke equals() ==> ListToMap.VideoInfo(id=456, width=4, height=5) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
<===> Invoke equals() ==> ListToMap.VideoInfo(id=456, width=4, height=5) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
<===> Invoke equals() ==> ListToMap.VideoInfo(id=123, width=1, height=2) vs. ListToMap.VideoInfo(id=123, width=1, height=2)
No Duplicated2:
<123, ListToMap.VideoInfo(id=123, width=1, height=2)>
<456, ListToMap.VideoInfo(id=456, width=4, height=5)>
果然，equals()調(diào)用了三次炉峰！看來的確只有hashCode相同的時候才會調(diào)用equal()進(jìn)一步判斷兩個對象究竟是否相同脉执；如果hashCode不相同，兩個對象顯然不相同半夷。猜想是正確的。
結(jié)論
list轉(zhuǎn)map推薦使用toMap()否彩，并且無論是否會出現(xiàn)重復(fù)的問題嗦随，都要指定重復(fù)后的取舍規(guī)則敬尺，不費(fèi)功夫但受益無窮；
對一個自定義的class使用distinct()砂吞，切記覆寫equals()方法蜻直；
覆寫equals()，一定要覆寫hashCode()概而；
雖然設(shè)計出一個hashCode()可以簡單地讓其return 1，這樣并不會違反Java規(guī)定王悍，但是這樣做會導(dǎo)致很多惡果餐曼。比如將這樣的對象存入hashMap的時候，所有的對象的hashCode都相同集惋，最終所有對象都存儲在hashMap的同一個桶中踩娘，直接將hashMap惡化成了一個鏈表。從而O(1)的復(fù)雜度被整成了O(n)的，性能自然大大下降臂拓。
好書是程序猿進(jìn)步的階梯习寸。——高爾基孵滞。比如《Effecctive Java》鸯匹。
最終參考程序：
package example.mystream;
import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class ListToMap {
@AllArgsConstructor
@NoArgsConstructor
@ToString
private static class VideoInfo {
@Getter
String id;
int width;
int height;
public static void main(String [] args) {
System.out.println(new VideoInfo("123", 1, 2).equals(new VideoInfo("123", 1, 2)));
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof VideoInfo)) {
return false;
}
VideoInfo vi = (VideoInfo) obj;
return this.id.equals(vi.id)
&& this.width == vi.width
&& this.height == vi.height;
}
/**
* If equals() is override, hashCode() must be override, too.
* 1\. if a equals b, they must have the same hashCode;
* 2\. if a doesn't equals b, they may have the same hashCode;
* 3\. hashCode written in this way can be affected by sequence of the fields;
* 3\. 2^5 - 1 = 31\. So 31 will be faster when do the multiplication,
* because it can be replaced by bit-shifting: 31 * i = (i << 5) - i.
* @return
*/
@Override
public int hashCode() {
int n = 31;
n = n * 31 + this.id.hashCode();
n = n * 31 + this.height;
n = n * 31 + this.width;
return n;
}
}
public static void main(String [] args) {
List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));
// preferred: handle duplicated data when toMap()
Map<String, VideoInfo> id2VideoInfo = list.stream().collect(
Collectors.toMap(VideoInfo::getId, x -> x,
(oldValue, newValue) -> newValue)
);
System.out.println("No Duplicated1: ");
id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
// handle duplicated data using distinct(), before toMap()
// Note that distinct() relies on equals() in the object
// if you override equals(), hashCode() must be override together
Map<String, VideoInfo> id2VideoInfo2 = list.stream().distinct().collect(
Collectors.toMap(VideoInfo::getId, x -> x)
);
System.out.println("No Duplicated2: ");
id2VideoInfo2.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
}
}
再拓展
假設(shè)類是別人的殴蓬，不能修改
以上，VideoInfo使我們自己寫的類痘绎，我們可以往里添加equals()和hashCode()方法肖粮。如果VideoInfo是我們引用的依賴中的一個類，我們無權(quán)對其進(jìn)行修改涩馆，那么是不是就沒辦法使用distinct()按照某些元素是否相同魂那，對對象進(jìn)行自定義的過濾了呢？
使用wrapper
在stackoverflow的一個回答上冰寻，我們可以找到一個可行的方法：使用wrapper。
假設(shè)在一個依賴中（我們無權(quán)修改該類）轻腺，VideoInfo定義如下：
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class VideoInfo {
@Getter
String id;
int width;
int height;
}
使用剛剛的wrapper思路划乖，寫程序如下（當(dāng)然，為了程序的可運(yùn)行性误算，還是把VideoInfo放進(jìn)來了，假設(shè)它就是不能修改的儿礼，不能為其添加任何方法）：
package example.mystream;
import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class DistinctByWrapper {
private static class VideoInfoWrapper {
private final VideoInfo videoInfo;
public VideoInfoWrapper(VideoInfo videoInfo) {
this.videoInfo = videoInfo;
}
public VideoInfo unwrap() {
return videoInfo;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof VideoInfo)) {
return false;
}
VideoInfo vi = (VideoInfo) obj;
return videoInfo.id.equals(vi.id)
&& videoInfo.width == vi.width
&& videoInfo.height == vi.height;
}
@Override
public int hashCode() {
int n = 31;
n = n * 31 + videoInfo.id.hashCode();
n = n * 31 + videoInfo.height;
n = n * 31 + videoInfo.width;
return n;
}
}
public static void main(String [] args) {
List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));
// VideoInfo --map()--> VideoInfoWrapper ----> distinct(): VideoInfoWrapper --map()--> VideoInfo
Map<String, VideoInfo> id2VideoInfo = list.stream()
.map(VideoInfoWrapper::new).distinct().map(VideoInfoWrapper::unwrap)
.collect(
Collectors.toMap(VideoInfo::getId, x -> x,
(oldValue, newValue) -> newValue)
);
id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
}
}
/**
* Assume that VideoInfo is a class that we can't modify
*/
@AllArgsConstructor
@NoArgsConstructor
@ToString
class VideoInfo {
@Getter
String id;
int width;
int height;
}
整個wrapper的思路無非就是構(gòu)造另一個類VideoInfoWrapper蚊夫，把hashCode()和equals()添加到wrapper中，這樣便可以按照自定義規(guī)則對wrapper對象進(jìn)行自定義的過濾壤圃。
搜索Java知音公眾號琅轧，回復(fù)“后端面試”，送你一份Java面試題寶典.pdf
我們沒法自定義過濾VideoInfo乍桂，但是我們可以自定義過濾VideoInfoWrapper岸米谩！
之后要做的忍疾，就是將VideoInfo全部轉(zhuǎn)化為VideoInfoWrapper谨朝，然后過濾掉某些VideoInfoWrapper，再將剩下的VideoInfoWrapper轉(zhuǎn)回VideoInfo则披，以此達(dá)到過濾VideoInfo的目的洗出。很巧妙！
使用“filter() + 自定義函數(shù)”取代distinct()
另一種更精妙的實現(xiàn)方式是自定義一個函數(shù)：
private static <T> Predicate<T> distinctByKey(Function<? super T, Object> keyExtractor) {
Map<Object, Boolean> map = new ConcurrentHashMap<>();
return t -> map.putIfAbsent(keyExtractor.apply(t), Boolean.TRUE) == null;
}
（輸入元素的類型是T及其父類阱洪，keyExtracctor是映射函數(shù)菠镇，返回Object，整個傳入的函數(shù)的功能應(yīng)該是提取key的利耍。distinctByKey函數(shù)返回的是Predicate函數(shù)盔粹，類型為T舷嗡。）
這個函數(shù)傳入一個函數(shù)（lambda）嵌莉，對傳入的對象提取key，然后嘗試將key放入concurrentHashMap烦秩，如果能放進(jìn)去，說明此key之前沒出現(xiàn)過兜蠕，函數(shù)返回false抛寝；如果不能放進(jìn)去，說明這個key和之前的某個key重復(fù)了盗舰，函數(shù)返回true钻趋。
這個函數(shù)最終作為filter()函數(shù)的入?yún)ⅰ８鶕?jù)Java API可知filter(func)過濾的規(guī)則為：如果func為true蛮位，則過濾，否則不過濾尸曼。因此萄焦，通過“filter() + 自定義的函數(shù)”，凡是重復(fù)的key都返回true茬射，并被filter()過濾掉烘苹，最終留下的都是不重復(fù)的。Java面試寶典PDF完整版
最終實現(xiàn)的程序如下
package example.mystream;
import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.ToString;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Collectors;
public class DistinctByFilterAndLambda {
public static void main(String[] args) {
List<VideoInfo> list = Arrays.asList(new VideoInfo("123", 1, 2),
new VideoInfo("456", 4, 5), new VideoInfo("123", 1, 2));
// Get distinct only
Map<String, VideoInfo> id2VideoInfo = list.stream().filter(distinctByKey(vi -> vi.getId())).collect(
Collectors.toMap(VideoInfo::getId, x -> x,
(oldValue, newValue) -> newValue)
);
id2VideoInfo.forEach((x, y) -> System.out.println("<" + x + ", " + y + ">"));
}
/**
* If a key could not be put into ConcurrentHashMap, that means the key is duplicated
* @param keyExtractor a mapping function to produce keys
* @param <T> the type of the input elements
* @return true if key is duplicated; else return false
*/
private static <T> Predicate<T> distinctByKey(Function<? super T, Object> keyExtractor) {
Map<Object, Boolean> map = new ConcurrentHashMap<>();
return t -> map.putIfAbsent(keyExtractor.apply(t), Boolean.TRUE) == null;
}
}
/**
* Assume that VideoInfo is a class that we can't modify
*/
@AllArgsConstructor
@NoArgsConstructor
@ToString
class VideoInfo {
@Getter
String id;
int width;
int height;
}
