목록hash table (1)

N

(TIL Day03-05)자료구조- 해시 테이블

해시 테이블(Hash Table) 키와 값을 받아 키를 해싱(Hashing)하여 나온 index 값을 저장하는 선형 자료구조. 삽입은 O(1)이며, 키를 알고 있다면 삭제와 탐색도 O(1)로 수행한다. 해시 함수를 통해 키를 특정 범위 내 숫자로 변경한다. 키로 "name"이 주어진다면, 컴퓨터에서는 해시 함수를 통해 1239593로 바꿔 데이터를 저장한다. 즉, 사람의 입장에서는 name이지만 컴퓨터의 입장에서는 1239539가 된다. value가 저장되는 공간을 bucket이라 한다. JavaScript에서 객체(Object)가 해시 테이블에 해당한다. 해시 충돌(Hash Collision) 만약 해시 함수의 결과가 기존에 있던 값과 같게 된다면 충돌이 발생한다. 이를 해결하기 위해서 "분리 연결법"..
TIL 2021. 8. 6. 11:04
이전 Prev 1 Next 다음