Hash Table
검색하고자하는 key값을 입력받아서 hash function을 돌려서 반환받은 hash code를 배열의 index로 환산을 해서 데이터에 접근하는 방식의 자료구조
Hash Table의 이점
선형구조로 데이터에 접근할 경우의 시간복잡도는 0(N)이어서 아이템이 많을 수록 찾는 시간도 오래 걸린다.
하지만, Hash Tables의 시간복잡도는 0(1)로 Constant Time(상수 시간)이다.
Hash Tables의 collision(충돌)
각기 다른 Key에 대하여 동일한 Index를 환산해 같은 공간에 들어가게 되는 상황을 말한다. 이 경우는 찾고자 하는 여러 데이터들이 들어간 공간에서 선형검색을 하게 된다. 이 때문에 Hash Tables는 언제나 상수 시간인 것은 아니다.
Hash Table을 사용하는 방법
이미 수많은 프로그래밍 언어에 깔려있고 좋은 Hash Function을 가져다 쓰면된다 .
* 참고자료
'알고리즘 풀이' 카테고리의 다른 글
| 그래프 정렬 (0) | 2022.06.11 |
|---|---|
| DFS (0) | 2022.06.04 |
| [20211128]알고리즘 풀 (0) | 2021.11.28 |
| [20211124]알고리즘 풀이 (0) | 2021.11.24 |
| [20211122]알고리즘 풀이 (0) | 2021.11.22 |