HashTable | HashMap | ConcurrentHashMap 개념 정리

Hash

• 임의의 길이의 값을 Hash Function을 이용해 고정된 길이의 값으로 변환하는 작업
• Hash 함수
  • Division Method : 입력값을 테이블의 크기로 나누어 계산 (주소 = 입력 값 % 테이블의 크기)
  • Digit Folding : key : 문자열을 ASCII 코드로 바꾸고 각각의 값을 합한 데이터를 테이블 내의 주소로 사용
  • Multiplication Method : h(k) = (kAmod1)xM  (숫자로 된 key값 K + 0<A<1 + 보통 2의 제곱수인 M)
  • Universal Hashing : 다수의 해시 함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시 값을 만드는 기법 
• 서로 다른 두 개의 키가 같은 index로 해싱되어 충돌이 발생할 수 있다
• 적재율 : 키의 개수/해시 테이블이 크기 = 해시 테이블 내 공간 대비 키 값들이 얼마나 있는지 = 충돌할 여지가 얼마나 있는지 
• Hash 충돌 해결 방안
  • 분리 연결법 (Separate Chaining)
    • 종류
      • 연결 리스트(Linked List) 사용 : 충돌이 발생했을 때 동일한 버킷에 연결 Linked List 형태로 데이터를 저장 
      • Tree(Red-Black Tree) 사용 : 충돌이 발생했을 때 동일한 버킷에 Tree 형태로 데이터를 저장 
    • Tree는 기본적으로 메모리 사용량이 많기 때문에, 데이터의 개수가 적다면 Linked List를 사용하는 것이 좋다
    • 해시 테이블을 확장할 필요없이 간단히 구현 가능하고 쉽게 삭제할 수 있다 
    • 데이터 수가 많아지면 1개의 버킷에 chaining 되는 데이터가 많아져 캐시의 효율성이 감소한다 
  • 개방 주소법 (Open Addressing)
    • 충돌이 발생했을 때 비어있는 해시 테이블의 공간을 활용한다
    • 종류
      • 선형 탐사 (Linear Probing) : 현재 버킷 index로부터 순차적으로 검색해 비어 있는 버킷에 데이터를 저장, 데이터가 밀집되는 클러스터링 문제가 발생해 탐색/삭제가 느려진다 
      • 제곱 탐사 (Quadratic Probing) : 해시의 저장 순서 폭을 제곱으로 저장 ex) +1^2 이동, +2^2 이동, +3^2 이동, 선형 탐사에 비해 폭넓게 탐사하기 때문에 탐색/삭제에 효율적일 수 있지만, 초기 해시값이 같은 경우에 마찬가지로 클러스터링 문제가 발생한다
      • Double Hashing Probing : 2번 해싱하게 되는데, 첫번째 해시 함수는 해시값을 찾기 위해 사용하고 두 번째 해시 함수는 충돌이 발생했을 때 탐사 폭을 계산하기 위해 사용된다 
    • Open Addressing은 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아지기 때문에 일반적으로 Separate Chaining보다 느리다. 
    • 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다 
    • 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되기 때문에 재정리 작업이 필요하다 

Hashtable

• 테이블 형태에 key-value를 매핑해서 데이터를 저장하고 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array (연관 배열: 키를 통해 값을 얻을 수 있다) 
• 해시 함수를 적용한 key 값을 배열의 index로 사용하고 이 index를 활용해 value를 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다 
• 배열(버킷)을 사용해 데이터를 저장하기 때문에 빠르게 데이터를 검색할 수 있다
• 모든 데이터 변경 함수가 synchronized로 선언 되어 있어 멀티스레드에 안전하다
• key, value에 null을 허용하지 않는다 
• 조회할 때 평균 O(1)의 시간 복잡도가 걸리지만, 데이터 충돌로 인해 Chaining이 되었을 경우 연결된 리스트까지 검색해야 하므로 최악의 경우 O(n) 시간 복잡도가 걸린다

HashMap

• key에 대한 해시 값(=hashCode)을 사용해 value를 저장하고 조회하며, key-value 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array
• Java Collections Framework에 속한 구현체 클래스
• Map 인터페이스를 구현했기 때문에 Map의 속성을 모두 가지고 있다
• key 중복을 허용하지 않는다. 만약 중복 된다먼 이전 value는 새로운 value로 덮어 씌워진다
• 순서를 보장하지 않는다
• index값의 분포를 가급적 균등하게 하기 위해 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 Hashtable보다 해시 충돌이 덜 발생할 수 있다 
• 많은 양의 데이터를 검색할 때 뛰어난 성능을 보인다 
• 기본적으로 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는데 결과 자료형은 int(32 bit)이다. 따라서 완전한 해시 함수를 만들 수 없다 
• key, value에 null을 허용한다
• 삽입, 검색의 시간 복잡도는 O(1)이다
• 버킷의 75%가 찼다면 용량을 2배로 늘린 새로운 버킷에 기존의 버킷들을 옮기는 과정이 진행된다 
• 동기화 보장이 필요하지 않을 때 사용한다 

ConcurrentHashMap 

• HashMap은 멀티스레드 환경에서 동시에 수정을 시도하는 경우 예상치 못한 결과가 발생할 수 있다. 이러한 멀티 스레드 환경에서 안전하게 HashMap을 조작할 수 있도록 java에서 제공하는 것이 cuncurrent 패키지의 자료 구조인 ConcurrentHashMap이다. 
• 멀티스레드 환경에서 안전하면서, 스레드가 병렬적으로 작업을 처리할 수 있다 
• 데이터 추가 방식
  • 빈 버킷에 노드를 삽입하는 경우, lock을 사용하지 않고 Compare and Swap을 이용해 삽입한다. Compare and Swap는 변수의 값을 변경하기 전에 기존 값이 내가 예상하던 값인지 비교하여 같은 경우에만 할당하는데, 여러 스레드에서 쓰기 작업을 할 수 있기 때문에 CAS 알고리즘을 사용해 원자성을 보장한다. 
  • 이미 노드가 존재하는 경우, synchronized(노드가 존재하는 버킷 객체)를 이용해 하나의 스레드만 접근할 수 있도록 제어한다. 서로 다른 스레드가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기게 된다. 동일한 key를 가진 노드가 있으면 새로 바꾸고, 해시 충돌인 경우 Separate Chaining에 추가하거나 ThreeNode에 추가하고, REEFITY_THRESHOLD값에 따라 LinkedList를 Tree로 바꾼다.

• key, value에 null을 허용하지 않는다 
• map의 일부에만 lock을 걸기 때문에 전체에 lock을 거는 HashTable과 synchorined map보다 성능이 좋다
• 검색 작업에는 lock이 동작하지 않으며 갱신 작업과 동시에 수행될 수 있다 
• 생성자에서 초기 해시 테이블 사이즈를 결정하고, 첫번째 노드가 삽입될 때 생성된다