해쉬 테이블 기본정리

UkJJang·2021년 9월 3일
0

해쉬테이블(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"));
        
    }


}
profile
꾸준하게 성실하게

0개의 댓글