HashTable | HashMap | ConcurrentHashMap 개념 정리

HashTable | HashMap | ConcurrentHashMap 개념 정리

데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되기 때문에 재정리 작업이 필요하다

연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다

Open Addressing은 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아지기 때문에 일반적으로 Separate Chaining보다 느리다.

Double Hashing Probing : 2번 해싱하게 되는데, 첫번째 해시 함수는 해시값을 찾기 위해 사용하고 두 번째 해시 함수는 충돌이 발생했을 때 탐사 폭을 계산하기 위해 사용된다

제곱 탐사 (Quadratic Probing) : 해시의 저장 순서 폭을 제곱으로 저장 ex) +1^2 이동, +2^2 이동, +3^2 이동, 선형 탐사에 비해 폭넓게 탐사하기 때문에 탐색/삭제에 효율적일 수 있지만, 초기 해시값이 같은 경우에 마찬가지로 클러스터링 문제가 발생한다

선형 탐사 (Linear Probing) : 현재 버킷 index로부터 순차적으로 검색해 비어 있는 버킷에 데이터를 저장, 데이터가 밀집되는 클러스터링 문제가 발생해 탐색/삭제가 느려진다

충돌이 발생했을 때 비어있는 해시 테이블의 공간을 활용한다

개방 주소법 (Open Addressing)

데이터 수가 많아지면 1개의 버킷에 chaining 되는 데이터가 많아져 캐시의 효율성이 감소한다

해시 테이블을 확장할 필요없이 간단히 구현 가능하고 쉽게 삭제할 수 있다

Tree는 기본적으로 메모리 사용량이 많기 때문에, 데이터의 개수가 적다면 Linked List를 사용하는 것이 좋다

Tree(Red-Black Tree) 사용 : 충돌이 발생했을 때 동일한 버킷에 Tree 형태로 데이터를 저장

연결 리스트(Linked List) 사용 : 충돌이 발생했을 때 동일한 버킷에 연결 Linked List 형태로 데이터를 저장

분리 연결법 (Separate Chaining)

Hash 충돌 해결 방안

적재율 : 키의 개수/해시 테이블이 크기 = 해시 테이블 내 공간 대비 키 값들이 얼마나 있는지 = 충돌할 여지가 얼마나 있는지

서로 다른 두 개의 키가 같은 index로 해싱되어 충돌이 발생할 수 있다

Universal Hashing : 다수의 해시 함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시 값을 만드는 기법

Multiplication Method : h(k) = (kAmod1)xM (숫자로 된 key값 K + 0

Digit Folding : key : 문자열을 ASCII 코드로 바꾸고 각각의 값을 합한 데이터를 테이블 내의 주소로 사용

Division Method : 입력값을 테이블의 크기로 나누어 계산 (주소 = 입력 값 % 테이블의 크기)

임의의 길이의 값을 Hash Function을 이용해 고정된 길이의 값으로 변환하는 작업

조회할 때 평균 O(1)의 시간 복잡도가 걸리지만, 데이터 충돌로 인해 Chaining이 되었을 경우 연결된 리스트까지 검색해야 하므로 최악의 경우 O(n) 시간 복잡도가 걸린다

key, value에 null을 허용하지 않는다

모든 데이터 변경 함수가 synchronized로 선언 되어 있어

모든 데이터 변경 함수가 synchronized로 선언 되어 있어 멀티스레드에 안전하다

배열(버킷)을 사용해 데이터를 저장하기 때문에

배열(버킷)을 사용해 데이터를 저장하기 때문에 빠르게 데이터를 검색할 수 있다

배열(버킷)을 사용해 데이터를 저장하기 때문에 빠르게 데이터를 검색할 수 있다

해시 함수를 적용한 key 값을 배열의 index로 사용하고 이 index를 활용해 value를 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다

해시 함수를 적용한 key 값을 배열의 index로 사용하고 이 index를 활용해 value를 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다

키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array (연관 배열: 키를 통해 값을 얻을 수 있다)

테이블 형태에 key-value를 매핑해서 데이터를 저장하고

테이블 형태에 key-value를 매핑해서 데이터를 저장하고 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array (연관 배열: 키를 통해 값을 얻을 수 있다)

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배로 늘린 새로운 버킷에 기존의 버킷들을 옮기는 과정이 진행된다

from http://devsh247.tistory.com/3 by ccl(A) rewrite - 2021-12-07 20:01:02