y-log

자바는 OS에 독립적인 특징을 가지고 있다.
JVM이 OS와 프로그램의 사이에서 기계어로 행석앻주는 역할을 하기 때문이다.

JVM JAVA Virtual Machine

컴파일된 바이트 코드를 기계가 이해할 수 있는 기계어로 변환

스택기반의 가상 머신 

메모리 관리와 GC를 수행

자바 코드의 실행 과정

1. 개발자가 자바코드를 작성한다. 

2. ( .java ) 인 파일을 자바 컴파일러를 통해 자바 바이트 코드로 컴파일한다.

3. 컴파일 된 바이트 코드를 JVM의 Class Loader에 전달한다. 

4. Class Loader는 동적 로딩을 통해 필요 클래스들을 로딩 및 링크하여 Runtime Data Area에 올린다. (JVM의 메모리)

5. 실행 엔진은 JVM메모리에 올라온 바이트 코드들을 명령어 단위로 하나씩 가져와서 실행한다.

JVM
Class Loader + Runtime Data Areas + Execution Engine

Class Loader 특징

1. 계층 구조 

클래스 로더는 여러 클래스 로더끼리 부모-자식 관계를 이루어 계층적인 구조로 되어 있다.

• 부트스트랩 클래스 로더 Bootstrap Class Loader
  • 최상위 클래스로더, 유일하게 JAVA가 아닌 네이티브 코드로 구현
  • JVM이 실행될 때 같이 메모리에 올라감
  • Object 클래스를 비롯하여 JAVA API들을 로드함

• 익스텐션 클래스 로더 Extension Class Loader
  • 기본 JAVA API를 제외한 확장 클래스들을 로드함 - 다양한 보안 확장 기능 로드

• 시스템 클래스 로더 System Class Loader
  • (부트 스트랩과 익스텐션 클래스로더가 JVM 자체의 구성 요소들을 로드한다) 시스템 클래스 로더는 어플리케이션의 클래스들을 로드함
  • 사용자가 지정한 $CLASSPATH 내의 클래스들을 로드함

• 사용자 정의 클래스 로더 User-Defined Class Loader
  • 어플리케이션 사용자가 직접 코드 상에서 생성하여 사용하는 클래스 로더
  • WAS와 같은 프레임워크는 서로 독립적으로 동작하게 하기 위해서 이를 위해 사용자 정의 클래스 로더들을 사용하여 클래스 로더의 위임 모델을 통해 어플리케이션의 독립성을 보장함

2. 위임모델 

처음 바이트 코드를 넘겨받은 클래스로더.

필요한 클래스를 로드할 때 혹은 실행 엔진에서 명령어 단위로 바이트 코드를 실행하다가 처음으로 참조하는 클래스에 대해 클래스 로더에게 로드를 요청할 때.

로드를 요청받은 클래스 로더는 다음 순서대로 요청받은 클래스가 있는지 확인함

1. 클래스 로더 캐시
2. 상위 클래스 로더
3. 자기 자신

이전에 로드된 클래스인지 클래스 로더 캐시를 확인한다.

없다면 상위 클래스 로더를 하나씩 거슬러 올라가며 확인하는데, 이 때 올라가는 도중에 클래스를 발견하더라도 부트 스트랩 클래스 로더(최상단 로더)까지 확인을 해서 부트 스트랩 클래스 로더에도 해당 클래스가 존재한다면 그 클래스를 로드하게 된다.

3. 가시성 제한

클래스 로더가 클래스 로드를 요청받았을 때 위임 모델에 의해서 클래스 로더 캐시를 확인하고 없으면 상위 클래스 로더를 확인한다. 이때 하위 클래스는 확인이 불가능한 특성이 바로 가시성 제한이다.

4. 언로드 불가

클래스를 로드하는 것은 가능하지만 그 반대로 unload하는 것은 불가능하다.

5. 이름 공간

네임 스페이스는 각 클래스 로더들이 가지고 있는 공간으로 로드된 클래스를 보관하는 공간

위임 모델을 통해서 상위 클래스 로더들을 확인해야할 때 확인하는 공간이 바로 이름 공간

네임 스페이스에 보관되는 기준은 FQCN Fully Qualified Class Name 으로 패키지 명까지 포함되어있는 식별자를 뜻한다.

