타짱의 기술블로그

Practical Testing: 실용적인 테스트 가이드 강의 - 대시보드 | 인프런 (inflearn.com)

본 내용은 'Practical Testing: 실용적인 테스트 가이드' 라는 인프런 강의를 들으며 내 생각을 정리한 내용입니다.

Spring&JPA 기반 테스트

Layer Architecture

레이어드 아키텍쳐란, 아래와 같이 관심사를 3가지(혹은 4가지) 로 분류한 아키텍쳐를 의미한다. 

테스트는 각 레이어마다 분리해서 진행한다. 

Persistance Layer 테스트

비즈니스 가공 로직이 포함되어서는 안된다. 데이터에 대한 CRUD에만 집중한 레이어

@DataJpaTest
class StockRepositoryTest {
    @Autowired
    private StockRepository stockRepository;

    @DisplayName("상품번호 리스트로 재고를 조회한다.")
    @Test
    void findAllByProductNumberIn() {
        //given
        Stock stock1 = Stock.create("001", 1);
        Stock stock2 = Stock.create("002", 2);
        Stock stock3 = Stock.create("003", 3);
        stockRepository.saveAll(List.of(stock1, stock2, stock3));

        //when
        List<Stock> stocks = stockRepository.findAllByProductNumberIn(List.of("001", "002"));

        //then
        Assertions.assertThat(stocks).hasSize(2)
                .extracting("productNumber", "quantity")
                .containsExactlyInAnyOrder(
                        Tuple.tuple("001", 1),
                        Tuple.tuple("002", 2)
                );
    }

}

@DataJpaTest

JPA 관련 어노테이션이 적용된 클래스만 스캔하여 빈에 올린다. 때문에 모든 빈들을 올리는 @SpringBootTest 보다 로드되는 시간이 빠르다는 장점이 있다.

또한, 내장된 인메모리 DB를 사용한다.

하지만 JPA 관련 어노테이션만 스캔하기 때문에, QueryDsl 같은 보조 라이브러리를 사용한다면 추가적인 설정이 필요하다.

Business Layer 테스트

@ActiveProfiles("test")
@SpringBootTest
//@Transactional
class OrderServiceTest {
    @Autowired
    private OrderService orderService;
    @Autowired
    private OrderRepository orderRepository;
    @Autowired
    private OrderProductRepository orderProductRepository;
    @Autowired
    private ProductRepository productRepository;
    @Autowired
    private StockRepository stockRepository;

    @AfterEach
    void tearDown(){
        orderProductRepository.deleteAllInBatch();
        productRepository.deleteAllInBatch();
        orderRepository.deleteAllInBatch();
        stockRepository.deleteAllInBatch();
    }

    @DisplayName("주문번호 리스트를 받아 주문을 생성한다.")
    @Test
    void createOrder() {
        //given
        Product product1 = creteProduct(HANDMADE,"001",1000);
        Product product2 = creteProduct(HANDMADE,"002",3000);
        Product product3 = creteProduct(HANDMADE,"003",5000);
        productRepository.saveAll(List.of(product1,product2,product3));

        OrderCreateRequest request = OrderCreateRequest.builder()
                .productNumbers(List.of("001", "002"))
                .build();
        //when
        LocalDateTime registeredDatetime = LocalDateTime.now();
        OrderResponse orderResponse = orderService.createOrder(request.toServiceRequest(), registeredDatetime);

        //then
        assertThat(orderResponse.getId()).isNotNull();
        assertThat(orderResponse)
                .extracting("registeredDateTime","TotalPrice")
                .contains(registeredDatetime,4000);
        assertThat(orderResponse.getProducts()).hasSize(2)
                .extracting("productNumber","price")
                .containsExactlyInAnyOrder(
                        tuple("001",1000),
                        tuple("002",3000)
                );
    }
    ...
}

tearDown 과 @Transactional, 그리고 JPA와 사용하는 @Transactional의 주의점

tearDown과 @Transactional 모두 전체 테스트를 수행할 때, 데이터가 전파되는것을 막기위한 방법이다. 

강사는 여기서 tearDown과 @Transactional의 차이를 제시해주었는데,

서비스단에 @Transactional이 없으면 변경감지를 하지 못해 실제로는 실패하지만, 

테스트단에 @Transactional이 있으면 변경감지를 하게 되기 때문에 테스트에서는 성공하는 케이스가 생긴다.

즉, 서비스에는 @Transactional이 없고, 테스트단에만 @Transactional이 있는 상황이 생길 수 있는데, 

실제로는 버그가 발생하지만 테스트에서는 이상없이 통과하는 케이스가 발생하게 된다라는 것이다.

결과적으로 테스트에서 @Transactional을 사용 할 때에는 서비스단에 @Transactional 적용을 했는지 여부를 한번에 파악할수 없기 때문에 주의해야한다고 한다.

서비스의 반환과 레포지토리의 반환이 동일하다면, 테스트를 전부 작성해야하는가에 대해

개인적으로 테스트 코드를 작성하면서 드는 고민 중 하나가 단순히 레포지토리에서 받아온 값을 반환하는 서비스라면, 동일한 결과를 테스트하는것인데 이걸 또 작성해야할까? 라는 의문이었다.

나는 이것에 대한 대답을 다음과 같이 정리했다. 

로직이 크게 없는 서비스와, 레포지토리의 테스트는 내용이 비슷하다.하지만
서비스가 발전할수록 기능이 추가되기 때문에 동일한 테스트라고 해도 작성하는것을 고민해보아야 한다.

도메인과 서비스에서 동일한 예외처리를 해야하는가에 대한 의문

아래 코드를 보면, 도메인과 서비스단에 동일한 예외(재고 부족)를 체크하고 있다. 이렇게 되면 동일한 예외를 중첩으로 체크하는데, 이유가 뭘까? 도메인에서만 예외를 터뜨려도 충분히 괜찮은 상황 아닐까?

public class Stock extends BaseEntity {
...

    public int deductQuantity(int quantity) {
        if(isQuantityLessThan(quantity)){
            throw new IllegalArgumentException("차감할 재고 수량이 없습니다.");
        }
        return this.quantity-=quantity;
    }
}

public class OrderService {
...

    private void deductStockQuantity(List<Product> products) {
        List<String> stockProductNumbers = extractStockProductNumbers(products);

        Map<String, Stock> stockMap = createStockMapBy(stockProductNumbers);

        Map<String, Long> productCountingMap = createCountingMapBy(stockProductNumbers);

        for (String stockProductNumber : new HashSet<>(stockProductNumbers)) {
            Stock stock = stockMap.get(stockProductNumber);
            int quantity = productCountingMap.get(stockProductNumber).intValue();
            if(stock.isQuantityLessThan(quantity)){
                throw new IllegalArgumentException("재고가 부족한 상품이 있습니다.");
            }
            stock.deductQuantity(quantity);
        }
    }
}

나는 답변을 다음처럼 정리했다.

클라이언트에게 주고싶은 메시지가 다르기 때문에 서비스단에서도 동일한 예외를 잡는다.
도메인에서 발생하는 예외는 범용적인 예외이고, 서비스단에서 발생하는 예외는 각 상황 맥락에 맞는 예외이기 때문에, 그에 맞는 메시지를 보내고 싶을 수 있다.

혹은 도메인 로직에서 커스텀 예외를 발생시키고, 외부에서 try-catch로 잡아 다시 원하는 예외 메시지를 전파하는 방법도 있다.

서비스단의 @Transactional(readOnly = true) - JPA 성능상 이점과 CQRS에 관하여

@Transactional(readOnly = true)가 되면 읽기 전용 즉, CRUD에서 R(조회) 만 동작하게 된다. 이렇게 되면 JPA에서 동작하는 변경감지같은 기능들이 동작할 필요가 없게되어 JPA 성능에 이점이 생긴다. 

CQRS란, command(업데이트) 와 query(읽기) 를 분리하는 패턴을 의미한다.

만약 서비스 자체를 읽기전용과 업데이트로 분리하게 된다면,

읽기전용 서비스는 슬레이브db, 업데이트 서비스는 마스터db에 배정하는 식으로 관리가 수월해진다.

Presentation Layer 테스트

파라미터에 대한 최소한의 검증을 수행

@WebMvcTest(controllers = ProductController.class)
class ProductControllerTest {
    @Autowired
    private MockMvc mockMvc;

    @Autowired
    private ObjectMapper objectMapper;

    @MockBean
    private ProductService productService;

   ...
   
    @DisplayName("판매 상품을 조회한다.")
    @Test
    void getSellingProducts() throws Exception {
        //given
        List<ProductResponse> responses = List.of();
        Mockito.when(productService.getSellingProducts()).thenReturn(responses);

        //when //then
        mockMvc.perform(
                get("/api/v1/products/selling")
        )
                .andDo(print())
                .andExpect(status().isOk())
                .andExpect(jsonPath("$.code").value("200"))
                .andExpect(jsonPath("$.status").value("OK"))
                .andExpect(jsonPath("$.message").value("OK"))
                .andExpect(jsonPath("$.data").isArray());

    }
}

@WebMvcTest, MockMvc,  @MockBean

@WebMvcTest : mvc에 관해서만 슬라이스 테스트할 수 있는 어노테이션. @component, @Service 같은 빈들은 자동구성되지 않는다. 또한 MockMvc, SpringSecurity 도 자동 구성한다. 일반적으로 @MockBean과 함께 사용한다.

MockMvc : Mock 객체를 사용해 스프링 mvc 동작을 재현할 수 있는 스프링 테스트 프레임워크

@MockBean : Mock 객체를 생성하여 빈에 올린다. 이후 Mockito를 이용해 조건과 결과를 설정할 수 있다.

Mock 객체를 사용하는 이유

테스트를 하기위해서 준비해야할 것들(객체를 생성하고, 저장하고, 서비스를 시행하고, 등등)이 너무 많아지기 때문에 잘 동작하는것을 가정하고 테스트를 하고자 Mock(가짜) 객체를 사용한다.

하위 레이어가 상위 레이어를 모르는것이 가장 좋다.

컨트롤러 레이어 하위 dto를 서비스단에 그대로 넘기게 된다면,

하위레이어가 상위 레이어의 정보를 알게 되므로(의존관계 생성),

각각의 레이어를 분리해서 관리하고자 할 때 어려움이 생긴다.

컨트롤러에서 서비스로 전송할 때에는, 서비스 레이어 하위 dto로 받아 넘기는것이 좋다.

@RestController
@RequiredArgsConstructor
public class ProductController {
    private final ProductService productService;

    @PostMapping("/api/v1/products/new")
    public ApiResponse<ProductResponse> createProduct(@Valid @RequestBody ProductCreateRequest request) {
        return ApiResponse.ok(productService.createProduct(request.toServiceRequest()));
    }
...

}


@Getter
@NoArgsConstructor
public class ProductCreateRequest {

   ...
    public ProductCreateServiceRequest toServiceRequest() {
        return ProductCreateServiceRequest.builder()
                .type(type)
                .sellingStatus(sellingStatus)
                .name(name)
                .price(price)
                .build();
    }
}

@Transactional(readOnly = true)
@Service
@RequiredArgsConstructor
public class ProductService {

    private final ProductRepository productRepository;
    @Transactional
    public ProductResponse createProduct(ProductCreateServiceRequest request) {
        String nextProductNumber = createNextProductNumber();

        Product product = request.toEntity(nextProductNumber);
        Product savedProduct = productRepository.save(product);

        return ProductResponse.of(savedProduct);
    }

  ...
}

@Valid 를 이용한 파라미터 검증

@NotNull 등과 같은 검증 어노테이션으로 파라미터를 검증할 수 있다.

@Getter
@NoArgsConstructor
public class ProductCreateRequest {

    @NotNull(message = "상품 타입은 필수입니다.")
    private ProductType type;

