무민은귀여워

해시테이블 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킨다. 간단한 해시테이블을 구현하기 위해선, 연결리스트와 해시 코드 함수만 있으면 된다. 최악의 경우 수행 시간은 O(N)이 된다. 충돌을 최소화 한 경우 O(1)이다. 또 다른 구현법으로는 균형 이진 탐색 트리를 사용하는 방법이 있다. 이 경우 탐색 시간은 O(logN)이 된다. ArrayList와 가변 크기 배열 ArrayList 는 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지한다. 배열이 가득차면 통상적으로 배열을 크기를 두배로 늘리고, 이 시간은 O(n)이지만, 자주 발생하는 일이 아니라서 상환 입력 시간으로 계산했을 때 여전히 O(1)이 된다. StringBuilder 1 2 3 4 5 ..