‘자료구조’ 태그의 글
8편 RSS로 구독
8편
Jump Consistent Hash: 표 없이 샤드 번호를 정하는 일관된 해시와 그 전제 조건
샤드를 10개에서 12개로 늘릴 때 hash mod n은 키의 5/6을 옮기지만 꼭 옮겨야 하는 건 1/6입니다. Lamping·Veach 논문의 Jump Consistent Hash 코드, 동작 원리, 버킷을 늘리고 줄일 때 생기는 일을 정리했습니다.
유니온 파인드의 경로 압축과 크기 가중치: α(n)은 어떤 구현에 붙는 숫자인가
유니온 파인드에서 크기 가중치, 경로 압축, 경로 절반이 parent 배열을 각각 어떻게 바꾸는지 작은 예로 따라가고, 최악 Θ(log n)과 연산 열 전체의 O(m α(n))이 어느 구현에 해당하는지 Princeton algs4 자료를 기준으로 정리했습니다.
Linux 커널 rbtree: 비교 함수를 저장하지 않고 노드를 구조체에 넣어 쓰는 레드-블랙 트리
Linux의 레드-블랙 트리는 비교 함수를 저장하지 않습니다. 노드를 구조체에 넣는 방식, 직접 쓰는 검색·삽입 루프와 호출마다 비교 함수를 받는 도우미, 색 비트, cached·augmented 트리, 락 없는 조회의 한계를 v6.17 소스로 정리했습니다.
스킵 리스트: 동전 던지기로 정한 레벨이 O(log n) 검색을 만드는 방식
정렬된 연결 리스트에 무작위 레벨의 포인터를 더하면 검색이 왜 기대 O(log n)이 될까요? Pugh의 보고서에 실린 알고리즘, '기대' 시간의 범위, Java ConcurrentSkipListMap 문서가 약속하는 것을 정리했습니다.
해시 테이블은 언제 O(1)이 아닐까: 충돌, O(n²) 삽입, 해시 플러딩
dict와 HashMap의 O(1)은 기댓값입니다. 키의 해시가 모두 같으면 n개 삽입에 비교가 최소 n(n−1)/2번 필요한 이유, Python 해시 무작위화와 PYTHONHASHSEED, Rust SipHash, Java의 Comparable 대응을 정리했습니다.
블룸 필터가 '없음'만 확신하는 이유
블룸 필터가 '확실히 없음'과 '있을 수도 있음'으로만 답하는 이유, 거짓 음성이 없다는 보장이 성립하는 조건, 거짓 양성 확률 식, 비트를 지우면 보장이 깨지는 이유를 정리합니다.
힙은 정렬된 배열이 아니다: 우선순위 큐의 배열 순서와 인덱스 공식
heapq나 PriorityQueue를 출력하면 왜 정렬되어 있지 않을까요? 힙이 지키는 조건과 0부터 세는 부모·자식 인덱스 공식, 정렬된 리스트와의 비용 차이, 같은 우선순위 처리를 공식 문서로 정리했습니다.
배열 끝에 추가하는 append는 왜 O(1)일까: 동적 배열과 상각 시간
가끔 배열 전체를 복사하는데도 append가 O(1)인 이유를 용량과 상각 분석으로 설명하고, Java·C++·Rust·Go 문서가 보장하는 범위와 구현이 정하는 증가율, 용량을 미리 잡는 방법을 정리했습니다.
찾는 글이 없습니다. 다른 낱말로 검색해 보세요.