    @NotNull(message = "상품 판매상태는 필수입니다.")
    private ProductSellingStatus sellingStatus;

    @NotBlank(message = "상품 이름은 필수입니다.")
    private String name;

    @Positive(message = "상품 가격은 양수여야 합니다.")
    private int price;

    ...
}


@RestController
@RequiredArgsConstructor
public class ProductController {
    private final ProductService productService;

    @PostMapping("/api/v1/products/new")
    public ApiResponse<ProductResponse> createProduct(@Valid @RequestBody ProductCreateRequest request) {
        return ApiResponse.ok(productService.createProduct(request.toServiceRequest()));
    }

  ..
}

@WebMvcTest(controllers = ProductController.class)
class ProductControllerTest {
    @Autowired
    private MockMvc mockMvc;

    @Autowired
    private ObjectMapper objectMapper;

    @MockBean
    private ProductService productService;
    
    ...

    @DisplayName("신규 상품을 등록할 때 상풉 타입은 필수값이다.")
    @Test
    void createProductWithOutType() throws Exception {
        //given
        ProductCreateRequest request = ProductCreateRequest.builder()
                .sellingStatus(ProductSellingStatus.SELLING)
                .name("아메리카노")
                .price(4000)
                .build();

        //when //then
        mockMvc.perform(post("/api/v1/products/new")
                        .content(objectMapper.writeValueAsString(request))
                        .contentType(APPLICATION_JSON)
                )
                .andDo(print())
                .andExpect(status().isBadRequest())
                .andExpect(jsonPath("$.code").value("400"))
                .andExpect(jsonPath("$.status").value("BAD_REQUEST"))
                .andExpect(jsonPath("$.message").value("상품 타입은 필수입니다."))
                .andExpect(jsonPath("$.data").isEmpty());


    }

   ...
}

마치며

이번 섹션을 공부하면서, 지난날의 내가 테스트 코드를 짤 때, 짤 필요가 있는 코드와 없는 코드를 과연 구분했었는가에 대해서 고민을 하게 되었다. 또, TDD에 대해서 찾아보니 TDD에 대한 비판적인 시각도 꽤 많다는것을 알게 되었고, 그 부분도 이해가 되는 부분들이였다. 덕분에 무조건 적으로 받아들이는것이 아닌 비판적인 시각도 키워야겠다는 생각도 하게 되었다. 하지만 각자 장 단점이 존재 할 뿐 좋고 나쁘다는 없다고 생각하기 때문에 받아들이지 않을 필요도 없다고 생각한다.

참고

https://mangkyu.tistory.com/242

https://mson-it.tistory.com/16

https://jojoldu.tistory.com/320

https://docs.spring.io/spring-boot/docs/current/reference/htmlsingle/#features.testing.spring-boot-applications.autoconfigured-spring-data-jpa

Practical Testing: 실용적인 테스트 가이드 강의 - 대시보드 | 인프런 (inflearn.com)

본 내용은 'Practical Testing: 실용적인 테스트 가이드' 라는 인프런 강의를 들으며 내 생각을 정리한 내용이다.

테스트 코드에 대해서 들어도 보았고, 중요하다는것은 알았지만,

어떤 형식으로 작성해야 할 지, 내가 제대로 이해하고 있는것은 맞는지 배우고자 수강했다.

나에게 테스트 코드란

필자는 테스트 코드라는 단어를 들어보기만 했지, 내 구현 코드를 위한 테스트코드를 실질적으로 작성해본적은 없었다.

그러다 작년 겨울 우아한테크코스 코딩 테스트에 참여하여 테스트 코드에 대해서 고민해보게 되면서 그 중요성을 조금씩 알아가게 되었다.

예전에는 나에게 테스트 코드란 '구현하기도 벅찬 나같은 사람이 아닌, 능력자들의 마지막 1% 같은 것'으로 보였지만,

지금은 '당장은 느려보일 수 있으나, 내 코드에 신뢰를 가질 수 있고, 내가 놓친 것들을 한번 더 생각하게 만드는 수단' 이라고 생각한다. 

테스트 코드는 왜 필요할까?

기능이 작을 때에는 수동으로 프로그램을 테스트를 어렵지 않게 수행 할 수 있다. 하지만, 기능이 점점 거치면서 수동으로 시행하기에는 너무 많은 테스트 케이스들이 생겨나게 된다. 이것들을 사람들이 일일이 테스트하기에는 시간과 비용이 들 뿐만 아니라, 실수도 필연적으로 생길 수 있다.

그렇기에 테스트 코드를 작성하여 사람이 수동으로 체크해야 할 사항들을 컴퓨터가 체크하게 함으로써 내 코드에 대한 신속한 피드백을 통해 코드 품질을 향상시킬 수 있다.

하지만 내가 무작정 테스트 코드를 작성한다고 해서, 수동 테스트의 단점이 전부 해결되는것은 아니다. 테스트 코드를 '잘' 작성해야지 수동 테스트가 가지는 어려움들을 해소할 수 있다. 

단위 테스트

단위 테스트(Unit test)

작은 코드 단위(클래스 or 메서드)를 독립적으로 검증하는 테스트를 의미한다.

또한, 테스트 방식 중 규모가 가장 작은 테스트 방식이다.

수동 테스트 ,자동화 테스트

수동 테스트는 사람이 직접 수동으로 프로그램을 실행하면서 검증하는 것 이라면, 

자동 테스트는 Junit5와 같은 테스트 프레임워크를 통하여 개발자가 작성한 케이스에 한하여 기계가 검증을 하는것을 의미한다.

또한, 모든 상황에서 수동 테스트 보다 자동화 테스트가 좋은 것은 아니기에

테스트 코드가 필요한 상황과 그렇지 않은 상황을 구분할 줄 아는 능력이 필요하다.

해피 케이스, 예외 케이스, 경계값 테스트

해피 케이스는 테스트 코드가 통과하는 케이스를 의미한다. 

우리가 아메리카노를 주문하는 코드를 작성한다고 할 때, 다음과 같은 해피 케이스 테스트 코드를 작성할 수 있다.

@Test
    void addSeveralBeverages() {
        CafeKiosk cafeKiosk = new CafeKiosk();
        Americano americano = new Americano();

        cafeKiosk.add(americano, 2);
        assertThat(cafeKiosk.getBeverages()).size().isEqualTo(2);
        assertThat(cafeKiosk.getBeverages().get(0)).isEqualTo(americano);
        assertThat(cafeKiosk.getBeverages().get(1)).isEqualTo(americano);

    }

예외 케이스는 코드에 예상치 못한 값을 넣었을 때, 그 값을 올바르게 처리할 수 있는지 테스트하는 케이스를 의미한다.

아래는 0잔의 아메리카노를 주문했을 때, 적절한 메시지가 출력되는지 확인하는 테스트 코드이다.

 @Test
    void addZeroBeverages() {
        CafeKiosk cafeKiosk = new CafeKiosk();
        Americano americano = new Americano();

        assertThatThrownBy(() -> cafeKiosk.add(americano, 0))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("음료는 1잔 이상 주문하실수 있습니다.");
    }

그리고 이런 케이스들을 테스트 할 때는 경계값을 테스트하는 것이 가장 중요하다.

예를들어서, 어떤 값이 3 이상 일 때, A라는 조건을 만족해야 한다면,

우리는 이 코드의 해피 케이스를 작성할 때, 4나 5 같은 수 보다는 경계값인 3으로 테스트 케이스를 작성함으로써,

지정한 범위 내에 코드가 정확히 동작하는지 파악 할 수 있다.

마찬가지로 예외 케이스를 작성 할 때, -1 이나 1을 이용하여 테스트 하기 보다는 경계값인 2를 테스트 하는것이 좋다. 

따라서 경계값이 존재하는 테스트 케이스는 경계값으로 테스트를 작성하는것이 중요하다.

테스트하기 어려운 부분을 분리하기

강의에서는 커피 가게의 오픈 시간을 예로 들어서 설명했다.

오전 10시 이전, 오후 10시 이후에는 "주문 시간이 아닙니다. 관리자에게 문의하세요." 라는 예외를 발생한다.

@Getter
public class CafeKiosk {
    private static final LocalTime SHOP_OPEN_TIME = LocalTime.of(10,0);
    private static final LocalTime SHOP_CLOSE_TIME = LocalTime.of(22,0);
    private final List<Beverage> beverages = new ArrayList<>();
    
    ...
    
        public Order createOrder(){
            LocalDateTime currentDateTime = LocalDateTime.now();
            LocalTime currentTime = currentDateTime.toLocalTime();

            if(currentTime.isBefore(SHOP_OPEN_TIME) || currentTime.isAfter(SHOP_CLOSE_TIME)){
                throw new IllegalArgumentException("주문 시간이 아닙니다. 관리자에게 문의하세요.");
            }
            return new Order(currentDateTime, beverages);
        }
    }

그리고 테스트하기 어려운 부분을 분리하지 않고 테스트 코드를 작성했다.

이 코드는 어쩔 때에는 통과하고, 어쩔 때에는 실패하게 된다. 이유가 뭘까?

CafeKiosk의 createOrder 내부 구현 때문이다.

createOrder는 현재 LocalDateTime.now()를 이용하여 주문을 생성하기 때문에, 우리가 테스트 하는 시간에 따라서 테스트가 통과할 수도, 실패할 수도 있게 된다.

@Test
    void createOrder() {
        CafeKiosk cafeKiosk = new CafeKiosk();
        Americano americano = new Americano();

        cafeKiosk.add(americano);

        assertThatThrownBy(() -> cafeKiosk.createOrder())
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("주문 시간이 아닙니다. 관리자에게 문의하세요.");
    }

이것을 해결하기 위해서는 테스트하기 어려운 영역(현재시간, LocalDateTime.now())를 기존 코드에서 제거하고,

메서드 외부에서 값을 주입받을 수 있도록 해야한다.

 public Order createOrder(LocalDateTime currentDateTime){
        LocalTime currentTime = currentDateTime.toLocalTime();

        if(currentTime.isBefore(SHOP_OPEN_TIME) || currentTime.isAfter(SHOP_CLOSE_TIME)){
            throw new IllegalArgumentException("주문 시간이 아닙니다. 관리자에게 문의하세요.");
        }
        return new Order(currentDateTime, beverages);
    }

이렇게 하면 우리가 원하는 시간대를 지정하여 테스트를 할 수 있게 된다.

 @Test
    void createOrderOutsideOpenTime() {
        CafeKiosk cafeKiosk = new CafeKiosk();
        Americano americano = new Americano();

        cafeKiosk.add(americano);

        assertThatThrownBy(() -> cafeKiosk.createOrder(LocalDateTime.of(2024, 3, 27, 9, 59)))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessage("주문 시간이 아닙니다. 관리자에게 문의하세요.");
    }

TDD: Test Driven Development

구현할 코드보다 테스트 코드를 먼저 작성하여 테스트가 구현을 주도하도록 하는 방법론을 의미한다.

쉽게 말하면 기능을 구현하고 테스트 코드를 작성하는 방식이 아닌,

테스트 코드를 먼저 작성하고, 테스트 결과를 피드백 받으면서 구현 코드를 완성해가는 방식이다. 

레드-그린-리펙토링

TDD를 수행하기 위한 기법이다. 레드  -> 그린 -> 리펙토링 순서대로 진행한다.

RED : 실패하는 테스트를 작성한다

실패하는 테스트를 작성하는 말이 책으로만 보면 무슨말인지 잘 이해가 되지 않았었다. 본 강의에서는 다음과 같은 예를 제시했다.

우리가 calculateTotalPrice라는 기능을 구현하려 할 때, 먼저 테스트 코드를 작성하여 기능이 없는 빈 메서드를 생성한다.