각각의 클래스 로더가 각자 네임 스페이스를 가지고 있기 때문에 FQCN이 같은 클래스라도 네임스페이스가 다르면 다른 클래스로 갖주한다. ( 이 기능을 통해 로드한 클래스 로더를 제거하고 언로드의 효과를 줄 수 있다. )

클래스 로드 과정 

1. 로드 - 클래스 파일을 가져와서 JVM의 메모리에 로드한다.

2. 검증 - 클래스 로드 전 과정 중에서 가장 복잡하고 시간이 많이 걸리는 과정으로, 읽어들인 클래스가 자바 언어 명세 및 JVM 명세에 명시된 대로 구성되어 있는지 검사한다.

3. 준비 - 클래스가 필요로 하는 메모리를 할당한다. 

4. 분석 - 클래스의 상수 풀 내 모든 심볼릭 레퍼런스를 다이렉트 레퍼런스로 변경한다.

5. 초기화 - 클래스 변수들을 적절한 값으로 초기화한다. (static 필드들은 설정된 값으로 초기화 )

런타임 데이터 영역 Runtime Data Area

JVM이 OS 위에서 실행되면서 할당받는 메모리 영역이 바로 런타임 데이터 영역이다.

이 영역은 크게 5가지, 세분화시 6가지로 나눠 볼 수 있다. 

PC 레지스터, JVM 스택, 네이티브 메서드 스택은 스레드마다 하나씩 생성되고 

힙, 메서드 영역은 모든 스레드가 공유해서 사용된다.

• PC 레지스터 
  • Program Counter 레지스터는 현재 수행 중인 명령의 주소를 가지며 스레드가 시작될 때 생성되며, 각 스레드마다 하나씩 존재함
• JVM 스택 
  • 스택 프레임이라는 구조체를 저장하는 스택
  • 예외 발생 시 printStackTrace( ) 메서드로 보여주는 Stack Trace의 각 라인 하나가 스택 프레임을 표현함
  • 스레드가 시작될 때 생성되며 각 스레드마다 하나씩 존재함
• 네이티브 메서드 스택
  • 자바 외의 언어로 작성된 네이티브 코드를 위한 스택
  • JAVA Native Interface를 통해 호출하는 C/C++ 등의 코드를 수행하기 위한 스택으로, 언어에 맞게 스택 생성
• 힙
  • 인스턴스 또는 객체를 저장하는 공간
  • Garbage Collection의 대상
  • JVM 성능 등의 이슈에서 가장 많이 언급되는 공간
  • 힙 구성 방식이나 가비지 컬렉션 방법 등은 JVM 벤더들의 재량
• 메서드 영역 
  • 모든 스레드가 공유하는 영역
  • JVM이 시작될 때 생성된다.
  • JVM이 읽어 들인 각각의 클래스와 인터페이스에 대한 런타임 상수 풀, 필드와 메서드에 대한 정보, static 변수, 메서드의 바이트 코드들을 보관함
• 런타임 상수 풀
  • JVM 동작에서 가장 핵심적인 역할을 수행하는 곳
  • 각 클래스와 인터페이스의 상수 뿐만 아니라, 메서드와 필드에 대한 모든 레퍼런스까지 담고 있는 테이블
  • 어떤 메서드나 필드를 참조할 때 JVM은 런타임 상수 풀을 통해 해당 메서드나 필드의 실제 메모리상 주소를 찾아서 참조한다.

실행 엔진 Execution Engine

실행 엔진은 클래스 로더를 통해 런타임 데이터 영역에 배치된 바이트 코드를 명령어 단위로 읽어서 실행

바이트 코드와 각 명령어는 1바이트 크기의 OpCode와 추가 피연산자로 이뤄져있음

실행 엔진은 하나의 OpCode를 가져와서 피연산자와 작업을 수행한 다음 OpCode를 수행하는 식으로 동작한다.

이 수행 과정에서 실행 엔진은 바이트 코드를 기계가 실행할 수 있는 형태로 변경한는데 두가지 방법을 사용한다.

• 인터프리터 
  • 바이트 코드 명령어를 하나씩 읽어서 해석하고 실행한다. 하나하나의 해석은 빠르지만 전체적인 실행 속도는 느리다는 단점을 가진다. 
  • JVM 안에서 바이트 코드는 기본적으로 인터프리터 방식으로 동작한다.
