Removing a map entry causes object reference within Map entry optional to change

When i retrieve a map entry from a map, store it in an optional and then remove that same entry from the map using remove(entry.getKey()) then the Optional suddenly starts pointing to the next map entry available inside the map.

Let me explain further:

I have a bunch of comment objects that i would like to sort. The comment list should always start with the comment that is accepted as the answer, it should be the first element in the list. The sort method starts with a map and uses a stream on entrySet to retrieve the first comment which has the acceptedAnswer boolean set to true.

Map<Long, CommentDTO> sortedAndLinkedCommentDTOMap = sortCommentsAndLinkCommentRepliesWithOwningComments(commentDTOSet);
Optional<Map.Entry<Long, CommentDTO>> acceptedAnswerCommentOptional = sortedAndLinkedCommentDTOMap.entrySet().stream()
        .filter(entry -> entry.getValue().isAcceptedAsAnswer()).findFirst();

Lets assume that the Map contains 3 comments with ids 3, 6, and 11. The key is always the id of the comment and the comment is always the value. The comment marked as the answer has id 6. In this case the code below is executed:

if(acceptedAnswerCommentOptional.isPresent()){
    Map.Entry<Long, CommentDTO> commentDTOEntry = acceptedAnswerCommentOptional.get();
    sortedAndLinkedCommentDTOMap.remove(commentDTOEntry.getKey());
}

When commentDTOEntry gets initialized with the value of acceptedAnswerCommentOptional it has a reference to the accepted answer with id 6. Now, when i remove that entry from sortedAndLinkedCommentDTOMap the reference to the accepted answer comment is not only removed from sortedAndLinkedCommentDTOMap but also from acceptedAnswerCommentOptional! But instead of becoming null acceptedAnswerCommentOptional now starts pointing to the next entry of sortedAndLinkedCommentDTOMap namely the one with key 11.

I don't understand what is causing this strange behavior. Why doesn't the value of acceptedAnswerCommentOptional simply become null? And why isn't acceptedAnswerCommentOptional able to maintain the reference to the accepted answer comment when i remove it from the map?

You can see this behavior yourself when running the code in intellij IDEA using debug mode, as soon as the remove method is called the explanatory debug label for commentDTOEntry next to acceptedAnswerCommentOptional flips from 6 -> .... to 11 -> ....

EDIT: I've made a reproducible example according to WJSs wishes. This is the code:

