패스트캠퍼스 챌린지 30일차

시청 강의 : Ch 09. 자료구조(해쉬) - 01. 블록체인에도 쓰이는 해쉬 테이블 1

시청 날짜 : 11/30/2021

해쉬 테이블 (Hash Table)

1. 해쉬 테이블

• key에 데이터(value)를 매핑할 수 있는 데이터 구조
• 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(index number)를 계산
• key를 통해 바로 데이터가 저장되어있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐
• 미리 해쉬 함수가 생성할 수 있는 주소 (인덱스 번호) 에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원

용어

1. 해쉬 함수 (Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

• Hash Adress : 해슁 함수를 통해 리턴된 고정된 길이의 값

2. 해쉬 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

• slot : 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간

이미지 출처 : 위키피디아

위 그림에서, hash function은 키가 저장된 주소로 refer 해주고, buckets 은 해쉬 테이블 구조라고 보면 된다.

Hash Table Class 생성

public class MyHash{
    public Slot[] hashTable;
    public MyHash(Integer size){
        this.hashTable = new Slot[size];
    }
    public class Slot{
        String value;
        Slot(String value){
        this.value = value;
        }
    }
   /*Hash Function 추가*/
   public int hashFunction(String key){
   return (int)(key.charAt(0)%this.hashTable.length; //주소를 확보한다
   }
}

해쉬 테이블의 장단점과 주요 용도

1. 장점

• 데이터 저장/읽기/검색 속도가 빠름
• 중복 확인 쉬움

2. 단점

• 저장 공간이 좀 더 많이 필요함
• 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위해 별도 자료구조가 필요함

3. 주요 용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현시(중복 확인이 쉽기 때문)
• 스도쿠 등 문제 풀때 유용 (중복 확인 )

---

패스트캠퍼스 환급 챌린지 바로가기👉 https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다