• JIT 컴파일러 Just-In-Time
  • 인터프리터의 단점을 보완하기 위해 도입된 방식
  • 바이트 코드 전체를 컴파일하여 네이티브 코드로 변경하고, 이후에는 해당 메서드를 더이상 인터프리팅 하지 않고 네이티브 코드로 직접 실행하는 방식
  • 전체적인 실행 속도는 인터프리팅방식보다 빠르다 ( 네이티브 코드는 캐시에 보관하기 때문에 한 번 컴파일된 코드는 캐시에서 바로 꺼내어 실행해 빠르게 수행된다 )
  • 하지만 JIT 컴파일러가 컴파일하는 과정은 바이트 코드를 하나씩 인터프리팅 하는 것보다 훨씬 오래 걸리기 때문에 JVM은 해당 메서드가 얼마나 자주 호출되고 실행되는 지를 체크하고, 일정 기준을 넘었을 때만 JIT 컴파일러를 통해 컴파일 하여 네이티브 코드를 생성한다.

참조

• https://steady-snail.tistory.com/67   
• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Language/%5Bjava%5D%20%EC%9E%90%EB%B0%94%20%EC%BB%B4%ED%8C%8C%EC%9D%BC%20%EA%B3%BC%EC%A0%95.md

자바 프로그래밍 = 객체 지향 프로그래밍

OOP
Object Oriented Programming
객체 지향 프로그래밍

객체란 말 그대로 대상을 나타내는 단어

예를 들어, 사람 개인 한 명 한 명을 모두 객체라 할 수 있고, 책 한 권 한 권을 객체라 할 수 있다.

클래스

사람들은 일반적으로 같은 속성들을 갖고 있는데, 여기서 속성이란 눈, 코, 입, 손, 발, 등의 신체들을 의미한다.

사람같은 객체들이 공통적으로 갖는 속성들을 모아서 정의내린 것을 클래스라고 한다.

객체 = 붕어빵

클래스 = 붕어빵 틀

oop하면 자동으로 4가지 속성이 떠올라야 한다.

OOP 속성

1. 캡슐화 Encapsulation

캡슐화란 하나의 객체에 대해 그 객체가 특정한 목적을 위해 필요한 변수나 메소드를 하나로 묶는 것을 의미한다.

따라서 클래스를 우리가 만들 때 훗날 이클래스에서 만들어진 객체가 특정한 목적을 가지고 사용해야할 변수와 그 변수를 가지고 특정한 액션 즉 메서드 또는 함수를 관련성 있게 클래스에 구성해야한다.

예를 들자면, 은행이라는 클래스는 잔고라는 변수가 있고 그 잔고를 조회하거나, 잔고를 수정할 수 있는 메서드등이 있다고 치는 것이다. 

근데 캡슐화를 하는 중요한 목적은 바로 정보의 은닉화이다.  잔고라는 변수가 만약 public 으로 선언되어있다고 치자. 200만원인 나의 잔고가 누군가 접근에 의해 0원이 될수도 있는 것이다. 따라서 잔고라는 변수를 바로 접근할 수 없도록 private로 선언하고 데이터를 보호하는 것이다.

이렇게 보호된 변수는 getter나 setter등의 메서드를 통해서만 간접적으로 접근이 가능하도록 하는 것이 바로 캡슐화의 중요한 목적이다.

2. 추상화 Abstraction

추상적으로 생각해 일단 큰틀의 클래스를 구현하고 거기에 최소 이러한 공통적인 요소나 필수적인 요소는 들어갔으면 하는 바램에서 만든 것이 추상클래스이다.

이 과정에서 공통적인 요소나 특징을 추출하는 과정이 추상화 인것 같다. 

예를 들자면, 벤츠,아우디,소나타,티코,밴틀리 등등 우리가 생각하는 여러종류의 자동차이 있다. 이것을 다 클래스화하고 변수와 메서드 등을 개별적으로 만드는 것은 무모한 짓이다. (거두절미하고 말하면 확장성때문에 추상화할 필요가 있다.)

따라서 방금 나열한 자동차들의 공통적인 요소나 특징을 추출하는 과정인 추상화를 거쳐 요소를 끄집어 내면, 바퀴,배기통,핸들,차문,유리창,등 필수적인 부품이 있고 바퀴는 굴러가야하며, 핸들은 좌우로 돌아가야하고 