import java.util.*;
import java.math.BigInteger;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.function.Function;
class CommentDTO implements Comparable<CommentDTO> {
private BigInteger id;
private BigInteger owningCommentId;
private BigInteger commenterId;
private Long owningEntityId; 
private String commenterName;
private String commenterRole;
private String country;
private String thumbnailImageUrl;
private String content;
private String commentDateVerbalized;
private boolean flagged;
private Integer flagCount;
private boolean deleted; 
private boolean liked;
private Integer likeCount;
private String lastEditedOnVerbalized;
private boolean acceptedAsAnswer;
private boolean rightToLeft;
private TreeSet<CommentDTO> replies = new TreeSet<>(); 
public CommentDTO() {
}
public CommentDTO(boolean acceptedAsAnswer, BigInteger id){
this.acceptedAsAnswer = acceptedAsAnswer;
this.id = id;
}
public CommentDTO(boolean acceptedAsAnswer, BigInteger id, BigInteger owningCommentId){
this.acceptedAsAnswer = acceptedAsAnswer;
this.id = id;
this.owningCommentId = owningCommentId;
}
public BigInteger getId() {
return id;
}
public void setId(BigInteger id) {
this.id = id;
}
public BigInteger getOwningCommentId() {
return owningCommentId;
}
public void setOwningCommentId(BigInteger owningCommentId) {
this.owningCommentId = owningCommentId;
}
public BigInteger getCommenterId() {
return commenterId;
}
public void setCommenterId(BigInteger commenterId) {
this.commenterId = commenterId;
}
public Long getOwningEntityId() {
return owningEntityId;
}
public void setOwningEntityId(Long owningEntityId) {
this.owningEntityId = owningEntityId;
}
public String getCommenterName() {
return commenterName;
}
public void setCommenterName(String commenterName) {
this.commenterName = commenterName;
}
public String getCommenterRole() {
return commenterRole;
}
public void setCommenterRole(String commenterRole) {
this.commenterRole = commenterRole;
}
public String getCountry() {
return country;
}
public void setCountry(String country) {
this.country = country;
}
public String getContent() {
return content;
}
public void setContent(String content) {
this.content = content;
}
public String getCommentDateVerbalized() {
return commentDateVerbalized;
}
public void setCommentDateVerbalized(String commentDateVerbalized) {
this.commentDateVerbalized = commentDateVerbalized;
}
public boolean isFlagged() {
return flagged;
}
public void setFlagged(boolean flagged) {
this.flagged = flagged;
}
public Integer getFlagCount() {
return flagCount;
}
public void setFlagCount(Integer flagCount) {
this.flagCount = flagCount;
}
public boolean isDeleted() {
return deleted;
}
public void setDeleted(boolean deleted) {
this.deleted = deleted;
}
public boolean isLiked() {
return liked;
}
public void setLiked(boolean liked) {
this.liked = liked;
}
public Integer getLikeCount() {
return likeCount;
}
public void setLikeCount(Integer likeCount) {
this.likeCount = likeCount;
}
public TreeSet<CommentDTO> getReplies() {
return replies;
}
public void setReplies(TreeSet<CommentDTO> replies) {
this.replies = replies;
}
public String getLastEditedOnVerbalized() {
return lastEditedOnVerbalized;
}
public void setLastEditedOnVerbalized(String lastEditedOnVerbalized) {
this.lastEditedOnVerbalized = lastEditedOnVerbalized;
}
public String getThumbnailImageUrl() {
return thumbnailImageUrl;
}
public void setThumbnailImageUrl(String thumbnailImageUrl) {
this.thumbnailImageUrl = thumbnailImageUrl;
}
public boolean isAcceptedAsAnswer() {
return acceptedAsAnswer;
}
public void setAcceptedAsAnswer(boolean acceptedAsAnswer) {
this.acceptedAsAnswer = acceptedAsAnswer;
}
public boolean isRightToLeft() {
return rightToLeft;
}
public void setRightToLeft(boolean rightToLeft) {
this.rightToLeft = rightToLeft;
}
@Override
public int compareTo(CommentDTO o) {
return this.id.compareTo(o.id);
}
@Override
public String toString() {
return "CommentDTO{" +
"id=" + id +
", owningCommentId=" + owningCommentId +
", commenterId=" + commenterId +
", owningEntityId=" + owningEntityId +
", commenterName='" + commenterName + '\'' +
", commenterRole='" + commenterRole + '\'' +
", country='" + country + '\'' +
", thumbnailImageUrl='" + thumbnailImageUrl + '\'' +
", content='" + content + '\'' +
", commentDateVerbalized='" + commentDateVerbalized + '\'' +
", flagged=" + flagged +
", flagCount=" + flagCount +
", deleted=" + deleted +
", liked=" + liked +
", likeCount=" + likeCount +
", lastEditedOnVerbalized='" + lastEditedOnVerbalized + '\'' +
", acceptedAsAnswer=" + acceptedAsAnswer +
", rightToLeft=" + rightToLeft +
", replies=" + replies +
'}';
}
}
public class HelloWorld implements Comparable<HelloWorld> {
private Long id;
private boolean acceptedAsAnswer;
public HelloWorld(){}
public HelloWorld(boolean acceptedAsAnswer, Long id){
this.acceptedAsAnswer = acceptedAsAnswer;
this.id = id;
}
@Override
public String toString() {
return "id= " + id + " acceptedAsAnswer= " + acceptedAsAnswer;   
}
public boolean isAcceptedAsAnswer(){
return acceptedAsAnswer;
}
public long getId(){
return id;
}
public static void main(String []args){
HelloWorld helloWorld = new HelloWorld();
helloWorld.doTest();
}
@Override
public int compareTo(HelloWorld o) {
return this.id.compareTo(o.id);
}
public void doTest(){
Set<CommentDTO> commentDTOSet = new HashSet<>();
commentDTOSet.add( new CommentDTO(false, BigInteger.valueOf(3)));
commentDTOSet.add( new CommentDTO(true, BigInteger.valueOf(6)));
commentDTOSet.add( new CommentDTO(false, BigInteger.valueOf(11)));
commentDTOSet.add( new CommentDTO(true, BigInteger.valueOf(7), BigInteger.valueOf(6)));
commentDTOSet.add( new CommentDTO(true, BigInteger.valueOf(8), BigInteger.valueOf(6)));
Map<Long, CommentDTO> sortedAndLinkedCommentDTOMap = sortCommentsAndLinkCommentRepliesWithOwningComments(commentDTOSet);
Optional<Map.Entry<Long, CommentDTO>> acceptedAnswerCommentOptional = sortedAndLinkedCommentDTOMap.entrySet().stream()
.filter(entry -> entry.getValue().isAcceptedAsAnswer()).findFirst();
if(acceptedAnswerCommentOptional.isPresent()){
Map.Entry<Long, CommentDTO> commentDTOEntry = acceptedAnswerCommentOptional.get();
System.out.println(commentDTOEntry.toString());
sortedAndLinkedCommentDTOMap.remove(commentDTOEntry.getKey());
System.out.println(commentDTOEntry.toString());
}
}
private Map<Long, CommentDTO> sortCommentsAndLinkCommentRepliesWithOwningComments(Set<CommentDTO> commentDTOSet){
Map<Long, CommentDTO> commentDTOMap = commentDTOSet.stream()
.collect(Collectors.toMap(comment -> comment.getId().longValueExact(), Function.identity(), (v1,v2) -> v1, TreeMap::new));
commentDTOSet.forEach(commentDTO -> {
BigInteger owningCommentId = commentDTO.getOwningCommentId();
if(owningCommentId != null){
CommentDTO owningCommentDTO = commentDTOMap.get(owningCommentId.longValueExact());
owningCommentDTO.getReplies().add(commentDTO);
}
});
commentDTOMap.values().removeIf(commentDTO -> commentDTO.getOwningCommentId() != null); 
return commentDTOMap;
}
}

