HashTable

CS지식

몰라모르겠어요 2022. 7. 22. 17:15

개념
키와 밸류를 1:1로 연관지어 저장하는 자료구조
키로 밸류를 가져올 수 있다.
기능(생성, 조회, 수정, 제거)
키와 밸류가 주어졌을 때, 두 값을 저장한다.
키가 주어지면 해당 키와 관련된 밸류를 조회한다.
기존 키에 새로운 밸류가 주어졌을 때, 기존 밸류를 새로운 밸류로 대체한다.
키가 주어졌을 때, 해당 키에 연관된 밸류 제거한다.
해시테이블 구조

1. Key
고유한 값
저장 공간의 효율성을 위해서 해시 펑션에 입력해서 해시로 변경하고 저장한다.

2. Hash Function

키를 해시로 바꿔주는 역할

해시 충돌(서로 다른 키가 같은 해시가 나오는 경우)을 최대한 줄이는 함수를 만드는 것이 중요하다.

3. Hash

해시 펑션의 결과

저장소에서 밸류와 매칭되어 저장된다.

4. Value

저장소에 최종적으로 저장되는 값

키와 매칭되어 저장, 조회, 접근, 삭제 가능하다.

HashTable 동작 과정
Key -> Hash Function -> Hash Funtion 결과 = Hash
해시를 배열의 인덱스로 사용
해당 인덱스에 밸류 저장 = 해시테이블 크기가 10이라면 A라는 키의 밸류를 찾을 때 hashFunction("A")%10 연산을 통해 인덱스 값을 계산하여 밸류 조회
HashTable 장점
적은 리소스로 많은 데이터 효율적으로 관리 가능
배열의 인덱스를 사용하기 때문에 빠른 검색, 삽입, 삭제 가능(O(1)) -> 해시테이블 인덱스는 데이터의 고유 위치이기 때문에 삽입, 삭제 시 다른 데이터를 이동할 필요가 없어서 빠른 속도 가능
키와 해시에 연관성이 없어 보안 유리
데이터 캐싱에 많이 사용한다. - get, put 기능에 캐시 로직 추가 시 자주 hit 하는 데이터 바로 검색 가능
중복 제거 유용(같은 키, 같은 해시)
HashTable 단점
충돌 발생 가능성이 있다.
공간 복잡도가 증가한다.
순서는 무시된다.
해시 함수에 의존한다.
HashTable 성능