hash
[Kotlin] Set, MutableSet 은 어떻게 원소에 빠르게 접근할 수 있을까? : Set이 평균적 O(1)의 속도로 원소에 접근하는 방법
Set, MutableSet 은 어떻게 원소에 빠르게 접근할 수 있을까? Kotlin의 Set은 원소에 접근하는데 걸리는 시간이 평균적으로 O(1)이고 중복을 체크하는데 걸리는 시간도 O(1)이다. 이 때문에 많은 Set을 사용하면 매우 효율적으로 원소에 접근할 수 있다. 이번 글에서는 그 이유를 알아보고자 한다. Kotlin의 Set, MutableSet에서 사용하는 자료 구조 Kotlin의 Set, MutableSet은 모두 인스턴스를 만들기 위해 LinkedHashSet을 사용한다. Set의 내부 구현 살펴보기 Set의 모든 생성자를 보는데는 너무 시간이 많이 걸리므로 Set을 만드는 대표적인 함수인 setOf 함수만 보도록 하자. Kotlin에서 setOf를 사용해 Set 생성하는 부분을 보면 ..
[Git] Git의 저장 단위인 commit의 동작 원리에 대해 알아보자
Git의 기본 저장 단위 Commit Commit은 Git의 기본 저장 단위이다. 우리는 Commit을 파일들에 대한 스냅샷이라고도 부르며, Commit은 Commit을 찍은 시간의 파일들의 상태에 대해 저장한다. Commit은은 tree, parent, author, commiter,message 5가지 구성요소로 이루어져 있다. tree : tree와 blob를 포인팅하는 구성요소이다. parent : 해당 커밋 직전에 어떤 커밋이 있었는지 포인팅한다. author : 작성자. commiter : 커밋을 만든 사람. message : 커밋을 설명하는 메세지. 예를 들어 commit이 두 개 찍힌 다음과 같은 로그를 가진 Git 폴더가 있다고 해보자 $ git log --oneline 6e3a608 ..
[Git] Git은 어떻게 파일을 저장하고 복구하는가? git의 기본 파일 단위인 blob와 Hashing의 관계에 대해 알아보자
변경사항을 압축해 저장하는 objects 폴더 objects 폴더 내부를 보면 두 글자 이름을 가진 폴더들이 있다. objects 폴더는 git의 모든 변경사항을 압축해서 파일들을 각 폴더 내부에 저장한다. 이 내부에는 commit, tree, blob, annotated tag들이 저장되며, git을 통해 히스토리를 확인할 수 있는 것은 바로 이 폴더 내부에 모든 스냅샷들이 저장되기 때문이다. 저장되는 방식은 hash에 해당하는 압축된 변경사항으로 저장된다. 예를 들어 위 폴더 중 02에는 7f7aa 로 시작하는 파일명인 파일이 있다. 이 파일은 Git의 저장의 기본 단위인 blob로, blob 파일 내부에는 027f7aa 해시값에 대한 변경사항이 압축되어 있다. 깃에서는 blob 파일의 압축을 풀어 ..