이런 상태에서 코드를 실행하면 RED,

즉, 실패하는 테스트를 작성하는것을 완료하게 된다.

 @Test
    void calculateTotalPrice() {

        CafeKiosk cafeKiosk = new CafeKiosk();
        Americano americano = new Americano();
        Latte latte = new Latte();

        cafeKiosk.add(americano);
        cafeKiosk.add(latte);

        int totalPrice = cafeKiosk.createTotalPrice();
        
        assertThat(totalPrice).isEqualTo(8500);

    }
    
public class CafeKiosk {
...

 	public int createTotalPrice() {
        return 0;
    }

}

GREEN : 테스트를 통과하는 최소한의 코드를 작성한다

강의에서는 다음과 같은 예를 제시했다.

극단적인 예이긴 하지만, 이것도 맞는 방법이라고 한다.

public class CafeKiosk {
...

 	public int createTotalPrice() {
        return 8500;
    }

}

REFACTORING : 구현 코드를 개선하여 테스트 통과를 유지한다.

이런식으로 코드를 리팩토링하여 여전히 테스트가 통과하도록 유지한다.

public int createTotalPrice() {
        return beverages.stream().mapToInt(Beverage::getPrice)
                .sum();
    }

1일차를 마치며

이 강의에서 좋은점이 각 섹션 마지막에는 키워드를 정리해 주는데 이 방식이 좋은것 같다. 추가적으로 알면 좋을 키워드들도 던져주면서 지식의 범위를 넓혀 주는데 아무래도 연관된 키워드다 보니 동기 부여가 되어서 , 그냥 무작정 자료들을 검색하는것들 보다 더 몰입하면서 공부할 수 있었다. 

참고 자료

Practical Testing: 실용적인 테스트 가이드 강의 - 대시보드 | 인프런 (inflearn.com)

https://testmanager.tistory.com/186

1.putTreeVal

레드-블랙 트리 형식의 노드를 추가함과 동시에 연결리스트 관점에서의 순서도 같이 할당한다.

TreeNode는 연결리스트와 레드-블랙 트리의 형태가 합쳐진 하나의 형태로 생각하기보다는

연결리스트, 레드-블랙 트리의 모습을 각각 가지고 있는 형태로 이해된다.

1-1. find

마지막 else if 구문은 같은 오른쪽 자식부터 재귀하며 순회한다.

처음엔 마지막 else if 문에 순회 대신 putTreeVal, treeify 처럼 tieBreakOrder 메서드를 사용하여 dir값을 반환 해 재귀하여 순회하는 대신 더 쉽게 값을 찾을 수 있지 않을까? 라고 생각했었지만

스텍오버플로우에 질문하고 받은 답변으로 생각해보았을 때,

Question about comparing Java's HashMap `find` method and `tieBreakOrder` - Stack Overflow

애초에 tieBreakOrder는 원본해시값을 비교하므로 내가 가진 key가 내부에 저장된 key와 완전히 동일한 원본해시를

가질 확률이 높지 않으므로 불가능하다. 

2. removeTreeNode

연결리스트의 순서를 제거하고

제거하려는 노드가 successor 가 필요한 노드인지, 아닌지를 판별하고 삭제 속성을 적용시킨 후 노드를 제거한다.

여기서 트리노드의 크기가 너무 작아지면 untreeify를 호출해

TreeNode(레드-블랙 트리) -> Node(연결리스트) 로 변환한다.

2-1. balanceDeletion

레드-블랙 트리의 삭제 case 들을 적용한다.

3. untreeify

기존의 TreeNode를 순회하면서 각각의 TreeNode를 이용해 Node 구현체를 생성하고 서로 연결하여

Node 연결리스트를 반환한다.

이전의 treeify를 정리 할 때 TreeNode의 형태가 연결리스트와 레드-블랙 트리의 구조가 결합된 모습이라는 것은 알았으나

머릿속에서는 그 형태가 모호했는데, 이번 정리를 통해서 TreeNode의 형태를 조금 더 명확하게 이해할 수 있었고,

참조와 인스턴스의 관계성에 대해서 좀 더 이해할 수 있는 기회가 되었다.

자바의 hashMap은 내부 배열의 길이가 64, 한 버킷의 요소 수가 8 이상이 되면 해당 배열의 요소들은 연결리스트가 아닌 레드-블랙 트리 기반의 트리노드로 구현된다.


putVal의 로직 중 다음 로직을 보면 binCount를 반복하면서 TREEIFY_THRESHOLD-1 값에 다다를 때 treeifyBin을 호출한다.

...
for (int binCount = 0; ; ++binCount) {  
    if ((e = p.next) == null) {  
        p.next = newNode(hash, key, value, null);  
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
            treeifyBin(tab, hash);  
        break;  
    }  
    if (e.hash == hash &&  
        ((k = e.key) == key || (key != null && key.equals(k))))  
        break;  
    p = e;  
}
...

1. treeifyBin

첫번째 조건으로 배열의 길이를 측정하고 64 미만이라면 treeify하지 않고 resize()를 호출한다.

그 외 조건에서는 replacementTreeNode를 이용해 TreeNode를 생성하고 해당 버킷에 대한 treeify를 수행한다.

2. treeify

treeify는 해시맵의 내부배열 요소를 Node(연결리스트) 에서 TreeNode(레드-블랙 트리, 연결리스트 통합) 으로 변경하는 작업을 수행한다.

3.balanceInsertion

레드-블랙 트리의 속성에 맞게 노드 구조를 재조정한다.

4.moveRootToFront

메서드 이름만 보면 단순히 root를 해당 버킷의 요소로 할당만 하는것 같지만

추가적으로 root.next에 기존의 연결리스트를 참조한다.

여기서 중요한 점은 hashMap의 TreeNode는 레드-블랙 트리의 특성과 LinkedList의 특성을 동시에 가지며,
이 메서드에서는 treeify를 호출한 버킷의 요소를 기존의 Node(LinkedList) 형식에서 TreeNode(red-black tree)로 변환하고

root(TreeNode).next에 기존의 Node를 연결하여 순서를 계속 기억하고 있다는 점이다.
이 연결 순서를 기억하기 위해 putTreeVal 같은 연산을 시행할 때, 해당 메서드 내부에서는 

TreeNode의 값만을 연산하는것이 아니라, Node의 순서또한 업데이트한다.   

이는 효율성의 문제로 LinkedList형식으로 돌아갈 때 사용하는 untreeify를 위해서이다.

5. checkInvariants

Node -> TreeNode 형식으로 변환되면서 참조, 속성에 대해서 위반사항이 없는지 확인한다.

treeify를 정리하면서 해시맵이 단순히 연결리스트 -> 레드-블랙 트리 구조로 변경되는것이

아니라 레드-블랙 트리 + 연결리스트 구조를 합친 TreeNode로 변경되는것이 놀라웠다.

그래서 putTreeVal 같은 메서드 호출시 내부 로직을 보면 보면 값을

TreeNode에 추가함과 동시에 연결리스트에도 추가한 값의 순서를 저장한다.

레드-블랙 트리(RBT)란, 이진검색트리(BST)의 한 종류로, 
스스로 구조를 최적화 한다는 점에서
자가 균형 이진 탐색 트리(AVL) 비슷하지만 
좀더 유연하며 삽입,수정이 상대적으로 빠르다.

해시맵의 TreeNode를 알아보다가 레드-블랙 트리 구조라는 것을 알게 되었고,

아래 유튜브에 설명이 잘 되어있어 그림으로 다시 그려보며 정리했다.

(1부) 레드블랙트리(red-black tree)의 기본 개념과 특징을 살펴보고, 삽입 때 레드블랙트리가 어떻게 동작하는지를 아주 자세히 설명합니다~ 헷갈리시는 분들 커몬요 (youtube.com)

(2부) 레드블랙트리(red-black tree)의 삭제는 어떻게 동작할까요? 시간 복잡도는 어떻게 될까요? AVL 트리와 차이는 무엇일까요? 이 영상으로 후련하게 해결하세요 :) (youtube.com)

레드-블랙 트리의 각 노드들은 red 혹은 black 노드로 구성되어있고, 각 리프에는 nil이라는 임시 노드들이 존재하며, 일반 노드와 동급 취급한다.

nil 노드는 다음과 같은 특징을 지닌다.
- 존재하지 않음을 의미하는 노드
- 자녀가 없을 때 자녀를 nil 노드로 표기
- 값이 있는 노드와 동등하게 취급
- RBT에서 leaf 노드는 nil 노드
- 모든 nil(leaf) 노드는 black

1. 속성 

레드-블랙 트리는 다음과 같은 속성이 존재한다.

#1 : 모든 노드는 red 혹은 black 이다
#2 : 루트 노드는 black 이다
#3 : 모든 nill 노드는 black 노드이다
#4 : 노드가 red라면 자녀들을 black 이다
#5 : 임의의 노드에서 그 노드의 자손 nil 노드들 까지 가는 경로들의 black 수는 같다.(자기 자신은 카운트에서 제외)

여기서 다른 속성들은 이해가 되는데, 5번은 무슨 의미인지 헷갈린다. 무슨 의미일까?

그림과 같이 B 노드에서 시작해 C의 nil 노드와, G의 nil 노드까지의 black 노드의 수는 모두 2이다. 

그외에도 어디든 nil 노드까지의 black 노드의 수는 2로 모두 동일하다.

이렇게 어디서든 모든 nil 노드까지의 black 노드의 수는 동일해야 한다는 것이 #5 규칙이다.

black height

특정 노드에서 nil 노드까지의 내려가는 경로에서 black 노드의 수를 black height 라고 한다.

RB 트리는 어떻게 균형을 잡을까?

삽입/삭제 시 주로 #4, #5 사항을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡힌다.

• #4 : 노드가 red라면 자녀들을 black 이다
• #5 : 임의의 노드에서 그 노드의 자손 nil 노드들 까지 가는 경로들의 black 수는 같다

2. 삽입

overveiw

삽입 과정은 다음과 같은 순서로 진행된다.

0. 삽입 전 RBT 속성을 만족한 상태
1. 삽입 방식은 일반 적인 BST와 동일
2. 삽입 후 RBT 위반 여부 확인
3. RBT 속성을 위반했다면 재조정
4. RB 트리 속성을 다시 만족

삽입 노드의 색

삽입하는 노드의 색은 언제나 red이다.

삽입 예시

최초에 50 노드를 삽입 하면 다음과 같은 형태가 된다.

두 nil 노드의 색은 black으로 고정되며
자연스럽게 #3 속성을 만족하게 된다.

• #3 : 모든 nill 노드는 black 노드이다

하지만 50은 root 노드이므로 #2 속성을 위반하게 된다.
이때는 루트 노드를 black으로 바꾸면 해결된다.

• #2 : 루트 노드는 black 이다

이렇게 노드 삽입 후 #2 의 속성을 위반한다면 black으로 변경해주면 해결된다.

이후 20을 삽입하면 자연스럽게 RBT의 모든 속성을 만족한다.

왜 새로 삽입하는 노드는 red인가?

red 노드로 삽입을 하면 black height의 변동이 없으므로 #5 속성을 만족하게 된다

•  #5 : 임의의 노드에서 그 노드의 자손 nil 노드들 까지 가는 경로들의 black 수는 같다

삽입 시 속성 해결

case3

삽입된 red 노드(N)가 부모(P)의 왼쪽 자식,
부모도 red 이고 할아버지(G)의 왼쪽 자식,
삼촌(U)은 black 이라면 
부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽 회전

예시 상황

insert(10)
현재 상황에서는 레드 노드 자식이 레드 노드이므로, #4 속성을 위반한다.

• #4 : 노드가 red라면 자녀들을 black 이다

