list的轉map的另一種猜想
Java8使用lambda運算式進行函式式編程可以對集合進行非常方便的操作,一個比較常見的操作是將list轉換成map,一般使用Collectors的toMap()方法進行轉換,一個比較常見的問題是當list中含有相同元素的時候,如果不指定取哪一個,則會拋出例外,因此,這個指定是必須的,Java面試寶典PDF完整版
當然,使用toMap()的另一個多載方法,可以直接指定,這里,我們想討論的是另一種方法:在進行轉map的操作之前,能不能使用distinct()先把list的重復元素過濾掉,然后轉map的時候就不用考慮重復元素的問題了,
使用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里總共有三個元素,其中有兩個我們認為是重復的,第一種轉換是使用toMap()直接指定了對重復key的處理情況,因此可以正常轉換成map,而第二種轉換是想先對list進行去重,然后再轉換成map,結果還是失敗了,拋出了IllegalStateException,所以distinct()應該是失敗了,
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()對物件進行去重時,是根據物件的equals()方法去處理的,如果我們的VideoInfo類不overrride超類Object的equals()方法,就會使用Object的,
但是Object的equals()方法只有在兩個物件完全相同時才回傳true,而我們想要的效果是只要VideoInfo的id/width/height均相同,就認為兩個videoInfo物件是同一個,所以我們比如重寫屬于videoInfo的equals()方法,
重寫equals()的注意事項
我們設計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物件的三個屬性都相同,這兩個物件就相同了,歡天喜地去運行程式,依舊失敗!why?
《Effective Java》是本好書,連Java之父James Gosling都說,這是一本連他都需要的Java教程,在這本書中,作者指出,如果重寫了一個類的equals()方法,那么就必須一起重寫它的hashCode()方法!必須!沒有商量的余地!
必須使得重寫后的equals()滿足如下條件:
-
根據equals()進行比較,相等的兩個物件,hashCode()的值也必須相同;
-
根據equals()進行比較,不相等的兩個物件,hashCode()的值可以相同,也可以不同;
因為這是Java的規定,違背這些規定將導致Java程式運行不再正常,
具體更多的細節,建議大家讀讀原書,必定獲益匪淺,強烈推薦!
最終,我按照神書的指導設計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中的重復元素,此時使用兩種toMap()將list轉換成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()是呼叫equals()進行比較的,那按照我的理解,list的3個元素至少需要比較3次吧,那是不是就呼叫了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;
}
結果:
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)>
結果發現才呼叫了一次equals(),為什么不是3次呢?仔細想想,根據hashCode()進行比較,hashCode()相同的情況就一次,就是list的第一個元素和第三個元素(都是VideoInfo(id=123, width=1, height=2))會出現hashCode()相同的情況,
所以我們是不是可以這么猜想:只有當hashCode()回傳的hashCode相同的時候,才會呼叫equals()進行更進一步的判斷,如果連hashCode()回傳的hashCode都不同,那么可以認為這兩個物件一定就是不同的了!
驗證猜想:
更改hashCode()如下:
@Override
public int hashCode() {
return 1;
}
這樣一來,所有的物件的hashCode()回傳值都是相同的,當然,這樣搞是符合Java規范的,因為Java只規定equals()相同的物件的hashCode必須相同,但是不同的物件的hashCode未必會不同,
結果:
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()呼叫了三次!看來的確只有hashCode相同的時候才會呼叫equal()進一步判斷兩個物件究竟是否相同;如果hashCode不相同,兩個物件顯然不相同,猜想是正確的,
結論
-
list轉map推薦使用toMap(),并且無論是否會出現重復的問題,都要指定重復后的取舍規則,不費功夫但受益無窮;
-
對一個自定義的class使用distinct(),切記覆寫equals()方法;
-
覆寫equals(),一定要覆寫hashCode();
-
雖然設計出一個hashCode()可以簡單地讓其return 1,這樣并不會違反Java規定,但是這樣做會導致很多惡果,比如將這樣的物件存入hashMap的時候,所有的物件的hashCode都相同,最終所有物件都存盤在hashMap的同一個桶中,直接將hashMap惡化成了一個鏈表,從而O(1)的復雜度被整成了O(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 + ">"));
}
}
再拓展
假設類是別人的,不能修改
以上,VideoInfo使我們自己寫的類,我們可以往里添加equals()和hashCode()方法,如果VideoInfo是我們參考的依賴中的一個類,我們無權對其進行修改,那么是不是就沒辦法使用distinct()按照某些元素是否相同,對物件進行自定義的過濾了呢?
使用wrapper
在stackoverflow的一個回答上,我們可以找到一個可行的方法:使用wrapper,
假設在一個依賴中(我們無權修改該類),VideoInfo定義如下:
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class VideoInfo {
@Getter
String id;
int width;
int height;
}
使用剛剛的wrapper思路,寫程式如下(當然,為了程式的可運行性,還是把VideoInfo放進來了,假設它就是不能修改的,不能為其添加任何方法):
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的思路無非就是構造另一個類VideoInfoWrapper,把hashCode()和equals()添加到wrapper中,這樣便可以按照自定義規則對wrapper物件進行自定義的過濾,
搜索Java知音公眾號,回復“后端面試”,送你一份Java面試題寶典.pdf
我們沒法自定義過濾VideoInfo,但是我們可以自定義過濾VideoInfoWrapper啊!
之后要做的,就是將VideoInfo全部轉化為VideoInfoWrapper,然后過濾掉某些VideoInfoWrapper,再將剩下的VideoInfoWrapper轉回VideoInfo,以此達到過濾VideoInfo的目的,很巧妙!
使用“filter() + 自定義函式”取代distinct()
另一種更精妙的實作方式是自定義一個函式:
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是映射函式,回傳Object,整個傳入的函式的功能應該是提取key的,distinctByKey函式回傳的是Predicate函式,型別為T,)
這個函式傳入一個函式(lambda),對傳入的物件提取key,然后嘗試將key放入concurrentHashMap,如果能放進去,說明此key之前沒出現過,函式回傳false;如果不能放進去,說明這個key和之前的某個key重復了,函式回傳true,
這個函式最終作為filter()函式的入參,根據Java API可知filter(func)過濾的規則為:如果func為true,則過濾,否則不過濾,因此,通過“filter() + 自定義的函式”,凡是重復的key都回傳true,并被filter()過濾掉,最終留下的都是不重復的,Java面試寶典PDF完整版
最終實作的程式如下
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;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/252920.html
標籤:其他
上一篇:LinkedList詳解