You can run the code above here: https://www.tutorialspoint.com/compile_java_online.php

EDIT 2: example code reproduces my problem now.

EDIT 3:
This line of code
commentDTOMap.values().removeIf(commentDTO -> commentDTO.getOwningCommentId() != null);
is causing the observed behavior. The accepted answer (commentDTO with id 6) has 2 replies to it. Those 2 comments (with id 7 and 8) are 'owned' by CommentDTO 6 and are also referenced by the replies list inside CommentDTO 6. At the end of sortCommentsAndLinkCommentRepliesWithOwningComments() I remove all CommentDTOs that can be considered replies to another comment owningCommentId != null. I do this because these comments are now referenced from within the replies lists of the owning comments. If i were to leave them in the original map then those replies will appear twice. Therefore i remove them but this is causing unexpected behavior. I would like to know why this is so.

That happens because the map you are using is a TreeMap.

A TreeMap is implemented as a red-black tree, which is a self-balancing binary tree.

The entries of the map are used as the nodes of the tree.

If you remove one entry then the tree has to re-balance itself and it might happen that the entry is then used to point to the node that takes its place.

Since TreeMap.entrySet() is backed by the map, the changes are reflected in the set.

The changes depends also on which node you are removing, for example if it's a leaf then it might just be unlinked from the tree and the entry is left unaffected.

If you use another map implementation like an HashMap then you won't get this behavior.

By the way, here's a simpler example, which doesn't even involve Optional or custom classes:

Map<Long, String> map = new TreeMap<>();
map.put(1L, "a");
map.put(2L, "b");
map.put(3L, "c");
map.put(4L, "d");
map.put(5L, "e");
map.put(6L, "f");
Map.Entry<Long, String> entry = map.entrySet().stream()
.filter(e -> e.getKey().equals(4L))
.findFirst()
.get();
System.out.println(entry);   // prints 4=d
map.remove(entry.getKey());
System.out.println(entry);   // prints 5=e