BST 속성을 유지하며 #4 속성 위반을 해결하기 위해서는 회전이 필요하다
그러기 위해서 부모와 할아버지의 색을 교체한 후 할아버지 기준으로 오른쪽으로 회전시킨다.

case2

삽입된 red 노드(N)가 부모(P)의 오른쪽 자녀,
부모도 red고 할아버지(G)의 왼쪽 자녀,
삼촌(U)은 black 이라면
부모를 기준으로 왼쪽 으로 회전한 뒤 case3 방식으로 해결

예시 상황

insert(40)

20을 기준으로 왼쪽으로 회전하여 case.3과 동일하게 만들어준다.
이후 case.3의 방식으로 문제를 해결한다.

case1

삽입된 red 노드(N)의 부모(P)도 red,
삼촌(U)도 red 라면
부모와 삼촌을 black으로 바꾸고 할아버지(G)를 red로 바꾼 뒤
할아버지에서 다시 확인을 시작(루트인지 아닌지, 할아버지 부모도 red 노드인지)

예시 상황

아래 상황에서는 case.2 을 적용할 수 없다.  왜일까?

이 상황에서 case.2를 적용하면 다음처럼 20-10 관계에서 추가적인 문제가 생기기 때문이다.
그렇기에 삼촌이 red이면 case.1을 적용해야 한다.

case.1을 적용하여 부모와 삼촌은 black, 할아버지는 red로 변경한다.
이후 RBT의 5 속성에 위반하는지 확인한다.

3. 삭제

삭제 방식 overview

0. 삭제 전 RBT 속성을 만족한 상태
1. 삭제 방식은 일반적인 BST와 동일
2. 삭제 후 RBT 속성 위반 여부 확인
3. RBT 속성을 위반했다면 재조정
4. RBT 속성을 다시 만족

속성 위반 여부 확인 방법

RBT에서 노드를 삭제할 때
어떤 색이 삭제되는지가
속성 위반 여부를 확인할 때 매우 중요

삭제하려는 노드의 자녀가 없거나 하나라면
삭제되는 색 = 삭제되는 노드의 색

25 삭제 -> red 삭제
80 삭제 -> black 삭제
40 삭제 -> black 삭제

삭제하려는 노드의 자녀가 둘이라면
삭제되는 색 = 삭제되는 노드의 successor의 색
* successor : 해당 노드보다 큰 가장 작은 노드 

20삭제 -> successor 25 -> red 삭제
35삭제 -> successor 37 -> red 삭제
50삭제 -> successor 80 -> black 삭제

삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.

#1 : 모든 노드는 red 혹은 black
#2 : 루트 노드는 black
#3 : 모든 nill 노드는 black
#4 : 노드가 red라면 자녀들을 black
#5 : 임의의 노드에서 그 노드의 자손 nil 노드들까지 가는 경로들의 black 수는 같다.

삭제되는 색이 black 이라면
#2, #4, #5 속성을 위반할 수 있다.

#2 : 루트 노드는 black
#4 : 노드가 red라면 자녀들을 black
#5 : 임의의 노드에서 그 노드의 자손 nil 노드들까지 가는 경로들의 black 수는 같다.

삭제되는 색이 black 일때

#2 위반 해결하기

루트 노드를 black으로 변환하면 된다

#5 위반 해결하기

extra black 부여

#5 속성을 다시 만족 시키기 위해 
삭제된 색의 위치를 대체한 노드에
extra black을 부여한다.

extra black의 역할

경로에서 black 수를 카운트 할 때
extra black은 하나의 black으로 카운트 된다

예시 상황

delete(10)
10의 위치를 대체한 nil 노드에 extra black 부여
-> #5 속성 다시 만족

delete(30)
삭제된 색은 30의 black이었으므로
30의 위치를대체한 노드인
25에 extra black 부여
-> #5 속성 다시 만족

delete(50)
50을 제거하는경우
50은 자식이 둘다 존재하기 때문에 제거하게되면 50의 successor인 80과 값을 교체하고 black 노드를 제거하게 된다.
black 노드를 제거하는 경우, 이를 대체하기 위한 extra black을 nil 노드에 부여한다. 

정리

삭제되는 색이 black 이고 #5 위반일 때
extra black 부여 결과

extra black 을 부여받은 노드는
doubly black이 되거나
red-and-black이 된다

red  - and - black 해결하기

red-and-black 을 
black 으로 바꾸면 해결

doubly black 해결하기

doubly black을 제거하는 방법은 
총 4가지 case로 분류됨

네가지 case로 분류할 때의 기준은
doubly black의 형제의 색과
그 형제의 자녀들의 색

doubly black 제거 케이스

case.4

doubly black의 오른쪽 형제가 black
그 형제의 오른쪽 자녀가 red 일 때

오른쪽 형제는 부모의 색으로,
오른족 형제의 오른쪽 자녀는 black으로,
부모는 black으로 바꾼 후에
부모를 기준으로 왼쪽으로 회전하면 해결

예시 상황

delete(15)

case.3

doubly black의 오른쪽 형제가 black
그 형제의 왼쪽 자녀가 red
그 형제의 오른쪽 자녀는 black 일때

doubly black의 형제의 오른쪽 자녀를
red가 되게 만들어
이후엔 case4를 적용

예시 상황

delete(33)

case.2

doubly black의 형제가 black
그 형제의 두 자녀 모두 black 일때
doubly black과 그 형제의 black을 모아
부모에게 전달해
부모가 extra black을 해결하도록 위임한다

부모가 루트노드라면 black으로 바꿔서 해결
아니라면 case1,2,3,4 중에 하나로 해결

예시 상황

delete(40)

case.1

doubly black의 오른쪽 형제가 red 일 때
부모와 형제의 색을 바꾸고
부모를 기준으로 왼쪽으로 회전한 뒤
doubly black을 기준으로
case 2,3,4 중에 하나로 해결 

예시 상황

delete(80)

자바에서 해시맵은 노드의 배열로 되어있는 자료구조이다.

자료를 저장할 때에는 데이터를 해싱이라는 작업을 통해 정수로 반환하고,
해당하는 인덱스의 배열에 저장한다.

마찬가지로 조회할 때에도 해싱을 통해 반환된 인덱스로 빠르게 자료를 조회할 수 있다.

여기서 주의해야할 점이 2가지 있다.

1. 해시맵 사용 시 주의 사항

첫번째는 해시값은 중복이 가능하다는 점이다. 이를 해시충돌 이라고 한다.
따라서 다른 데이터여도, 해시값이 같으면 같은 인덱스에 노드로써 저장된다. 기본적으로 연결리스트 형식으로 저장되지만, 크기가 커지면 트리노드형식으로 저장된다.

두번째는 같은 상태를 가진 동일한 객체라고 해도 참조가 다르다면, 다른 해시코드를 반환한다는 점이다.

TmpObject object1 = new TmpObject(1);  
TmpObject object2 = new TmpObject(1);  
System.out.println("object1 = " + object1.hashCode());  
System.out.println("object2 = " + object2.hashCode());

---
object1 = 793589513
object2 = 824909230

이것이 왜 중요한것일까? 
이것이 중요한 이유는 해시맵의 내부 배열 저장 인덱스, 즉 버킷 인덱스는, 
키값의 해시코드값에 달려있기 때문이다.

최소 jdk1.8 이후 객체의 해시코드(Object.hashCode)는 어떠한 규칙에 의해 만들어지는것이 아니라,
로컬-스레드 난수로 이루어진 id값으로 생성된다.

그렇기에 우리가 다른곳에서 저장한 값을 불러오고자 할때, 같은 벨류를 가진 객체를 이용해서 찾는다고해도,

결국은 새로운 객체이기 때문에 새로운 해시코드를 할당받는다. 
그렇기에 우리는 같은 밸류라면 같은 해쉬코드를 반환한다는 약속을 해야하는 것이다.

그것이 흔히 이야기하는 hashCode 메서드를 오버라이드 하라는 의미이다.

@Override  
public boolean equals(Object o) {  
    if (this == o) {  
        return true;  
    }  
    if (o == null || getClass() != o.getClass()) {  
        return false;  
    }  
    TmpObject tmpObject = (TmpObject) o;  
    return num == tmpObject.num;  
}  
  
@Override  
public int hashCode() {  
//Object.hashCode와는 다르게, 객체 데이터 값을 이용해 해시값을 지정한다.
    return Objects.hash(num);
}

TmpObject object1 = new TmpObject(1);  
TmpObject object2 = new TmpObject(1);

//오버라이드한 hashCode값을 반환한다.
System.out.println("object1 = " + object1.hashCode());  
System.out.println("object2 = " + object2.hashCode());

// 본래 hashCode값(Obejct.hashCode)을 반환한다.
int OriginalObject1Hash = System.identityHashCode(object1);  
int OriginalObject2Hash = System.identityHashCode(object2);  
System.out.println("OriginalObject1Hash = " + OriginalObject1Hash);  
System.out.println("OriginalObject2Hash = " + OriginalObject2Hash);

---

object1 = 32
object2 = 32

OriginalObject1Hash = 664223387
OriginalObject2Hash = 824909230

그렇다면 equals는 왜 따라서 오버라이드 해야 하는 것일까?
해시코드만 동일하게 고정시키고, 저장, 조회한다면, equals는 왜 필요할까?

그것은 해시맵의 구조 자체가 한 인덱스에 하나의 데이터만 들어가는 구조가 아니기 때문이다.
즉, 해시 충돌이 발생한 인덱스의 경우, 정확히 어떤값을 찾아야할지 비교해야하므로,
우리는 equlas를 오버라이드하여, 해시맵이 보통 타입, 벨류들을 비교 후 동등한지 아닌지를 
비교하여 반환하게 한다.

이것이 equals, hashCode 메서드가 해시관련 자료구조에서 오버라이딩해야하는 이유이다.

2. 멤버 인스턴스

다음은 멤버 인스턴스를 살펴보자.

 2-1. 상수

DEFAULT_INITIAL_CAPACITY  :  최초로 값을 넣을 때 생성되는 맵 내부 배열의 크기이다. 주석을 보면 2의 제곱만 가능하다고 되어있는데, 이것은 이후에 소개 할 resize 메서드와 관련이 있다.

MAXIMUM_CAPACITY  :  해시맵 으로써 가질수 있는 길이의 최대 크기이다. 

DEFAULT_LOAD_FACTOR  :  배열의 크기를 늘리는 기준이다.

TREEIFY_THRESHOLD  :  배열에서 한 버킷 안에 연결되어있는 노드가 연결될 수 있는 최대 수, 내부배열의 자료구조가 링크드리스트에서 트리맵으로 변경되는 기준1

UNTREEIFY_THRESHOLD  :  트리노드에서 다시 배열로 전환되는 버킷 사이즈에 대한 값이다. 

MIN_TREEIFY_CAPACITY  :  배열의 길이를 의미하며, 내부배열의 자료구조가 링크드리스트에서 트리맵으로 변경되는 기준2

/**  
 * The default initial capacity - MUST be a power of two. 
 */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  
  
/**  
 * The maximum capacity, used if a higher value is implicitly specified 
 * by either of the constructors with arguments. 
 * MUST be a power of two <= 1<<30. 
 */
 static final int MAXIMUM_CAPACITY = 1 << 30;  
  
/**  
 * The load factor used when none specified in constructor. 
 */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;  
  
/**  
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater 
 * than 2 and should be at least 8 to mesh with assumptions in 
 * tree removal about conversion back to plain bins upon 
 * shrinkage. 
 */
 static final int TREEIFY_THRESHOLD = 8;  
  
/**  
 * The bin count threshold for untreeifying a (split) bin during a 
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at 
 * most 6 to mesh with shrinkage detection under removal. 
 */
 static final int UNTREEIFY_THRESHOLD = 6;  
  
