Kaden Sungbin Cho Kaden Sungbin Cho

해시 알고리즘은 String 데이터를 고정된 길이의 숫자형 String 결과물로 변환해주는 함수입니다. 이 결과물 String은 보통 원본 데이터보다 길이가 훨씬 짧은데요. 이렇게 해시 함수가 리턴한 값은 해시 값(hash values), 해시 코드, digests, hashes 등의 이름으로 불립니다. 해시 함수는 대부분의 언어에 기초 자료형으로 쓰이는 해시 테이블에 중심적인 역할을 합니다. 그 외에도 checksums, check digits, 핑거프린팅, lossy compression, randomization 함수, 에러 체킹 코드, ciphers 등에 사용됩니다. 이 글에서는 아래와 같은 사항들을 알아보겠습니다: 해시 함수의 기본적인 사항들 해시 함수가 쓰이는 곳 해시 함수의 일반적인 특징들 ..

레드-블랙 트리는 각 노드에 "color"라는 추가적인 비트 정보가 담긴 self-balancing 이진 탐색 트리입니다. 노드 삽입, 삭제 시에도 균형을 유지하기에 빠른 접근을 가능하게 해주는 자료구조인데요 [2]. 트리가 변경될 때마다, 새로운 트리는 재-나열(re-arrange)되고 다시 색깔이 설정되어(re-painted) 색깔 특성을 회복하고 이것은 unbalanced 트리가 worst-case가 되는 것을 막습니다. 재-균형(rebalance)은 완벽하진 않지만 O(log n)의 검색 시간을 보장합니다. 노드 삽입과 삭제 시에도 재-나열과 repaint를 포함해 O(log n) 안에 수행됩니다. 또한, 디스크 소비와 관련해서 "color"라는 추가적인 비트 정보는 노드 당 1비트를 소모하기에 ..