차문은 열려야한다는 공통적인 행등 즉 어떤 차든 필수적으로 필요한 메서드가 추출된다. 

3. 다형성 Polymorphism

다형성은 상속을 통해 기능을 확장하거나 변경하는 것을 가능하게 해준다. 이를 통해 코드의 재사용, 코드길이 감소가 되어 유지보수가 용이하도록 도와주는 개념이다.

쉽게 같은 동작이지만 다른결과물을 나올때 이를 다형성이라고 생각하면 된다.

크게 자바프로그래밍 객체지향에서 다형성의 개념을 녹여내는 방법은 두가지인데, 바로

오버라이딩(Overriding) 과 오버로딩(Overloading) 이다.

오버라이딩은 부모클래스에서 상속받은 서브클래스 즉 자식클래스에서 부모클래스,즉 상위클래스에서 만들어진 메서드를 자신의 입맛대로 다시 재창조해서 사용하는 것을 말한다.

오버로딩은 하나의 클래스 안에서 같은이름의 메서드를 사용하지만 각 메서드마다 다른 용도로 사용되며 그 결과물도 다르게 구현할 수 있게 만드는 개념인데 오버로딩이 가능하려면 메서드끼리 이름은 같지만 매개변수의 갯수나 데이터타입이 다르면 오버로딩이 적용되어 메서드 이름이 같아도 
문법 에러가 나지않는다..

4. 상속성, 재사용 Inheritance

상속은 객체지향의 꽃이라고 할 수 있다. 상속이란 기존 상위클래스에 근거하여 새롭게 클래스와 행위를 정의할 수 있게 도와주는 개념이다.

기존클래스에 기능을 가져와 재사용할 수있으면서도 동시에 새롭게 만든 클래스에 새로운 기능을 추가할 수 있게 만들어 준다.

* 자바에선 상속은 단일상속밖에 지원이 안된다.

그러나 다중상속이 필요할 순 있다고 인정하여 대비책으로 인터페이스를 다중상속(구현) 할 수 있게해서 임시적인 다중 상속에 대한 활로는 뚫어줬다. 그렇지만 인터페이스의 존재이유가 다중상속을 지원하기 위함이다 라고 생각하면 안된다.

JVM
Java Virtual Machine
자바 가상 머신

* 가상 머신 : 프로그램을 실행하기 위해 물리적 머신과 유사한 머신을 소프트웨어로 구현한 것

• JVM은 JAVA와 OS 사이에서 중개자 역할을 수행하여 JAVA가 OS에 구애받지 않고 재사용을 가능케 해준다.
• 메모리관리, Garbage collection을 수행한다.
• JVM은 스택기반의 가상머신이므로 스택기반으로 동작한다.

왜 자바 가상머신을 알아야할까?

한정된 메모리를 효율적으로 사용하여 최고의 성능을 내기 위해서이다.
메모리 효율성을 위해 메모리 구조를 알아야 하기 때문.
동일한 기능의 프로그램이라도 메모리 관리에 따라 성능이 좌우된다. 메모리가 관리가 되지 않은 경우 속도 저하 현상이나 튕김 현상등이 일어날 수 있다. 

자바 프로그램 실행과정

1. 프로그램 실행시 JVM은 OS로부터 이 프로그램이 필요로 하는 메모리를 할당받는다. 
                         JVM은 이 메모리를 용도에 따라 여러 영역으로 나누어 관리한다.
2. 자바 컴파일러가 자바 소스코드를 읽어들여 자바 바이트 코드로 변환시킨다. ( .java -> .class )
3. Class Loader를 통해 class 파일들을 JVM으로 로딩한다.
4. 로딩된 class 파일들은 Execution engine을 통해 해석된다.
5. 해석된 바이트 코드는 runtime data areas에 배치되어 실질적인 수행이 이루어진다.
             이러한 실행과정 속에서 JVM은 필요에 따라 Thread Synchronization과 GC 같은 관리작업 수행

JVM 구성

Class Loader

