HAMA 블로그

다음 내용은 정익사의 화일구조의 마지막에 나온 소스 (부록3. 디스크 기반 해시) 를 기반으로 설명된다. (그림 - 1) 그림에서 주요 포인트는 : 디스크 , HashPage , HashRecord 이다. 1. 초기화 - 디스크에 저장하기위해 파일을 만든다.(creat 함수, fopen 함수이용) - 페이지 자체의 크기를 4096byte 로 설정한다. (실제 디스크의 블럭크기와 일치시키면 좋을듯) - 페이지의 갯수를 3000개로 설정한다. (자신이 만들 어플리케이션의 용도에 맞추면 좋고~) - HashPage 객체하나로 1->2999 번 (1개는 헤더용) 값을 바꾸어서 , 그 내용을 디스크상에 그대로 쓴다. - 아직 HashPage 안에 recArray 는 아직 아무 값이 없겠지요. - 결국 HashPa..

C++ 의 map 은 레드블랙트리로 구현되있으며, java 의 treeMap 또한 레드블랙트리로 구현되어있습니다.C++ 진영에서 해쉬테이블이 표준으로 구현되지 않았었기때문에, 많은 경우 해쉬를 굳이 외부라이브러리등을 통하거나,만들어서 사용하지 않았는데, 그 의미는 많은 경우에 있어서 레드블랙트리로 맵을 사용하는게 충분하다는 방증(circumstantial evidence) 이겠지요. Java 진영에서는 많은 경우 HashMap 을 사용하더군요. 이런걸 보면 , 두개 알고리즘의 각각의 특징에 따라서 맵을 사용한다기보다는 , 대개의 프로그래머들은 그냥 아무 생각없이 많이 쓰여 지는것을 쓴다고 볼수있습니다. 이 얘기는 프로그래머들이 게을러서라고 생각치 않습니다. 많은 경우 두개의 알고리즘의 성능차이는 80대2..

레드블랙트리는 이진트리이자, 균형을 갖춘트리입니다. C++ 의 map 이 레드블랙트리 기반이며, jemalloc 에서도 사용됩니다.레드블랙트리의 정의는 다음과 같습니다.1. 모든 노드는 red나 black의 색깔을 갖는다. 2. Root 노드는 항상 black이다. 3. 모든 leaf 노드는 센티넬 노드(sentinel node)로서 black이다. (일단 항상 2개의 다른 값으로 채워질 수 있는 NIL=NULL 자식을 가진다.) 4. Red 노드의 자식은 모두 black이다. (Black의 자식은 black/red 모두 가능) 5. 루트(root)에서 leaf로의 경로를 생각할 때, 모든 경로에 대해서 black의 숫자는 같다. (이것을 black height라고 한다.) 삽입삽입시에 이진트리와 마찬가..

public class KthLargest { public static void main(String[] args) { int[] x = new int[] { 3, 6, 92, 34, 1, 35, 62, 13, 12, 24, 53 }; System.out.println(getKthLargest(x, 3)); } private static int getKthLargest(int[] x, int k) { int low = 0; int high = x.length - 1; while (true) { int pivot = (low + high) / 2; int newPiv = partition(x, low, high, pivot); if (newPiv == k) { return x[newPiv]; } else ..