/**  
 * The smallest table capacity for which bins may be treeified. 
 * (Otherwise the table is resized if too many nodes in a bin.) 
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts 
 * between resizing and treeification thresholds. 
 */
 static final int MIN_TREEIFY_CAPACITY = 64;

2-2 변수

/**  
 * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */
   transient Node<K,V>[] table;  
  
/**  
 * Holds cached entrySet(). Note that AbstractMap fields are used 
 * for keySet() and values(). 
 * */
   transient Set<Map.Entry<K,V>> entrySet;  
  
/**  
 * The number of key-value mappings contained in this map.
 * */
   transient int size;  
  
/**  
 * The number of times this HashMap has been structurally modified 
 * Structural modifications are those that change the number of mappings in 
 * the HashMap or otherwise modify its internal structure (e.g., 
 * rehash).  This field is used to make iterators on Collection-views of 
 * the HashMap fail-fast.  (See ConcurrentModificationException). 
 */
   transient int modCount;
   
/**  
 * The next size value at which to resize (capacity * load factor). 
 * * @serial  
 */  
// (The javadoc description is true upon serialization.  
// Additionally, if the table array has not been allocated, this  
// field holds the initial array capacity, or zero signifying  
// DEFAULT_INITIAL_CAPACITY.)  
int threshold;  
  
/**  
 * The load factor for the hash table. 
 * * @serial  
 */  
final float loadFactor;

 3. 기본 생성자

Stack, ArrayDeque와는 다르게, 초기화 할 때 내부 배열의 크기를 정하지 않는다.

/**  
 * Constructs an empty {@code HashMap} with the default initial capacity  
 * (16) and the default load factor (0.75). */public HashMap() {  
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  
}

4. 삽입

해시맵에서는 객체의 해시값 외에 자체적인 내부 해시값을 객체에 부여하며,
해시충돌 수, 배열의 크기에 따라 연결리스트에서 트리노드로 변환되기도 하며, 반대의 경우도 있다.
이 글에서는 연결리스트 섹션을 중심으로 정리하고자 한다.
각각의 파라미터는 다음과 같다.

4-1. put

put 메서드에서는 hash라는 메서드를 통해 객체의 해시코드를 해시맵에 사용할수 있게 내부용 해시코드를 생성한다.

public V put(K key, V value) {  
    return putVal(hash(key), key, value, false, true);  
}

static final int hash(Object key) {  
    int h;  
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
}

4-2. putVal

hash : 내부용 해시코드
key : 키
value : 값
onlyIfOnlyAbsent : 참이면, 동일한 키의 데이터가 이미 저장되어있을 때 값을 덮어 씌우지 않는다.
evict : LinkedHashMap에서 사용되며, 해시맵 자체에서는 단독으로 사용되지 않는다.

/**  
 * Implements Map.put and related methods. * * @param hash hash for key  
 * @param key the key  
 * @param value the value to put  
 * @param onlyIfAbsent if true, don't change existing value  
 * @param evict if false, the table is in creation mode.  
 * @return previous value, or null if none  
 */
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
               boolean evict) {  
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //1  
    if ((tab = table) == null || (n = tab.length) == 0)  
        n = (tab = resize()).length;  
    //2
    if ((p = tab[i = (n - 1) & hash]) == null)  
        tab[i] = newNode(hash, key, value, null);  
    else {  
        Node<K,V> e; K k;
        //3  
        if (p.hash == hash &&  
            ((k = p.key) == key || (key != null && key.equals(k))))  
            e = p;
    //  
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //4
        else {  
            for (int binCount = 0; ; ++binCount) {
            //4-1  
                if ((e = p.next) == null) {  
                    p.next = newNode(hash, key, value, null);  
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);  
                    break;  
                }
                //4-2  
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    break;  
                p = e;  
            }  
        }
        //5 
        if (e != null) { // existing mapping for key  
            V oldValue = e.value;  
            if (!onlyIfAbsent || oldValue == null)  
                e.value = value;  
            afterNodeAccess(e);//미구현  
            return oldValue;  
        }  
    }
    //6  
    ++modCount;  
    if (++size > threshold)  
        resize();  
    afterNodeInsertion(evict);//미구현  
    return null;  
}

(1) 
내부 배열이 생성되지 않은 경우에는 resize 메서드를 이용하여 내부 배열을 초기화한다.

//1
if ((tab = table) == null || (n = tab.length) == 0)  
        n = (tab = resize()).length;

(2)
해당 인덱스가 null 이라면, 데이터를 저장한다.

//2
if ((p = tab[i = (n - 1) & hash]) == null)  
        tab[i] = newNode(hash, key, value, null);

(3) 
해당 인덱스의 첫번째 키가 저장하려는 키와 동일하다면, 저장하려는 노드를 e로 할당한다

//3
if (p.hash == hash &&  
            ((k = p.key) == key || (key != null && key.equals(k))))  
            e = p;

(4) 

버킷의 노드를 순회한다.

//4
else {  
            for (int binCount = 0; ; ++binCount) {
            //4-1  
                if ((e = p.next) == null) {  
                    p.next = newNode(hash, key, value, null);  
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);  
                    break;  
                }
                //4-2  
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    break;  
                p = e;  
            }  
        }

(4-1)
현재 노드의 다음노드가 없다면
그 다음노드로 현재 노드를 추가한다.

만약 특정 버킷에서 연결 리스트의 길이가 `TREEIFY_THRESHOLD` (기본값은 8)를 초과하면, 연결 리스트는 트리 구조로 변환된다. 이는 버킷 내부에 있는 노드들의 총 수에 기반한다.

//4-1
if ((e = p.next) == null) {  
p.next = newNode(hash, key, value, null);  
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
treeifyBin(tab, hash);  
break;  
}

(4-2)
만약 버킷에서 동일한 키의 노드를 찾으면 루프를 벗어난다.

//4-2
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))  
    break;

(5)
이미 키가 존재한다면,  기존 키의 값을 반환하고, 현재 값으로 덮어쓴다.

//5
if (e != null) { // existing mapping for key  
            V oldValue = e.value;  
            if (!onlyIfAbsent || oldValue == null)  
                e.value = value;  
            afterNodeAccess(e);  
            return oldValue;  
        }

(6)
현재 해쉬맵에 저장된 데이터 수량이 임계값을 넘어가면 resize를 호출한다.

//6
++modCount;  
if (++size > threshold)  
    resize();  
afterNodeInsertion(evict);  
return null;

4-3. resize

final Node<K,V>[] resize() {  
    Node<K,V>[] oldTab = table;  
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  
    int oldThr = threshold;  
    int newCap, newThr = 0;
    //1  
    if (oldCap > 0) {
    //1-1  
        if (oldCap >= MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;  
            return oldTab;  
        }
        //1-2  
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                 oldCap >= DEFAULT_INITIAL_CAPACITY)  
            newThr = oldThr << 1; // double threshold  
    }
    //2
    //2-1
    else if (oldThr > 0) // initial capacity was placed in threshold  
        newCap = oldThr;
    //2-2  
    else {               // zero initial threshold signifies using defaults  
        newCap = DEFAULT_INITIAL_CAPACITY;  
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
    }
    //3
    if (newThr == 0) {  
        float ft = (float)newCap * loadFactor;  
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
                  (int)ft : Integer.MAX_VALUE);  
    }  
    threshold = newThr;
    //4  
    @SuppressWarnings({"rawtypes","unchecked"})  
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
    table = newTab;  
    if (oldTab != null) {  
        for (int j = 0; j < oldCap; ++j) {  
            Node<K,V> e;  
            if ((e = oldTab[j]) != null) {  
                oldTab[j] = null;  
                if (e.next == null)  
                    newTab[e.hash & (newCap - 1)] = e;  
                else if (e instanceof TreeNode)  
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
                else { // preserve order  
                    Node<K,V> loHead = null, loTail = null;  
                    Node<K,V> hiHead = null, hiTail = null;  
                    Node<K,V> next;  
                    do {  
                        next = e.next;  
                        if ((e.hash & oldCap) == 0) {  
                            if (loTail == null)  
                                loHead = e;  
                            else  
                                loTail.next = e;  
                            loTail = e;  
                        }  
                        else {  
                            if (hiTail == null)  
                                hiHead = e;  
                            else  
                                hiTail.next = e;  
                            hiTail = e;  
                        }  
                    } while ((e = next) != null);  
                    if (loTail != null) {  
                        loTail.next = null;  
                        newTab[j] = loHead;  
                    }  
                    if (hiTail != null) {  
                        hiTail.next = null;  
                        newTab[j + oldCap] = hiHead;  
                    }  
                }  
            }  
        }  
    }  
    return newTab;  
}

(1)

이미 내부 배열이 할당 된 경우의 조건문이다.

//1  
    if (oldCap > 0) {
    //1-1  
        if (oldCap >= MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;  
            return oldTab;  
        }
        //1-2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                 oldCap >= DEFAULT_INITIAL_CAPACITY)  
            newThr = oldThr << 1; // double threshold  
    }

(1-1)
기존의 내부 배열이 MAXIMUM_CAPACITY 이상이면
저장가능한 데이터 수량(threshold)을 최대치로 변경하고 그대로 반환한다.

(1-2)
내부 배열을 2배로 늘린 값이 MAXIMUM_CAPACITY 보다 작고,
기존의 내부 배열이 DEFAULT_INITIAL_CAPACITY 이상이면
newThr(데이터 최대 저장 수) 또한 기존의 oldThr의 2배로 늘린다. 

(2)

//2
//2-1
    else if (oldThr > 0) // initial capacity was placed in threshold  
        newCap = oldThr;
    //2-2  
    else {               // zero initial threshold signifies using defaults  
        newCap = DEFAULT_INITIAL_CAPACITY;  
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
    }

(2-1)
주석에는 '최초 용량이 threshold에 할당되어 있다' 라고 적혀있다.
언뜻 조건을 보면 이상하게 느껴진다. (1)의 oldCap이 0 이하이고, oldThr 가 0보다 큰 경우는 뭘까?

//2-1
    else if (oldThr > 0) // initial capacity was placed in threshold  
        newCap = oldThr;

답은 생성자에 있었다.
(1)을 보면, 최초 내부 용량을  tableSizeFor메서드를 이용해서 threshold로 전송하고있다.
내부 배열 크기를 결정하는 변수가 따로 존재하지 않아,
threshold를 이용해 임시적으로 initialCapacity를 전송한 것으로 보인다.

/**  
 * Constructs an empty {@code HashMap} with the specified initial  
 * capacity and load factor. * * @apiNote  
 * To create a {@code HashMap} with an initial capacity that accommodates  
 * an expected number of mappings, use {@link #newHashMap(int) newHashMap}.  
 * * @param  initialCapacity the initial capacity  
 * @param  loadFactor      the load factor  
 * @throws IllegalArgumentException if the initial capacity is negative  
 *         or the load factor is nonpositive */public HashMap(int initialCapacity, float loadFactor) {  
    if (initialCapacity < 0)  
        throw new IllegalArgumentException("Illegal initial capacity: " +  
                                           initialCapacity);  
    if (initialCapacity > MAXIMUM_CAPACITY)  
        initialCapacity = MAXIMUM_CAPACITY;  
    if (loadFactor <= 0 || Float.isNaN(loadFactor))  
        throw new IllegalArgumentException("Illegal load factor: " +  
                                           loadFactor);  
    this.loadFactor = loadFactor;
    //1  
    this.threshold = tableSizeFor(initialCapacity);  
}

(2-2)
기본 생성자로 해시맵을 생성 했을 때의 로직이다.

//2-2  
    else {               // zero initial threshold signifies using defaults  
        newCap = DEFAULT_INITIAL_CAPACITY;  
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
    }

(3)
(2-1) 의 경우, oldThr로 newCap은 값이 할당되지만,
newThr는 따로 값이 초기화되지 않으므로,
newThr값을 연산하여 threshold에 대입한다.