JVM내로 클래스( .class 파일 )를 로드하고 링크를 통해 배치하는 작업을 수행하는 모듈이다. runtime 시에 동적으로 클래스를 로드한다. jar 파일 내 저장된 클래스들을 JVM 위에 탑재하고 사용하지 않는 클래스들은 메모리에서 삭제한다. (컴파일러 역할) 자바는 동적 코드, 컴파일 타임이 아니라 런타임에 참조한다. 즉, 클래스를 처음으로 참조할 때, 해당 클래스를 로드하고 링크한다는 것이다. 그 역할을 수행하는 것이 클래스 로더다.

Execution Engine 

클래스를 실행시키는 역할이다. 클래스로더가 JVM 내의 런타임 데이터 영역에 바이트 코드를 배치시키고, 이것은 실행 엔진에 의해 실행된다. 자바 바이트코드는 기계가 바로 수행할 수 있는 언어보다는 비교적 인간이 보기 편한 형태로 기술된 것이다. 그래서 실행 엔진은 바이트 코드를 실제 JVM 내부에서 기계가 실행할 수 있는 형태로 변경한다. 

이때 두가지 방식을 사용하게 된다.

Interpreter 
실행 엔진은 자바 바이트 코드를 명령어 단위로 읽어서 실행한다.
하지만 이 방식은 인터프리터 언어의 단점을 그대로 갖고 있다. 
한 줄 씩 수행하기 때문에 느리다는 것이다.

JIT ( Just - In - Time )
인터프리터 방식의 단점을 보안하기 위해 도입된 JIT 컴파일러다. 
인터프리터 방식으로 실행하다가 적절한 시점에 바이트 코드 전체를 컴파일하여 네이티브 코드로 변경하고, 이후에는 더이상 인터프리팅 하지 않고 네이티브 코드로 직접 실행하는 방식이다.
네이티브 코드는 캐시에 보관하기 때문에 한 번 컴파일된 코드는 빠르게 수행하게 된다.
물론 JIT컴파일러가 컴파일 하는 과정은 바이트코드를 인터프리팅하는 것보다 훨씬 오래걸리므로, 한번만 실행되는 코드라면 컴파일하지 않고 인터프리팅하는 것이 유리하다.
따라서 JIT컴파일러를 사용하는 JVM들은 내부적으로 해당 메서드가 얼마나 자주 수행되는지 체크하고 일정 정도를 넘을 때에만 컴파일을 수행한다.

Garbage collector

GC를 수행하는 모듈(thread)이 있다.

Runtime Data Area

:프로그램을 수행하기 위해 OS에서 할당받은 메모리 공간

1. PC 레지스터

Thread가 시작될 때 생성된다.

스레드마다 하나씩 존재하고 thread가 어떤 부분을 어떤 명령으로 실행해야할지에 대한 기록을 하는 부분으로 현재 수행 중인 JVM 명령의 주소를 갖는다.

2. JVM 스택 영역

프로그램 실행과정에서 임의로 할당되었다가 메소드를 빠져나가면 바로 소멸되는 특성의 데이터를 저장하기 위한 영역이다. 각종 형태의 변수나 임세 데이터, 스레드나 메소드의 정보를 저장한다.

메소드 호출 시마다 각각의 스택 프레임(그 메소드만을 위한 공간)이 생성된다.

메소드 수행이 끝나면 프레임 별로 삭제를 한다.

메소드 안에서 사용되는 값들(local variable)을 저장한다.

또 호출된 메소드의 매개변수, 지역변수, 리턴 값 및 연산 시 일어나는 값들을 임시로 저장한다.

3. Native method stack

자바 프로그램이 컴파일되어 생성되는 바이트 코드가 아닌, 실제 실행가능한 기계어로 작성된 프로그램을 실행시키는 영역이다. (JAVA가 아닌 다른 언어로 작성된 코드를 위한 공간)

JAVA Native Interface를 통해 바이트 코드로 전환하여 저장하게 된다. 

일반 프로그램처럼 커널이 스택을 잡아 독자적으로 프로그램을 실행시키는 영역이다.

이 부분을 통해 C code를 실행시켜 커널에 접근할 수 있다.

4. Metod Area = class area = static area

클래스 정보를 처음 메모리 공간에 올릴 때 초기화 되는 대상을 저장하기 위한 메모리 공간이다.

올라가게 되는 메소드의 바이트 코드는 프로그램의 흐름을 구성하는 바이트 코드이다. 자바 프로그램은 main 메소드의 호출에서부터 계속된 메소드의 호출로 흐름을 이어가기 때문이다. 

