Java 자료구조 Hash (1) 간략히 보기

Hash 이란?

• 파이썬 딕셔너리랑 비슷

Hash table

• (Key, Value) 쌍을 저장
• 순서 X

Hashing

• 데이터를 빠르게 저장하고 가져오는 기법 중 한
• 키에 특정 연산을 적용하여 테이블의 주소를 계산

Hashing - Key

• 키를 기준으로 값을 매핑
• 고유한 값
  • 중복 X
  • 이름 같은 경우 동명이인이 있을 수 있기 때문에 주민번호 혹은 중복 없는 아이디를 사용
  • Hshing - Hash Function
    • 임의의 데이터(키)를 특정 값(해시값)으로 매핑 시키는 함수
    • 시간복잡도 O(1)

Hashing - Hash Fumction

• 좋은 해시 함수
  • 키 값을 고르게 분포 시킴
  • 빠른 계산
  • 충돌 최소화
    • 해시 충돌 Hash Collision
      • 키 값이 다른데, 해시 함수의 결과값이 동일한 경우
      • 예) 키 1, 2 의 값이 둘다 빨간 색일 경우
        • 충돌이 발생했을 경우 체이닝 방식으로 해결
        • 링크드 리스크가 가장 기본적인 방법
        • 데이터는 노드 키 벨류

코드 구현

package hashtable;  
  
public interface IHashTable<K, V> {  
    void put(K key, V value);  
    V get(K key);  
    boolean delete(K key);  
    boolean contains(K key);  
    int size();  
}

package hashtable;  
  
import java.util.Iterator;  
import java.util.LinkedList;  
import java.util.List;  
  
public class MyLinkedHashTable<K, V> implements IHashTable<K, V> {  
    private List<Node>[] buckets;   // hashTable -> chaining  
    private int size;  
    private int bucketSize;  
  
    public MyLinkedHashTable() {  
        this.buckets = new List[1024];  // 2의 10제곱  
        this.bucketSize = 1024;  
        this.size = 0;  
        for(int i = 0; i < bucketSize; i++) {  
            this.buckets[i] = new LinkedList<>();  
            // 이렇게 안 할 경우 null 값이라 데이터를 넣을 수 없음
        }  
    }  
  
    public MyLinkedHashTable(int bucketSize) {  // 사용자가 사이즈 정의
        this.buckets = new List[bucketSize];  
        this.bucketSize = bucketSize;  
        this.size = 0;  
        for(int i = 0; i < bucketSize; i++) {  
            this.buckets[i] = new LinkedList<>();  
        }  
    }  
  
    @Override  
    public void put(K key, V value) {  
        int idx = this.hash(key);  
        List<Node> bucket = this.buckets[idx];  
        for (Node node : bucket) {  
            if (node.key.equals(key)) {  
                node.data = value;  // 동일한 키가 있을 때 새로운 키로 업데이트
                return;            }  
        }  
        Node node = new Node(key, value);  
        bucket.add(node);  
        this.size++;  
    }  
  
    @Override  
    public V get(K key) {  
        int idx = this.hash(key);  
        List<Node> bucket = this.buckets[idx];  
        for (Node node : bucket) {  
            if (node.key.equals(key)) {  
                return node.data;  
            }  
        }  
        return null;  
    }  
  
    @Override  
    public boolean delete(K key) {  
        int idx = this.hash(key);  
        List<Node> bucket = this.buckets[idx];  
        for (Iterator<Node> iter = bucket.iterator(); iter.hasNext(); // 데이터 없을 때 까지) {  
        // Iterator는 데이터 집합에서 값을 하나씩 꺼내서 순환하는 객체
            Node node = iter.next();  
            if (node.key.equals(key)) {  
                iter.remove();  
                this.size--;  
                return true;            }  
        }  
        return false;  
    }  
  
    @Override  
    public boolean contains(K key) {  
        int idx = this.hash(key);  
        List<Node> bucket = this.buckets[idx];  
        for (Node node : bucket) {  
            if (node.key.equals(key)) {  
                return true;  
            }  
        }  
        return false;  
    }  
  
    @Override  
    public int size() {  
        return this.size;  
    }  
  
    private int hash(K key) {  
        int hash = 0;  
  
        for (Character ch : key.toString().toCharArray()) {  // key를 문자열로 바꾸고 다시 to CharArray로 바꿔줌 -> 문자를 한 글자로 다 쪼개버림 -> Abcde -> A b c d e
            hash += (int) ch;  
        }  
  
        return hash % this.bucketSize;  // bucketSize 사이즈보다 작게 만들기
    }  
  
    private class Node {  
        K key;  
        V data;  
  
        Node(K key, V data) {  
            this.key = key;  
            this.data = data;  
        }  
    }  
}

String array

List 노드 타입의 array

• 배열은 배열인데 배열 한 칸에 List <Node>를 넣을 수 있음

해시 충돌 Hash Collision

• 키 값이 다른데, 해시 함수의 결과 값이 동일한 경우
  • 이런 경우가 많으면 성능을 떨어트림
• 근데 필연적으로 생길 수 밖에 없음
• 따라서 해결해주는 방법이 꼭 필요함
  • Chaining -> 하지만 구조상 중복 value 값이 많아질 수록 시간 복잡도가 O(N) 으로 늘어남
    • 요즘에는 list 대신 tree 방법을 쓴다고 함
  • Open Addressing -> 충돌 발생시 다른 버킷에 데이터를 저장 (다른 버킷에서 어떻게 데이터를 찾는지로 또 나뉨)
    • 선형탐색
      • 해시 충돌 시 n칸을 건너 뛴 다음 버킷에 저장
      • 계산 단순
      • 하지만 검색 시간이 많이 소요 -> 시간 복잡도가 O(N) 까지 늘어날 수 있음
      • 데이터들이 특정 위치에만 밀집 (클러스터링)
        • 제곱 탐색
          • N^2 칸(1,4,9,16…) 을 건너뛴 버킷에 데이터를 저장
          • 데이터들이 특정 위치에 밀집하는 문제를 해결
          • 하지만 처음 해시 값이 같아면 문제는 똑같다.
    • 이중해시
      • 해시 값에 다른 해시 함수를 한 번 더 적용
      • Hashfunction1() - 최초의 해시 값을 구함
      • Hashfunction2() - 충돌 발생시 이동 폭을 구함
      • 최초 해시 값이 같더라도 이동 폭이 다르기 때문에 clustering 문제 해결 가능