//3  
    if (newThr == 0) {  
        float ft = (float)newCap * loadFactor;  
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  
                  (int)ft : Integer.MAX_VALUE);  
    }  
    threshold = newThr;

(4)

//4
//4-1
    @SuppressWarnings({"rawtypes","unchecked"})  
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
    table = newTab;  
    if (oldTab != null) {  
        for (int j = 0; j < oldCap; ++j) {  
            Node<K,V> e;  
            if ((e = oldTab[j]) != null) {  
                oldTab[j] = null;  
                if (e.next == null)  
                    newTab[e.hash & (newCap - 1)] = e;  
                else if (e instanceof TreeNode)  
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //4-2  
                else { // preserve order  
                    Node<K,V> loHead = null, loTail = null;  
                    Node<K,V> hiHead = null, hiTail = null;  
                    Node<K,V> next;  
                    do {  
                        next = e.next;  
                        if ((e.hash & oldCap) == 0) {  
                            if (loTail == null)  
                                loHead = e;  
                            else  
                                loTail.next = e;  
                            loTail = e;  
                        }  
                        else {  
                            if (hiTail == null)  
                                hiHead = e;  
                            else  
                                hiTail.next = e;  
                            hiTail = e;  
                        }  
                    } while ((e = next) != null);
                    //4-3  
                    if (loTail != null) {  
                        loTail.next = null;  
                        newTab[j] = loHead;  
                    }  
                    if (hiTail != null) {  
                        hiTail.next = null;  
                        newTab[j + oldCap] = hiHead;  
                    }  
                }  
            }  
        }

(4-1)
newCap으로 배열을 확장하고, oldCap의 배열들을 순회하면서 
버킷에 요소가 하나뿐인것들을 골라 newTab에 재배열한다.

//4-1
    @SuppressWarnings({"rawtypes","unchecked"})  
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
    table = newTab;  
    if (oldTab != null) {  
        for (int j = 0; j < oldCap; ++j) {  
            Node<K,V> e;  
            if ((e = oldTab[j]) != null) {  
                oldTab[j] = null;  
                if (e.next == null)  
                    newTab[e.hash & (newCap - 1)] = e;  
                else if (e instanceof TreeNode)  
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    ...

(4-2)
버킷에 요소가 다수일 경우, 해시값에 대한 연산을 통해 low, high로 지정한다.

//4-2  
                else { // preserve order  
                    Node<K,V> loHead = null, loTail = null;  
                    Node<K,V> hiHead = null, hiTail = null;  
                    Node<K,V> next;  
                    do {  
                        next = e.next;  
                        if ((e.hash & oldCap) == 0) {  
                            if (loTail == null)  
                                loHead = e;  
                            else  
                                loTail.next = e;  
                            loTail = e;  
                        }  
                        else {  
                            if (hiTail == null)  
                                hiHead = e;  
                            else  
                                hiTail.next = e;  
                            hiTail = e;  
                        }  
                    } while ((e = next) != null);  
                    ...

이렇게 나뉘어진 두 연결 리스트의 head를 각각의 버킷 인덱스에 할당한다 .

(4-3)

//4-3
if (loTail != null) {  
                        loTail.next = null;  
                        newTab[j] = loHead;  
                    }  
                    if (hiTail != null) {  
                        hiTail.next = null;  
                        newTab[j + oldCap] = hiHead;  
                    }

이렇게 resize를 호출할때마다 기존 버킷의 요소들을 넓게 분포시킴으로써  해시충돌을 완화하여 시간복잡도를 낮게 유지시켜준다.

24.01.31

이렇게 resize()로 기존 요소들을 다시 여러 버킷으로 재할당 할 때, Node의 hash값 자체는 변경하지 않는다.
즉, 동일한 버킷 내에서도 여러 hash값들이 존재할 수 있다.

5. 조회

찾으려는 값의  key를 내부 해시함수로 연산하여 버킷값을 찾고, 
해당하는 값이 나올때까지 연결 리스트를 순회한다. 
없다면 null을 반환한다.

public V get(Object key) {  
    Node<K,V> e;  
    return (e = getNode(key)) == null ? null : e.value;  
}

final Node<K,V> getNode(Object key) {  
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;  
    if ((tab = table) != null && (n = tab.length) > 0 &&  
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {  
        if (first.hash == hash && // always check first node  
            ((k = first.key) == key || (key != null && key.equals(k))))  
            return first;  
        if ((e = first.next) != null) {  
            if (first instanceof TreeNode)  
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
            do {  
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    return e;  
            } while ((e = e.next) != null);  
        }  
    }  
    return null;  
}

해시코드란, 객체의 고유한 정수값이다. 

Object.hashCode는 객체에 대한 해시값을 정수로 반환한다.
이 해시코드는 상태가 같더라도 인스턴스마다 고유한 값을 가진다

static void hashCodeTest(){  
    TmpObject object1 = new TmpObject(1);  
    TmpObject object2 = new TmpObject(1);  
    System.out.println("object1 = " + object1.hashCode());  
    System.out.println("object2 = " + object2.hashCode());  
}  
  
static class TmpObject{  
    int num;  
  
    public TmpObject(int num) {  
        this.num = num;  
    }  
}

---
object1 = 793589513
object2 = 824909230

객체의 equals,hashcode를 오버라이드하면 상태가 같은 객체는 같은 해시값을 반환하게 만들 수 있다.

static class TmpObject{  
    int num;  
  
    public TmpObject(int num) {  
        this.num = num;  
    }  
  
    @Override  
    public boolean equals(Object o) {  
        if (this == o) {  
            return true;  
        }  
        if (o == null || getClass() != o.getClass()) {  
            return false;  
        }  
        TmpObject tmpObject = (TmpObject) o;  
        return num == tmpObject.num;  
    }  
  
    @Override  
    public int hashCode() {  
        return Objects.hash(num);  
    }  
}


---
object1 = 32
object2 = 32

이와는 별개로 System.identityHashCode를 사용하면 
오버라이딩 이전의 원본 해시코드값을 알아낼 수 있다.

System

/**  
 * Returns the same hash code for the given object as * would be returned by the default method hashCode(), * whether or not the given object's class overrides * hashCode(). * The hash code for the null reference is zero. * * @param x object for which the hashCode is to be calculated  
 * @return  the hashCode  
 * @since   1.1  
 * @see Object#hashCode  
 * @see java.util.Objects#hashCode(Object)  
 */@IntrinsicCandidate  
public static native int identityHashCode(Object x);
```


```java
TmpObject object1 = new TmpObject(1);  
TmpObject object2 = new TmpObject(1);  
System.out.println("object1 = " + object1.hashCode());  
System.out.println("object2 = " + object2.hashCode());  
int OriginalObject1Hash = System.identityHashCode(object1);  
int OriginalObject2Hash = System.identityHashCode(object2);  
System.out.println("OriginalObject1Hash = " + OriginalObject1Hash);  
System.out.println("OriginalObject2Hash = " + OriginalObject2Hash);

---
object1 = 32
object2 = 32
OriginalObject1Hash = 664223387
OriginalObject2Hash = 824909230

hashCode의 알고리즘에 대해서 궁금해서 찾아보니 
난수, 메모리 기반 생성등 다양한  주장들이 있었는데, 
이것에 대해서 명확하게 하고자 알아보았다.

Object

@IntrinsicCandidate  
public native int hashCode();

native가 선언되어있어 IDE에서는 코드를 확인할 수 는 없었지만, github에서 찾아 볼 수 있었다.

다음은 해시코드에 대한 C++ 코드이다.
HashCode의 값에 따라서 java의 Object.hashCode의 해시코드 생성 전략이 달라진다.

hashCode == 0 : 난수 반환
hashCode == 1 : 객체의 메모리주소에 추가연산 후 반환
hashCode == 2 : 상수 1을 반환
hashCode == 3 : 전역 카운터를 사용하여 반환
hashCode == 4 : 메모리 주소 직접 반환
hashCode == else : 스레드-로컬 난수값 반환 

// hashCode() generation :
//
// Possibilities:
// * MD5Digest of {obj,stw_random}
// * CRC32 of {obj,stw_random} or any linear-feedback shift register function.
// * A DES- or AES-style SBox[] mechanism
// * One of the Phi-based schemes, such as:
//   2654435761 = 2^32 * Phi (golden ratio)
//   HashCodeValue = ((uintptr_t(obj) >> 3) * 2654435761) ^ GVars.stw_random ;
// * A variation of Marsaglia's shift-xor RNG scheme.
// * (obj ^ stw_random) is appealing, but can result
//   in undesirable regularity in the hashCode values of adjacent objects
//   (objects allocated back-to-back, in particular).  This could potentially
//   result in hashtable collisions and reduced hashtable efficiency.
//   There are simple ways to "diffuse" the middle address bits over the
//   generated hashCode values:

static inline intptr_t get_next_hash(Thread* current, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    // This form uses global Park-Miller RNG.
    // On MP system we'll have lots of RW access to a global, so the
    // mechanism induces lots of coherency traffic.
    value = os::random();
  } else if (hashCode == 1) {
    // This variation has the property of being stable (idempotent)
    // between STW operations.  This can be useful in some of the 1-0
    // synchronization schemes.
    intptr_t addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
  } else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
  } else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
  } else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
  } else {
    // Marsaglia's xor-shift scheme with thread-specific state
    // This is probably the best overall implementation -- we'll
    // likely make this the default in future releases.
    unsigned t = current->_hashStateX;
    t ^= (t << 11);
    current->_hashStateX = current->_hashStateY;
    current->_hashStateY = current->_hashStateZ;
    current->_hashStateZ = current->_hashStateW;
    unsigned v = current->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    current->_hashStateW = v;
    value = v;
  }

  value &= markWord::hash_mask;
  if (value == 0) value = 0xBAD;
  assert(value != markWord::no_hash, "invariant");
  return value;
}

HashCode값은 jdk8 이하 버전에서는 확인이 가능하나, 이후 버전부터는 확인이 불가능 한 것으로 보인다.

하지만 else 구문 주석에서 볼 수 있듯이, 아마 else부분이 디폴트 옵션으로 동작하지 않을까 싶다.

jdk8 이하에서는 jdk 버전/bin 에 들어가 
실제 HashCode 값을 확인 할 수 있다.
다음을 명령을 실행한다.

java -XX:+PrintFlagsFinal -version

다음과 같이 HashCode값이 5라는 것을 확인 할 수 있다.

해시코드 로직에 대한 답이 다양해서 이해가 잘 안되었는데
메모리주소, 난수 모두 가능하며, 꽤 오래전부터 해시코드는 난수로 생성한다는것을 알 수 있었다.

참고자료

https://shipilev.net/jvm/anatomy-quarks/26-identity-hash-code/#_footnotedef_4

https://github.com/openjdk/jdk/blob/4927ee426aedbeea0f4119bac0a342c6d3576762/src/hotspot/share/runtime/synchronizer.cpp#L760-L798

https://bugs.openjdk.org/browse/JDK-8199394

https://stackoverflow.com/questions/49172698/default-hashcode-implementation-for-java-objects/49175508#49175508

큐는 FIFO 자료구조이다.
처음 넣은 데이터가 처음 반환된다는 것인데,
실생활의 예를 들면, 식당에서 밥을 먹기 위해 줄을 서는것을 볼 수있다.
맨 앞에서면 맨 먼저 입장한다.

Deque는 'Double Ended Queue'의 줄임말로, 기존 Queue의 개념을 확장한 일반화된 형태다.

이 자료구조는 양쪽 끝에서 데이터의 삽입과 삭제가 가능하며, 그래서 Queue와 Stack의 기능을 모두 포함하고 있다.

이로 인해 Deque는 Queue나 Stack보다 더 유연하고 다용도로 사용될 수 있다.

이전에 Stack 자료구조에서 설명했듯이, 양 LIFO,FIFO 를 모두 구현하는 자료구조인데,  원래는 순수 FIFO의 기능을 하는  큐 구현체를 소개하려 했지만, 생각보다 순수하게 FIFO만을 구현하는 구현체가 많이 없고, 스레드 세이프한 자료구조들이 많아 소개하기 복잡할것같아, deque를 FIFO 자료구조 소개 수단으로 채택했고, 그 구현체 중 하나인 ArrayDeque로 

중심으로 설명하고자 한다.

ArrayDeque

이 ArrayDeque에는 사실 스텍과 큐의 메서드 모두가 정의되어있다.

ArrayDeque 인터페이스인 Deque의 문서를 읽어보면, 이에 대해서 다음과 같이 보여준다.

Stack, Queue에서의 메서드와 
Deque에서 동일한 기능을 하는 메서드를 소개한다.

Deque는 Stack, Queue의 메서드를 모두 사용할 수는 있지만, 코드를 뜯어보면 결국 구현로직은 아래처럼 Deque메서드를 사용하기 때문에, Deque의 메서드 중심으로 설명하고자 한다.

1. 생성자 

일단 생성자부터 살펴보자

/**  
 * Constructs an empty array deque with an initial capacity * sufficient to hold 16 elements. */
 public ArrayDeque() {  
    elements = new Object[16 + 1];  
}

그런데 주석을 보니, 처음부터 의문이 생긴다.
주석에서는 16개의 요소를 가지고있다고 하는데
왜 실제 구현에서는 크기가 16+1 일까?

이는 순환큐(Circular Queue)와 관련이 있다.
그럼 순환 큐는 큐와 어떻게 다르냐?
큐는 우리가 알고있는 FIFO 자료구조 형식이고,

이런 Queue는 LinkedList, ArrayDeque같이 여러 방식으로 구현이 가능하다.

Queue, Stack, List와 같은 개념적인 자료구조들은 추상 데이터 타입(ADT)으로 분류하는데,
ADT는 데이터와 그 데이터에 적용할 수 있는 연산들을 정의하지만, 
구체적인 구현 방식은 정의하지 않는다.

순환 큐 는 큐라는 자료구조의 구체적인 구현 구조라고 보면 된다.

이 순환 큐는 배열 구조로 구현되는데, 이를 위해  ArrayDeque는 head, tail을 추가적으로 선언한다.

그럼 이제 우리는 순환 큐가 큐의 구현 방식 중 하나 이고, head, tail은 순환 큐를 위한 것을 알았다. 그럼, 순환큐는 왜 이 head, tail이 필요한가? 그리고 이 head, tail은 정확히 무엇을 의미하는가?

삽입과정을 통해 알아보자.

2. 삽입

public void addLast(E e) {  
    if (e == null)  
        throw new NullPointerException();  
    final Object[] es = elements;  
    es[tail] = e;  
    if (head == (tail = inc(tail, es.length)))  
        grow(1);  
}

static final int inc(int i, int modulus) {  
    if (++i >= modulus) i = 0;  
    return i;  
}

ArrayDeque를 처음 생성하고, 첫 값을 넣을 때를 예를 들어보자.

생성자를 보면 최초 생성시 배열의 총 길이는 17이므로 내부에는 17개의 배열을 생성하며, 

실제로는 16개의 배열만 사용한다.
여기서 head,tail은 배열의 가장 앞의 요소 인덱스, 가장 마지막 요소 인덱스를 의미한다.

클레스에서 맴버변수는 자동으로 초기화되므로,
head, tail = 0이 된다.
총 17개의 배열이 있으며, 마지막 따로 표시한 배열은 값을 저장하는데 사용하지 않고, 해당 인덱스가 끝에 도달했는지 여부를 비교할때 사용한다. (빈칸은 모두 null이다.)

그럼 es[0], 즉 첫번째 배열은 "a"가 된다.

이제 head == tail ,즉 배열이 가득 찼는지 판별한다. 동일하다면,
배열이 가득 찼다는 의미이므로, 배열 크기를 늘릴것이고, 아니라면 늘리지 않는다.

inc메서드는 tail 인덱스가 마지막 배열을 넘어서는지 확인하고, 

아니라면 그대로 tail을 반환할것이고,  넘어간다면, tail을 0으로 변경한다.

현 상황에서는 1을 반환하므로 tail = 1이 되고, 
배열이 가득차지 않았으므로, grow는 호출되지 않는다.

grow는 단순하게 이야기하면 배열을 늘려주는 메서드이다.

배열의 크기를 비교해서 작으면 2배 정도를 늘리고,  크다면 원본의 절반의 크기를 늘린다.

이후 늘어난 배열 크기만큼 요소들의 위치를 재정렬한다.

private void grow(int needed) {  
    // overflow-conscious code  
    final int oldCapacity = elements.length;  
    int newCapacity;  
    // Double capacity if small; else grow by 50%  
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);  
    if (jump < needed  
        || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)  
        newCapacity = newCapacity(needed, jump);  
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity);  
    // Exceptionally, here tail == head needs to be disambiguated  
    if (tail < head || (tail == head && es[head] != null)) {  
        // wrap around; slide first leg forward to end of array  
        int newSpace = newCapacity - oldCapacity;  
        System.arraycopy(es, head,  
                         es, head + newSpace,  
                         oldCapacity - head);  
        for (int i = head, to = (head += newSpace); i < to; i++)  
            es[i] = null;  
    }  
}

