얼거스 개발 일지

Map

• Interface
• 순서가 없는 자료형
• 키 , 값 의 형태로 데이터 관리
• 대표 구현 클래스 -> HashMap , TreeMap

 

Hash

• 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수

 

Hashtable , HashMap

(+ HashSet)

• 키 , 값의 형태로 데이터를 관리하는 자료구조 -> 키를 통해 데이터에 빠르게 접근 가능하다.
• 해싱 : 키를 특정 계산식(해시 함수)에 넣어 나온 결과를 사용하여 값에 접근하는 과정
• Hashtable과 HashMap 차이

	( 키 , 값 ) = ( null , null )	Thread - safe
Hash table	X	O ( 멀티스레드에서 좋음 )
Hash Map	O	X ( 싱글스레드에서 성능 좋음)
		-> 멀티스레드 환경을 위한 ConcurrentHashMap이 있음

• HashMap은 Hashtable로 구현된 자료구조일까?? 아님. 해시테이블 자료구조를 구현하는 자료구조로 hashtable이 처음 등장했고, 그 다음 Java 버전에서 HashMap이 등장했기 때문에 HashMap이 나중에 등장한것도 맞으며, 해시함수를 사용하여 키를 해싱하여 해시테이블에서 키-값 쌍을 관리하는 형태도 같지만, 둘은 해시테이블을 구현하는 자료구조가 다르며, 이때 사용되는 용어도 다르다. 이 둘은 해시테이블 자료구조를 구현한 서로 다른 구현체라고 봐야 한다고 생각한다.

chatGTP 발췌 🔻

Java 1.0 버전에서는 
Hashtable 클래스가 해시 테이블 자료구조를 구현하는 유일한 클래스였습니다. 
그러나 Java 1.2 버전에서는 HashMap 클래스가 추가되었으며, 
HashMap 클래스는 Hashtable과 다른 방식으로 해시 테이블 자료구조를 구현합니다.

HashMap은 내부적으로 배열과 연결 리스트를 사용하여 데이터를 저장합니다.
데이터를 추가할 때, 
key의 해시 값을 이용하여 배열의 인덱스를 계산하고 해당 인덱스에 데이터를 저장합니다. 
만약 해당 인덱스에 이미 다른 데이터가 저장되어 있다면, 
연결 리스트를 이용하여 새로운 데이터를 추가합니다.

Hashtable도 해시 테이블 자료구조를 사용하지만, 
내부적으로는 배열과 연결 리스트 대신 버킷(bucket)과 엔트리(entry)라는 용어를 사용합니다. 
버킷은 각각의 해시 값에 해당하는 슬롯을 의미하며, 엔트리는 각각의 Key-Value 쌍을 의미합니다. 
Hashtable은 데이터를 추가할 때, 
key의 해시 값을 이용하여 해당하는 버킷을 찾고, 해당 버킷에 엔트리를 추가합니다.

따라서, 
HashMap과 Hashtable은 해시 테이블 자료구조를 구현하는 방식이 다르며, 
내부적으로 사용하는 용어도 다릅니다. 
또한, HashMap은 스레드 안전하지 않지만, Hashtable은 스레드 안전한 클래스입니다.

• HashSet

중복되지 않는 값을 관리하는 자료구조. Set 인터페이스의 구현체이나, 이 구현 과정에서 HashMap이 사용된다. HashSet에 값이 들어오면 HashMap에 key로 적용되어서 값을 추가하게 되는데, 이 때 value에는 모두 null이 적용된다. 그래서 HashSet은 중복을 허용하지 않는 데이터 저장소로 사용되며, HashMap은 key-value 쌍의 데이터를 저장하고, 검색에 사용되는 자료구조로 사용된다.

Hashtable , HashMap 구조

• 키 Key : 해시 테이블 접근을 위한 값
• 해시 함수 Hash Fundtion : 키를 해시 값으로 매핑하는 연산
• 해시 값 Hash Value : 해시 테이블의 인덱스
• 해시 테이블 Hash Table : 키-값을 연관시켜 저장하는 데이터 구조

해시 테이블에 접근하기 위해 어떤 키가 주어지면, 주어진 키가 Hash Function을 통과하여 Hash Value가 되고, Hash Value가 된 키가 Hash Table에 인덱스가 되어 인덱스의 위치에 값이 기록된다.

이때, Hash Function에 따라 분명 다른 값인 Key를 입력했지만 인덱스(HashValue)가 같아져서 해시테이블에 먼저 있던 인덱스 위치에 새로운 값이 덮어씌워지는 경우가 생길 수 있는데, 이를 충돌 이라고 한다.

Hash Function은 개발자가 어떤 계산식을 만들어주기 나름이기때문에 구현해서 사용할때 주의해야 할것 같다. 🫥

해시 충돌이 일어나면 충돌해결 메서드가 실행되어 인덱스를 새로 계산해서 비어있는 인덱스를 찾은 후 테이블에 값을 저장한다. 이때 사용될 수 있는 충돌 해결 방법으로는 아래와 같은 방법들이 있다.

해시 충돌

서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우, 해시 테이블의 같은 공간에 서로 다른 값을 저장하게되며 이를 충돌이라고 함

해결방법으로는 크게 개방주소법과 분리 연결법이 있다.

1. 개방 주소법

• 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
• hash 와 value가 1:1 관계 유지
• 비어있는 공간 탐색 방법에 따라 3가지로 분류된다. -> 선형 탐사법, 제곱 탐사법, 이중 해싱

* 선형 탐사법

• 충돌발생 지점부터 이후의 빈 공간을 순차적으로 탐사
• 일차 군집화 문제 발생 -> 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생

* 제곱 탐사법

• 충돌 발생 지점부터 이후의 빈 공간을 n 제곱 간격으로 탐사
• 일차군집화 문제를 일부 보완했지만, 이차 군집화 문제 발생 가능성 있음

* 이중 해싱

• 해싱함수를 이중으로 사용
• 선형 탐사, 제곱탐사에 비해 데이터가 골고루 분포됨

2. 분리 연결법

• 해시 테이블을 연결 리스트로 구성
• 충돌 발생 시 , 테이블 내의 다른위치를 탐색하지 않고 연결리스트를 이용하여 해당 테이블에 데이터를 연결