대부분 인스턴스의 생성도 메소드 내에서 명령하고 호출한다. 

사실상 컴파일 된 바이트 코드의  대부분이 메소드 바이트 코드이기 때문에 거의 모든 바이트코드가 올라간다고 봐도 상관 없다. 

이 공간에는 Runtime Constant Pool이라는 별도의 관리영역이 존재하는데, 이는 상수 자료형을 저장하여 참조하고 중복을 막는 역할을 수행한다.

올라가는 정보의 종류

- field information : 멤버 변수의 이름, 데이터 타입, 접근 제어자에 대한 정보
- method information : 메소드의 이름, 리턴 타입, 매개변수, 접근 제어자에 대한 정보
- type information : class인지 interface인지의 여부 저장, type이 속성, 전체 이름, super class의 전체 이름

* method area = 클래스 데이터를 위한 공간   |   heap 영역 = 객체를 위한 공간

  heap과 마찬가지로 GC의 관리 대상에 포함된다.

5. Heap

객체를 저장하는 가상 메모리 공간이다. new 연산자로 생성된 객체와 배열을 저장한다.

물론 class area 영역에 올라온 클래스들만 객체로 생성할 수 있다. 

힙은 세 부분으로 나뉜다.

• New/Young Generation

Eden : 객체들이 최초로 생성되는 공간

Survivor 0/1 : Eden에서 참조되는 객체들이 저장되는 공간

• Old 영역

new area에서 일정 시간 참조되고 있는, 살아남은 객체들이 저장되는 공간인 Eden 영역에 객체가 가득차게되면 첫번째 GC가 발생한다. eden 영역에 있는 값들을 survivor 1 영역에 복사하고 이 영역을 제외한 나머지 영역의 객체를 삭제한다.

* 인스턴스는 소멸 방법과 소멸 시점이 지역 변수와는 다르기에 힙이라는 별도의 영역에 할당 된다. JVM은 매우 합리적으로 인스턴스를 소멸시킨다. ( 더이상 인스턴스의 존재 이유가 없을 때 소멸시킨다 )

• Permanent Generation

생성된 객체들의 정보의 주소값이 저장된 공간이다.

class loader에 의해 로드되는 class, method 등에 대한 meta 정보가 저장되는 영역이고 JVM에 의해 사용된다. 

reflection을 사용하여 동적으로 클래스가 로딩되는 경우에 사용된다.

내부적으로 reflection 기능을 자주 사용하는 spring framework를 이용할 경우 이 영역에 대한 고려가 필요하다.

HashMap과 HashTable

동기화가 필요없다면 해시맵을,
동기화 보장이 필요하다면 해시테이블을!

차이점

동기화 Synchronization

HashMap의 경우 동기화를 지원하지 않는다. 

반면 다중 스레드 환경에서 HashTable은 동기화를 지원하기 때문에 실행 환경에 따라 구분하여 사용하면 된다.

* vector의 상위 호환 개념인 ArrayList의 사용을 권장하듯, 새로운 버전인 HashMap을 주로 사용하고 동기화가 필요하면 ConcurrentHashMap을 사용하는 것이 더 좋은 방법이라고 한다. 구형인 HashTable은 동기화 처리라는 비용때문에 HashMap에 비해 느리다. 

Thread-safe 여부

Hashtable은 Thread-safe하고, HashMap은 Thread-safe하지 않다.

따라서 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다.

Null 값 허용 여부

Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용한다.

Enumeration 여부 

HashMap은 저장된 요소들의 순회를 위해 Fail-Fast Iterator를 반환한다.(ConcurrentHashMap의 경우에는 Fail-Safe Iterator)

Hashtable은 같은 경우 Enumeration을 반환한다.

* Fail-Fast Iterator : 말 그대로 빠른 에러를 발생시켜 버그를 예방할 수 있다.

반면에 Enumeration를 사용한 코드는 중간에 remove를 해도 예외가 발생하지 않는다. 그렇기 때문에 나중에 버그를 발견하지 못할 확률도 존재한다.

보조 해시 사용

HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.

<참고>

https://odol87.tistory.com/3 https://devlog-wjdrbs96.tistory.com/253 https://12216715011126.tistory.com/53

용어 정리

Hash 자료구조란

key와 value를 갖는 자료구조로 효율적인 검색과 저장을 위해 사용된다. 

