반응형 hash table1 [CS 노트] : Hash table에 대해서 Hash table이란? 효율적인 탐색을 위한 자료구조로 key-value 쌍의 데이터를 입력받는다. Hash function h에 key값을 넣어 얻은 해시값h(k)를 위치로 지정해 키,벨류 데이터 쌍을 저장하고 저장,삭제,검색의 시간복잡도는 O(1)이다. Direct address table를 미리 알아보자 직접 주소화 테이블은 Key 값을 index에 저장하는 방식인데 문제는 메모리 공간이 낭비된다. 예를 들면 key 값이 1000부터 시작하면 1부터 999까지는 비어 있게 된다. 또, 다양한 자료형을 담을 수 없다는 문제도 있는데 String으로 들어온 경우 Key 값을 바로 index로 사용하는 특성상 활용이 불가능하다는 문제가 있다. 이런 단점을 보완하는 게 Hash table이다. Hash .. 2022. 4. 8. 이전 1 다음 반응형