클래스로더

Loading: 로드

클래스 파일을 로드하여 JVM 의 Method area 에 올림

Linking: 링크

• Verification: 검증
  읽어들인 클래스가 명세에 맞게 잘 구성되어있는지 검사 (제일 오래 걸리는 단계)
• Preparation: 준비
  클래스가 필요로 하는 메모리를 할당 & 클래스의 필드 메서드 인터페이스를 나타내는 구조를 준비
• Resolution: 해결
  심볼릭 메모리 참조를 실제 메모리 참조로 변경함
  클래스 상수 풀 내 모든 심볼릭 레퍼런스를 다이렉트 레퍼런스로 변경

Initialization: 초기화

클래스 변수를 해당하는 초기 값으로 초기화 함

이 초기화 단계에서 static block 이 실행 될 수 있음.

클래스로더 특징

• 계층 구조
  JVM 은 클래스 로더를 계층 구조로 관리함.
  부모 클래스 로더로 부터 클래스를 로드 할 수 있으며 이를 통해 클래스 간의 종속성과 공유 리소스의 관리가 가능해짐.
• Dynamic Loading: 동적 로딩
• Dynamic Linking: 동적 링크

해시테이블

• 효율적인 데이터 검색을 위해 만들어짐
• key / value 매핑을 이용하여
• 해시 함수를 사용하여 키를 해시코드로 변환, 배열의 인덱스에 매핑하여 값을 저장함

장점

• 검색 및 조회: 언제나 O(1) 의 탐색/읽기 속도를 가진다.
• 고유한 값 유지: 중복된 키 불가능

특징

• 로드 팩터(Load factor): 기본 값 0.75(해시 테이블이 75%이상 찼을 때 크기 조정) 이며 생성자를 통해 생성 할 때 변경 가능.
• 버킷 (buckets): 해시테이블 내부에서 실제 데이터를 저장하기 위한 배열
• 해시코드
• 해시 함수
• 해시 충돌: 서로 다른 키가 같은 해시 코드를 생성하는 문제
  해결 방법
  * Chaining: 체이닝
  * Open addressing: 개방 주소법
     * 리니어 프로빈
     * 쿼드라틱 프로빈
     * 더블 해싱

의문점

해시 함수는 일반적으로 큰 범위의 숫자를 리턴함. 해시 테이블의 내부가 배열로 되어있다면 가용하는 공간보다 큰 공간을 사용해야 할텐데 왜 O(1) 시간복잡도를 가짐?

answer:
해시 함수를 이용하여 인덱스 접근. 이 때 시간 복잡도는 O(1) 이 됨
해시 함수는 모듈로(Modulo: %) 연산을 통해 기본적으로 큰 범위의 해시값을 특정 인덱스로 접근 할 수 있도록 함. 때문에 일반적인 hashcode() 메서드에 비해 해시 충돌이 자주 일어날 수 있음.

해시 테이블과 해시맵 차이

공통 개념

키의 해싱(Hashing) 결과를 활용하여 값을 저장하고 조회하고, 키-값 쌍의 개수에 따라 동적으로 증가하는 연관 배열(Associate array) 이다.

• Associate array: 연관 배열?
  * 자료구조 중 하나
  * 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관된 값을 얻을 수 있다 (이 때 값에 컬렉션 프레임워크가 들어와도 괜찮음.)
• Worst case (키워드)
  해시 충돌이 많이 발생하는 상황

해시 맵

• 해시 충돌 해결 방식: Separate channing
• 해시 충돌이 너무 빈번히 발생 할 경우 내부 자료구조를 변경 (LinkedList → Tree[RedBlack])
• 내부 버킷의 자료구조를 변경하는 기준: 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 내부 자료구조를 변경
• 중복 키의 버킷 데이터가 6개로 줄어들면 다시 LinkedList로 변경

둘의 차이

Open addressing 은 데이터를 삭제 할 때 효율적이기 어려움

Open addresing 의 Liner probing, Quardratic probing, Double hashing 등 에서는 Worst case 발생 시 인덱스 위치를 특정 알고리즘을 통해 조작한다. 조작된 index 를 찾기 위해서는 해당 인덱스가 충돌이 발생하여 이동 된 것인지 아닌 것인지 확인 할 수 있어야 하는데, 이러한 구현 방식에서는 효율에 한계가 있기 때문에 삭제할 때 효율적이지 못할 수 있다.