[자료구조] 해시 (HashMap, HashTable)
1. 해쉬 구조
Hash Table : 키에 데이터를 저장하는 구조
key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빠르다.
배열로 미리 HashTable 사이즈 만큼 생성 후에 사용한다.
2. 알아둘 용어
- 해쉬 : 임의 값을 고정길이로 변환하는 것
- 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
- 해싱 함수 : key에 대해 산술연산을 이용해서 데이터 위치를 찾을 수 있는 함수
- 해쉬 값 or 해쉬 주소 : key를 해싱 함수로 연산해서 해쉬값을 알아 낼 수 있음. 해쉬값(해쉬 주소)를 기반으로 해당 Key에 대한 위치를 찾을 수 있음
- 슬롯 : 한 개의 데이터를 저장할 수 있는 공간
- 저장할 데이터에 대해 key를 추출할 수 있는 별도 함수도 존재할 수 있다.
3. 해쉬 테이블의 장단점과 주요 용도
장점
- 데이터 저장/읽기 속도가 빠르다. (검색속도가 빠르다)
- 해쉬는 키에 대한 데이터가 있는지 확인이 쉽다.(중복확인)
단점
- 일반적으로 저장공간이 좀 더 많이 필요하다.
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다. (Linear Probing 기법, 체이닝기법)
주요용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문)
4. 해쉬 메소드 사용 in 자바
(1) HashTable
1. 선언
HashTable<Integer, String> hashtable = new HashTable<Integer, String>();
*key, value에 null을 넣을 수 없다.
2. 메소드 정리
◆ .put() : 값을 집어넣는 메소드
ht.put(5, "five");
ht.put(1, "one");
* 여기서 key자리는 고유한 식별자이므로 중복이 되선 안된다.
◆ containsKey(key) : 키의 존재유무를 확인하는 메소드
해당 키의 존재 유무를 Boolean타입으로 반환
◆ containsValue(data) : 값이 있는지 없는지 확인하는 메소드
해당 값의 존재 유무를 Boolean타입으로 반환
◆ .get(key) : 키값에 해당하는 값을 검색해 반환해준다.
ht.get(5); 를 실행했다면 five 반환
◆ .clear() : 해시테이블을 지운다.
◆ .keySet() : 전체 key확인
(2) HashMap
Map 인터페이스를 상속하여 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다.
이때 key는 식별하는 역할이므로 중복이 불가능하다. 동일한 key값으로 값을 삽입하는 경우 최근에 넣은 값이 적용된다.
해싱을 사용하기 때문에 대량의 데이터를 검색할때 뛰어난 성능을 가지고 있다.
1. 선언
Map은 HashMap, TreeMap, HashTable, LinkedHashMap로 선언이가능하다.
//Map 안에서 key, value에 따른 순서가 존재하지않음
HashMap<Integer, String> hashtable = new HashMap<Integer, String>();
HashMap<Integer, String> hashtable2 = new HashMap<>(); //new에서 타입 파라미터 생략 가능
HashMap<Integer, String> hashtable2 = new HashMap<>(hashtable1); // hashtable1의 모든 값을 가진 HashMap 생성
HashMap<Integer, String> hashtable2 = new HashMap<>(100); //초기 용량 capacity 지정
HashMap<String,String> map6 = new HashMap<String,String>() { { //초기값 지정
put("a", "b"); } };
//TreeMap : key 값에 따라 오름차순으로 정렬 - 정렬로 인해 데이터 삽입/삭제 시 오래 걸림
TreeMap
//LinkedHashMap : 삽입 순서로 정렬
//HashTable :
2. 메소드 정리
◆ .put(key, value) : Map안에 값을 집어넣는 메소드
◆ .size() : 크기 확인
◆ .replace(key, value) : Map안의 value 변경
◆ .containsKey(), .containsValue : Map안에 해당 key, value가 들어있는지 확인
◆ .isEmpty() : 크기가 0인지 확인
◆ .remove(key) : Map 안의 내용 삭제
◆ .getOrDefault(key, default) : key에 해당하는 value가 없는 경우 default 호출
출력
◆ .get(key) : Map안의 값 가져오기
◆ entrySet() 활용
◆ KeySet() 활용
*HashMap과 HashTable의 차이
1. HashMap은 synchronized(동기화)~
2. Hashtable은 key,value에 null값을 허용하지 않는다. HashMap은 허용한다.
3) HashSet
HashSet은 Set인터페이스의 구현 클래스이다. 객체를 중복해서 저장할 수 없고 하나의 null 값만 저장이 가능하고 저장순서가 유지되지 않는다.
Set의 가장 큰 장점은 중복을 자동으로 제거해준다는 것이다. 비선형 구조이기때문에 순서가 없으며 인덱스도 없다.
HashSet<Integer> set = new HashSet<Integer>();
2. 메소드 정리
◆ .add(1) : 값추가. 입력한 값이 HashSet내부에 있다면 false를 반환하고 그 값이 있다면 true를 반환합니다.
◆ .remove(1) : 값 제거. 입력한 값이 HashSet내부에 있다면 삭제한 후 true를 반환합니다.
◆ .clear() : 값 전체 제거.
HashSet 값 출력
4. 충돌 해결 알고리즘
해쉬 테이블의 큰 문제는 충돌이다. 이것은 충돌 또는 해쉬 충돌이라고 부른다.
4.1. Chaining 기법
개방 해싱 또는 Open Hashing 기법 중 하나이다.
해쉬테이블 저장공간 외의 공간을 활용하는 기법이다.
충돌이 일어나면, 링크드리스트를 사용해서 링크드리스트로 데이터를 추가한 후 뒤 쪽에 연결시켜 저장한다.
Chaining 구현 코드
package Hash;
import java.util.Scanner;
//해시 테이블은 키에 데이터를 저장하는 구조를 가진 자료구조
public class HashTableCode {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
HashTable hashTable = new HashTable();
hashTable.add("솔라", "마마무");
hashTable.add("로제", "블랙핑크");
hashTable.add("태민", "샤이니");
hashTable.add("우기", "아이들");
hashTable.print();
System.out.print("\nkey를 검색하세요 : ");
String inputKey;
while (!(inputKey = sc.next()).equals("stop")) {
System.out.println(hashTable.find(inputKey));
}
System.out.print("제거할 key를 검색하세요 : ");
String removeKey;
while (!(removeKey = sc.next()).equals("stop")) {
System.out.println(hashTable.remove(removeKey) + "를 제거하였습니다");
}
hashTable.print();
}
}
class HashTable {
private static int MAX_TABLE = 100;
private static Item[] table = new Item[MAX_TABLE];
private static int size = 0;
//해시값 얻기
private int hash(String key) {
int hash = 0;
for (int i = 0; i < key.length(); i++) {
int c = (int) key.charAt(i);
hash = (hash + c * (i + 1)) % MAX_TABLE;
}
return hash;
}
//key로 데이터 검색
public String find(String key) {
int hash = hash(key);
while(table[hash] != null && !table[hash].key.equals(key)) {
hash = hash + 1 % MAX_TABLE;
}
if (table[hash] == null) {
return null;
}
return table[hash].data;
}
//데이터 저장
public boolean add(String key, String data) {
int hash = hash(key);
while (table[hash] != null) {
if (table[hash].key.equals(key)) {
return false;
}
hash = hash + 1 % MAX_TABLE;
}
table[hash] = new Item(key, data);
size++;
return true;
}
public String remove(String key) {
int hash = hash(key);
String removed;
while (table[hash] != null && !table[hash].key.equals(key)) {
hash = hash + 1 % MAX_TABLE;
}
removed = table[hash].data;
table[hash] = null;
size--;
return removed;
}
//배열 출력
public void print() {
String out = "<HashTable>\n";
for (int i = 0; i < table.length; i++) {
Item item = table[i];
if (item != null) {
out += " Key(hash, index): " + table[i].key
+ "(" + hash(table[i].key) + ", " + i + ")"
+ ", Value: " + table[i].data + "\n";
}
}
System.out.print(out);
}
}
class Item {
String key;
String data;
public Item(String key, String data) {
this.key = key;
this.data = data;
}
}4.2. Linear Probing 기법
폐쇄 해싱 또는 Close Hashing 기법 중 하나이다.
해쉬 테이블 저장공간 안에서 충돌을 해결하는 기법이다.
충돌이 일어나면 해당 해쉬주소의 다음 빈공간에 저장하는 기법이다. (저장공간 활용도를 높인다.)
Linear Probing 구현 코드
5. 유명한 해시 함수
SHA-256
6. 시간복잡도
충돌이 없는 일반적인 경우 O(1)이고
최악의 경우 O(n)이다.
하지만 해쉬테이블은 일반적인 경우를 기대하고 만들기 때문에 O(1)이다.
사이즈가 10인 배열에 데이터를 저장하고, 검색할 때는 O(n)이지만 똑같은 저장공간을 가진 해쉬테이블에 데이터를 저장하고 검색하는 것은 O(1)이다.