[알고리즘] 해시(Hash)

2022. 7. 15. 00:03

[해시(Hash)]

1. 해시의 등장배경

배열은 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면

데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야하기 때문에 많은 시간이 소요된다.
반면에 연결리스트는 삽입, 삭제 시 인근 노드들의 참조값만 수정해줌으로써 빠른 처리가 가능했었다.
단, 처음 노드 마지막 노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우에는 해당 노드를
찾기 위하여 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수 밖에 없는 구조다.
이러한 한계를 극복하기 위하여 제시된 방법이 바로 해시(Hash)이다.

2. 해시란?

해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다.
그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 채우는 작업이 필요없도록 특별한 알고리즘을 이용하여

데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.

특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기때문에 삽입 시 다른 데이터의 사이에 끼어들거나
삭제 시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조이다.

* 해시의 특징

해시는 검색과 저장에서 아주 우수한 성능을 보인다
해시의 핵심은 KEY, VALUE를 함께 저장하는 자료구조이다.

3. 해시의 충돌

key를 해시함수를 통해서 해시코드로 변환시키고 이 해시코드를 인덱스로 사용하여 value를 저장하는데,

이때 충돌(Collision)이 발생할 수 있다. 다음의 예시를 보자.

John Smith와 Sandra Dee라는 key가 해시함수를 통해 해시코드로 변환되었는데 우연히 같은 코드로 변환된 것이다.
해시충돌은 완벽히 피할수는 없지만 개선방법은 2가지 존재한다.

1) 충돌해결 - Separate Chaining 기법

John Smith가 들어가 있는데 그 공간에 또 Sandra Dee가 들어갈 때 Collision이 발생한다. 이 때 Sandra의 value를 기존 John의 뒤에 연결리스트를 이용해 체인처럼 이어 붙혀준다. 152번지에 John과 Sandra의 정보가 함께 존재하도록 한것이다.

* 장점

한정된 저장공간을 효율적으로 사용할 수 있다.
해시함수에 대한 의존성이 상대적으로 적다.
메모리 공간을 미리 잡아 놓을 필요가 없다.(그때그때 이어붙이기 때문)

* 단점

한 Hash에만 자료가 계속들어간다면(쏠린다면) 검색 효율이 떨어진다.(최악의 경우 O(n))
외부 저장공간을 사용한다.

2) 충돌해결 - Open Addressing(개방주소법)
개방주소법은 데이터의 해시(hash)가 변경되지 않았던 Chaining과는 달리 비어있는 해시를 찾아 데이터를 저장하는 기법이다. 즉, 해시 충돌이 일어나면 다른 버킷에 데이터를 삽입한다.

따라서 개방주소법에서의 해시테이블은 1개의 해시와 1개의 값이 매칭되어 있는 형태로 유지된다.

* 장점

추가 저장공간이 필요없다.
저장할 데이터가 적을 때 더 유리하다.

* 단점

해시 함수의 성능에 전체 해시테이블의 성능이 좌지우지 된다.
데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야한다.

* 개방주소법 3가지 방법
① 선형 탐색(Linear Probing) : 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
② 제곱 탐색(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4, 9.16...)
③ 이중 해시(Double Hashing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

4. HashMap vs HashTable(파이썬에서는 Dictionary)

1) HashMap

null을 key, value로 사용할 수 있다.
동기화를 지원하지 않는다.(멀티스레드가 동시에 사용할 때 문제가 발생할 수 있다) => 대신 실행속도가 빠르다.

2) HashTalbe

key가 null이 될 수 없다.
value가 null이 될 수 없다.
동기화를 지원

=>HashMap은 HashTalbe의 신버전

5. HashMap vs HashSet

1) 정의
HashMap은 Map 인터페이스의 구현체로, HashTable과 유사한 자료구조로 데이터를 저장한다.
HashSet은 Set 인터페이스의 구현체로, 내부적으로 HashMap을 사용하기 때문에 HashTable과 유사한 자료구조로 데이터를 저장한다.

2) 데이터 저장 형태
HashMap은 Key-Value 쌍 형태로 데이터를 저장하며, Key와 Value의 mapping을 유지하고 있다.
HashSet은 객체 그 자체를 저장한다. 위에서 HashMap을 내부적으로 사용한다고 했는데,
Key 값으로는 삽입되는 객체 그 자체를, Value 값으로는 HashSet 내부 구현 코드에서 미리 선언해둔 dummy 객체를 사용한다.

3) 중복 허용 여부
HashMap은 중복 key 값을 허용하지 않지만, Value값은 허용한다.
HashSet은 객체 자체를 데이터로 저장하기 때문에 중복을 허용하지 않는다.

4) 기본적인 사용법

- HashMap

HashMap<Integer,String> map = new HashMap<>();//new에서 타입 파라미터 생략가능
map.put(1,"사과"); //값 추가
map.put(2,"바나나");
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

//반복문을 이용한 출력
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("[Key]:" + key + " [Value]:" +  map.get(key));
}

- HashSet

HashSet<Integer> set = new HashSet<Integer>();//HashSet생성
set.add(1); //값 추가
set.add(2);
set.remove(1);//값 1 제거
set.clear();//모든 값 제거

//출력
Iterator iter = set.iterator();	// Iterator 사용
while(iter.hasNext()) {//값이 있으면 true 없으면 false
    System.out.println(iter.next());
}

//검색
System.out.println(set.contains(1)); //set내부에 값 1이 있는지 check : true

출처

저작자표시 비영리 변경금지

'알고리즘' 카테고리의 다른 글

[알고리즘] 조합(Combination) (0)	2022.12.02
[알고리즘] 슬라이딩 윈도우 (0)	2022.09.15
[알고리즘] 정렬1(버블,선택,삽입) (0)	2022.07.29
[알고리즘] 힙(Heap) (0)	2022.07.21
[알고리즘] 우선순위큐(Priority Queue) (0)	2019.05.27

자몽 스토리