기록들 https://github.com/ndgndg91

지난 글에서는 ArrayList 를 까보면서 native 메서드에 대해 잠시 다루어보았다. 이번 글에서는 직접 HashMap 을 구현해보도록 하겠다. JDK 를 까보면서 그리고 여라 다른 블로깅을 참고하면서 내 방식으로 구현해 보았다. https://medium.com/@mr.anmolsehgal/java-hashmap-internal-implementation-21597e1efec3 https://www.devglan.com/java8/hashmap-custom-implementation-java https://d2.naver.com/helloworld/831311 우선, 핵심을 먼저 정리하고 작성해보겠다. HashMap 은 Key Value 저장소이다. 분할상환방식에 의해서 get() put() 메서드는 상수 시간의 시간복잡도 O(1) 을 가진다. HashMap 은 내부적으로 key, value 를 지닌 Node 의 배열을 가진다. Node 의 개념과 일치하는 class 는 Entry<K, V> class 이다. HashMap 은 get(), put() 메서드 호출 시  객체의 hashcode 를 통해 index 를 계산하고  Node 배열의 Node 를 배치시킨다.  그렇다면 같은 index 를 가지는 객체들은 어떻게 관리를 할까? 바로 LinkedList 를 배열의 index 마다 가지며, 2차원 형태의 테이블을 이루게 된다. 아래는 JDK 11 버전의 HashMap 을 직접 까보았다. 아래와 같이 Node 는 Map.Entry<K, V> interface 를 구현하고 있다. 그리고 필드로는 hash, key, value, 그리고 LinkedList 이기에 next 를 가진다. 여기까지가 HashMap 가장 기본적인 원리이다. 하지만 가장 큰 문제가 있다. 바로 다른 객체가 동일한 hashcode 를 가질 때 이다. 예를 들어, 아래와 같이 Developer class 를 작성했다. equals() 와 h...

요즘, 그동안 기본기를 너무 챙기지 않고 프레임 워크와 아키텍쳐에 빠졌나 싶어서, 자료구조와 알고리즘을 다시 보고 있다가, 실질적으로 jdk 의 List 구현체인 ArrayList 를 까서 보았다. 그러다가 흥미로운 것을 보게되었고, 실질적으로 jdk 를 까보는 것도 재미가 있어서 블로깅을 해본다. 다들 알겠지만, ArrayList 는 말 그대로 내부적으로 data 를 저장하는 배열(array) 을 가지고 있다. 자료구조와 알고리즘 공부를 하게되면, 기본중의 기본인 ArrayList 와 LinkedList 의 비교를 하게 된다. ArrayList 의 add() 메서드는 끝에 집어 넣을 때 O(1) 상수 시간이고, 처음에 집어 넣을 때와 일반적인 상황에서 O(n) 으로 선형 시간이 된다.  remove() 메서드도 배열의   제일 마지막을 지울 경우 O(1) 상수 시간이고, 처음을 지울 때와 일반적인 상황에서는 O(n) 으로 선형 시간이 된다. 배열을 내부적으로 가지고 있기 때문에, 당연하게 시작 혹은 중간에 data 를 삽입하게 되면 삽입 지점 index 에 있던 원래 있던 data 부터 배열의 끝까지의 모든 데이터들을 다음 index 공간( 오른쪽 )으로 Shift 연산을 해야 한다. 즉 해당 index 지점부터 배열의 끝까지 순회 하면서 오른쪽으로 한 칸 씩 밀어주게 된다. 반대로 remove 삭제의 경우에도, 시작 혹은 중간에 data 를 지우려고 하면 해당 지점 index 한칸 뒤에 있는 지점부터 배열의 끝까지의 data 들을 한칸 씩 모두 왼쪽으로 Shift 연산을 해야 한다. 즉 해당 index 다음 지점부터 배열의 끝까지 순회 하면서 왼쪽으로 한 칸 씩 밀어주게 된다. 이미지 제작의 귀찮음으로 아래 사이트의 이미지를 사용했다. https://cloudstudying.kr/lectures/138 그래서 Shift 연산이 필요하기 때문에 선형 시간 O(n) 의 시간 복잡도를 가진다. 자, 그렇다면 이제 JDK 를 까보자....

문제풀기 :  https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays&h_r=next-challenge&h_v=zen It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their   initial   position in the queue. Initial positions increment by     from     at the front of the line to     at the back. Any person in the queue can bribe the person   directly in front   of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe   at most two others . For example, if     and     bribes   , the queue will look like this:   . Fascinated by this chaotic queue, you decide you must know the minimum number of bribes th...