grow메서드의 로직이 잘 이해가 안된다면 이런 Deque 내부 배열이 있다고 예를 들어보자

현재 상황은 ArrayDeque에 1,2,3을 전부 삽입한 경우이다.

여기서 addLast 메서드는 head, tail이 동일하므로 
grow(1) 을 실행한다.

Object[] integer = {1,2,3};

배열의 크기가 3 이므로, newCapacity = 8 이 된다.

현재 head == tail && head != null 이므로, 재정렬을 시행한다.

제거되어야 할 배열을 정리한다.
동시에 head의 값도 맞게 할당한다.

3. 반환

public E removeFirst() {  
    E e = pollFirst();  
    if (e == null)  
        throw new NoSuchElementException();  
    return e;  
}

public E pollFirst() {  
    final Object[] es;  
    final int h;  
    E e = elementAt(es = elements, h = head);  
    if (e != null) {  
        es[h] = null;  
        head = inc(h, es.length);  
    }  
    return e;  
}

static final <E> E elementAt(Object[] es, int i) {  
    return (E) es[i];  
}

반환은 배열 크기를 정하는 로직은 필요 없으므로 상대적으로 쉬운 구조이다.

해당 배열 요소를 가져오고, null 처리하며, head를 1 증가 시킨 후

배열 요소를 반환한다.

이러한 ArrayDeque는 싱글스레드에서 사용하도록 구현되었으므로 멀티스레드 환경에서는 사용을 주의해야한다.

Stack은 LIFO 구조로 구현된 자료구조이다. 

여기서 LIFO(Last In First Out)란,

마지막으로 들어온 데이터가 가장 먼저 반환된다는 의미다.

실생활에서 우리는 LIFO를 책을 쌓아놓은 것으로 예를 들 수 있다.

책을 눕혀서 차곡차곡 쌓아놓으면, 가장 처음 쌓은 책은 가장 마지막에,

가장 마지막에 올려둔 책은 가장 먼저 꺼낼 수 있다. 

이것을 후입선출, LIFO 라고 한다. 

시작하기에 앞서, 자바에서는 Stack보다는 이후에 나온 Deque 구현체의 사용을 권장한다.

Deque는 LIFO,FIFO를 모두 지원하는 자료구조이다.

1. 상속

이제 자바의 Stack을 뜯어보자. Stack은 Vector라는 구현체를 상속하고있다.

public class Stack<E> extends Vector<E> {}

 Vector란 ArrayList와 유사하게 배열의 크기를 조절하는 자료구조로, ArrayList 이전에 구현된 자료구조이다.

이 둘은 기능적으로는 유사한점이 많지만, Vector는 다중 스레드에, ArrayList는 단일 스레드에 적합하다.

2. 삽입

먼저 삽입을 알아보자. 

Stack

public E push(E item) {  
    addElement(item);  
  
    return item;  
}

Vector

public synchronized void addElement(E obj) {  
    modCount++;  
    add(obj, elementData, elementCount);  
}

private void add(E e, Object[] elementData, int s) {  
    if (s == elementData.length)  
        elementData = grow();  
    elementData[s] = e;  
    elementCount = s + 1;  
}

Vector의 add 메서드를 살펴보는데 궁금한점이 생겼다.

우리는 보통 List같은 자료구조로 데이터를 저장할 때 제네릭 타입을 이용해서 한가지 타입으로만 저장한다.

여기서 제네릭이란, <> 를 의미하며, 컴파일 시 타입을 체크해준다.

아래 예제에서는 <Integer>가 제네릭이며, Integer를 제네릭타입으로 지정한것이다.

List<Integer> numbers = new ArrayList<>();

근데 Vector의 맴버인스턴스를 확인해보면 배열의 타입이 Object로 되어있다.

