[ 목차 ]
📢 해시 테이블
- 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조이다.
- 키(Key)를 통해 해당 데이터에 빠르게 접근이 가능하다.
📢 해시 테이블 구조
- 키(Key) : 해시 테이블 접근을 위한 입력 값이다.
- 해시 함수(Hash Function) : 키를 해시 값으로 매핑하는 연산
- 해시 값(Hash Value) : 해시 테이블의 인덱스
- 해시 테이블(Hash Table) : 키와 값을 연관시켜 저장하는 데이터 구조이다.
📢 해시 충돌
- 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우이다.
- 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우이다.
📢 해시 충돌 해결 방법
🔥 개방 주소법(Open Address)
- 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
- hash와 Value가 1:1 관계를 유지한다.
- 비어 있는 공간 탐색 방법에 따라 : 선형 탐사법, 제곱 탐사법, 이중 해싱
🌟선형 탐사법(Linear Probing)
- 빈 공간을 순차적으로 탐사 -> 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
🌟제곱 탐사법(Quadratic Probing)
- 빈 공간을 n 제곱만큼의 간격을 두고 탐사 -> 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사
🌟이중 해싱(Double Hashing)
- 해싱 함수를 이중으로 사용
- (1)번 해시 함수 => 최초 해시를 구할 때 사용
- (2)번 해시 함수 => 충돌 발생 시, 탐사 이동 간격을 구할 때 사용
- 선형 탐사와 제곱 탐사에 비해 데이터가 골고루 분포가 된다.
🔥 분리 연결법(Separate Chaning)
- 해시 테이블을 연결 리스트로 구성
- 충돌 발생 시, 테이블 내에 다른 위치를 탐색하는 것이 아닌 연결리스트를 이용하여 해당 테이블에 데이터를 연결
📢 Hash를 이용한 예시
//Hashtable
Hashtable<Integer, Integer> ht = new Hashtable<>();
ht.put(0,10);
System.out.println(ht.get(0));
//HashMap
HashMap<Integer, Integer> hm = new HashMap<>();
ht.put(0,10);
System.out.println(ht.get(0));
//Map 형변환
Map<Integer,Integer> map1 = ht;
Map<Integer,Integer> map2 = hm;
System.out.println(map1.get(0));
System.out.println(map1.get(1));
📢해시맵(HashMap)과 해시테이블(HashTable)의 차이점
- 해시맵(HashMap) : 속도를 우선시하면 사용 (HashMap은 무엇인가요?)
- 해시테이블(HashTable) : 안전성을 우선시하면 사용
- HashMap과 HashTable은 유사하지만 Map은 동기화가 안되지만, Null 값 저장이 가능하다.
//차이점 : Key의 Null을 사용 여부
// ht.put(null, -999); //NG
hm.put(null, -999);
System.out.println(hm.get(null));
📢 노트 정리
반응형
'Knowledge > 자료구조' 카테고리의 다른 글
[Java/자료구조] 연결리스트(Linked List)의 특징 (0) | 2023.08.11 |
---|---|
[Java/자료구조] HashMap 자료구조 파헤치기 (0) | 2023.08.11 |
[Java/자료구조] 배열 (0) | 2023.08.09 |
댓글