linked list와 달리 해당 자료가 위치한 버킷의 주소값을 바로 알아내어 찾아갈 수 있다.

시간 복잡도가 O(1)에 수렴하게 된다.

Hash 함수, Hash 알고리즘, Hash 코드

임의의 길이의 데이터를 고정 길이의 데이터로 매핑하는 함수

비둘기집 원리에 의해 해시함수의 결과값이 중복 되어 해시 충돌을 야기할 수 있다.

* 비둘기집 원리 : n+1개의 물건을 n개의 상자에 넣을 때, 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리

데이터의 value값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필요하다.

예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자의 아스키 코드 값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있습니다. 

만약, 
hello 라는 문자열을 정수형 key 값으로 바꾼다면,
h + e + l + l + o -> 104 +101 + 108 + 108 + 111 = 532라는
해시코드로 변환할 수 있다.

여러가지 방법으로 데이터를 해시코드로 바꾸기 위한 과정을 진행하게 되는데, 주어진 문제마다 적절한 해시 함수(해시 알고리즘)을 구현하는 것은 개발자의 역량에 달려있다.

Hash 코드를 사용해서 Hash table에 저장하기

해시코드로 나올 수 있는 숫자의 경우의 수는 아주 많다. 저장할 배열의 크기는 물리적 한계가 있고 수 많은 해시코드들을 대처 할 수 없다.

이런 경우 해시코드를 배열의 크기로 나누고, 그 나머지를 인덱스로 사용하게 되면 0부터 배열의 사이즈-1 만큼의 숫자로 변환하여 사용 할 수 있다.

예를들어 해쉬코드가 532이고 배열의 크기가 10인 경우 나머지가 2가 나오고, 이 나머지 값을 인덱스로 사용한다.

* 각 버킷은 몇 개의 슬롯으로 구성되어 있다.

OverFlow란 

여러개의 키값이 공통된 버킷을 가리키는 경우, 버킷들의 공간은 유한해서 결국 버킷이 꽉 차게 된다.

꽉 차있는 순간 또하나의 키값이 해당 버킷에 맵핑된다면 오버플로우가 발생한다.

충돌 Collision

다른 해시코드임에도 같은 인덱스가 나오는 경우가 발생할 수 있다.

이런 경우 충돌이 발생했다고 하는데 충돌의 해결방식은 여러가지가 있다. 

분리 체인법, 선형 탐사법, 2차 탐사법, 이중 해싱 등이 존재한다.

* 이러한 이유로 자바에서 hashCode( )를 오버라이딩 할 때 equals( )도 오버라이딩 해야한다. 별개의 객체가 우연히 해시코드가 똑같이 나오게 되더라도 equals로 값의 동등성을 한번 더 확인하는 과정을 거치게 되면 충돌을 방지할 수 있다.

충돌 해결하기

1. 분리 체인법 seperate chaning (open hashing)

같은 인덱스를 가지는 데이터가 여러개인 경우, 그 인덱스의 Linked List를 선언하고 각 데이터들을 이 리스트에 저장한다.

이 인덱스의 값을 저장, 검색하는 경우 먼저 인덱스의 접근하고 인덱스에 존재하는 링크드 리스트의 데이터들을 하나씩 조회합니다.

한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해시 함수 (해시 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해봐야 한다. 

* 충돌이 발생하면 주어진 해시테이블 공간외의 새로운 공간을 할당해주기 때문에 open hashing이라고도 불린다.

2. Open Addressing (Closed Hashing)

주어진 해시테이블에서 정해진 규칙에 따라 버킷을 찾아 저장하는 방법이다. open addressing의 버킷 결정 방법에는 몇가지가 있다.

2.1 선형 조사

충돌이 일어난 다음 자리에 저장하는 방법

제 1 군집 현상이 발생한다

* 제 1 군집 현상 : 특정 영역에 데이터가 몰릴 때, linked list의 순차 탐색으로 데이터의 저장공간이 지정되어 성능이 치명적으로 저하된다. ( 이차원 조사로 해결 가능하다)

2.2 이차원 조사

충돌이 발생한 경우 다음 데이터의 자리를 이차함수로 결정한다.

2.3 더블 해싱

2.4 무작위 처리 방법

<참고>

https://siyoon210.tistory.com/85 https://galid1.tistory.com/171