public class Vector<E>  
    extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
{  
    /**  
     * The array buffer into which the components of the vector are     * stored. The capacity of the vector is the length of this array buffer,     * and is at least large enough to contain all the vector's elements.     *     * <p>Any array elements following the last element in the Vector are null.  
     *     * @serial  
     */  
    @SuppressWarnings("serial") // Conditionally serializable  
    protected Object[] elementData;  
  
    /**  
     * The number of valid components in this {@code Vector} object.  
     * Components {@code elementData[0]} through  
     * {@code elementData[elementCount-1]} are the actual items.  
     *     * @serial  
     */  
    protected int elementCount;  
  
    /**  
     * The amount by which the capacity of the vector is automatically     * incremented when its size becomes greater than its capacity.  If     * the capacity increment is less than or equal to zero, the capacity     * of the vector is doubled each time it needs to grow.     *     * @serial  
     */  
    protected int capacityIncrement;
    
    ...

즉, 제네릭으로 타입체크를 한 후 자료구조에 저장을 하면

타입이 제네릭 타입으로 저장되는게 아니라, 

Object로 저장되는 것이다.

3. 반환

Stack

public synchronized E pop() {  
    E obj;  
    int len = size();  
  
    obj = peek();  
    removeElementAt(len - 1);  
  
    return obj;  
}

public synchronized E peek() {  
    int     len = size();  
  
    if (len == 0)  
        throw new EmptyStackException();  
    return elementAt(len - 1);  
}

여기서 elementCount는 요소의 수량을 반환하는것 같고, elementAt은 해당 인덱스의 값을 반환하는것 같다.

removeElementAt은 지정한 요소를 제거하는것 같은데, 로직이 뭔가 많다.

여기서 j는 뭘 의미하고, System.arraycopy는 무엇일까?

Vector

public synchronized int size() {  
    return elementCount;  
}

public synchronized void removeElementAt(int index) {  
    if (index >= elementCount) {  
        throw new ArrayIndexOutOfBoundsException(index + " >= " +  
                                                 elementCount);  
    }  
    else if (index < 0) {  
        throw new ArrayIndexOutOfBoundsException(index);  
    }  
    int j = elementCount - index - 1;  
    if (j > 0) {  
        System.arraycopy(elementData, index + 1, elementData, index, j);  
    }  
    modCount++;  
    elementCount--;  
    elementData[elementCount] = null; /* to let gc do its work */  
}

public synchronized E elementAt(int index) {  
    if (index >= elementCount) {  
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
    }  
  
    return elementData(index);  
}

j가 무엇인지 알려면, 일단 System.arraycopy가 어떤 역할을 하는지부터 알아야 한다.

이름을 보면 배열을 복사한다는것같은데, 파라미터는 또 왜이리 많은가?

코드를 뜯어보면 다음처럼 구성되어있다.

여기서 native 라는 선언은, 자바 코드가 아닌, c나 c++같은 로우레벨 언어로 구현된 메서드라는 의미이다.

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

Object src : 원본 배열
int srcPost :  복사를 시작할 첫번째 인덱스
Obejct dest : 목적 배열
destPos : 목적배열에서 복사한 값을 할당할 첫번재 인덱스
length : 복사할 배열 요소의 수

실제로 적용해보면 다음과 같다.
정말 단순히 배열값을 복사하는 메서드이다.

String[] src = {"a","b","c","d","e"};  
String[] dest = new String[5];  
System.arraycopy(src,2,dest,0,3);  
  
for (String s : dest) {  
    System.out.print(s + " ");  
}

---
c d e null null

이번엔 src와 dest에 모두에 src를 넣고 실행해보자.
1인덱스 요소부터 3개의 요소를 원본의 맨 처음 부분부터 할당한다.

String[] arr = {"a","b","c","d","e"};  
System.arraycopy(arr,1,arr,0,3);  
for (String s : arr) {  
    System.out.print(s + " ");  
}

---
b c d d e

b c d d e 가 된 이유는
원본 배열에 붙여 넣었으므로,

원본배열 : [a,b,c,d,e]
복사 요소 : b,c,d
배열 할당 : [b,c,d,d,e]

순서로 할당되기 때문이다.

이번엔 하나의 값만을 제거한 후 배열을 앞으로 당기는 예를 보자.

String[] arr = {"a","b","c","d","e"};  
System.arraycopy(arr,1,arr,0,4);  
arr[arr.length-1] = null;  
for (String s : arr) {  
    System.out.print(s + " ");  
}

---
b c d e null

이제 다시 벡터의 removeElement 메서드를 보면 이해가 좀더 쉽다.

이제 우리는 j가 삭제한 요소 뒤에 존재하는 요소들의 수량이라는것을 알았고,

System.arraycopy는 지정한 배열 요소를 복사하는 기능이며

상황에 따라 같은 배열의 값을 제거하고, 앞으로 당기는 역할을 할 수 있다는것을 알았다.

전체적인 로직은 이렇다.

삭제하고자 하는 배열의 인덱스가 마지막이면 바로 마지막 인덱스를 null 처리한다.
그렇지 않다면, arraycopy를 이용해 값을 제거하고 마지막의 불필요한 배열을 null처리한다.

왜 JVM의 스택 영역은 LIFO인것일까?

왜 스택 영역은 LIFO인가?

그전에, LIFO,FIFO의 차이는 뭘까?

처음엔 단순히 LIFO,FIFO의 차이는 '첫번째들어간 데이터가 나오는 순서의 차이' 로만 이해했지만,

지금은 LIFO,FIFO의 차이는 '데이터의 실행 시점의 차이'에 있다고 생각한다.

LIFO는 마지막 데이터가 가장 마지막으로 조회되지만, 가장 먼저 실행된다.
하지만 FIFO는 첫번째 데이터가 가장 먼저 실행된다.
즉, 조회는 동일하지만, 실행 시점에 있어서 차이가 있다는 의미다.

스택 영역은 메모리 호출 순서를 관리하는 곳인데,
말 그대로 Stack, LIFO로 구현된다.
그럼 왜 스택영역은 FIFO로 구현되면 안될까?

답은 간단했다. FIFO는 첫번째 실행된 메서드가 가장먼저 연산되어야 한다. 하지만 재귀같은 내부에 다른 메서드가 포함되어있는 메서드의 경우에는 어떤가? 첫번째 메서드가 실행이 완료되기전에 내부 메서드의 연산이 종료되고, 이후에 그 연산값을 이용해 첫번째 메서드가 연산을 완료한다.

즉, FIFO로 메모리 호출이 구현된다면
첫번째 메서드가 실행되면서 두번째 메서드를 실행하고, 첫번째 메서드는 연산을 기다린다. 하지만, 두번째 메서드는 실행되지 않는다. 왜냐?  첫번째 메서드가 종료되지 않았으니까!

하지만 LIFO는 조금 다르다
첫번째 메서드가 실행되면, 내부에서는 또 메서드를 실행한다.

그리고 가장 마지막 메서드의 연산값, 즉 마지막 메서드가 종료되면, 그 이전 메서드가 실행되게 된다.

LinkedList는 Node라는 인스턴스변수를 가지는 자료구조이다.
쉽게 표현하자면 LinkedList는 기차 라는 전체적인 틀 이고, Node는 이 기차의 연결된 열차로 보면 이해하기가 쉽다.
즉, node는 서로 연결되어있는 노드의 위치와, 자신이 가지고 있어야 할 값만을 가지고 있다.

LinkedList의 인스턴스변수 는 대략적으로 이렇게 구성되어있다.
여기서 frist와 last는 말 그대로 노드의 처음과 마지막을 의미하는데, 이 first, last를 기준으로 노드들을 추가,제거,순회한다.

1. 구조

public class LinkedList<E>  
extends AbstractSequentialList<E>  
implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
{  
    transient int size = 0;  

    /**  
    * Pointer to first node.  
    */  
    transient Node<E> first;  

    /**  
    * Pointer to last node.  
    */  
    transient Node<E> last;

LinkedList 내부에 구현되어있는 Node 구현은 다음과 같다.

private static class Node<E> {  
    E item;  
    Node<E> next;  
    Node<E> prev;  

    Node(Node<E> prev, E element, Node<E> next) {  
        this.item = element;  
        this.next = next;  
        this.prev = prev;  
    }  
}

이와같이  next와, prev가 존재하는 노드를 양방향리스트 라고 부른다.

2. add

우리가 처음 LinkedList를 생성하면 다음과 같은 상황이 연출된다.
객체는 초기화가 되므로 선언만 되었던 변수들이 각자 초기화가 되면서 0, null을 할당한다.

여기서 다음과 같이 값을 추가하면,

linkedList.add("firstValue");

다음과 같은 코드가 호출된다.
linkLast 메서드를 5단계로 분류했다.

public boolean add(E e) {  
    linkLast(e);  
    return true;  
}

void linkLast(E e) {  
    final Node<E> l = last;  //1
    final Node<E> newNode = new Node<>(l, e, null);  //2
    last = newNode;  //3
    if (l == null)  
    	first = newNode;  	
    else  
        l.next = newNode;  
    size++;  //4
    modCount++;  //5
}

이 부분은 현재 last노드를 임시로 비교하고자 변수로 선언한다. 

final Node<E> l = last; //1

그리고 다음과 같이 새 노드를 생성한다.

final Node<E> newNode = new Node<>(l, e, null); //2

시각적으로 표현하면 다음과 같다.
최초 삽입 시에는 last도 null이므로 결국 prev = null이 된다.

여기서는 linkdList의 last를 직접적으로 newNode로 지정한다.
만약 
inkedList에 아무런 데이터도 없을 때에는 newNode를 최초,최후 노드로 지정한다.
그렇지 않다면,
기존에 데이터가 있던 상황이라면, l.next, 즉 마지막 노드의 다음 노드로 newNode를 지정한다.

last = newNode;  //3
if (l == null)  
	first = newNode;  
else  
	l.next = newNode;

단순하게 시각화 한다면 다음과 같다

최초 노드 삽입 시

기존 노드에 추가적으로 삽입 시(size=1)

이제 linkdList에 newNode가 추가되었으니, size를 증가시켜준다.

size++;  //4

그런데 이상한점을 발견한다. 분명, modCount는 인스턴스 변수에 없었는데, 어디서 나타난걸까?

modCount++;  //5

modCount는 AbstractList로 구현된 것이고, LinkedList는 이를 계승 했기 때문에 가능하다. 

modCount는 수정된 횟수를 추적하는데 이것은 Iterator를 위해 사용된다.
Iterator는 조회의 역할을 위해 사용하므로 순회 중 데이터 변경이 감지되면,
즉 modCount의 변경이 감지되면 예외를 발생 시켜서 
데이터 무결성을 방지하는 역할이라고 이해하고 있다.

3. remove 

이번에는 제거 로직을 알아보자.

LinkedList<String> linkedList = new LinkedList<>();  
linkedList.add("first");
linkedList.add("second");
linkedList.add("third");

 remove를 호출하면

linkedList.remove("firstValue");

LinkedList는 null도 데이터로 취급하기에 null인 경우와 아닌 경우를 나누어서 제거한다. 

public boolean remove(Object o) {  
    if (o == null) {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (x.item == null) {  
                unlink(x);  
                return true;  
            }  
        }  
    } else {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (o.equals(x.item)) {  
                unlink(x);  
                return true;  
            }  
        }  
    }  
    return false;  
}

E unlink(Node<E> x) {  
    // assert x != null;  
    final E element = x.item;  //1
    final Node<E> next = x.next;  
    final Node<E> prev = x.prev;  

    if (prev == null) {  //2
        first = next;  
    } else {  
        prev.next = next;  
        x.prev = null;  
    }  

    if (next == null) {  //3
    	last = prev;  
    } else {  
        next.prev = prev;  
        x.next = null;  
    }  

    x.item = null;  
    size--;  
    modCount++;  
    return element;  
}

remove에서 값(item)이 일치하는 Node를 찾아 unlink에게 전달한다.
제시한 예시의 경우, prev = null, next = xxx222가 할당된다.

final E element = x.item;  //1
final Node<E> next = x.next;  //xxx222
final Node<E> prev = x.prev;  //null

만약 
prev=null 즉, 현재 노드가 제일 앞의 노드라면 
linkedList의 first는 현재 노드의 next(다음 노드)가 된다.

if (prev == null) {  //2
	first = next;  
} else {  
    prev.next = next;  
    x.prev = null;  
}

근데 이해가 가지 않는 부분이 존재했다.
first = next 이전에, next.prev를 null처리 하지 않는 이유는 뭘까?

이해가 잘 가지 않아 스텍오버플로우에 질문했다.

[data structures - Why is next.prev not explicitly set to null in Java LinkedList's unlink method when removing the first node? - Stack Overflow](https://stackoverflow.com/questions/77703595/why-is-next-prev-not-explicitly-set-to-null-in-java-linkedlists-unlink-method-w?noredirect=1#comment136988909_77703595)

이유는 매우 간단했다.
next가 null아닐때의 로직을 보면, 
next.prev = prev로 설정하는것을 볼 수 있다.
즉, x의 prev = null 이므로, next.prev= null이 되고,
x.next = null로 설정하므로 GC가 동작하게 된다.

if (next == null) {  //3
	last = prev;  
} else {  
    next.prev = prev;  
    x.next = null;  
}

이렇게 보면 next.prev = null 처리가 진행된다.

이렇게 되면 GC가 동작하여 노드가 성공적으로 제거된다.

추가적으로, remove는 위에서 말했듯이, null인지 아닌지 여부를 먼저 판단하고 진행한다. 

그래서 이런식으로 null에 대한 참조변수가 다르거나, null을 직접 넣어도

동일하게 순회시 발견되는 첫번째 null만 제거한다.

String nullValue = null;
String nullValue2 = null;
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("firstValue");
linkedList.add(nullValue);
linkedList.add(nullValue);
System.out.println("linkedList = " + linkedList);

linkedList.remove("firstValue");
System.out.println("linkedList = " + linkedList);

linkedList.remove(nullValue2);
System.out.println("linkedList = " + linkedList);

linkedList.remove(null);
System.out.println("linkedList = " + linkedList);
System.out.println("linkedList.size() = " + linkedList.size());

linkedList = [firstValue, null, null]
linkedList = [null, null]
linkedList = [null]
linkedList = []
linkedList.size() = 0