Map & HashMap & Hash Collision
Map
1.Key, Value를 pair(쌍)로 데이터를 저장하는 ADT
2.Key를 중복해서 가질 수 없지만, Value는 중복이 가능하다.
Map의 구현체
1.HashMap(=Hash table) : 배열과 hash function을 이용한 자료구조
2.TreeMap : tree 형태로 Map을 구현한 자료구조
HashMap
HashMap정의
HashMap : 배열과 해시 함수(hash function)를 사용하여 map을 구현한 자료구조
일반적으로 배열의 크기와 상관없이 상수 시간{O(1)}으로 데이터 삽입, 삭제, 갱신, 탐색이 빠르다.
Hash Function
1.임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로
변환하는 함수
2. Hash table에서 임의의 데이터를 정수로 변환하는 역할을 한다.
즉, Key의 데이터를 hashfunction을 통해 hash로 변환한다. HashMap에서는 hashfunction이 중요하다 => 구현이 잘되어있어야 hash collision 가능성이 낮아진다.
동작방법
public hash hashfunction(String key){
//내부 동작과정 생략.
return hash;
}
int index = hash % capacity;
Key의 데이터를 hashfunction을 통해 hash로 계산하고 bucket의 capacity를 통해 모듈러 계산 후 해당 인덱스에 Key,Value pair형태로 저장한다.
Hash Collision
Hash Collision 정의
hash collision은 hashfunction 결과가 같아 같은 인덱스에 데이터를 저장하게 되는경우 발생한다.
1. Key가 다르지만 같은 hash값이 생성된 경우
2. hash값이 다르지만 hash % capacity한 값이 같은 경우
why) Key는 웬만한 데이터 타입이 무한으로 가능하지만, hashfunction의 결과는 정수형이기 때문에 중복을 피할 수 없다.
Hash Collision 해결
Open addressing
open addressing 방법 중 linear probing은 hash collision이 발생하면 다음 bucket에 데이터를 저장한다. 탐색할때 index 접근 후 키가 다르면 다음 bucket을 체크한다.
"010-2222-222"의 인덱스 값과 "010-1010-1010"의 인덱스 값이 2로 동일한 경우
인덱스 2에는 "010-2222-222" : "홍진호"가 저장되고,
그다음 인덱스 3에는 "010-1010-1010" : "이진수"가 저장된다.
map.get("010-1010-1010")를 실행하게 되면, index[2]로 접근하게 되는데
index[2]의 key값과 "010-1010-1010"를 equals 비교하여 만약 true면
해당 index의 value를 리턴하고 false면 index[3]으로 이동 후 index[3]의 key와 비교한다.Separate Chaining
계속해서 map.put을 통해 데이터가 추가 되는 경우 :
hashfunction을 통해 index를 재계산하여 새로운 bucket에 저장한다.
만약, hash collision 후 저장된 데이터를 삭제하게 되면 어떻게 될까?
map.remove("010-2222-2222")를 수행 할 경우 index[2]에있는 데이터를 삭제하고,
그후 get("010-1010-1001")를 수행하게 되면 index[2]로 향하는데
만약 해당 index에 값이 비어있다면 null을 반환할 수도 있다. 따라서, remove로 데이터를
제거했을경우 해당 index에 delete marker를 생성하여 제거상태를 표시한다.Separate chaining
Separate chaining은 Java에서 hash collision을 해결하는 방법으로서, bucket에 존재하는 데이터는 LinkedList의 참조주소를 가리킨다.
같은 index값이 추가되는 경우 node를 새로 생성하여 기존 LinkedList의 Head에 연결한다.
remove를 통해 데이터를 삭제했을경우 해당 node만 제거하면 되기 때문에 비용이 적게든다.
