해쉬테이블

해쉬테이블(Hash Table)

• 키에 데이터를 매핑할 수 있는 자료구조

• 해쉬 함수를 통해 배열에 키에 대한 데이터를 저장할 수 있는 인덱스를 계산함

• 키 값을 통해 데이터에 접근이 바로 가능하기 때문에 속도가 빠르다

• 데이터를 저장할 수 있는 슬롯이 있음

해쉬테이블 장단점

• * 장점 **

1. 데이터 저장/읽기 속도가 빠르다.

2. 해쉬는 키에대한 중복확인이 쉽다.

• * 단점 **

1. 저장공간이 일반적으로 좀 더 필요하다.

2. 여러 키에 해당하는 주소가 동일할 경우에 충돌 예외처리를 위한 별도의 자료구조가 필요하게된다.

• * 해쉬 테이블의 용도 **

1. 검색이 많이 필요할 때

2. 저장, 삭제, 읽기가 많을때

3. 캐쉬 구현시(중복 확인때문에)

해쉬함수(Hash Function)

• 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

해쉬 : 해시 함수를 통해 리턴된 고정된 길이의 값

• * 직접 작성해본 해쉬예제 **

public class HashEx {

    public Table[] hashTable;

    public HashEx(Integer size) {
        this.hashTable = new Table[size];
    }

    public class Table {
        String value;

        Table(String value) {
            this.value = value;
        }

    }

    public Integer HashKey(String key) {

        return (int) (key.charAt(0)) % hashTable.length;

    }

    public boolean saveData(String key, String value) {
        Integer addr = this.HashKey(key);
        if (this.hashTable[addr] != null) {
            this.hashTable[addr].value = value;
        } else {
            this.hashTable[addr] = new Table(value);
        }
        return true;
    }

    public String getData(String key) {
        Integer addr = HashKey(key);
        if (this.hashTable[addr] != null) {
            return this.hashTable[addr].value;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {

        HashEx myHash = new HashEx(20);
        myHash.saveData("hyoung", "12341234");
        myHash.saveData("junjun", "234234");
        myHash.saveData("hohoho", "456567");

        System.out.println(myHash.getData("hohoho"));

    }


}

Chaining

• 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 방법

• 충돌이 일어나면 리스트 자료구조를 이용해서 충돌이 일어난 address에 리스트 데이터를 추가로 만들어 작업을 해주는 방법

Linear Probing

• 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 방법

• 충돌이 일어날 경우에 Hash Address 다음 주소부터 맨 처음 나온 빈 공간에 데이터를 저장하는 기법

• 저장공간의 활용도를 높이기 위한 방법이다.

빈번한 충돌이 일어날 경우엔

• 해쉬 테이블의 저장공간을 확대한다

• 해쉬 함수를 재정의 해준다.